List:Commits« Previous MessageNext Message »
From:Olav Sandstaa Date:May 16 2011 11:52am
Subject:Re: bzr commit into mysql-trunk branch (jorgen.loland:3382) Bug#11765831
View as plain text  
Hi Jørgen,

Thanks for taking a systematic approach for fixing this. The commit 
message is great and helped a lot to understand how the patch solves the 
problem.

The fix looks good and works as described in the commit message and the 
comments in the source code. I have only some very minor comments that 
you mostly are free to ignore.
OK to push.

Olav


On 06/05/2011 15:57, Jorgen Loland wrote:
> #At file:///export/home/jl208045/mysql/mysql-trunk-11765831/ based on
> revid:jorgen.loland@stripped
>
>   3382 Jorgen Loland	2011-05-06
>        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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:57:35 +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-05-06 13:26:31 +0000
> +++ b/sql/opt_range.cc	2011-05-06 13:57:35 +0000
> @@ -7069,11 +7069,53 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>           This is the case ("cmp>=0" means that tmp.max>= key2.min):
>           key2:              [----]
>           tmp:     [------------*****]
> +      */
> +
> +      if (!tmp->next_key_part)
> +      {
> +        /*
> +          tmp has no next_key_part, thus
> +            tmp->next_key_part == (tmp->next_key_part OR
> key2->next_key_part)
> +                               == empty
> +
> +          The range that is covered by tmp can be cut from key2

I found this a bit hard to read and understand. I think the more 
textly/verbose way of explain a similar situation you used further down 
(as step 0) was easier to understand. Suggestion: Change this to be more 
like the explanation for "step 0" below.

> +         */

Remove on "space" in front of */

> +        if (tmp->cmp_max_to_max(key2)>= 0)
> +        {
> +          /*
> +            tmp covers the entire range in key2.
> +            key2:              [----]
> +            tmp:     [-----------------]
> +
> +            Move on to next range in key2
> +          */
> +          key2->increment_use_count(-1); // Free not used tree
> +          key2=key2->next;
> +          continue;
> +        }
> +        else
> +        {
> +          /*
> +            This is the case:
> +            key2:           [-------]
> +            tmp:     [---------]
> +
> +            Result:
> +            key2:               [---]
> +            tmp:     [---------]
> +          */
> +          key2->copy_max_to_min(tmp);
> +          continue;
> +        }
> +      }
>
> +      /*
>           The ranges are overlapping but have not been merged because
> -        next_key_part of tmp and key2 are different
> +        next_key_part of tmp and key2 differ.
> +        key2:              [----]
> +        tmp:     [------------*****]
>
> -        Result:
> +        Split tmp in two where key2 starts:
>           key2:              [----]
>           key1:    [--------][--*****]
>                    ^         ^
> @@ -7082,7 +7124,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>         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);
> @@ -7191,12 +7233,21 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *
>                         ^        ^
>                         new_arg  tmp
>             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
>              2) Make tmp the range [key2.max, tmp.max]
>              3) Insert new_arg into key1
>           */
> +        if (!tmp->next_key_part) // Step 0)

Minor suggestion: just write "Step 0" (without the ")" ) as it makes it 
harder to see that this is a comment?

> +        {
> +          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
>
>
>
>


Thread
bzr commit into mysql-trunk branch (jorgen.loland:3382) Bug#11765831Jorgen Loland6 May
  • Re: bzr commit into mysql-trunk branch (jorgen.loland:3382) Bug#11765831Olav Sandstaa16 May