List:Commits« Previous MessageNext Message »
From:Ole John Aske Date:February 21 2012 10:32am
Subject:bzr push into mysql-trunk branch (ole.john.aske:3933 to 3934) WL#5558
View as plain text  
 3934 Ole John Aske	2012-02-21
      Fix for WL#5558: Resolve ORDER BY execution method at the optimization stage
      
      Recommit, including review comments, and some new tests after
      trunk-backporting was merged into trunk.
      
      The decision whether to sort result dataset or use ordered index scan to get 
      sorted result was partly made in JOIN::optimize, and partly in JOIN::execute().
      Furthermore the logic for EXPLAIN'ing the sort was different/incorrect compared
      to the logic used for determine filesort or not during execution. This sometimes
      caused EXPLAIN to be incorrect.
            
      This refactoring WL moves the decision on how to handle ORDER BY to the 
      optimization stage. It is a pure refactoring in the sense that it
      does not change the current filesort cost model. However, several 
      test results has changed as the EXPLAIN of those used to be incorrect.
      During the refactoring task several other bugs has also been 
      reported and fixed as standalone bugs, these are: 
            
       - bug 13514959: query plan fails to 'using index' where it should
       - bug 13528826: test_if_cheaper_ordering(): calculates incorrect 'select_limit'
       - bug 13529048: test_if_skip_sort_order() don't have to filesort a single row.
       - bug 13531865: test_if_skip_sort_order() incorrectly skip filesort if 'type' is ref_or_null
      
      As of today these fixes has already been reviewed and pushed into mysql-trrunk.
            
      As an extension of the refactoring in this commit, one should considder
      to move test_if_skip_sort_order() w/ family from sql_select.cc 
      into sql_optimize.cc as this is new the only place it is used.
      (make it 'static' also)
            
      There is likely also some code in JOIN::execute() related to
      maintaining 'pre_idx_push_cond' which now is obsolete and
      should be considdered for removal. (later)
     @ mysql-test/r/group_by.result
        Fixed 2 bugs:
        
         1. An incorrect explain where 'keys_in_use_for_query' was incorrectly
            used as argument to test_if_skip.. as part of explain. 
            The 'IGNORE INDEX FOR...' was therefore ignored for EXPLAIN
            (Did check with gdb that filesort was (and is) used during execute)
        
         2. SQL_BIG_RESULT incorrectly explained as we should avoid filesort with 
            this option.
     @ mysql-test/r/join_cache_bka.result
        'LIMIT 2' was incorrectly used to limit #rows being input 
        to 'GROUP BY' leading to incorrect access type being choosen -
        or at least explained.
     @ mysql-test/r/join_cache_bka_nixbnl.result
        'LIMIT 2' was incorrectly used to limit #rows being input 
        to 'GROUP BY' leading to incorrect access type being choosen -
        or at least explained.
     @ mysql-test/r/join_cache_bkaunique.result
        'LIMIT 2' was incorrectly used to limit #rows being input 
        to 'GROUP BY' leading to incorrect access type being choosen -
        or at least explained.
     @ mysql-test/r/join_cache_bnl.result
        'LIMIT 2' was incorrectly used to limit #rows being input 
        to 'GROUP BY' leading to incorrect access type being choosen -
        or at least explained.
     @ mysql-test/r/join_cache_nojb.result
        'LIMIT 2' was incorrectly used to limit #rows being input 
        to 'GROUP BY' leading to incorrect access type being choosen -
        or at least explained.
     @ mysql-test/r/select_found.result
        When SQL_CALC_FOUND_ROWS is specified *all* rows should
        be read from table, so 'LIMIT 10' should be ignored. 
        As there actually are 200 rows in the table, this should now
        be used to calculate access 'type' which cause that to change.
        This also leads to another ordering of the rows such that 
        the final 'LIMIT 10' clause will cause another part of the
        resultset to be returned within the limit-window.
     @ mysql-test/r/subquery_mat_none.result
        These result changes are all other materializations of 
        bug 13528826: test_if_cheaper_ordering(): calculates incorrect 'select_limit',
        which now surface on other places as there now is a single call
        to test_if_skip_... where there used to be two calls to this function.
     @ mysql-test/suite/opt_trace/r/bugs_no_prot_all.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ mysql-test/suite/opt_trace/r/bugs_no_prot_none.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ mysql-test/suite/opt_trace/r/bugs_ps_prot_none.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ mysql-test/suite/opt_trace/r/range_no_prot.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ mysql-test/suite/opt_trace/r/range_ps_prot.result
        Trace output changed as test_if_skip_sort_order is now called
        as part of ::optimize() instead of ::execute()
     @ sql/sql_executor.cc
        Moved all usage of test_if_skip_sort_order() out of the execute path
        and replace it with 'ordered_index_usage'which contans the
        skip / no skip decision as made by optimizer.
     @ sql/sql_optimizer.cc
        Move all usage of test_if_skip_sort_order() into 
        JOIN::optimize() and set 'ordered_index_usage' to reflect 
        the desicion made by test_if_skip....
        
        Also fix a bug in how the LIMIT-clause was incorrectly used 
        to limit #rows when there was a GROUP BY followed by an
        ORDER BY.
     @ sql/sql_optimizer.h
        Introduce 'enum ordered_index_usage' which remember optimizers 
        decision to possibly use an ordered index to skip filesort
        for either ORDER BY or GROUP BY
     @ sql/sql_select.cc
        Fix up EXPLAIN to use the 'ordered_index_usage' as 
        calculated by ::optimize() instead of calling
        test_if_skip_sort_order()

    modified:
      mysql-test/r/group_by.result
      mysql-test/r/join_cache_bka.result
      mysql-test/r/join_cache_bka_nixbnl.result
      mysql-test/r/join_cache_bkaunique.result
      mysql-test/r/join_cache_bnl.result
      mysql-test/r/join_cache_nojb.result
      mysql-test/r/select_found.result
      mysql-test/r/subquery_mat_none.result
      mysql-test/suite/opt_trace/r/bugs_no_prot_all.result
      mysql-test/suite/opt_trace/r/bugs_no_prot_none.result
      mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result
      mysql-test/suite/opt_trace/r/bugs_ps_prot_none.result
      mysql-test/suite/opt_trace/r/range_no_prot.result
      mysql-test/suite/opt_trace/r/range_ps_prot.result
      sql/sql_executor.cc
      sql/sql_optimizer.cc
      sql/sql_optimizer.h
      sql/sql_select.cc
 3933 Georgi Kodinov	2012-02-21 [merge]
      merge mysql-5.5->mysql-trunk

