[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (igor:2747)

29 Oct 2009

#At lp:maria based on revid:igor@askmonty.org-20091026173514-biry7lgxqiz2zz7a

 2747 Igor Babaev	2009-10-29
      Replaced a lame implementation of the function sel_trees_must_be_ored
      that blocked building index merge plans for the queries with where
      conditions of the form 
      (key1|2_p1=c AND range(key1_p2)) OR (key1|2_p1=c AND range(key2_p2)).
      
      The problem was discovered by Sergey Petrunia when he reviewed the patch
      for WL#24.
      
      Added new test cases. One of them failed to produce an index merge plan
      before the patch was applied.
modified:
  mysql-test/r/range_vs_index_merge.result
  mysql-test/r/range_vs_index_merge_innodb.result
  mysql-test/t/range_vs_index_merge.test
  sql/opt_range.cc

=== modified file 'mysql-test/r/range_vs_index_merge.result'

--- a/mysql-test/r/range_vs_index_merge.result	2009-10-17 18:40:46 +0000
+++ b/mysql-test/r/range_vs_index_merge.result	2009-10-29 18:49:58 +0000
@@ -1076,6 +1076,68 @@ ID BETWEEN 3500 AND 3800) AND Country='U
         AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300);
 ID	Name	Country	Population
 3798	Phoenix	USA	1321045
+DROP INDEX Population ON City;
+DROP INDEX Name ON City;
+EXPLAIN
+SELECT * FROM City
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,CountryPopulation,CountryName	CountryPopulation,CountryName	7,38	NULL	10	Using sort_union(CountryPopulation,CountryName); Using where
+SELECT * FROM City USE INDEX()
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+SELECT * FROM City
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+EXPLAIN
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,CountryPopulation,CountryName	CountryPopulation,CountryName	7,38	NULL	10	Using sort_union(CountryPopulation,CountryName); Using where
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
 DROP DATABASE world;
 use test;
 CREATE TABLE t1 (

=== modified file 'mysql-test/r/range_vs_index_merge_innodb.result'
--- a/mysql-test/r/range_vs_index_merge_innodb.result	2009-10-17 18:40:46 +0000
+++ b/mysql-test/r/range_vs_index_merge_innodb.result	2009-10-29 18:49:58 +0000
@@ -1077,6 +1077,68 @@ ID BETWEEN 3500 AND 3800) AND Country='U
         AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300);
 ID	Name	Country	Population
 3798	Phoenix	USA	1321045
