bzr commit into mysql-5.0-bugteam branch (kgeorge:2744) Bug#36817

[Georgi Kodinov]

#At file:///home/kgeorge/mysql/work/B36817-5.0-bugteam/ based on revid:sergey.glukhov@stripped

 2744 Georgi Kodinov	2008-12-12
      Bug #36817: Non optimal index choice, depending on index creation order
      
      When selecting among the available indexes for REF access the optimizer can take 
      into account that certain indexes may require sorting for ORDER BY and some may not.
      This can be done by putting extra weight to the indexes that would require filesort.
      Note that this extra weight should not be added when comparing with the other access
      methods (e.g. quick access) because it's considered at a later stage anyway.
modified:
  mysql-test/r/order_by.result
  mysql-test/t/order_by.test
  sql/sql_select.cc

per-file messages:
  mysql-test/r/order_by.result
    Bug #36817: test case
  mysql-test/t/order_by.test
    Bug #36817: test case
  sql/sql_select.cc
    Bug #36817: prefer for REF access the index that is not causing a filesort
    for ORDER BY over the one that does cause it.
=== modified file 'mysql-test/r/order_by.result'
--- a/mysql-test/r/order_by.result	2008-10-16 16:37:17 +0000
+++ b/mysql-test/r/order_by.result	2008-12-12 14:45:32 +0000
@@ -1092,3 +1092,18 @@ FROM t3;
 2
 NULL
 DROP TABLE t1, t2, t3;
+CREATE TABLE t1 (a INT, b INT, c INT, d INT, e INT, 
+KEY large_k (a,b,c,d), KEY small_k (a,b,d));
+INSERT INTO t1 (a,b,c) VALUES
+(1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
+EXPLAIN SELECT e FROM t1 WHERE a=1 AND b=1 ORDER BY d DESC LIMIT 0,4;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	large_k,small_k	small_k	10	const,const	3	Using where
+SELECT e FROM t1 WHERE a=1 AND b=1 ORDER BY d DESC LIMIT 0,4;
+e
+NULL
+NULL
+NULL
+NULL
+DROP TABLE t1;
+End of 5.0 tests

=== modified file 'mysql-test/t/order_by.test'
--- a/mysql-test/t/order_by.test	2008-10-16 16:37:17 +0000
+++ b/mysql-test/t/order_by.test	2008-12-12 14:45:32 +0000
@@ -756,3 +756,20 @@ SELECT
   FROM t3;
 
 DROP TABLE t1, t2, t3;
+
+#
+# Bug #36817: Non optimal index choice, depending on index creation order
+#
+
+CREATE TABLE t1 (a INT, b INT, c INT, d INT, e INT, 
+  KEY large_k (a,b,c,d), KEY small_k (a,b,d));
+
+INSERT INTO t1 (a,b,c) VALUES
+(1,1,1),(1,1,1),(1,1,1),(1,1,1),(1,0,1),(1,2,1),(1,3,1);
+
+EXPLAIN SELECT e FROM t1 WHERE a=1 AND b=1 ORDER BY d DESC LIMIT 0,4;
+SELECT e FROM t1 WHERE a=1 AND b=1 ORDER BY d DESC LIMIT 0,4;
+
+DROP TABLE t1;
+
+--echo End of 5.0 tests

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2008-12-10 14:13:11 +0000
+++ b/sql/sql_select.cc	2008-12-12 14:45:32 +0000
@@ -218,7 +218,8 @@ static void select_describe(JOIN *join, 
 static Item *remove_additional_cond(Item* conds);
 static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
 static bool test_if_ref(Item_field *left_item,Item *right_item);
-
+static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
+				uint *used_key_parts);
 
 /*
   This handles SELECT with and without UNION
@@ -3887,6 +3888,7 @@ best_access_path(JOIN      *join,
   uint best_max_key_part=   0;
   my_bool found_constraint= 0;
   double best=              DBL_MAX;
+  double best_sort=         0;
   double best_time=         DBL_MAX;
   double records=           DBL_MAX;
   double tmp;
@@ -3913,6 +3915,8 @@ best_access_path(JOIN      *join,
       key_part_map const_part= 0;
       /* The or-null keypart in ref-or-null access: */
       key_part_map ref_or_null_part= 0;
+      uint not_used;
+      double tmp_sort= 0;
 
       /* Calculate how many key segments of the current key we can use */
       start_key= keyuse;
@@ -4208,10 +4212,28 @@ best_access_path(JOIN      *join,
             tmp= best_time;                    // Do nothing
         }
       } /* not ft_key */
-      if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
+
+      /*
+        When comparing the weights of the indexes take into cosnideration
+        the fact that some of them may cause filesort and some may not.
+        The additional cost here (best_sort/tmp_sort) reflects this fact.
+        But note that it should influence only the relative weight of the
+        indexes and not when compared to the other access method (e.g. quick).
+      */  
+      if (idx == join->const_tables && s->table == join->sort_by_table &&
+          join->order && !join->skip_sort_order &&
+          !test_if_order_by_key (join->order, table, start_key->key, &not_used))
+      {
+          /* We will have to make a temp table with this index */
+          tmp_sort= tmp;
+      }
+
+      if (tmp + tmp_sort < best_time + best_sort - 
+          records/(double) TIME_FOR_COMPARE)
       {
         best_time= tmp + records/(double) TIME_FOR_COMPARE;
         best= tmp;
+        best_sort= tmp_sort;
         best_records= records;
         best_key= start_key;
         best_max_key_part= max_key_part;