From: Jorgen Loland Date: March 21 2011 9:10am Subject: bzr push into mysql-trunk branch (jorgen.loland:3280 to 3281) List-Archive: http://lists.mysql.com/commits/133403 Message-Id: <20110321091039.949E37D8@atum21.norway.sun.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit 3281 Jorgen Loland 2011-03-21 Fixed two related optimizer tracing bugs. It was assumed that TABLE_READ_PLAN pointers to SEL_ARGs pointed to the first range interval when it in fact points to the root node of the SEL_ARG red-black tree. Added test case for * multiple ranges over a multi-keypart range * multiple ranges analyzed in group quick select Problems were that trace failed to print only about half of all ranges (the root and every range after it) in * the chosen_range_access_summary{} section * the group_index_range{} section Fixed by navigating to the first range interval before printing ranges. modified: mysql-test/include/optimizer_trace_range.inc mysql-test/r/optimizer_trace_range_no_prot.result mysql-test/r/optimizer_trace_range_ps_prot.result sql/opt_range.cc 3280 Guilhem Bichot 2011-03-17 Opt_trace_context::get_current_struct() not needed anymore, is deleted. @ sql/opt_range.cc fix for compiler problem @ sql/opt_trace.cc get_current_struct() gone; assert_current_struct() is enough and has narrower scope. @ sql/opt_trace.h get_current_struct() gone modified: WL4800_TODO.txt sql/opt_range.cc sql/opt_trace.cc sql/opt_trace.h === modified file 'mysql-test/include/optimizer_trace_range.inc' --- a/mysql-test/include/optimizer_trace_range.inc 2011-01-18 13:00:16 +0000 +++ b/mysql-test/include/optimizer_trace_range.inc 2011-03-21 09:01:05 +0000 @@ -92,7 +92,9 @@ SELECT * FROM information_schema.OPTIMIZ # group with range --echo -EXPLAIN SELECT key2, MIN(key2_1) FROM t2 where key2 < 5 GROUP BY key2; +EXPLAIN SELECT key2, MIN(key2_1) FROM t2 +WHERE key2 = 5 or key2 = 4 or key2 = 3 or key2 = 2 or key2 = 1 +GROUP BY key2; --echo SELECT * FROM information_schema.OPTIMIZER_TRACE; @@ -120,6 +122,13 @@ EXPLAIN SELECT * FROM t2 WHERE key1a = 5 --echo SELECT * FROM information_schema.OPTIMIZER_TRACE; +# Multiple ranges on key parts in same index +--echo +EXPLAIN SELECT * FROM t2 WHERE (key1a = 5 and key1b < 10 and key1b > 2) or + (key1a = 4 and key1b < 7 and key1b > 3); +--echo +SELECT * FROM information_schema.OPTIMIZER_TRACE; + # more_expensive_than_table_scan --echo EXPLAIN SELECT * FROM t1 WHERE (key1 > 1 OR key2 > 2); === modified file 'mysql-test/r/optimizer_trace_range_no_prot.result' --- a/mysql-test/r/optimizer_trace_range_no_prot.result 2011-03-01 10:55:27 +0000 +++ b/mysql-test/r/optimizer_trace_range_no_prot.result 2011-03-21 09:01:05 +0000 @@ -1006,20 +1006,24 @@ EXPLAIN SELECT DISTINCT key2 FROM t2 { ] /* steps */ } 0 -EXPLAIN SELECT key2, MIN(key2_1) FROM t2 where key2 < 5 GROUP BY key2; +EXPLAIN SELECT key2, MIN(key2_1) FROM t2 +WHERE key2 = 5 or key2 = 4 or key2 = 3 or key2 = 2 or key2 = 1 +GROUP BY key2; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t2 range i2_1,i2_2 i2_1 4 NULL 47 Using where; Using index SELECT * FROM information_schema.OPTIMIZER_TRACE; QUERY TRACE MISSING_BYTES_BEYOND_MAX_MEM_SIZE -EXPLAIN SELECT key2, MIN(key2_1) FROM t2 where key2 < 5 GROUP BY key2 { +EXPLAIN SELECT key2, MIN(key2_1) FROM t2 +WHERE key2 = 5 or key2 = 4 or key2 = 3 or key2 = 2 or key2 = 1 +GROUP BY key2 { "steps": [ { "join_preparation": { "select#": 1, "steps": [ { - "expanded_query": "/* select#1 */ select `test`.`t2`.`key2` AS `key2`,min(`test`.`t2`.`key2_1`) AS `MIN(key2_1)` from `test`.`t2` where (`test`.`t2`.`key2` < 5) group by `test`.`t2`.`key2`" + "expanded_query": "/* select#1 */ select `test`.`t2`.`key2` AS `key2`,min(`test`.`t2`.`key2_1`) AS `MIN(key2_1)` from `test`.`t2` where ((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1)) group by `test`.`t2`.`key2`" } ] /* steps */ } /* join_preparation */ @@ -1031,19 +1035,19 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "condition_processing": { "condition": "WHERE", - "original_condition": "(`test`.`t2`.`key2` < 5)", + "original_condition": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))", "steps": [ { "transformation": "equality_propagation", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" }, { "transformation": "constant_propagation", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" }, { "transformation": "trivial_condition_removal", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" } ] /* steps */ } /* condition_processing */ @@ -1114,7 +1118,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_1", "covering": true, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "records": 5, "cost": 31 @@ -1123,7 +1131,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_2", "covering": true, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "records": 5, "cost": 31 @@ -1143,7 +1155,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "key2" ] /* key_parts_used_for_access */, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "chosen": true } /* best_group_range_summary */, @@ -1152,7 +1168,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "index": "i2_1", "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "index_only": true, "records": 47, @@ -1163,7 +1183,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "index": "i2_2", "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "index_only": true, "records": 47, @@ -1184,7 +1208,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_1", "records": 47, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */ } /* range_access_plan */, "records_for_plan": 47, @@ -1219,14 +1247,14 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 }, { "attaching_conditions_to_tables": { - "original_condition": "(`test`.`t2`.`key2` < 5)", + "original_condition": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))", "attached_conditions_computation": [ ] /* attached_conditions_computation */, "attached_conditions_summary": [ { "database": "test", "table": "t2", - "attached": "(`test`.`t2`.`key2` < 5)" + "attached": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))" } ] /* attached_conditions_summary */ } /* attaching_conditions_to_tables */ @@ -2111,6 +2139,207 @@ EXPLAIN SELECT * FROM t2 WHERE key1a = 5 ] /* steps */ } 0 +EXPLAIN SELECT * FROM t2 WHERE (key1a = 5 and key1b < 10 and key1b > 2) or +(key1a = 4 and key1b < 7 and key1b > 3); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range PRIMARY,i1b PRIMARY 8 NULL 2 Using index condition + +SELECT * FROM information_schema.OPTIMIZER_TRACE; +QUERY TRACE MISSING_BYTES_BEYOND_MAX_MEM_SIZE +EXPLAIN SELECT * FROM t2 WHERE (key1a = 5 and key1b < 10 and key1b > 2) or +(key1a = 4 and key1b < 7 and key1b > 3) { + "steps": [ + { + "join_preparation": { + "select#": 1, + "steps": [ + { + "expanded_query": "/* select#1 */ select `test`.`t2`.`key1a` AS `key1a`,`test`.`t2`.`key1b` AS `key1b`,`test`.`t2`.`key2` AS `key2`,`test`.`t2`.`key2_1` AS `key2_1`,`test`.`t2`.`key2_2` AS `key2_2`,`test`.`t2`.`key3` AS `key3` from `test`.`t2` where (((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))" + } + ] /* steps */ + } /* join_preparation */ + }, + { + "join_optimization": { + "select#": 1, + "steps": [ + { + "condition_processing": { + "condition": "WHERE", + "original_condition": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))", + "steps": [ + { + "transformation": "equality_propagation", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + }, + { + "transformation": "constant_propagation", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + }, + { + "transformation": "trivial_condition_removal", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + } + ] /* steps */ + } /* condition_processing */ + }, + { + "ref_optimizer_key_uses": [ + ] /* ref_optimizer_key_uses */ + }, + { + "records_estimation": [ + { + "database": "test", + "table": "t2", + "range_analysis": { + "table_scan": { + "records": 1024, + "cost": 215.15 + } /* table_scan */, + "potential_range_indices": [ + { + "index": "PRIMARY", + "usable": true, + "key_parts": [ + "key1a", + "key1b" + ] /* key_parts */ + }, + { + "index": "i1b", + "usable": true, + "key_parts": [ + "key1b", + "key1a" + ] /* key_parts */ + }, + { + "index": "i2_1", + "usable": false, + "cause": "not_applicable" + }, + { + "index": "i2_2", + "usable": false, + "cause": "not_applicable" + } + ] /* potential_range_indices */, + "setup_range_conditions": [ + ] /* setup_range_conditions */, + "group_index_range": { + "chosen": false, + "cause": "not_group_by_or_distinct" + } /* group_index_range */, + "analyzing_range_alternatives": { + "range_scan_alternatives": [ + { + "index": "PRIMARY", + "ranges": [ + "4 <= key1a <= 4 AND 3 < key1b < 7", + "5 <= key1a <= 5 AND 2 < key1b < 10" + ] /* ranges */, + "index_only": false, + "records": 2, + "cost": 4.41, + "rowid_ordered": false, + "chosen": true + }, + { + "index": "i1b", + "ranges": [ + "2 < key1b <= 3 AND 5 <= key1a <= 5", + "3 < key1b < 7", + "7 <= key1b < 10 AND 5 <= key1a <= 5" + ] /* ranges */, + "index_only": false, + "records": 6, + "cost": 10.21, + "rowid_ordered": false, + "chosen": false, + "cause": "cost" + } + ] /* range_scan_alternatives */, + "analyzing_roworder_intersect": { + "usable": false, + "cause": "too_few_roworder_scans" + } /* analyzing_roworder_intersect */ + } /* analyzing_range_alternatives */, + "chosen_range_access_summary": { + "range_access_plan": { + "type": "range_scan", + "index": "PRIMARY", + "records": 2, + "ranges": [ + "4 <= key1a <= 4 AND 3 < key1b < 7", + "5 <= key1a <= 5 AND 2 < key1b < 10" + ] /* ranges */ + } /* range_access_plan */, + "records_for_plan": 2, + "cost_for_plan": 4.41, + "chosen": true + } /* chosen_range_access_summary */ + } /* range_analysis */ + } + ] /* records_estimation */ + }, + { + "considered_execution_plans": [ + { + "database": "test", + "table": "t2", + "best_access_path": { + "considered_access_paths": [ + { + "access_type": "range", + "records": 2, + "cost": 4.41, + "chosen": true + } + ] /* considered_access_paths */ + } /* best_access_path */, + "cost_for_plan": 4.41, + "records_for_plan": 2, + "chosen": true + } + ] /* considered_execution_plans */ + }, + { + "attaching_conditions_to_tables": { + "original_condition": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))", + "attached_conditions_computation": [ + ] /* attached_conditions_computation */, + "attached_conditions_summary": [ + { + "database": "test", + "table": "t2", + "attached": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))" + } + ] /* attached_conditions_summary */ + } /* attaching_conditions_to_tables */ + }, + { + "refine_plan": [ + { + "database": "test", + "table": "t2", + "scan_type": "table" + } + ] /* refine_plan */ + } + ] /* steps */ + } /* join_optimization */ + }, + { + "join_execution": { + "select#": 1, + "steps": [ + ] /* steps */ + } /* join_execution */ + } + ] /* steps */ +} 0 + EXPLAIN SELECT * FROM t1 WHERE (key1 > 1 OR key2 > 2); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 ALL i1,i2 NULL NULL NULL 1024 Using where === modified file 'mysql-test/r/optimizer_trace_range_ps_prot.result' --- a/mysql-test/r/optimizer_trace_range_ps_prot.result 2011-03-01 10:55:27 +0000 +++ b/mysql-test/r/optimizer_trace_range_ps_prot.result 2011-03-21 09:01:05 +0000 @@ -1006,20 +1006,24 @@ EXPLAIN SELECT DISTINCT key2 FROM t2 { ] /* steps */ } 0 -EXPLAIN SELECT key2, MIN(key2_1) FROM t2 where key2 < 5 GROUP BY key2; +EXPLAIN SELECT key2, MIN(key2_1) FROM t2 +WHERE key2 = 5 or key2 = 4 or key2 = 3 or key2 = 2 or key2 = 1 +GROUP BY key2; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t2 range i2_1,i2_2 i2_1 4 NULL 47 Using where; Using index SELECT * FROM information_schema.OPTIMIZER_TRACE; QUERY TRACE MISSING_BYTES_BEYOND_MAX_MEM_SIZE -EXPLAIN SELECT key2, MIN(key2_1) FROM t2 where key2 < 5 GROUP BY key2 { +EXPLAIN SELECT key2, MIN(key2_1) FROM t2 +WHERE key2 = 5 or key2 = 4 or key2 = 3 or key2 = 2 or key2 = 1 +GROUP BY key2 { "steps": [ { "join_preparation": { "select#": 1, "steps": [ { - "expanded_query": "/* select#1 */ select `test`.`t2`.`key2` AS `key2`,min(`test`.`t2`.`key2_1`) AS `MIN(key2_1)` from `test`.`t2` where (`test`.`t2`.`key2` < 5) group by `test`.`t2`.`key2`" + "expanded_query": "/* select#1 */ select `test`.`t2`.`key2` AS `key2`,min(`test`.`t2`.`key2_1`) AS `MIN(key2_1)` from `test`.`t2` where ((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1)) group by `test`.`t2`.`key2`" } ] /* steps */ } /* join_preparation */ @@ -1031,19 +1035,19 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "condition_processing": { "condition": "WHERE", - "original_condition": "(`test`.`t2`.`key2` < 5)", + "original_condition": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))", "steps": [ { "transformation": "equality_propagation", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" }, { "transformation": "constant_propagation", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" }, { "transformation": "trivial_condition_removal", - "resulting_condition": "(`test`.`t2`.`key2` < 5)" + "resulting_condition": "(multiple equal(5, `test`.`t2`.`key2`) or multiple equal(4, `test`.`t2`.`key2`) or multiple equal(3, `test`.`t2`.`key2`) or multiple equal(2, `test`.`t2`.`key2`) or multiple equal(1, `test`.`t2`.`key2`))" } ] /* steps */ } /* condition_processing */ @@ -1114,7 +1118,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_1", "covering": true, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "records": 5, "cost": 31 @@ -1123,7 +1131,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_2", "covering": true, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "records": 5, "cost": 31 @@ -1143,7 +1155,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "key2" ] /* key_parts_used_for_access */, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "chosen": true } /* best_group_range_summary */, @@ -1152,7 +1168,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "index": "i2_1", "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "index_only": true, "records": 47, @@ -1163,7 +1183,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 { "index": "i2_2", "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */, "index_only": true, "records": 47, @@ -1184,7 +1208,11 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 "index": "i2_1", "records": 47, "ranges": [ - "key2 < 5" + "1 <= key2 <= 1", + "2 <= key2 <= 2", + "3 <= key2 <= 3", + "4 <= key2 <= 4", + "5 <= key2 <= 5" ] /* ranges */ } /* range_access_plan */, "records_for_plan": 47, @@ -1219,14 +1247,14 @@ EXPLAIN SELECT key2, MIN(key2_1) FROM t2 }, { "attaching_conditions_to_tables": { - "original_condition": "(`test`.`t2`.`key2` < 5)", + "original_condition": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))", "attached_conditions_computation": [ ] /* attached_conditions_computation */, "attached_conditions_summary": [ { "database": "test", "table": "t2", - "attached": "(`test`.`t2`.`key2` < 5)" + "attached": "((`test`.`t2`.`key2` = 5) or (`test`.`t2`.`key2` = 4) or (`test`.`t2`.`key2` = 3) or (`test`.`t2`.`key2` = 2) or (`test`.`t2`.`key2` = 1))" } ] /* attached_conditions_summary */ } /* attaching_conditions_to_tables */ @@ -2111,6 +2139,207 @@ EXPLAIN SELECT * FROM t2 WHERE key1a = 5 ] /* steps */ } 0 +EXPLAIN SELECT * FROM t2 WHERE (key1a = 5 and key1b < 10 and key1b > 2) or +(key1a = 4 and key1b < 7 and key1b > 3); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range PRIMARY,i1b PRIMARY 8 NULL 2 Using index condition + +SELECT * FROM information_schema.OPTIMIZER_TRACE; +QUERY TRACE MISSING_BYTES_BEYOND_MAX_MEM_SIZE +EXPLAIN SELECT * FROM t2 WHERE (key1a = 5 and key1b < 10 and key1b > 2) or +(key1a = 4 and key1b < 7 and key1b > 3) { + "steps": [ + { + "join_preparation": { + "select#": 1, + "steps": [ + { + "expanded_query": "/* select#1 */ select `test`.`t2`.`key1a` AS `key1a`,`test`.`t2`.`key1b` AS `key1b`,`test`.`t2`.`key2` AS `key2`,`test`.`t2`.`key2_1` AS `key2_1`,`test`.`t2`.`key2_2` AS `key2_2`,`test`.`t2`.`key3` AS `key3` from `test`.`t2` where (((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))" + } + ] /* steps */ + } /* join_preparation */ + }, + { + "join_optimization": { + "select#": 1, + "steps": [ + { + "condition_processing": { + "condition": "WHERE", + "original_condition": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))", + "steps": [ + { + "transformation": "equality_propagation", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + }, + { + "transformation": "constant_propagation", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + }, + { + "transformation": "trivial_condition_removal", + "resulting_condition": "(((`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2) and multiple equal(5, `test`.`t2`.`key1a`)) or ((`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3) and multiple equal(4, `test`.`t2`.`key1a`)))" + } + ] /* steps */ + } /* condition_processing */ + }, + { + "ref_optimizer_key_uses": [ + ] /* ref_optimizer_key_uses */ + }, + { + "records_estimation": [ + { + "database": "test", + "table": "t2", + "range_analysis": { + "table_scan": { + "records": 1024, + "cost": 215.15 + } /* table_scan */, + "potential_range_indices": [ + { + "index": "PRIMARY", + "usable": true, + "key_parts": [ + "key1a", + "key1b" + ] /* key_parts */ + }, + { + "index": "i1b", + "usable": true, + "key_parts": [ + "key1b", + "key1a" + ] /* key_parts */ + }, + { + "index": "i2_1", + "usable": false, + "cause": "not_applicable" + }, + { + "index": "i2_2", + "usable": false, + "cause": "not_applicable" + } + ] /* potential_range_indices */, + "setup_range_conditions": [ + ] /* setup_range_conditions */, + "group_index_range": { + "chosen": false, + "cause": "not_group_by_or_distinct" + } /* group_index_range */, + "analyzing_range_alternatives": { + "range_scan_alternatives": [ + { + "index": "PRIMARY", + "ranges": [ + "4 <= key1a <= 4 AND 3 < key1b < 7", + "5 <= key1a <= 5 AND 2 < key1b < 10" + ] /* ranges */, + "index_only": false, + "records": 2, + "cost": 4.41, + "rowid_ordered": false, + "chosen": true + }, + { + "index": "i1b", + "ranges": [ + "2 < key1b <= 3 AND 5 <= key1a <= 5", + "3 < key1b < 7", + "7 <= key1b < 10 AND 5 <= key1a <= 5" + ] /* ranges */, + "index_only": false, + "records": 6, + "cost": 10.21, + "rowid_ordered": false, + "chosen": false, + "cause": "cost" + } + ] /* range_scan_alternatives */, + "analyzing_roworder_intersect": { + "usable": false, + "cause": "too_few_roworder_scans" + } /* analyzing_roworder_intersect */ + } /* analyzing_range_alternatives */, + "chosen_range_access_summary": { + "range_access_plan": { + "type": "range_scan", + "index": "PRIMARY", + "records": 2, + "ranges": [ + "4 <= key1a <= 4 AND 3 < key1b < 7", + "5 <= key1a <= 5 AND 2 < key1b < 10" + ] /* ranges */ + } /* range_access_plan */, + "records_for_plan": 2, + "cost_for_plan": 4.41, + "chosen": true + } /* chosen_range_access_summary */ + } /* range_analysis */ + } + ] /* records_estimation */ + }, + { + "considered_execution_plans": [ + { + "database": "test", + "table": "t2", + "best_access_path": { + "considered_access_paths": [ + { + "access_type": "range", + "records": 2, + "cost": 4.41, + "chosen": true + } + ] /* considered_access_paths */ + } /* best_access_path */, + "cost_for_plan": 4.41, + "records_for_plan": 2, + "chosen": true + } + ] /* considered_execution_plans */ + }, + { + "attaching_conditions_to_tables": { + "original_condition": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))", + "attached_conditions_computation": [ + ] /* attached_conditions_computation */, + "attached_conditions_summary": [ + { + "database": "test", + "table": "t2", + "attached": "(((`test`.`t2`.`key1a` = 5) and (`test`.`t2`.`key1b` < 10) and (`test`.`t2`.`key1b` > 2)) or ((`test`.`t2`.`key1a` = 4) and (`test`.`t2`.`key1b` < 7) and (`test`.`t2`.`key1b` > 3)))" + } + ] /* attached_conditions_summary */ + } /* attaching_conditions_to_tables */ + }, + { + "refine_plan": [ + { + "database": "test", + "table": "t2", + "scan_type": "table" + } + ] /* refine_plan */ + } + ] /* steps */ + } /* join_optimization */ + }, + { + "join_execution": { + "select#": 1, + "steps": [ + ] /* steps */ + } /* join_execution */ + } + ] /* steps */ +} 0 + EXPLAIN SELECT * FROM t1 WHERE (key1 > 1 OR key2 > 2); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 ALL i1,i2 NULL NULL NULL 1024 Using where === modified file 'sql/opt_range.cc' --- a/sql/opt_range.cc 2011-03-17 15:49:17 +0000 +++ b/sql/opt_range.cc 2011-03-21 09:01:05 +0000 @@ -177,16 +177,45 @@ class RANGE_OPT_PARAM; The entire graph is partitioned into "interval lists". - An interval list is a sequence of ordered disjoint intervals over the same - key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally, - all intervals in the list form an RB-tree, linked via left/right/parent - pointers. The RB-tree root SEL_ARG object will be further called "root of the - interval list". - + An interval list is a sequence of ordered disjoint intervals over + the same key part. SEL_ARG are linked via "next" and "prev" pointers + with NULL as sentinel. + In the example pic, there are 4 interval lists: "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13". The vertical lines represent SEL_ARG::next/prev pointers. + Additionally, all intervals in the list form a red-black (RB) tree, + linked via left/right/parent pointers with null_element as sentinel. The + red-black tree root SEL_ARG object will be further called "root of the + interval list". + + A red-black tree with 7 SEL_ARGs will look similar to what is shown + below. Left/right/parent pointers are shown while next pointers go from a + node with number X to the node with number X+1 (and prev in the + opposite direction): + + Root + +---+ + | 4 | + +---+ + left/ \ right + __/ \__ + / \ + +---+ +---+ + | 2 | | 6 | + +---+ +---+ + left / \ right left / \ right + | | | | + +---+ +---+ +---+ +---+ + | 1 | | 3 | | 5 | | 7 | + +---+ +---+ +---+ +---+ + + In this tree, + * node0->prev == node7->next == NULL + * node1->left == node1->right == + node3->left == ... node7->right == &null_element + In an interval list, each member X may have SEL_ARG::next_key_part pointer pointing to the root of another interval list Y. The pointed interval list must cover a key part with greater number (i.e. Y->part > X->part). @@ -204,6 +233,17 @@ class RANGE_OPT_PARAM; (kp1=2 AND (kp3=11 OR kp3=14)) OR (kp1=3 AND (kp3=11 OR kp3=14)) + In red-black tree form: + + +------------------------------+ + | kp1=2 AND (kp3=11 OR kp3=14) | + +------------------------------+ + / \ + / \ + +------------------------+ +--------------------+ + | kp1 < 1 AND kp2=5 AND | | kp1=3 AND | + | (kp3=10 OR kp3=12) | | (kp3=11 OR kp3=14) | + +------------------------+ +--------------------+ 3. SEL_ARG GRAPH USE @@ -1976,7 +2016,11 @@ public: class TRP_RANGE : public TABLE_READ_PLAN { public: - SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */ + /** + Root of red-black tree for intervals over key fields to be used in + "range" method retrieval. See SEL_ARG graph description. + */ + SEL_ARG *key; uint key_idx; /* key number in PARAM::key and PARAM::real_keynr*/ uint mrr_flags; uint mrr_buf_size; @@ -2018,13 +2062,17 @@ void TRP_RANGE::trace_basic_info(const P add_utf8("index", cur_key.name).add("records", records); Opt_trace_array trace_range(param->thd->opt_trace, "ranges"); - for (const SEL_ARG *current= key; - current; - current= current->next) + + const SEL_ARG *current_range= key; + // navigate from root to first interval in the interval tree + while (current_range->left && current_range->left != &null_element) + current_range= current_range->left; + + while (current_range) { String range_info; range_info.set_charset(system_charset_info); - for (const SEL_ARG *part= current; + for (const SEL_ARG *part= current_range; part; part= part->next_key_part) { @@ -2034,6 +2082,7 @@ void TRP_RANGE::trace_basic_info(const P part->min_flag | part->max_flag); } trace_range.add_utf8(range_info.ptr(), range_info.length()); + current_range= current_range->next; } #endif } @@ -2295,13 +2344,19 @@ void TRP_GROUP_MIN_MAX::trace_basic_info } } Opt_trace_array trace_range(param->thd->opt_trace, "ranges"); - for (const SEL_ARG *current= index_tree; - current; - current= current->next) + + + const SEL_ARG *current_range= index_tree; + // navigate from root to first interval in the interval tree + while (current_range && // can have group quick without ranges + current_range->left && current_range->left != &null_element) + current_range= current_range->left; + + while (current_range) { String range_info; range_info.set_charset(system_charset_info); - for (const SEL_ARG *part= current; + for (const SEL_ARG *part= current_range; part; part= part->next_key_part) { @@ -2311,6 +2366,7 @@ void TRP_GROUP_MIN_MAX::trace_basic_info part->min_flag | part->max_flag); } trace_range.add_utf8(range_info.ptr(), range_info.length()); + current_range= current_range->next; } #endif } @@ -8081,8 +8137,9 @@ uint sel_arg_range_seq_next(range_seq_t /* Ok, we're at some "full tuple" position in the tree */ /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->next) { + DBUG_ASSERT(key_tree->next != &null_element); //step down; (update the tuple, we'll step right and stay there) seq->i--; step_down_to(active_trace_ptr, seq, key_tree->next); @@ -8102,8 +8159,9 @@ uint sel_arg_range_seq_next(range_seq_t key_tree= seq->stack[seq->i].key_tree; /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->next) { + DBUG_ASSERT(key_tree->next != &null_element); // Step down; update the tuple seq->i--; step_down_to(active_trace_ptr, seq, key_tree->next); @@ -8170,8 +8228,9 @@ walk_right_n_up: key_tree= key_tree->next_key_part; walk_up_n_right: - while (key_tree->prev && key_tree->prev != &null_element) + while (key_tree->prev) { + DBUG_ASSERT(key_tree->prev != &null_element); /* Step up */ key_tree= key_tree->prev; } No bundle (reason: useless for push emails).