List:Commits« Previous MessageNext Message »
From:Jorgen Loland Date:March 21 2011 9:01am
Subject:bzr commit into mysql-trunk branch (jorgen.loland:3281)
View as plain text  
#At file:///export/home/jl208045/mysql/wl4800/mysql-next-mr-opt-backporting-wl4800/ based on revid:guilhem.bichot@stripped

 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
=== 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;
     }


Attachment: [text/bzr-bundle] bzr/jorgen.loland@oracle.com-20110321090105-ou67r5inm3bt4jc1.bundle
Thread
bzr commit into mysql-trunk branch (jorgen.loland:3281) Jorgen Loland21 Mar
  • Re: bzr commit into mysql-trunk branch (jorgen.loland:3281)Guilhem Bichot21 Mar
    • Re: bzr commit into mysql-trunk branch (jorgen.loland:3281)Jorgen Loland24 Mar