From: Jorgen Loland
Date: April 29 2011 9:17am
Subject: Re: bzr commit into mysql-trunk branch (jorgen.loland:3341)
List-Archive: http://lists.mysql.com/commits/136378
Message-Id: <4DBA821A.1040102@oracle.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

Reviewer advice: review http://lists.mysql.com/commits/136356 together with this 
patch.

On 04/29/2011 11:13 AM, Jorgen Loland wrote:
> #At file:///export/home/jl208045/mysql/mysql-trunk-11765831/ based on revid:jorgen.loland@stripped
>
>   3341 Jorgen Loland	2011-04-29
>        BUG##11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
>                        AWAY QUALIFYING ROWS
>
>        The problem was that the ranges created when OR'ing two
>        conditions could be incorrect. Without the bugfix,
>        "I<>  6 OR (I<>  8 AND J = 5)" would create these ranges:
>
>        "NULL<  I<  6",
>        "6<= I<= 6 AND 5<= J<= 5",
>        "6<  I<  8",
>        "8<= I<= 8 AND 5<= J<= 5",
>        "8<  I"
>
>        While the correct ranges is
>        "NULL<  I<  6",
>        "6<= I<= 6 AND 5<= J<= 5",
>        "6<  I"
>
>        The problem occurs when key_or() ORs
>        (1) "NULL<  I<  6, 6<= I<= 6 AND 5<= J<= 5, 6<  I" with
>        (2) "8<  I AND 5<= J<= 5"
>
>        The reason for the bug is that in key_or(), SEL_ARG *tmp is
>        used to point to the range in (1) above that is merged with
>        (2) while key1 points to the root of the red-black tree of
>        (1). When merging (1) and (2), tmp refers to the "6<  I"
>        part whereas the root is the "6<= ... AND 5<= J<= 5" part.
>
>        key_or() decides that the tmp range needs to be split into
>        "6<  I<  8, 8<= I<= 8, 8<  I", in which next_key_part of the
>        second range should be that of tmp. However, next_key_part is
>        set to key1->next_key_part ("5<= J<= 5") instead of
>        tmp->next_key_part (empty). Fixing this gives the correct but
>        not optimal ranges:
>        "NULL<  I<  6",
>        "6<= I<= 6 AND 5<= J<= 5",
>        "6<  I<  8",
>        "8<= I<= 8",
>        "8<  I"
>
>
>        A second problem can be seen above: key_or() may create
>        adjacent ranges that could be replaced with a single range.
>        Fixes for this is also included in the patch so that the range
>        above becomes correct AND optimal:
>        "NULL<  I<  6",
>        "6<= I<= 6 AND 5<= J<= 5",
>        "6<  I"
>
>        Merging adjacent ranges like this gives a slightly lower cost
>        estimate for the range access.
>       @ mysql-test/include/range.inc
>          Add test for BUG##11765831
>       @ mysql-test/r/group_min_max.result
>          BUG##11765831 merges adjacent ranges, resulting in a slightly
>          lower cost estimate for accessing the table through range access.
>       @ mysql-test/r/range_icp.result
>          Add test for BUG##11765831
>       @ mysql-test/r/range_icp_mrr.result
>          Add test for BUG##11765831
>       @ mysql-test/r/range_mrr.result
>          Add test for BUG##11765831
>       @ mysql-test/r/range_mrr_cost.result
>          Add test for BUG##11765831
>       @ mysql-test/r/range_none.result
>          Add test for BUG##11765831
>       @ sql/opt_range.cc
>          In key_or(): When a range in key1 was split due to a
>          partially overlapping range in key2, the non-overlaping part
>          incorrectly got next_key_part from the R-B tree root node instead
>          of the currently active range. key_or() could also create
>          adjacent ranges that could be replaced by a single continous
>          range. This is also fixed.
>
>      modified:
>        mysql-test/include/range.inc
>        mysql-test/r/group_min_max.result
>        mysql-test/r/range_icp.result
>        mysql-test/r/range_icp_mrr.result
>        mysql-test/r/range_mrr.result
>        mysql-test/r/range_mrr_cost.result
>        mysql-test/r/range_none.result
>        sql/opt_range.cc
> === modified file 'mysql-test/include/range.inc'
> --- a/mysql-test/include/range.inc	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/include/range.inc	2011-04-29 09:13:14 +0000
> @@ -1471,3 +1471,35 @@ INSERT INTO t2 VALUES (1, 1, 2);
>   EXPLAIN SELECT * FROM t2 WHERE a = 1 AND b>= 2 AND c>= 2;
>
>   DROP TABLE t1, t2;
> +
> +--echo #
> +--echo # BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +--echo #               AWAY QUALIFYING ROWS
> +--echo #
> +
> +CREATE TABLE t10(
> +  K INT NOT NULL AUTO_INCREMENT,
> +  I INT, J INT,
> +  PRIMARY KEY(K),
> +  KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +                            (6,6),(6,7),(6,8),(6,9),(6,0);
> +
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +
> +# Insert offending value:
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +let $query= SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +
> +#Verify that 'range' access will be used
> +--echo
> +--eval EXPLAIN $query
> +
> +# Only row 101,8,26 should be returned
> +--echo
> +--eval $query
> +
> +DROP TABLE t10,t100;
>
> === modified file 'mysql-test/r/group_min_max.result'
> --- a/mysql-test/r/group_min_max.result	2011-04-27 09:10:45 +0000
> +++ b/mysql-test/r/group_min_max.result	2011-04-29 09:13:14 +0000
> @@ -876,10 +876,10 @@ id	select_type	table	type	possible_keys	
>   1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
>   explain select a1,a2,b,       max(c) from t1 where (c>  'b1') or (c<= 'g1') group by a1,a2,b;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
> +1	SIMPLE	t1	range	NULL	idx_t1_1	147	NULL	17	Using where; Using index for group-by
>   explain select a1,a2,b,min(c),max(c) from t1 where (c>  'b1') or (c<= 'g1') group by a1,a2,b;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
> +1	SIMPLE	t1	range	NULL	idx_t1_1	147	NULL	17	Using where; Using index for group-by
>   explain select a1,a2,b,min(c),max(c) from t1 where (c>  'b111') and (c<= 'g112') group by a1,a2,b;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t1	range	NULL	idx_t1_1	163	NULL	17	Using where; Using index for group-by
> @@ -924,7 +924,7 @@ id	select_type	table	type	possible_keys	
>   1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by
>   explain select a1,a2,b,       max(c) from t2 where (c>  'b1') or (c<= 'g1') group by a1,a2,b;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by
> +1	SIMPLE	t2	range	NULL	idx_t2_1	146	NULL	#	Using where; Using index for group-by
>   explain select a1,a2,b,min(c),max(c) from t2 where (c>  'b1') or (c<= 'g1') group by a1,a2,b;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	range	NULL	idx_t2_1	163	NULL	#	Using where; Using index for group-by
>
> === modified file 'mysql-test/r/range_icp.result'
> --- a/mysql-test/r/range_icp.result	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/r/range_icp.result	2011-04-29 09:13:14 +0000
> @@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using index condition; Using where
>   DROP TABLE t1, t2;
> +#
> +# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +#               AWAY QUALIFYING ROWS
> +#
> +CREATE TABLE t10(
> +K INT NOT NULL AUTO_INCREMENT,
> +I INT, J INT,
> +PRIMARY KEY(K),
> +KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +(6,6),(6,7),(6,8),(6,9),(6,0);
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +EXPLAIN SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t100	range	I	I	10	NULL	4	Using index condition
> +
> +SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +K	I	J
> +101	8	26
> +DROP TABLE t10,t100;
>   set optimizer_switch=default;
>
> === modified file 'mysql-test/r/range_icp_mrr.result'
> --- a/mysql-test/r/range_icp_mrr.result	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/r/range_icp_mrr.result	2011-04-29 09:13:14 +0000
> @@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using index condition; Using where
>   DROP TABLE t1, t2;
> +#
> +# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +#               AWAY QUALIFYING ROWS
> +#
> +CREATE TABLE t10(
> +K INT NOT NULL AUTO_INCREMENT,
> +I INT, J INT,
> +PRIMARY KEY(K),
> +KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +(6,6),(6,7),(6,8),(6,9),(6,0);
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +EXPLAIN SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t100	range	I	I	10	NULL	4	Using index condition; Using MRR
> +
> +SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +K	I	J
> +101	8	26
> +DROP TABLE t10,t100;
>   set optimizer_switch=default;
>
> === modified file 'mysql-test/r/range_mrr.result'
> --- a/mysql-test/r/range_mrr.result	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/r/range_mrr.result	2011-04-29 09:13:14 +0000
> @@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
>   DROP TABLE t1, t2;
> +#
> +# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +#               AWAY QUALIFYING ROWS
> +#
> +CREATE TABLE t10(
> +K INT NOT NULL AUTO_INCREMENT,
> +I INT, J INT,
> +PRIMARY KEY(K),
> +KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +(6,6),(6,7),(6,8),(6,9),(6,0);
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +EXPLAIN SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t100	range	I	I	10	NULL	4	Using where; Using MRR
> +
> +SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +K	I	J
> +101	8	26
> +DROP TABLE t10,t100;
>   set optimizer_switch=default;
>
> === modified file 'mysql-test/r/range_mrr_cost.result'
> --- a/mysql-test/r/range_mrr_cost.result	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/r/range_mrr_cost.result	2011-04-29 09:13:14 +0000
> @@ -1849,4 +1849,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
>   DROP TABLE t1, t2;
> +#
> +# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +#               AWAY QUALIFYING ROWS
> +#
> +CREATE TABLE t10(
> +K INT NOT NULL AUTO_INCREMENT,
> +I INT, J INT,
> +PRIMARY KEY(K),
> +KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +(6,6),(6,7),(6,8),(6,9),(6,0);
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +EXPLAIN SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t100	range	I	I	10	NULL	4	Using where
> +
> +SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +K	I	J
> +101	8	26
> +DROP TABLE t10,t100;
>   set optimizer_switch=default;
>
> === modified file 'mysql-test/r/range_none.result'
> --- a/mysql-test/r/range_none.result	2011-02-01 12:47:39 +0000
> +++ b/mysql-test/r/range_none.result	2011-04-29 09:13:14 +0000
> @@ -1848,4 +1848,28 @@ EXPLAIN SELECT * FROM t2 WHERE a = 1 AND
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	ref	k,l,m,n	l	5	const	69	Using where
>   DROP TABLE t1, t2;
> +#
> +# BUG#11765831: 'RANGE ACCESS' MAY INCORRECTLY FILTER
> +#               AWAY QUALIFYING ROWS
> +#
> +CREATE TABLE t10(
> +K INT NOT NULL AUTO_INCREMENT,
> +I INT, J INT,
> +PRIMARY KEY(K),
> +KEY(I,J)
> +);
> +INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),
> +(6,6),(6,7),(6,8),(6,9),(6,0);
> +CREATE TABLE t100 LIKE t10;
> +INSERT INTO t100(I,J) SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
> +INSERT INTO t100(I,J) VALUES(8,26);
> +
> +EXPLAIN SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	t100	range	I	I	10	NULL	4	Using where
> +
> +SELECT * FROM t100 WHERE I<>  6 OR (I<>  8 AND J = 5);
> +K	I	J
> +101	8	26
> +DROP TABLE t10,t100;
>   set optimizer_switch=default;
>
> === modified file 'sql/opt_range.cc'
> --- a/sql/opt_range.cc	2011-04-29 08:02:04 +0000
> +++ b/sql/opt_range.cc	2011-04-29 09:13:14 +0000
> @@ -6970,11 +6970,42 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>           tmp:     [------**********]
>                           ^         ^
>                           tmp.max is somewhere between these points here
> +
> +        If tmp->next_key_part is empty:
> +          =>  tmp->next_key_part OR key2->next_key_part will be empty
> +          If tmp.max>= key2.max: the key2 range is covered by tmp.
> +                                  Move on to next range in key2
> +          If key2.max>  tmp.max:  Make range of key2 [tmp.max, key2.max]
> +                                  and start from the top
> +        If tmp->next_key_part is NOT empty:
> +          1) Make new_arg with range [tmp.min, key2.min] and
> +             insert it into key1
> +          2) Make tmp the range [key2.min, tmp.max]
>         */
> +      if (!tmp->next_key_part)
> +      {
> +        if (tmp->cmp_max_to_max(key2)>= 0)
> +        {
> +          /*
> +            tmp.max>= key2.max. tmp covers the entire range in key2.
> +            Move to next key2 range
> +          */
> +          key2->increment_use_count(-1); // Free not used tree
> +          key2=key2->next;
> +          continue;
> +        }
> +        else
> +        {
> +          // Make key2 the range [tmp.max, key2.max]
> +          key2->copy_max_to_min(tmp);
> +          continue;
> +        }
> +      }
> +
>         SEL_ARG *new_arg=tmp->clone_first(key2);
>         if (!new_arg)
>           return 0; // OOM
> -      if ((new_arg->next_key_part= key1->next_key_part))
> +      if ((new_arg->next_key_part= tmp->next_key_part))
>           new_arg->increment_use_count(key1->use_count+1);
>         tmp->copy_min_to_min(key2);
>         key1=key1->insert(new_arg);
> @@ -7074,6 +7105,10 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>
>             Steps:
>
> +           0) If tmp->next_key_part is empty: do nothing. Reason:
> +              (key2_cpy->next_key_part OR tmp->next_key_part) will be
> +              empty and therefore equal to tmp->next_key_part. Thus,
> +              the range in key2_cpy is completely covered by tmp
>              1) Make new_arg with range [tmp.min, key2_cpy.max].
>                 new_arg->next_key_part is OR between next_key_part
>                 of tmp and key2_cpy
> @@ -7081,6 +7116,11 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>              3) Insert new_arg into key1 (after changing tmp range to
>                 insert into correct location in key1 tree)
>           */
> +        if (!tmp->next_key_part) // Step 0)
> +        {
> +          key2_cpy.increment_use_count(-1);     // Free not used tree
> +          break;
> +        }
>           SEL_ARG *new_arg=tmp->clone_last(&key2_cpy);
>           if (!new_arg)
>             return 0; // OOM
>
>
>
>
>

-- 
Jørgen Løland | Senior Software Engineer | +47 73842138
Oracle MySQL
Trondheim, Norway