=== modified file 'mysql-test/r/group_by.result'
--- a/mysql-test/r/group_by.result	2012-02-02 13:44:26 +0000
+++ b/mysql-test/r/group_by.result	2012-02-21 10:31:44 +0000
@@ -1340,10 +1340,10 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	144	
 EXPLAIN SELECT a FROM t1 IGNORE INDEX FOR GROUP BY (PRIMARY,i2) GROUP BY a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	144	Using index
+1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	144	Using index; Using filesort
 EXPLAIN SELECT a FROM t1 IGNORE INDEX FOR ORDER BY (PRIMARY,i2) ORDER BY a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	144	Using index
+1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	144	Using index; Using filesort
 SELECT a FROM t1 IGNORE INDEX FOR ORDER BY (PRIMARY,i2) ORDER BY a;
 a
 1
@@ -2166,7 +2166,7 @@ INSERT INTO t1 VALUES (1),(2),(3),(4),(5
 EXPLAIN SELECT SQL_BIG_RESULT col1 AS field1, col1 AS field2
 FROM t1 GROUP BY field1, field2;;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	NULL	idx	5	NULL	6	Using index for group-by; Using filesort
+1	SIMPLE	t1	range	NULL	idx	5	NULL	6	Using index for group-by
 SELECT SQL_BIG_RESULT col1 AS field1, col1 AS field2
 FROM t1 GROUP BY field1, field2;;
 field1	field2

=== modified file 'mysql-test/r/join_cache_bka.result'
--- a/mysql-test/r/join_cache_bka.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/join_cache_bka.result	2012-02-21 10:31:44 +0000
@@ -2233,7 +2233,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1 force index (col_int_key), t2 ignore index (col_int_key)

=== modified file 'mysql-test/r/join_cache_bka_nixbnl.result'
--- a/mysql-test/r/join_cache_bka_nixbnl.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/join_cache_bka_nixbnl.result	2012-02-21 10:31:44 +0000
@@ -2233,7 +2233,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1 force index (col_int_key), t2 ignore index (col_int_key)

=== modified file 'mysql-test/r/join_cache_bkaunique.result'
--- a/mysql-test/r/join_cache_bkaunique.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/join_cache_bkaunique.result	2012-02-21 10:31:44 +0000
@@ -2234,7 +2234,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1 force index (col_int_key), t2 ignore index (col_int_key)

=== modified file 'mysql-test/r/join_cache_bnl.result'
--- a/mysql-test/r/join_cache_bnl.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/join_cache_bnl.result	2012-02-21 10:31:44 +0000
@@ -2216,7 +2216,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ref	col_int_key	col_int_key	5	const	1	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1,t2
@@ -2234,7 +2234,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1 force index (col_int_key), t2 ignore index (col_int_key)

=== modified file 'mysql-test/r/join_cache_nojb.result'
--- a/mysql-test/r/join_cache_nojb.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/join_cache_nojb.result	2012-02-21 10:31:44 +0000
@@ -2216,7 +2216,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ref	col_int_key	col_int_key	5	const	1	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1,t2
@@ -2234,7 +2234,7 @@ GROUP BY t1.col_int_key
 ORDER BY t1.col_int_key, t1.col_datetime
 LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	3	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using temporary; Using filesort
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 SELECT t1.col_int_key, t1.col_datetime 
 FROM t1 force index (col_int_key), t2 ignore index (col_int_key)

=== modified file 'mysql-test/r/select_found.result'
--- a/mysql-test/r/select_found.result	2011-06-27 07:17:26 +0000
+++ b/mysql-test/r/select_found.result	2012-02-21 10:31:44 +0000
@@ -84,19 +84,19 @@ UNIQUE KEY e_n (email,name)
 EXPLAIN SELECT SQL_CALC_FOUND_ROWS DISTINCT email FROM t2 LEFT JOIN t1  ON kid = t2.id WHERE t1.id IS NULL LIMIT 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	system	kid	NULL	NULL	NULL	0	const row not found
-1	SIMPLE	t2	index	NULL	e_n	104	NULL	10	
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	200	Using temporary
 SELECT SQL_CALC_FOUND_ROWS DISTINCT email FROM t2 LEFT JOIN t1  ON kid = t2.id WHERE t1.id IS NULL LIMIT 10;
 email
 email1
+email2
+email3
+email4
+email5
+email6
+email7
+email8
+email9
 email10
-email100
-email101
-email102
-email103
-email104
-email105
-email106
-email107
 SELECT FOUND_ROWS();
 FOUND_ROWS()
 200

=== modified file 'mysql-test/r/subquery_mat_none.result'
--- a/mysql-test/r/subquery_mat_none.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/subquery_mat_none.result	2012-02-21 10:31:44 +0000
@@ -137,7 +137,7 @@ explain extended
 select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
-2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	3	100.00	Using index
+2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	5	60.00	Using index
 Warnings:
 Note	1003	/* select#1 */ select `test`.`t1`.`a1` AS `a1`,`test`.`t1`.`a2` AS `a2` from `test`.`t1` where <in_optimizer>((`test`.`t1`.`a1`,`test`.`t1`.`a2`),<exists>(/* select#2 */ select `test`.`t2i`.`b1`,max(`test`.`t2i`.`b2`) from `test`.`t2i` group by `test`.`t2i`.`b1` having (((<cache>(`test`.`t1`.`a1`) = `test`.`t2i`.`b1`) or isnull(`test`.`t2i`.`b1`)) and ((<cache>(`test`.`t1`.`a2`) = max(`test`.`t2i`.`b2`)) or isnull(max(`test`.`t2i`.`b2`))) and <is_not_null_test>(`test`.`t2i`.`b1`) and <is_not_null_test>(max(`test`.`t2i`.`b2`)))))
 select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1);
