List:Commits« Previous MessageNext Message »
From:Jorgen Loland Date:April 29 2011 9:13am
Subject:bzr commit into mysql-trunk branch (jorgen.loland:3341)
View as plain text  
#At file:///export/home/jl208045/mysql/mysql-trunk-11765831/ based on revid:jorgen.loland@stripped

 3341 Jorgen Loland	2011-04-29
      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
=== 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-04-29 09:13:14 +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-04-27 09:10:45 +0000
+++ b/mysql-test/r/group_min_max.result	2011-04-29 09:13:14 +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-04-29 09:13:14 +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-04-29 09:13:14 +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-04-29 09:13:14 +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-04-29 09:13:14 +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-04-29 09:13:14 +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-04-29 08:02:04 +0000
+++ b/sql/opt_range.cc	2011-04-29 09:13:14 +0000
@@ -6970,11 +6970,42 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
         tmp:     [------**********]
                         ^         ^
                         tmp.max is somewhere between these points here
+
+        If tmp->next_key_part is empty:
+          => tmp->next_key_part OR key2->next_key_part will be empty
+          If tmp.max >= key2.max: the key2 range is covered by tmp.
+                                  Move on to next range in key2
+          If key2.max > tmp.max:  Make range of key2 [tmp.max, key2.max]
+                                  and start from the top
+        If tmp->next_key_part is NOT empty:
+          1) Make new_arg with range [tmp.min, key2.min] and
+             insert it into key1
+          2) Make tmp the range [key2.min, tmp.max]
       */
+      if (!tmp->next_key_part)
+      {
+        if (tmp->cmp_max_to_max(key2) >= 0)
+        {
+          /*
+            tmp.max >= key2.max. tmp covers the entire range in key2.
+            Move to next key2 range
+          */
+          key2->increment_use_count(-1); // Free not used tree
+          key2=key2->next;
+          continue;
+        }
+        else
+        {
+          // Make key2 the range [tmp.max, key2.max]
+          key2->copy_max_to_min(tmp);
+          continue;
+        }
+      }
+
       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);
@@ -7074,6 +7105,10 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
 
           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
@@ -7081,6 +7116,11 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
            3) Insert new_arg into key1 (after changing tmp range to
               insert into correct location in key1 tree)
         */
+        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


Attachment: [text/bzr-bundle] bzr/jorgen.loland@oracle.com-20110429091314-7c5oqhir1ikg3e42.bundle
Thread
bzr commit into mysql-trunk branch (jorgen.loland:3341) Jorgen Loland29 Apr
  • Re: bzr commit into mysql-trunk branch (jorgen.loland:3341)Jorgen Loland29 Apr