List:Commits« Previous MessageNext Message »
From:Ole John Aske Date:December 3 2010 2:45pm
Subject:bzr commit into mysql-5.1 branch (ole.john.aske:3477) Bug#57030
View as plain text  
#At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-5.1/ based on revid:georgi.kodinov@stripped

 3477 Ole John Aske	2010-12-03
      Alternative fix for bug#57030: 'BETWEEN' evaluation is incorrect
      
      This is a more extensive, but IMHO a more correct fix for handling BETWEEN optimization.
      It introduce some refactoring where a BETWEEN condition is rewritten 
      to a 'GE AND LE' condition inside add_key_fields() and optimized as such.
      
      The special condition 'field' BETWEEN <c1> and <c1> is still detected and rewritten
      to 'field' EQ <c1>. 
      
      ALternative (shorter and more hacky) fix is at: http://lists.mysql.com/commits/125940
      
      ..................
      
      Root cause for this bug is that the optimizer try to detect & optimize the special case:
        '<field> BETWEEN c1 AND c1' and handle this as the condition '<field> = c1'
      
      This was implemented inside add_key_field(.. *field, *value[]...) which assumed
      field to refer key Field, and value[] to refer a [low...high] constant pair.
      value[0] and value[1] was then compared for equality.
      
      In a 'normal' BETWEEN condition of the form '<field> BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with 
      parameters field= <field>, *value=val1.
      
      However, if the BETWEEN predicate specified:
      
      1)  '<const1> BETWEEN <const2> AND <field> 
      
      the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented
      by trying the cheat add_key_field() to handle it like:
      
      2) '<const1> GE <const2> AND <const1> LE <field>'
      
      As we didn't really replace the BETWEEN operation with 'ge' and 'le', 
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped) 
      arguments <const1> and <const2> for equality. If they was equal, the 
      condition 1) was incorrectly 'optimized' to:
      
      3) '<field> EQ <const1>'
      
      This fix replace the BETWEEN with a 'GE AND LE' pair and let add_key_field() extract
      any key equalities / ranges from from this transformed condition.

    modified:
      mysql-test/r/range.result
      mysql-test/t/range.test
      sql/sql_select.cc
=== modified file 'mysql-test/r/range.result'
--- a/mysql-test/r/range.result	2010-08-24 15:51:32 +0000
+++ b/mysql-test/r/range.result	2010-12-03 14:45:55 +0000
@@ -1666,4 +1666,91 @@ c_key	c_notkey
 1	1
 3	3
 DROP TABLE t1;
+#
+# Bug #57030: 'BETWEEN' evaluation is incorrect
+#
+CREATE TABLE t1(pk INT PRIMARY KEY, i4 INT);
+CREATE UNIQUE INDEX i4_uq ON t1(i4);
+INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	const	i4_uq	i4_uq	5	const	1	
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10;
+pk	i4
+1	10
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	i4_uq	i4_uq	5	NULL	1	Using where
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4;
+pk	i4
+1	10
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	i4_uq	i4_uq	5	NULL	3	Using where
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4;
+pk	i4
+1	10
+2	20
+3	30
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	i4_uq	i4_uq	5	NULL	1	Using where
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10;
+pk	i4
+1	10
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10;
+pk	i4
+1	10
+2	20
+3	30
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11;
+pk	i4
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0;
+pk	i4
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0;
+pk	i4
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	i4_uq	i4_uq	5	NULL	2	Using where
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999;
+pk	i4
+1	10
+2	20
+3	30
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30;
+pk	i4
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	i4_uq	i4_uq	5	NULL	1	Using where
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20';
+pk	i4
+1	10
+2	20
+DROP TABLE t1;
 End of 5.1 tests

=== modified file 'mysql-test/t/range.test'
--- a/mysql-test/t/range.test	2010-08-24 15:51:32 +0000
+++ b/mysql-test/t/range.test	2010-12-03 14:45:55 +0000
@@ -1325,4 +1325,63 @@ SELECT * FROM t1 WHERE 2 NOT BETWEEN c_n
 
 DROP TABLE t1;
 
