bzr commit into mysql-5.5 branch (jorgen.loland:3382) Bug#11882131

[Jorgen Loland]

#At file:///export/home/jl208045/mysql/mysql-5.5-11882131/ based on revid:gkodinov@stripped

 3382 Jorgen Loland	2011-03-18
      BUG#11882131: OPTIMIZER CHOOSES FILESORT WHEN REVERSE 
                    INDEX SCAN COULD BE USED
      
      Consider the following case:
      
      CREATE TABLE t1 (a INT,KEY (a));
      INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
      SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
      
      This query could have been resolved by GROUP range access
      if it hadn't been for the descending ordering [1]. 
      
      To access this table, covering index scan is first chosen. 
      Later an attempt to avoid sorting is made by calling 
      test_if_skip_sort_order(). Range analysis now decides that
      GROUP range access is the most efficient access method, but
      since this access method cannot produce records in 
      descending order, it is scrapped by 
      test_if_skip_sort_order() before concluding that filesort 
      is required after all. 
      
      In this case, test_if_skip_sort_order() fails to check if 
      the descending ordering can be resolved by scanning the 
      covering index in reverse order instead. Because of this, 
      the resulting execution plan is to 1) scan the index and 2) 
      sort the result instead of simply do 1) scan the index in 
      reverse order.
      
      With this patch, test_if_skip_sort_order() will try to 
      produce a result in descending order by doing reverse scan 
      on the index in the case that the suggested range access 
      plan cannot be used.
      
      Note that even without this patch, reverse index scan would
      be chosen given that an unusable range access plan was not 
      suggested used.
      
      [1] GROUP, INDEX_MERGE, ROR_INTERSECT and ROR_UNION range 
      access methods cannot produce reverse ordering.
     @ mysql-test/r/order_by.result
        BUG#11882131: Changed test output

    modified:
      mysql-test/r/order_by.result
      sql/sql_select.cc
=== modified file 'mysql-test/r/order_by.result'
--- a/mysql-test/r/order_by.result	2011-02-07 09:40:42 +0000
+++ b/mysql-test/r/order_by.result	2011-03-18 10:48:27 +0000
@@ -1651,7 +1651,7 @@ CREATE TABLE t1 (a INT,KEY (a));
 INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
 EXPLAIN SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	a	a	5	NULL	10	Using where; Using index; Using filesort
+1	SIMPLE	t1	index	a	a	5	NULL	10	Using where; Using index
 SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
 a	1
 10	1

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2011-03-16 14:11:20 +0000
+++ b/sql/sql_select.cc	2011-03-18 10:48:27 +0000
@@ -13827,7 +13827,17 @@ check_reverse_order:                  
             quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
         {
           tab->limit= 0;
-          goto use_filesort;               // Use filesort
+          if (select && select->quick != save_quick)
+          {
+            /*
+              A new quick was created by this function, but it cannot
+              produce reverse ordering. Restore save_quick and
+              continue to check of ordering can be resolved by reverse
+              scan of best_key index instead.
+            */
+            delete select->quick;
+            select->quick= save_quick;
+          }
         }
       }
     }
@@ -13929,7 +13939,7 @@ check_reverse_order:                  
   /*
     Cleanup:
     We may have both a 'select->quick' and 'save_quick' (original)
-    at this point. Delete the one that we wan't use.
+    at this point. Delete the one that we won't use.
   */
 
 skipped_filesort:


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