@@ -148,11 +148,11 @@ prepare st1 from "explain select * from 
 execute st1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where
-2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	3	Using index
+2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	5	Using index
 execute st1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where
-2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	3	Using index
+2	DEPENDENT SUBQUERY	t2i	index	NULL	it2i3	18	NULL	5	Using index
 prepare st2 from "select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1)";
 execute st2;
 a1	a2
@@ -764,7 +764,7 @@ EXPLAIN
 SELECT * FROM t1 WHERE (a,b) = ANY (SELECT a, max(b) FROM t1 GROUP BY a);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	9	Using where
-2	DEPENDENT SUBQUERY	t1	index	NULL	a	8	NULL	1	Using filesort
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	9	Using temporary; Using filesort
 DROP TABLE t1;
 CREATE TABLE t1 (a INT);
 INSERT INTO t1 VALUES (1),(2);
@@ -1277,7 +1277,7 @@ HAVING COUNT(*) > 0
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	table1	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	table2	system	PRIMARY	NULL	NULL	NULL	1	
-2	DEPENDENT SUBQUERY	innr	index	NULL	col_int_key	5	NULL	2	Using where; Using filesort
+2	DEPENDENT SUBQUERY	innr	ALL	NULL	NULL	NULL	NULL	2	Using where; Using temporary; Using filesort
 SELECT table1.pk, table2.pk
 FROM t2 AS table1 LEFT JOIN t2 AS table2
 ON table2.pk = table1.pk AND

