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 List-Archive: http://lists.mysql.com/commits/143003 Message-Id: <20120221103217.7539C23B@fimafeng09.norway.sun.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit 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 ((`test`.`t1`.`a1`,`test`.`t1`.`a2`),(/* select#2 */ select `test`.`t2i`.`b1`,max(`test`.`t2i`.`b2`) from `test`.`t2i` group by `test`.`t2i`.`b1` having ((((`test`.`t1`.`a1`) = `test`.`t2i`.`b1`) or isnull(`test`.`t2i`.`b1`)) and (((`test`.`t1`.`a2`) = max(`test`.`t2i`.`b2`)) or isnull(max(`test`.`t2i`.`b2`))) and (`test`.`t2i`.`b1`) and (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).