+--echo #
+--echo # Bug #57030: 'BETWEEN' evaluation is incorrect
+--echo #
+
+# Test some BETWEEN predicates which does *not* follow the
+# 'normal' pattern of <field> BETWEEN <low const> AND <high const>
+
+CREATE TABLE t1(pk INT PRIMARY KEY, i4 INT);
+CREATE UNIQUE INDEX i4_uq ON t1(i4);
+
+INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
+
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10;
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4;
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4;
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10;
+SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10;
+SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11;
+SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11;
+
+EXPLAIN
+SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0;
+SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0;
+
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0;
+SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0;
+
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999;
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999;
+
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30;
+SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30;
+
+EXPLAIN
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20';
+SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20';
+
+
+DROP TABLE t1;
+
 --echo End of 5.1 tests

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-10-29 08:23:06 +0000
+++ b/sql/sql_select.cc	2010-12-03 14:45:55 +0000
@@ -3348,26 +3348,7 @@ add_key_field(KEY_FIELD **key_fields,uin
         eq_func is NEVER true when num_values > 1
        */
       if (!eq_func)
-      {
-        /* 
-          Additional optimization: if we're processing
-          "t.key BETWEEN c1 AND c1" then proceed as if we were processing
-          "t.key = c1".
-          TODO: This is a very limited fix. A more generic fix is possible. 
-          There are 2 options:
-          A) Make equality propagation code be able to handle BETWEEN
-             (including cases like t1.key BETWEEN t2.key AND t3.key)
-          B) Make range optimizer to infer additional "t.key = c" equalities
-             and use them in equality propagation process (see details in
-             OptimizerKBAndTodo)
-        */
-        if ((cond->functype() != Item_func::BETWEEN) ||
-            ((Item_func_between*) cond)->negated ||
-            !value[0]->eq(value[1], field->binary()))
-          return;
-        eq_func= TRUE;
-      }
-
+        return;
       if (field->result_type() == STRING_RESULT)
       {
         if ((*value)->result_type() != STRING_RESULT)
@@ -3563,9 +3544,49 @@ add_key_fields(JOIN *join, KEY_FIELD **k
   case Item_func::OPTIMIZE_KEY:
   {
     Item **values;
-    // BETWEEN, IN, NE
-    if (is_local_field (cond_func->key_item()) &&
-	!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
+    /*
+     'a BETWEEN low AND high' is transformed to 
+     'a >= low AND a <= high' before further key optimization:
+    */
+    if (cond_func->functype() == Item_func::BETWEEN)
+    {
+      values= cond_func->arguments();
+      /*
+       Additional optimization: If 'low = high', transform to
+       "t.key = low".
+      */
+      if (!((Item_func_between*)cond_func)->negated &&
+          values[0]->real_item()->type() == Item::FIELD_ITEM &&
+          values[1]->const_item() &&
+          values[1]->eq(values[2], ((Item_field*)values[0]->real_item())->field->binary()))
+      {
+        Item_bool_func *eq= new Item_equal(values[1],((Item_field*)values[0]->real_item()));
+        if (eq)
+        {
+          add_key_fields(join, key_fields, and_level, eq, usable_tables,
+                         sargables);
+        }
+      }
+      else
+      {
+        Item_bool_func2 *ge= new Item_func_ge(values[0],values[1]);
+        if (ge)
+        {
+          add_key_fields(join, key_fields, and_level, ge, usable_tables,
+                         sargables);
+        }
+        Item_bool_func2 *le= new Item_func_le(values[0],values[2]);
+        if (le)
+        {
+          add_key_fields(join, key_fields, and_level, le, usable_tables,
+                         sargables);
+        }
+      }
+    }
+
+    // IN, NE
+    else if (is_local_field (cond_func->key_item()) &&
+            !(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
     {
       values= cond_func->arguments()+1;
       if (cond_func->functype() == Item_func::NE_FUNC &&
@@ -3579,21 +3600,6 @@ add_key_fields(JOIN *join, KEY_FIELD **k
                            cond_func->argument_count()-1,
                            usable_tables, sargables);
     }
-    if (cond_func->functype() == Item_func::BETWEEN)
-    {
-      values= cond_func->arguments();
-      for (uint i= 1 ; i < cond_func->argument_count() ; i++)
-      {
-        Item_field *field_item;
-        if (is_local_field (cond_func->arguments()[i]))
-        {
-          field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
-          add_key_equal_fields(key_fields, *and_level, cond_func,
-                               field_item, 0, values, 1, usable_tables, 
-                               sargables);
-        }
-      }  
-    }
     break;
   }
   case Item_func::OPTIMIZE_OP:


Attachment: [text/bzr-bundle] bzr/ole.john.aske@oracle.com-20101203144555-zbvxbceg9ack7k9y.bundle
Thread
bzr commit into mysql-5.1 branch (ole.john.aske:3477) Bug#57030Ole John Aske3 Dec
  • Re: bzr commit into mysql-5.1 branch (ole.john.aske:3477) Bug#57030Evgeny Potemkin19 Dec