Backport of:

revno: 2876.47.174
revision-id: jorgen.loland@oracle.com-20110519120355-qn7eprkad9jqwu5j
parent: mayank.prasad@oracle.com-20110518143645-bdxv4udzrmqsjmhq
committer: Jorgen Loland <jorgen.loland@oracle.com>
branch nick: mysql-trunk-11765831
timestamp: Thu 2011-05-19 14:03:55 +0200
message:
  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.

1 files changed, 47 insertions, 1 deletions

diff --git a/mysql-test/t/range.test b/mysql-test/t/range.test
index 7206235e3e2..0a34bac32ba 100644
--- a/mysql-test/t/range.test
+++ b/mysql-test/t/range.test
@@ -3,7 +3,7 @@
 #
 
 --disable_warnings
-drop table if exists t1, t2, t3;
+drop table if exists t1, t2, t3, t10, t100;
 --enable_warnings
 
 CREATE TABLE t1 (
@@ -1402,3 +1402,49 @@ insert into t1 values ('2000-03-09 15:56:59'),('2000-05-05 23:24:28'),('2000-06-
 select  min(f1)  from t1 where f1 >= '2006-05-25 07:00:20' and f1 between '2003-11-23 10:00:09' and '2010-01-01 01:01:01' and f1 > '2001-01-01 01:01:01';
 drop table t1;
 
+--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;
+
+--echo #
+--echo # lp:817363: Wrong result with sort_union and multipart key in maria-5.3
+--echo # 
+CREATE TABLE t1 (a int NOT NULL , b int, c int, d varchar(32), KEY (d,b), PRIMARY KEY (a)) ;
+INSERT INTO t1 VALUES (7,7,NULL,'e'),(8,1,0,'p'),(9,7,1,'s'),(10,1,1,'j'),(12,2,0,'c'),(13,0,0,'a'),(14,1,1,'q');
+
+SELECT c FROM t1                  WHERE d='q' OR d>='q' OR a > 97 OR (d IN ('j','s','i') AND b = 102);
+SELECT c FROM t1 ignore index (d) WHERE d='q' OR d>='q' OR a > 97 OR (d IN ('j','s','i') AND b = 102);
+
+SELECT * FROM t1 ignore index(d) WHERE d = 'q' OR d >= 'q' OR (d IN ( 'j' , 's' , 'i' ) AND ( b = 102 ));
+SELECT * FROM t1 force index(d)  WHERE d = 'q' OR d >= 'q' OR (d IN ( 'j' , 's' , 'i' ) AND ( b = 102 ));
+
+DROP TABLE t1;
+