bzr commit into mysql-next-mr-bugfixing branch (martin.hansson:3270) Bug#26106

[Martin Hansson]

#At file:///data0/martin/bzr/bug26106/n-mr-bf/ based on revid:martin.hansson@stripped

 3270 Martin Hansson	2010-06-24
      Bug#26106: Wrong plan may be chosen when there are several possible range and
      ref accesses
        
      For ref(const) access methods there are two kinds of statistics when a prefix
      of a key is matched: range access estimate and table statistics, which are not
      necessarily consistent with each other. This may make the optimizer choose a
      key which matches fewer key parts than some other key, which is obviously not
      correct.
        
      Fixed by giving preferrence to the keys that match the most parts, and
      choosing the best one among these.

    modified:
      mysql-test/r/range.result
      mysql-test/t/range.test
      sql/sql_select.cc
=== modified file 'mysql-test/r/range.result'
--- a/mysql-test/r/range.result	2010-05-11 08:27:53 +0000
+++ b/mysql-test/r/range.result	2010-06-24 14:39:23 +0000
@@ -1698,3 +1698,64 @@ Variable_name	Value
 Handler_read_key	4
 DROP TABLE t1, t2;
 End of 5.1 tests
+#
+# Bug #26106: Wrong plan may be chosen when there are several possible
+# range and ref accesses
+#
+CREATE TABLE t1( 
+a INT,
+b INT,
+KEY k ( a ),
+KEY l ( a, b )
+);
+INSERT INTO t1(a) VALUES (1);
+INSERT INTO t1 
+VALUES (2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3);
+INSERT INTO t1 SELECT 3, 4 FROM t1 WHERE a = 2 AND b = 3;
+INSERT INTO t1 SELECT 4, 1 FROM t1 WHERE a = 2 AND b = 3;
+ANALYZE TABLE t1;
+Table	Op	Msg_type	Msg_text
+test.t1	analyze	status	OK
+INSERT INTO t1 VALUES (1, 2);
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2;
+# This must use range over index l, not k.
+EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b >= 2;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	k,l	l	10	NULL	138	Using where; Using index
+CREATE TABLE t2( 
+a INT, 
+b INT, 
+c INT,
+KEY k ( a ), 
+KEY l ( a, b ),
+KEY m ( b ), 
+KEY n ( a, c )
+);
+INSERT INTO t2(a) VALUES (1);
+INSERT INTO t2 
+VALUES (2,3,3),(2,3,3),(2,3,3),(2,3,3),(2,3,3),
+(2,3,3),(2,3,3),(2,3,3),(2,3,3),(2,3,3);
+INSERT INTO t2 SELECT 3, 4, 4 FROM t2 WHERE a = 2 AND b = 3;
+INSERT INTO t2 SELECT 4, 1, 1 FROM t2 WHERE a = 2 AND b = 3;
+ANALYZE TABLE t2;
+Table	Op	Msg_type	Msg_text
+test.t2	analyze	status	OK
+INSERT INTO t2 VALUES (1, 2, 2);
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2;
+INSERT INTO t2 VALUES (1, 1, 2);
+# This must use range over index l, not n.
+EXPLAIN SELECT * FROM t2 WHERE a = 1 AND b >= 2 AND c >= 2;
+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;

=== modified file 'mysql-test/t/range.test'
--- a/mysql-test/t/range.test	2010-05-10 07:23:23 +0000
+++ b/mysql-test/t/range.test	2010-06-24 14:39:23 +0000
@@ -1355,3 +1355,62 @@ SHOW status LIKE 'handler_read_key';
 DROP TABLE t1, t2;
 
 --echo End of 5.1 tests