=== modified file 'mysql-test/suite/opt_trace/r/bugs_no_prot_all.result'
--- a/mysql-test/suite/opt_trace/r/bugs_no_prot_all.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_no_prot_all.result	2012-02-21 10:31:44 +0000
@@ -2290,14 +2290,7 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                             "table": "t1"
                           }
                         ] /* refine_plan */
-                      }
-                    ] /* steps */
-                  } /* join_optimization */
-                },
-                {
-                  "join_execution": {
-                    "select#": 2,
-                    "steps": [
+                      },
                       {
                         "reconsidering_access_paths_for_index_ordering": {
                           "index_order_summary": {
@@ -2311,6 +2304,13 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                         } /* reconsidering_access_paths_for_index_ordering */
                       }
                     ] /* steps */
+                  } /* join_optimization */
+                },
+                {
+                  "join_execution": {
+                    "select#": 2,
+                    "steps": [
+                    ] /* steps */
                   } /* join_execution */
                 }
               ] /* steps */

=== modified file 'mysql-test/suite/opt_trace/r/bugs_no_prot_none.result'
--- a/mysql-test/suite/opt_trace/r/bugs_no_prot_none.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_no_prot_none.result	2012-02-21 10:31:44 +0000
@@ -1757,14 +1757,7 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                             "table": "t1"
                           }
                         ] /* refine_plan */
-                      }
-                    ] /* steps */
-                  } /* join_optimization */
-                },
-                {
-                  "join_execution": {
-                    "select#": 2,
-                    "steps": [
+                      },
                       {
                         "reconsidering_access_paths_for_index_ordering": {
                           "index_order_summary": {
@@ -1778,6 +1771,13 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                         } /* reconsidering_access_paths_for_index_ordering */
                       }
                     ] /* steps */
+                  } /* join_optimization */
+                },
+                {
+                  "join_execution": {
+                    "select#": 2,
+                    "steps": [
+                    ] /* steps */
                   } /* join_execution */
                 }
               ] /* steps */

=== modified file 'mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result'
--- a/mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result	2012-02-21 10:31:44 +0000
@@ -2290,14 +2290,7 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                             "table": "t1"
                           }
                         ] /* refine_plan */
-                      }
-                    ] /* steps */
-                  } /* join_optimization */
-                },
-                {
-                  "join_execution": {
-                    "select#": 2,
-                    "steps": [
+                      },
                       {
                         "reconsidering_access_paths_for_index_ordering": {
                           "index_order_summary": {
@@ -2311,6 +2304,13 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                         } /* reconsidering_access_paths_for_index_ordering */
                       }
                     ] /* steps */
+                  } /* join_optimization */
+                },
+                {
+                  "join_execution": {
+                    "select#": 2,
+                    "steps": [
+                    ] /* steps */
                   } /* join_execution */
                 }
               ] /* steps */

=== modified file 'mysql-test/suite/opt_trace/r/bugs_ps_prot_none.result'
--- a/mysql-test/suite/opt_trace/r/bugs_ps_prot_none.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_ps_prot_none.result	2012-02-21 10:31:44 +0000
@@ -1737,14 +1737,7 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                             "table": "t1"
                           }
                         ] /* refine_plan */
-                      }
-                    ] /* steps */
-                  } /* join_optimization */
-                },
-                {
-                  "join_execution": {
-                    "select#": 2,
-                    "steps": [
+                      },
                       {
                         "reconsidering_access_paths_for_index_ordering": {
                           "index_order_summary": {
@@ -1758,6 +1751,13 @@ SELECT 1 FROM t1 WHERE 1 LIKE
                         } /* reconsidering_access_paths_for_index_ordering */
                       }
                     ] /* steps */
+                  } /* join_optimization */
+                },
+                {
+                  "join_execution": {
+                    "select#": 2,
+                    "steps": [
+                    ] /* steps */
                   } /* join_execution */
                 }
               ] /* steps */

=== modified file 'mysql-test/suite/opt_trace/r/range_no_prot.result'
--- a/mysql-test/suite/opt_trace/r/range_no_prot.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/range_no_prot.result	2012-02-21 10:31:44 +0000
@@ -878,10 +878,6 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -1417,10 +1413,6 @@ GROUP BY key2	{
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -4645,14 +4637,7 @@ EXPLAIN SELECT * FROM t1 WHERE i1 > '2' 
                 "access_type": "range"
               }
             ] /* refine_plan */
