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).
| Thread |
|---|
| • bzr push into mysql-trunk branch (jorgen.loland:3280 to 3281) | Jorgen Loland | 21 Mar |
