List:Commits« Previous MessageNext Message »
From:Evgeny Potemkin Date:December 21 2010 12:30pm
Subject:Re: bzr commit into mysql-5.1 branch (ole.john.aske:3529) Bug#57030
View as plain text  
Hi Ole,

Ok to push with a small correction (see below).

Regards, Evgen.

On 12/21/10 13:26, Ole John Aske wrote:
> #At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-5.1/ based on
> revid:georgi.kodinov@stripped
>
>   3529 Ole John Aske	2010-12-21
>        Updated fix after review for bug#57030 'BETWEEN' evaluation is incorrect'
>
>        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 to 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 moves this optimization of '<field>   BETWEEN c1 AND c1' into
>        add_key_fields() which then calls add_key_equal_fields() to collect
>        key equality / comparison for the key fields in the BETWEEN condition.
>
>        Compared to first commit, a few new testcases has also been added as
>        suggested by Evgeny Potemkin.
>
>      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-21 10:26:56 +0000
> @@ -1666,4 +1666,105 @@ 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	const	i4_uq	i4_uq	5	const	1	
> +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
> +EXPLAIN
> +SELECT * FROM t1, t1 as t2 WHERE t2.pk BETWEEN t1.i4 AND t1.i4;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t1	ALL	i4_uq	NULL	NULL	NULL	3	
> +1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.i4	1	Using where
> +SELECT * FROM t1, t1 as t2 WHERE t2.pk BETWEEN t1.i4 AND t1.i4;
> +pk	i4	pk	i4
> +EXPLAIN
> +SELECT * FROM t1, t1 as t2 WHERE t1.i4 BETWEEN t2.pk AND t2.pk;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t1	ALL	i4_uq	NULL	NULL	NULL	3	
> +1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.i4	1	Using where
> +SELECT * FROM t1, t1 as t2 WHERE t1.i4 BETWEEN t2.pk AND t2.pk;
> +pk	i4	pk	i4
> +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-21 10:26:56 +0000
> @@ -1325,4 +1325,71 @@ 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';
> +
> +#Should detect the EQ_REF 't2.pk=t1.i4'
> +EXPLAIN
> +SELECT * FROM t1, t1 as t2 WHERE t2.pk BETWEEN t1.i4 AND t1.i4;
> +SELECT * FROM t1, t1 as t2 WHERE t2.pk BETWEEN t1.i4 AND t1.i4;
> +
> +EXPLAIN
> +SELECT * FROM t1, t1 as t2 WHERE t1.i4 BETWEEN t2.pk AND t2.pk;
> +SELECT * FROM t1, t1 as t2 WHERE t1.i4 BETWEEN t2.pk AND t2.pk;
> +
> +DROP TABLE t1;
> +
>   --echo End of 5.1 tests
>
> === modified file 'sql/sql_select.cc'
> --- a/sql/sql_select.cc	2010-12-16 14:40:52 +0000
> +++ b/sql/sql_select.cc	2010-12-21 10:26:56 +0000
> @@ -3349,26 +3349,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)
> @@ -3564,9 +3545,65 @@ 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))
> +    /*
> +      Build list of possible keys for 'a BETWEEN low AND high'.
> +      It is handled similar to the equivalent condition
> +      'a>= low AND a<= high':
> +    */
> +    if (cond_func->functype() == Item_func::BETWEEN)
> +    {
> +      Item_field *field_item;
> +      bool equal_func= FALSE;
> +      uint num_values= 2;
> +      values= cond_func->arguments();
> +
> +      bool binary_cmp= (values[0]->real_item()->type() == Item::FIELD_ITEM)
> +            ? ((Item_field*)values[0]->real_item())->field->binary()
> +            : TRUE;
> +
> +      /*
> +        Additional optimization: If 'low = high':
> +        Handle as if the condition was "t.key = low".
> +      */
> +      if (!((Item_func_between*)cond_func)->negated&&
> +          values[1]->eq(values[2], binary_cmp))
> +      {
> +        equal_func= TRUE;
> +        num_values= 1;
> +      }
> +
> +      /*
> +        Append keys for 'field<cmp>  value[]' if the
> +        condition is of the form::
> +        '<field>  BETWEEN value[1] AND value[2]'
> +      */
> +      if (is_local_field (values[0]))
> +      {
> +        field_item= (Item_field *) (values[0]->real_item());
> +        add_key_equal_fields(key_fields, *and_level, cond_func,
> +                             field_item, equal_func,&values[1],
> +                             num_values, usable_tables, sargables);
> +      }
> +      /*
> +        Append keys for 'value[0]<cmp>  field' if the
> +        condition is of the form:
> +        'value[0] BETWEEN field1 AND field2'
> +      */
> +      for (uint i= 1; i<= num_values; i++)
> +      {
> +        if (is_local_field (values[i]))
> +        {
> +          field_item= (Item_field *) (values[i]->real_item());
> +          add_key_equal_fields(key_fields, *and_level, cond_func,
> +                               field_item, equal_func,&values[0],
You could pass just "values" instead of "&values[0]"
> +                               1, usable_tables, sargables);
> +        }
> +      }
> +    } // if ( ... Item_func::BETWEEN)
> +
> +    // 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&&
> @@ -3580,21 +3617,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:
>
>
>
>

Thread
bzr commit into mysql-5.1 branch (ole.john.aske:3529) Bug#57030Ole John Aske21 Dec
  • Re: bzr commit into mysql-5.1 branch (ole.john.aske:3529) Bug#57030Evgeny Potemkin21 Dec