-          }
-        ] /* steps */
-      } /* join_optimization */
-    },
-    {
-      "join_explain": {
-        "select#": 1,
-        "steps": [
+          },
           {
             "reconsidering_access_paths_for_index_ordering": {
               "rows_estimation": {
@@ -4732,6 +4717,13 @@ EXPLAIN SELECT * FROM t1 WHERE i1 > '2' 
             } /* reconsidering_access_paths_for_index_ordering */
           }
         ] /* steps */
+      } /* join_optimization */
+    },
+    {
+      "join_explain": {
+        "select#": 1,
+        "steps": [
+        ] /* steps */
       } /* join_explain */
     }
   ] /* steps */
@@ -5077,18 +5069,6 @@ EXPLAIN SELECT DISTINCT i1 FROM t1 WHERE
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-              "index_order_summary": {
-                "database": "test",
-                "table": "t1",
-                "index": "k1",
-                "order_direction": "desc",
-                "plan_changed": true,
-                "access_type": "index_scan"
-              } /* index_order_summary */
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -6237,14 +6217,7 @@ EXPLAIN SELECT * FROM t1 WHERE c1 = '1' 
                 "table_condition_attached": null
               }
             ] /* refine_plan */
-          }
-        ] /* steps */
-      } /* join_optimization */
-    },
-    {
-      "join_explain": {
-        "select#": 1,
-        "steps": [
+          },
           {
             "reconsidering_access_paths_for_index_ordering": {
               "index_order_summary": {
@@ -6259,6 +6232,13 @@ EXPLAIN SELECT * FROM t1 WHERE c1 = '1' 
             } /* reconsidering_access_paths_for_index_ordering */
           }
         ] /* steps */
+      } /* join_optimization */
+    },
+    {
+      "join_explain": {
+        "select#": 1,
+        "steps": [
+        ] /* steps */
       } /* join_explain */
     }
   ] /* steps */

=== modified file 'mysql-test/suite/opt_trace/r/range_ps_prot.result'
--- a/mysql-test/suite/opt_trace/r/range_ps_prot.result	2012-02-14 15:18:33 +0000
+++ b/mysql-test/suite/opt_trace/r/range_ps_prot.result	2012-02-21 10:31:44 +0000
@@ -878,10 +878,6 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -1417,10 +1413,6 @@ GROUP BY key2	{
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -4645,14 +4637,7 @@ EXPLAIN SELECT * FROM t1 WHERE i1 > '2' 
                 "access_type": "range"
               }
             ] /* refine_plan */
-          }
-        ] /* steps */
-      } /* join_optimization */
-    },
-    {
-      "join_explain": {
-        "select#": 1,
-        "steps": [
+          },
           {
             "reconsidering_access_paths_for_index_ordering": {
               "rows_estimation": {
@@ -4732,6 +4717,13 @@ EXPLAIN SELECT * FROM t1 WHERE i1 > '2' 
             } /* reconsidering_access_paths_for_index_ordering */
           }
         ] /* steps */
+      } /* join_optimization */
+    },
+    {
+      "join_explain": {
+        "select#": 1,
+        "steps": [
+        ] /* steps */
       } /* join_explain */
     }
   ] /* steps */
@@ -5077,18 +5069,6 @@ EXPLAIN SELECT DISTINCT i1 FROM t1 WHERE
       "join_explain": {
         "select#": 1,
         "steps": [
-          {
-            "reconsidering_access_paths_for_index_ordering": {
-              "index_order_summary": {
-                "database": "test",
-                "table": "t1",
-                "index": "k1",
-                "order_direction": "desc",
-                "plan_changed": true,
-                "access_type": "index_scan"
-              } /* index_order_summary */
-            } /* reconsidering_access_paths_for_index_ordering */
-          }
         ] /* steps */
       } /* join_explain */
     }
@@ -6237,14 +6217,7 @@ EXPLAIN SELECT * FROM t1 WHERE c1 = '1' 
                 "table_condition_attached": null
               }
             ] /* refine_plan */
-          }
-        ] /* steps */
-      } /* join_optimization */
-    },
-    {
-      "join_explain": {
-        "select#": 1,
-        "steps": [
+          },
           {
             "reconsidering_access_paths_for_index_ordering": {
               "index_order_summary": {
@@ -6259,6 +6232,13 @@ EXPLAIN SELECT * FROM t1 WHERE c1 = '1' 
             } /* reconsidering_access_paths_for_index_ordering */
           }
         ] /* steps */
+      } /* join_optimization */
+    },
+    {
+      "join_explain": {
+        "select#": 1,
+        "steps": [
+        ] /* steps */
       } /* join_explain */
     }
   ] /* steps */

