#At file:///export/home/jl208045/mysql/mysql-trunk-11765831/ based on revid:jorgen.loland@stripped
3382 Jorgen Loland 2011-05-06
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-05-06 13:57:35 +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-05-06 13:57:35 +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-06 13:57:35 +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-06 13:57:35 +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-06 13:57:35 +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-06 13:57:35 +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-06 13:57:35 +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-06 13:26:31 +0000
+++ b/sql/opt_range.cc 2011-05-06 13:57:35 +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 has no next_key_part, thus
+ tmp->next_key_part == (tmp->next_key_part OR key2->next_key_part)
+ == empty
+
+ The range that is covered by tmp can be cut from key2
+ */
+ 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
Attachment: [text/bzr-bundle] bzr/jorgen.loland@oracle.com-20110506135735-qw9qba2ohe6b6mna.bundle
