From: Jorgen Loland
Date: May 19 2011 12:04pm
Subject: bzr push into mysql-trunk branch (jorgen.loland:3101 to 3102) Bug#11765831
List-Archive: http://lists.mysql.com/commits/137697
X-Bug: 11765831
Message-Id: <20110519120409.6C232453@atum21.norway.sun.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit

 3102 Jorgen Loland	2011-05-19
      BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
                            AWAY QUALIFYING ROWS
            
      The problem was that the ranges created when OR'ing two 
      conditions could be incorrect. Without the bugfix, 
      "I <> 6 OR (I <> 8 AND J = 5)" would create these ranges:
      
      "NULL < I < 6",
      "6 <= I <= 6 AND 5 <= J <= 5",
      "6 < I < 8",
      "8 <= I <= 8 AND 5 <= J <= 5",
      "8 < I"
      
      While the correct ranges is
      "NULL < I < 6",
      "6 <= I <= 6 AND 5 <= J <= 5",
      "6 < I"
      
      The problem occurs when key_or() ORs
      (1) "NULL < I < 6, 6 <= I <= 6 AND 5 <= J <= 5, 6 < I" with 
      (2) "8 < I AND 5 <= J <= 5"
      
      The reason for the bug is that in key_or(), SEL_ARG *tmp is 
      used to point to the range in (1) above that is merged with 
      (2) while key1 points to the root of the red-black tree of 
      (1). When merging (1) and (2), tmp refers to the "6 < I" 
      part whereas the root is the "6 <= ... AND 5 <= J <= 5" part. 
      
      key_or() decides that the tmp range needs to be split into
      "6 < I < 8, 8 <= I <= 8, 8 < I", in which next_key_part of the 
      second range should be that of tmp. However, next_key_part is
      set to key1->next_key_part ("5 <= J <= 5") instead of 
      tmp->next_key_part (empty). Fixing this gives the correct but
      not optimal ranges:
      "NULL < I < 6",
      "6 <= I <= 6 AND 5 <= J <= 5",
      "6 < I < 8",
      "8 <= I <= 8",
      "8 < I"
      
      A second problem can be seen above: key_or() may create 
      adjacent ranges that could be replaced with a single range. 
      Fixes for this is also included in the patch so that the range
      above becomes correct AND optimal:
      "NULL < I < 6",
      "6 <= I <= 6 AND 5 <= J <= 5",
      "6 < I"
      
      Merging adjacent ranges like this gives a slightly lower cost 
      estimate for the range access.
     @ mysql-test/include/range.inc
        Add test for BUG#11765831
     @ mysql-test/r/group_min_max.result
        BUG#11765831 merges adjacent ranges, resulting in a slightly lower cost estimate for accessing the table through range access.
     @ mysql-test/r/range_icp.result
        Add test for BUG#11765831
     @ mysql-test/r/range_icp_mrr.result
        Add test for BUG#11765831
     @ mysql-test/r/range_mrr.result
        Add test for BUG#11765831
     @ mysql-test/r/range_mrr_cost.result
        Add test for BUG#11765831
     @ mysql-test/r/range_none.result
        Add test for BUG#11765831
     @ sql/opt_range.cc
        In key_or(): When a range in key1 was split due to a partially overlapping range in key2, the non-overlaping part incorrectly got next_key_part from the R-B tree root node instead of the currently active range. key_or() could also create adjacent ranges that could be replaced by a single continous range. This is also fixed.

    modified:
      mysql-test/include/range.inc
      mysql-test/r/group_min_max.result
      mysql-test/r/range_icp.result
      mysql-test/r/range_icp_mrr.result
      mysql-test/r/range_mrr.result
      mysql-test/r/range_mrr_cost.result
      mysql-test/r/range_none.result
      sql/opt_range.cc
 3101 Mayank Prasad	2011-05-18 [merge]
      merge from 5.5 for bug#11764633

    modified:
      client/mysql.cc
      libmysqld/lib_sql.cc
      sql/mysqld.h
      sql/sql_class.cc
      sql/sql_class.h
=== modified file 'mysql-test/include/range.inc'
--- a/mysql-test/include/range.inc	2011-02-01 12:47:39 +0000
+++ b/mysql-test/include/range.inc	2011-05-19 12:03:55 +0000
@@ -1471,3 +1471,35 @@ INSERT INTO t2 VALUES (1, 1, 2);
 EXPLAIN SELECT * FROM t2 WHERE a = 1 AND b >= 2 AND c >= 2;
 
 DROP TABLE t1, t2;