=== modified file 'sql/sql_executor.cc'
--- a/sql/sql_executor.cc	2012-02-07 14:50:31 +0000
+++ b/sql/sql_executor.cc	2012-02-21 10:31:44 +0000
@@ -117,11 +117,6 @@ static bool setup_copy_fields(THD *thd, 
   Execute select, executor entry point.
 
   @todo
-    Note, that create_sort_index calls test_if_skip_sort_order and may
-    finally replace sorting with index scan if there is a LIMIT clause in
-    the query.  It's never shown in EXPLAIN!
-
-  @todo
     When can we have here thd->net.report_error not zero?
 */
 
@@ -606,6 +601,9 @@ JOIN::execute(JOIN *parent)
           Note: here we call make_cond_for_table() a second time in order
           to get sort_table_cond. An alternative could be to use
           Item::copy_andor_structure() to make a copy of sort_table_cond.
+
+          TODO: This is now obsolete as test_if_skip_sort_order()
+                is not any longer called as part of JOIN::execute() !
         */
         if (curr_table->pre_idx_push_cond)
         {
@@ -664,9 +662,6 @@ JOIN::execute(JOIN *parent)
 	Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser
 	chose FILESORT to be faster than INDEX SCAN or there is no 
 	suitable index present.
-	Note, that create_sort_index calls test_if_skip_sort_order and may
-	finally replace sorting with index scan if there is a LIMIT clause in
-	the query. XXX: it's never shown in EXPLAIN!
 	OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
       */
       DBUG_PRINT("info",("Sorting for order by/group by"));
@@ -936,11 +931,9 @@ JOIN::optimize_distinct()
   /* Optimize "select distinct b from t1 order by key_part_1 limit #" */
   if (order && skip_sort_order)
   {
-    /* Should always succeed */
-    if (test_if_skip_sort_order(&join_tab[const_tables],
-                                order, unit->select_limit_cnt, false, 
-                                &join_tab[const_tables].table->
-                                keys_in_use_for_order_by))
+    /* Should already have been optimized away */
+    DBUG_ASSERT(ordered_index_usage == ordered_index_order_by);
+    if (ordered_index_usage == ordered_index_order_by)
       order= NULL;
   }
 }
@@ -3861,19 +3854,25 @@ create_sort_index(THD *thd, JOIN *join, 
   select= tab->select;
 
   /*
-    When there is SQL_BIG_RESULT do not sort using index for GROUP BY,
-    and thus force sorting on disk unless a group min-max optimization
-    is going to be used as it is applied now only for one table queries
-    with covering indexes.
+    JOIN::optimize may have prepared an access path which makes
+    either the GROUP BY or ORDER BY sorting obsolete by using an
+    ordered index for the access. If the requested 'order' match
+    the prepared 'ordered_index_usage', we don't have to build 
+    a temporary sort index now.
   */
-  if ((order != join->group_list || 
-       !(join->select_options & SELECT_BIG_RESULT) ||
-       (select && select->quick &&
-        select->quick->get_type() == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)) &&
-      test_if_skip_sort_order(tab,order,select_limit,0, 
-                              is_order_by ?  &table->keys_in_use_for_order_by :
-                              &table->keys_in_use_for_group_by))
-    DBUG_RETURN(0);
+  {
+    DBUG_ASSERT((is_order_by) == (order == join->order));  // Obsolete arg !
+    const bool is_skippable= (is_order_by) ?
+      ( join->simple_order &&
+        join->ordered_index_usage == JOIN::ordered_index_order_by )
+      :
+      ( join->simple_group &&
+        join->ordered_index_usage == JOIN::ordered_index_group_by );
+
+    if (is_skippable)
+      DBUG_RETURN(0);
+  }
+
   for (ORDER *ord= join->order; ord; ord= ord->next)
     length++;
   if (!(join->sortorder= 

=== modified file 'sql/sql_optimizer.cc'
--- a/sql/sql_optimizer.cc	2012-02-16 13:09:08 +0000
+++ b/sql/sql_optimizer.cc	2012-02-21 10:31:44 +0000
@@ -591,15 +591,21 @@ JOIN::optimize()
     JOIN_TAB *tab= &join_tab[const_tables];
     bool all_order_fields_used;
     if (order)
-      skip_sort_order= test_if_skip_sort_order(tab, order, m_select_limit, 1, 
-        &tab->table->keys_in_use_for_order_by);
+    {
+      skip_sort_order=
+        test_if_skip_sort_order(tab, order, m_select_limit,
+                                true,           // no_changes
+                                &tab->table->keys_in_use_for_order_by);
+    }
     if ((group_list=create_distinct_group(thd, ref_ptrs,
                                           order, fields_list, all_fields,
 				          &all_order_fields_used)))
     {
-      bool skip_group= (skip_sort_order &&
-        test_if_skip_sort_order(tab, group_list, m_select_limit, 1, 
-                                &tab->table->keys_in_use_for_group_by) != 0);
+      const bool skip_group=
+        skip_sort_order &&
+        test_if_skip_sort_order(tab, group_list, m_select_limit,
+                                  true,         // no_changes
+                                  &tab->table->keys_in_use_for_group_by);
       count_field_types(select_lex, &tmp_table_param, all_fields, 0);
       if ((skip_group && all_order_fields_used) ||
 	  m_select_limit == HA_POS_ERROR ||
@@ -820,6 +826,26 @@ JOIN::optimize()
 
   if (const_tables != tables)
   {
+    JOIN_TAB *tab= &join_tab[const_tables];
+
+    if (order)
+    {
+      /*
+        Force using of tmp table if sorting by a SP or UDF function due to
+        their expensive and probably non-deterministic nature.
+      */
+      for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
+      {
+        Item *item= *tmp_order->item;
+        if (item->is_expensive())
+        {
+          /* Force tmp table without sort */
+          need_tmp=1; simple_order=simple_group=0;
+          break;
+        }
+      }
+    }
+
     /*
       Because filesort always does a full table scan or a quick range scan
       we must add the removed reference to the select for the table.
@@ -827,54 +853,80 @@ JOIN::optimize()
       as in other cases the join is done before the sort.
     */
     if ((order || group_list) &&
-        join_tab[const_tables].type != JT_ALL &&
-        join_tab[const_tables].type != JT_FT &&
-        join_tab[const_tables].type != JT_REF_OR_NULL &&
+        tab->type != JT_ALL &&
+        tab->type != JT_FT &&
+        tab->type != JT_REF_OR_NULL &&
         ((order && simple_order) || (group_list && simple_group)))
     {
-      if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
+      if (add_ref_to_table_cond(thd,tab)) {
         DBUG_RETURN(1);
       }
     }
     
-    if (!(select_options & SELECT_BIG_RESULT) &&
-        ((group_list &&
-          (!simple_group ||
-           !test_if_skip_sort_order(&join_tab[const_tables], group_list,
-                                    unit->select_limit_cnt, 0, 
-                                    &join_tab[const_tables].table->
-                                    keys_in_use_for_group_by))) ||
-         select_distinct) &&
-        tmp_table_param.quick_group && !procedure)
-    {
-      need_tmp=1; simple_order=simple_group=0;	// Force tmp table without sort
-    }
-    if (order)
+    /*
+      Investigate whether we may use an ordered index as part of either
+      DISTINCT, GROUP BY or ORDER BY execution. An ordered index may be
+      used for only the first of any of these terms to be executed. This
+      is reflected in the order which we check for test_if_skip_sort_order()
+      below. However we do not check for DISTINCT here, as it would have
+      been transformed to a GROUP BY at this stage if it is a candidate for 
+      ordered index optimization.
+      If a decision was made to use an ordered index, the availability
+      if such an access path is stored in 'ordered_index_usage' for later
+      use by 'execute' or 'explain'
+    */
+    DBUG_ASSERT(ordered_index_usage == ordered_index_void);
+
+    if (group_list)   // GROUP BY honoured first
+                      // (DISTINCT was rewritten to GROUP BY if skippable)
     {
       /*
-        Do we need a temporary table due to the ORDER BY not being equal to
-        the GROUP BY? The call to test_if_skip_sort_order above tests for the
-        GROUP BY clause only and hence is not valid in this case. So the
-        estimated number of rows to be read from the first table is not valid.
-        We clear it here so that it doesn't show up in EXPLAIN.
-       */
-      if (need_tmp && (select_options & SELECT_DESCRIBE) != 0)
-        join_tab[const_tables].limit= 0;
-      /*
-        Force using of tmp table if sorting by a SP or UDF function due to
-        their expensive and probably non-deterministic nature.
+        When there is SQL_BIG_RESULT do not sort using index for GROUP BY,
+        and thus force sorting on disk unless a group min-max optimization
+        is going to be used as it is applied now only for one table queries
+        with covering indexes.
       */
-      for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
+      if (!(select_options & SELECT_BIG_RESULT) ||
+            (tab->select &&
+             tab->select->quick &&
+             tab->select->quick->get_type() ==
+             QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
       {
-        Item *item= *tmp_order->item;
-        if (item->is_expensive())
+        if (simple_group &&              // GROUP BY is possibly skippable
+            !select_distinct)            // .. if not preceded by a DISTINCT
         {
-          /* Force tmp table without sort */
-          need_tmp=1; simple_order=simple_group=0;
-          break;
+          /*
+            Calculate a possible 'limit' of table rows for 'GROUP BY':
+            A specified 'LIMIT' is relative to the final resultset.
+            'need_tmp' implies that there will be more postprocessing 
+            so the specified 'limit' should not be enforced yet.
+           */
+          const ha_rows limit = need_tmp ? HA_POS_ERROR : m_select_limit;
+
+          if (test_if_skip_sort_order(tab, group_list, limit, false, 
+                                      &tab->table->keys_in_use_for_group_by))
+          {
+            ordered_index_usage= ordered_index_group_by;
+          }
+        }
+
+        if ((ordered_index_usage != ordered_index_group_by) &&
+            tmp_table_param.quick_group && !procedure)
+        {
+          need_tmp=1;
+          simple_order= simple_group= false; // Force tmp table without sort
         }
       }
     }
+    else if (order &&                      // ORDER BY wo/ preceeding GROUP BY
+             (simple_order || skip_sort_order)) // which is possibly skippable
+    {
+      if (test_if_skip_sort_order(tab, order, m_select_limit, false, 
+                                  &tab->table->keys_in_use_for_order_by))
+      {
+        ordered_index_usage= ordered_index_order_by;
+      }
+    }
   }
 
   tmp_having= having;

=== modified file 'sql/sql_optimizer.h'
--- a/sql/sql_optimizer.h	2012-02-16 11:36:03 +0000
+++ b/sql/sql_optimizer.h	2012-02-21 10:31:44 +0000
@@ -187,6 +187,19 @@ public:
     GROUP/ORDER BY.
   */
   bool simple_order, simple_group;
+
+  /*
+    ordered_index_usage is set if an ordered index access
+    should be used instead of a filesort when computing 
+    ORDER/GROUP BY.
+  */
+  enum
+  {
+    ordered_index_void,       // No ordered index avail.
+    ordered_index_group_by,   // Use index for GROUP BY
+    ordered_index_order_by,   // Use index for ORDER BY
+  } ordered_index_usage;
+
   /**
     Is set only in case if we have a GROUP BY clause
     and no ORDER BY after constant elimination of 'order'.
@@ -323,6 +336,7 @@ public:
     no_order= 0;
     simple_order= 0;
     simple_group= 0;
+    ordered_index_usage= ordered_index_void;
     skip_sort_order= 0;
     need_tmp= 0;
     hidden_group_fields= 0; /*safety*/

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2012-02-16 10:52:45 +0000
+++ b/sql/sql_select.cc	2012-02-21 10:31:44 +0000
@@ -862,6 +862,7 @@ JOIN::explain()
     table to resolve ORDER BY: in that case, we only may need to do
     filesort for GROUP BY.
   */
+  bool is_order_by= true;
   if (!order && !no_order && (!skip_sort_order || !need_tmp))
   {
     /*
@@ -871,21 +872,32 @@ JOIN::explain()
     order= group_list;
     simple_order= simple_group;
     skip_sort_order= 0;
+    is_order_by= false;
   }
-  if (order && 
-      (order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
-      (const_tables == tables ||
-       ((simple_order || skip_sort_order) &&
-        test_if_skip_sort_order(&join_tab[const_tables], order,
-                                m_select_limit, 0, 
-                                &join_tab[const_tables].table->
-                                keys_in_use_for_query))))
-    order=0;
+
   having= tmp_having;
   if (tables)
+  {
+    /*
+      JOIN::optimize may have prepared an access patch which makes
+      either the GROUP BY or ORDER BY sorting obsolete by using an
+      ordered index for the access. If the required 'order' match
+      the available 'ordered_index_usage' we will use ordered index
+      access instead of doing a filesort.
+
+      NOTE: This code is intentional similar to 'is_skippable' code
+            in create_sort_index() which is the ::execute()
+            counterpart of what we 'explain' here.
+    */
+    const bool is_skippable= (is_order_by) ?
+      ( simple_order && ordered_index_usage == ordered_index_order_by )
+      :
+      ( simple_group && ordered_index_usage == ordered_index_group_by );
+
     explain_query_specification(thd, this, need_tmp,
-                                order != 0 && !skip_sort_order,
+                                (order != NULL) && !is_skippable,
                                 select_distinct);
+  }
   else
     explain_no_table(thd, this, "No tables used");
 

No bundle (reason: useless for push emails).
Thread
bzr push into mysql-trunk branch (ole.john.aske:3933 to 3934) WL#5558Ole John Aske21 Feb