+
+--echo #
+--echo # Bug #26106: Wrong plan may be chosen when there are several possible
+--echo # range and ref accesses
+--echo #
+CREATE TABLE t1( 
+  a INT,
+  b INT,
+  KEY k ( a ),
+  KEY l ( a, b )
+); 
+
+INSERT INTO t1(a) VALUES (1);
+INSERT INTO t1 
+VALUES (2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3),(2,3);
+INSERT INTO t1 SELECT 3, 4 FROM t1 WHERE a = 2 AND b = 3;
+INSERT INTO t1 SELECT 4, 1 FROM t1 WHERE a = 2 AND b = 3;
+ANALYZE TABLE t1;
+INSERT INTO t1 VALUES (1, 2);
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 2
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 4
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 8
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 16
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 32
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 64
+INSERT INTO t1 SELECT a, b FROM t1 WHERE a=1 AND b=2; # 128
+--echo # This must use range over index l, not k.
+EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b >= 2;
+
+CREATE TABLE t2( 
+  a INT, 
+  b INT, 
+  c INT,
+  KEY k ( a ), 
+  KEY l ( a, b ),
+  KEY m ( b ), 
+  KEY n ( a, c )
+); 
+
+INSERT INTO t2(a) VALUES (1);
+INSERT INTO t2 
+VALUES (2,3,3),(2,3,3),(2,3,3),(2,3,3),(2,3,3),
+       (2,3,3),(2,3,3),(2,3,3),(2,3,3),(2,3,3);
+INSERT INTO t2 SELECT 3, 4, 4 FROM t2 WHERE a = 2 AND b = 3;
+INSERT INTO t2 SELECT 4, 1, 1 FROM t2 WHERE a = 2 AND b = 3;
+ANALYZE TABLE t2;
+INSERT INTO t2 VALUES (1, 2, 2);
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 2
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 4
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 8
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 16
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 32
+INSERT INTO t2 SELECT a, b, c FROM t2 WHERE a=1 AND b=2; # 64
+INSERT INTO t2 VALUES (1, 1, 2);
+
+--echo # This must use range over index l, not n.
+EXPLAIN SELECT * FROM t2 WHERE a = 1 AND b >= 2 AND c >= 2;
+
+DROP TABLE t1, t2;

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-06-24 12:17:37 +0000
+++ b/sql/sql_select.cc	2010-06-24 14:39:23 +0000
@@ -4320,6 +4320,13 @@ best_access_path(JOIN      *join,
   double best=              DBL_MAX;
   double best_time=         DBL_MAX;
   double records=           DBL_MAX;
+  /* Holds the current number of records from the range optimizer, if any */
+  double quick_records=     DBL_MAX;
+  /* 
+     When a key from the range optimizer matches more parts than a ref key, the
+     estimates from these sources are not comparable.
+  */
+  double best_quick_records= DBL_MAX;
   table_map best_ref_depends_map= 0;
   double tmp;
   ha_rows rec;
@@ -4349,6 +4356,12 @@ best_access_path(JOIN      *join,
       /* Calculate how many key segments of the current key we can use */
       start_key= keyuse;
 
+      /* 
+         True if we find some keys from the range optimizer that match more
+         key parts than the best ref key. We then choose the best range key.
+      */
+      bool quick_matches_more_parts= false;
+      
       do /* For each keypart */
       {
         uint keypart= keyuse->keypart;
@@ -4583,7 +4596,10 @@ best_access_path(JOIN      *join,
                 if (!found_ref && table->quick_keys.is_set(key) &&    // (1)
                     table->quick_key_parts[key] > max_key_part &&     // (2)
                     records < (double)table->quick_rows[key])         // (3)
-                  records= (double)table->quick_rows[key];
+                {
+                  records= quick_records= (double)table->quick_rows[key];
+                  quick_matches_more_parts= true;                  
+                }
 
                 tmp= records;
               }
@@ -4672,8 +4688,11 @@ best_access_path(JOIN      *join,
             tmp= best_time;                    // Do nothing
         }
       } /* not ft_key */
-      if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
+      if (tmp < best_time - records/(double) TIME_FOR_COMPARE ||
+          (quick_matches_more_parts && 
+           quick_records < best_quick_records))
       {
+        best_quick_records = quick_records;
         best_time= tmp + records/(double) TIME_FOR_COMPARE;
         best= tmp;
         best_records= records;


Attachment: [text/bzr-bundle] bzr/[e-mail]