+
+--echo #
+--echo # BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+--echo #               AWAY QUALIFYING ROWS
+--echo #
+
+CREATE TABLE t10(
+  K INT NOT NULL AUTO_INCREMENT,
+  I INT, J INT,
+  PRIMARY KEY(K),
+  KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+                            (6,6),(6,7),(6,8),(6,9),(6,0);
+
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+
+# Insert offending value:
+INSERT INTO t100(I,J) VALUES(8,26);
+
+let $query= SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+
+#Verify that 'range' access will be used
+--echo
+--eval EXPLAIN $query
+
+# Only row 101,8,26 should be returned
+--echo
+--eval $query
+
+DROP TABLE t10,t100;

=== modified file 'mysql-test/r/group_min_max.result'
--- a/mysql-test/r/group_min_max.result	2011-05-13 12:41:14 +0000
+++ b/mysql-test/r/group_min_max.result	2011-05-19 12:03:55 +0000
@@ -876,10 +876,10 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
 explain select a1,a2,b,       max(c) from t1 where (c > 'b1') or (c <= 'g1') group by a1,a2,b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
+1	SIMPLE	t1	range	NULL	idx_t1_1	147	NULL	17	Using where; Using index for group-by
 explain select a1,a2,b,min(c),max(c) from t1 where (c > 'b1') or (c <= 'g1') group by a1,a2,b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
+1	SIMPLE	t1	range	NULL	idx_t1_1	147	NULL	17	Using where; Using index for group-by
 explain select a1,a2,b,min(c),max(c) from t1 where (c > 'b111') and (c <= 'g112') group by a1,a2,b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
@@ -924,7 +924,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by
 explain select a1,a2,b,       max(c) from t2 where (c > 'b1') or (c <= 'g1') group by a1,a2,b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by
+1	SIMPLE	t2	range	NULL	idx_t2_1	146	NULL	#	Using where; Using index for group-by
 explain select a1,a2,b,min(c),max(c) from t2 where (c > 'b1') or (c <= 'g1') group by a1,a2,b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by

=== modified file 'mysql-test/r/range_icp.result'
--- a/mysql-test/r/range_icp.result	2011-02-01 12:47:39 +0000
+++ b/mysql-test/r/range_icp.result	2011-05-19 12:03:55 +0000
@@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using index condition; Using where
 DROP TABLE t1, t2;
+#
+# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+#               AWAY QUALIFYING ROWS
+#
+CREATE TABLE t10(
+K INT NOT NULL AUTO_INCREMENT,
+I INT, J INT,
+PRIMARY KEY(K),
+KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+(6,6),(6,7),(6,8),(6,9),(6,0);
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+INSERT INTO t100(I,J) VALUES(8,26);
+
+EXPLAIN SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t100	range	I	I	10	NULL	4	Using index condition
+
+SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+K	I	J
+101	8	26
+DROP TABLE t10,t100;
 set optimizer_switch=default;

=== modified file 'mysql-test/r/range_icp_mrr.result'
--- a/mysql-test/r/range_icp_mrr.result	2011-02-01 12:47:39 +0000
+++ b/mysql-test/r/range_icp_mrr.result	2011-05-19 12:03:55 +0000
@@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using index condition; Using where
 DROP TABLE t1, t2;
+#
+# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+#               AWAY QUALIFYING ROWS
+#
+CREATE TABLE t10(
+K INT NOT NULL AUTO_INCREMENT,
+I INT, J INT,
+PRIMARY KEY(K),
+KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+(6,6),(6,7),(6,8),(6,9),(6,0);
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+INSERT INTO t100(I,J) VALUES(8,26);
+
+EXPLAIN SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t100	range	I	I	10	NULL	4	Using index condition; Using MRR
+
+SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+K	I	J
+101	8	26
+DROP TABLE t10,t100;
 set optimizer_switch=default;

=== modified file 'mysql-test/r/range_mrr.result'
--- a/mysql-test/r/range_mrr.result	2011-02-01 12:47:39 +0000
+++ b/mysql-test/r/range_mrr.result	2011-05-19 12:03:55 +0000
@@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
 DROP TABLE t1, t2;
+#
+# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+#               AWAY QUALIFYING ROWS
+#
+CREATE TABLE t10(
+K INT NOT NULL AUTO_INCREMENT,
+I INT, J INT,
+PRIMARY KEY(K),
+KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+(6,6),(6,7),(6,8),(6,9),(6,0);
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+INSERT INTO t100(I,J) VALUES(8,26);
+
+EXPLAIN SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t100	range	I	I	10	NULL	4	Using where; Using MRR
+
+SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+K	I	J
+101	8	26
+DROP TABLE t10,t100;
 set optimizer_switch=default;

=== modified file 'mysql-test/r/range_mrr_cost.result'
--- a/mysql-test/r/range_mrr_cost.result	2011-02-01 12:47:39 +0000
+++ b/mysql-test/r/range_mrr_cost.result	2011-05-19 12:03:55 +0000
@@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
 DROP TABLE t1, t2;
+#
+# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+#               AWAY QUALIFYING ROWS
+#
+CREATE TABLE t10(
+K INT NOT NULL AUTO_INCREMENT,
+I INT, J INT,
+PRIMARY KEY(K),
+KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+(6,6),(6,7),(6,8),(6,9),(6,0);
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+INSERT INTO t100(I,J) VALUES(8,26);
+
+EXPLAIN SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t100	range	I	I	10	NULL	4	Using where
+
+SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+K	I	J
+101	8	26
+DROP TABLE t10,t100;
 set optimizer_switch=default;

=== modified file 'mysql-test/r/range_none.result'
--- a/mysql-test/r/range_none.result	2011-02-01 12:47:39 +0000
+++ b/mysql-test/r/range_none.result	2011-05-19 12:03:55 +0000
@@ -1848,4 +1848,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
 DROP TABLE t1, t2;
+#
+# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER 
+#               AWAY QUALIFYING ROWS
+#
+CREATE TABLE t10(
+K INT NOT NULL AUTO_INCREMENT,
+I INT, J INT,
+PRIMARY KEY(K),
+KEY(I,J)
+);
+INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
+(6,6),(6,7),(6,8),(6,9),(6,0);
+CREATE TABLE t100 LIKE t10;
+INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
+INSERT INTO t100(I,J) VALUES(8,26);
+
+EXPLAIN SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t100	range	I	I	10	NULL	4	Using where
+
+SELECT * FROM t100 WHERE I <> 6 OR (I <> 8 AND J = 5);
+K	I	J
+101	8	26
+DROP TABLE t10,t100;
 set optimizer_switch=default;

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2011-05-18 10:43:46 +0000
+++ b/sql/opt_range.cc	2011-05-19 12:03:55 +0000
@@ -7069,11 +7069,53 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
         This is the case ("cmp>=0" means that tmp.max >= key2.min):
         key2:              [----]
         tmp:     [------------*****]
+      */
+
+      if (!tmp->next_key_part)
+      {
+        /*
+          tmp->next_key_part is empty: cut the range that is covered
+          by tmp from key2. 
+          Reason: (key2->next_key_part OR tmp->next_key_part) will be
+          empty and therefore equal to tmp->next_key_part. Thus, this
+          part of the key2 range is completely covered by tmp.
+        */
+        if (tmp->cmp_max_to_max(key2) >= 0)
+        {
+          /*
+            tmp covers the entire range in key2. 
+            key2:              [----]
+            tmp:     [-----------------]
 
+            Move on to next range in key2
+          */
+          key2->increment_use_count(-1); // Free not used tree
+          key2=key2->next;
+          continue;
+        }
+        else
+        {
+          /*
+            This is the case:
+            key2:           [-------]
+            tmp:     [---------]
+
+            Result:
+            key2:               [---]
+            tmp:     [---------]
+          */
+          key2->copy_max_to_min(tmp);
+          continue;
+        }
+      }
+
+      /*
         The ranges are overlapping but have not been merged because
-        next_key_part of tmp and key2 are different
+        next_key_part of tmp and key2 differ. 
+        key2:              [----]
+        tmp:     [------------*****]
 
-        Result:
+        Split tmp in two where key2 starts:
         key2:              [----]
         key1:    [--------][--*****]
                  ^         ^
@@ -7082,7 +7124,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
       SEL_ARG *new_arg=tmp->clone_first(key2);
       if (!new_arg)
         return 0;                               // OOM
-      if ((new_arg->next_key_part= key1->next_key_part))
+      if ((new_arg->next_key_part= tmp->next_key_part))
         new_arg->increment_use_count(key1->use_count+1);
       tmp->copy_min_to_min(key2);
       key1=key1->insert(new_arg);
@@ -7191,12 +7233,21 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
                       ^        ^
                       new_arg  tmp
           Steps:
+           0) If tmp->next_key_part is empty: do nothing. Reason:
+              (key2_cpy->next_key_part OR tmp->next_key_part) will be
+              empty and therefore equal to tmp->next_key_part. Thus,
+              the range in key2_cpy is completely covered by tmp
            1) Make new_arg with range [tmp.min, key2_cpy.max].
               new_arg->next_key_part is OR between next_key_part
               of tmp and key2_cpy
            2) Make tmp the range [key2.max, tmp.max]
            3) Insert new_arg into key1
         */
+        if (!tmp->next_key_part) // Step 0
+        {
+          key2_cpy.increment_use_count(-1);     // Free not used tree
+          break;
+        }
         SEL_ARG *new_arg=tmp->clone_last(&key2_cpy);
         if (!new_arg)
           return 0; // OOM

No bundle (reason: useless for push emails).