+DROP INDEX Population ON City;
+DROP INDEX Name ON City;
+EXPLAIN
+SELECT * FROM City
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,CountryPopulation,CountryName	CountryPopulation,CountryName	7,38	NULL	8	Using sort_union(CountryPopulation,CountryName); Using where
+SELECT * FROM City USE INDEX()
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+SELECT * FROM City
+WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+Country='USA' AND Name LIKE 'Pa%';
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+EXPLAIN
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	City	index_merge	Country,CountryPopulation,CountryName	CountryPopulation,CountryName	7,38	NULL	8	Using sort_union(CountryPopulation,CountryName); Using where
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
+SELECT * FROM City
+WHERE Country='USA' AND 
+(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+ID	Name	Country	Population
+3932	Paterson	USA	149222
+3943	Pasadena	USA	141674
+3953	Pasadena	USA	133936
+3967	Paradise	USA	124682
+3986	Palmdale	USA	116670
+4030	Sandy	USA	101853
+4031	Athens-Clarke County	USA	101489
+4032	Cambridge	USA	101355
 DROP DATABASE world;
 use test;
 CREATE TABLE t1 (

=== modified file 'mysql-test/t/range_vs_index_merge.test'
--- a/mysql-test/t/range_vs_index_merge.test	2009-10-17 18:40:46 +0000
+++ b/mysql-test/t/range_vs_index_merge.test	2009-10-29 18:49:58 +0000
@@ -570,6 +570,51 @@ SELECT * FROM City
         AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300);
 
 
+DROP INDEX Population ON City;
+DROP INDEX Name ON City;
+
+# The pattern of the WHERE condition used in the following query is
+#   (key1|2_p1=c AND range(key1_p2)) OR (key1|2_p1=c AND range(key2_p2))
+# We get an index merge retrieval over key1, key2 for it
+
+EXPLAIN
+SELECT * FROM City
+  WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+        Country='USA' AND Name LIKE 'Pa%';
+
+# The following 2 queries check that the plans
+# for the previous plan is valid
+
+SELECT * FROM City USE INDEX()
+  WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+        Country='USA' AND Name LIKE 'Pa%';
+
+SELECT * FROM City
+  WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR
+        Country='USA' AND Name LIKE 'Pa%';
+
+
+# The pattern of the WHERE condition used in the following query is
+#   key1|2_p1=c AND (range(key1_p2) OR range(key2_p2))
+# We get an index merge retrieval over key1, key2 for it
+
+EXPLAIN
+SELECT * FROM City
+  WHERE Country='USA' AND 
+        (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+
+# The following 2 queries check that the plans
+# for the previous plan is valid
+
+SELECT * FROM City
+  WHERE Country='USA' AND 
+        (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+
+SELECT * FROM City
+  WHERE Country='USA' AND 
+        (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%');
+
+
 DROP DATABASE world;
 
 use test;

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2009-10-12 04:59:34 +0000
+++ b/sql/opt_range.cc	2009-10-29 18:49:58 +0000
@@ -262,6 +262,11 @@ public:
   uint8 part;					// Which key part
   uint8 maybe_null;
   /* 
+    The ordinal number the least significant component encountered the ranges
+    of the SEL_ARG tree (the first component has number 1) 
+  */
+  uint max_part_no; 
+  /* 
     Number of children of this element in the RB-tree, plus 1 for this
     element itself.
   */
@@ -737,12 +742,12 @@ public:
   uint real_keynr[MAX_KEY];
   /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
   uint alloced_sel_args; 
+  KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
 };
 
 class PARAM : public RANGE_OPT_PARAM
 {
 public:
-  KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
   ha_rows quick_rows[MAX_KEY];
   longlong baseflag;
   uint max_key_part, range_count;
@@ -2172,6 +2177,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_allo
   min_value=arg.min_value;
   max_value=arg.max_value;
   next_key_part=arg.next_key_part;
+  max_part_no= arg.max_part_no;
   use_count=1; elements=1;
 }
 
@@ -2189,7 +2195,7 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *m
   :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
    elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
    max_value((uchar*) max_value_arg), next(0),prev(0),
-   next_key_part(0),color(BLACK),type(KEY_RANGE)
+   next_key_part(0), color(BLACK), type(KEY_RANGE), max_part_no(1)
 {
   left=right= &null_element;
 }
@@ -2202,6 +2208,7 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 par
    field(field_), min_value(min_value_), max_value(max_value_),
    next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
 {
+  max_part_no= part+1;
   left=right= &null_element;
 }
 
@@ -2244,6 +2251,7 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM 
   increment_use_count(1);
   tmp->color= color;
   tmp->elements= this->elements;
+  tmp->max_part_no= max_part_no;
   return tmp;
 }
 
@@ -7000,14 +7008,14 @@ bool sel_trees_can_be_ored(RANGE_OPT_PAR
       ordable_keys       bitmap of SEL_ARG trees that can be ored
 
   DESCRIPTION
-    For two trees tree1 and tree2 and the bitmap ordable_keys containing
-    bits for indexes that have SEL_ARG trees in range parts of both trees
-    and these SEL_ARG trees can be ored the function checks if there are
-    indexes for which SEL_ARG trees must be ored. Two SEL_ARG trees for the
-    same index must be ored if all indexes for which SEL_SRG trees from the
-    range parts of tree1 anf tree2 that can be ored have the same field as 
-    their major index component. 
-
+    For two trees tree1 and tree2 the function checks whether they must be
+    ored. The function assumes that the bitmap ordable_keys contains bits for
+    those corresponding pairs of SEL_ARG trees from tree1 and tree2 that can
+    be ored.
+    We believe that tree1 and tree2 must be ored if any pair of SEL_ARG trees
+    r1 and r2, such that r1 is from tree1 and r2 is from tree2 and both
+    of them are marked in ordable_keys, can be merged.
+    
   NOTE
     The function sel_trees_must_be_ored as a rule is used in pair with the
     function sel_trees_can_be_ored.
@@ -7031,21 +7039,31 @@ bool sel_trees_must_be_ored(RANGE_OPT_PA
   if (!tmp.is_clear_all())
     DBUG_RETURN(FALSE);
 
-  Field *field= 0;
-  uint part;
-  int key_no;
-  key_map::Iterator it(oredable_keys);
-  while ((key_no= it++) != key_map::Iterator::BITMAP_END)
-  {
-    SEL_ARG *key1= tree1->keys[key_no];
-    if (!field)
+  int idx1, idx2;
+  key_map::Iterator it1(oredable_keys);
+  while ((idx1= it1++) != key_map::Iterator::BITMAP_END)
+  {
+    KEY_PART *key1_init= param->key[idx1]+tree1->keys[idx1]->part;
+    KEY_PART *key1_end= param->key[idx1]+tree1->keys[idx1]->max_part_no;
+    key_map::Iterator it2(oredable_keys);
+    while ((idx2= it2++) != key_map::Iterator::BITMAP_END)
     {
-      field= key1->field;
-      part= key1->part;
+      if (idx2 <= idx1)
+        continue;
+      
+      KEY_PART *key2_init= param->key[idx2]+tree2->keys[idx2]->part;
+      KEY_PART *key2_end= param->key[idx2]+tree2->keys[idx2]->max_part_no;
+      KEY_PART *part1, *part2;
+      for (part1= key1_init, part2= key2_init;
+           part1 < key1_end && part2 < key2_end;
+           part1++, part2++)
+      { 
+        if (!part1->field->eq(part2->field))
+          DBUG_RETURN(FALSE);
+      }
     }
-    else if (!field->eq(key1->field))
-      DBUG_RETURN(FALSE);
   }
+      
   DBUG_RETURN(TRUE);
 }  
 
@@ -7342,6 +7360,7 @@ and_all_keys(RANGE_OPT_PARAM *param, SEL
   if (!key1)
     return &null_element;			// Impossible ranges
   key1->use_count++;
+  key1->max_part_no= max(key2->max_part_no, key2->part+1);
   return key1;
 }
 
@@ -7441,6 +7460,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG 
   key1->use_count--;
   key2->use_count--;
   SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;
+  uint max_part_no= max(key1->max_part_no, key2->max_part_no);
 
   while (e1 && e2)
   {
@@ -7478,6 +7498,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG 
   key2->free_tree();
   if (!new_tree)
     return &null_element;			// Impossible range
+  new_tree->max_part_no= max_part_no;
   return new_tree;
 }
 
@@ -7557,6 +7578,8 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
   bool key2_shared=key2->use_count != 0;
   key1->maybe_flag|=key2->maybe_flag;
 
+  uint max_part_no= max(key1->max_part_no, key2->max_part_no);
+
   for (key2=key2->first(); key2; )
   {
     SEL_ARG *tmp=key1->find_range(key2);	// Find key1.min <= key2.min
@@ -7749,6 +7772,7 @@ end:
     key2=next;
   }
   key1->use_count++;
+  key1->max_part_no= max_part_no;
   return key1;
 }

    