maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #13029
Re: [Commits] 677643a: MDEV-27262 Unexpected index intersection with full index scan for an index
Hello Igor,
I'm trying examples with this patch:
create table t1 (a int not null, key(a));
insert into t1 select seq from seq_1_to_1000;
First, I debug this example:
explain select * from t1 where a <10 or a>=10;
The execution enters key_or(), passes through the new code this patch has added
and key_or() returns NULL. Good.
But if I modify the example slightly:
explain select * from t1 where a <20 or a>=10 ;
Here, key_or() still returns a SEL_ARG object that represents an infinite
range:
(gdb) fini
Run till exit from #0 key_or (...)
0x0000555555f1fca2 in tree_or (...)
Value returned is $24 = (SEL_ARG *) 0x7fff70064d88
(gdb) p dbug_print_sel_arg($24)
$26 = 0x7fff70024390 "SEL_ARG(-inf<=a<=+inf)"
Should this case be fixed as well?
On Fri, Dec 17, 2021 at 02:11:40PM -0800, IgorBabaev wrote:
> revision-id: 677643a80986107491b7886441f2828384f0494b (mariadb-10.2.31-1286-g677643a)
> parent(s): 8bb55633699612279744c055e22eeca8d4058273
> author: Igor Babaev
> committer: Igor Babaev
> timestamp: 2021-12-17 14:11:39 -0800
> message:
>
> MDEV-27262 Unexpected index intersection with full index scan for an index
>
> If when extracting a range condition foran index from the WHERE condition
I think the comment wording could be improved also.
> Range Optimizer sees that the range condition covers the whole index then
> such condition should be discarded because cannot it be used in any range
> scan. In some cases Range Optimizer really does it, but there remained some
> conditions for which it was not done. As a result the optimizer could
> produce index merge plans with the full index scan for one of the indexes
> participating in the index merge.
> This could be observed in one of the test cases from index_merge1.inc
> where a plan with index_merge_sort_union was produced and in the test case
> reported for this bug where a plan with index_merge_sort_intersect was
> produced. In both cases one of two index scans participating in index merge
> ran over the whole index.
> The patch slightly changes the original above mentioned test case from
> index_merge1.inc to be able to produce an intended plan employing
> index_merge_sort_union. The original query was left to show that index
> merge is not used for it anymore.
> It should be noted that for the plan with index_merge_sort_intersect could
> be chosen for execution only due to a defect in the InnoDB code that
> returns wrong estimates for the cardinality of big ranges.
>
> This bug led to serious problems in 10.4+ where the optimization using
> Rowid filters is employed (see mdev-26446).
>
> Approved by Oleksandr Byelkin <sanja@xxxxxxxxxxx>
>
> ---
> mysql-test/include/index_merge1.inc | 8 +++-
> mysql-test/r/index_merge_myisam.result | 12 +++--
> mysql-test/r/range_innodb.result | 81 ++++++++++++++++++++++++++++++++++
> mysql-test/t/range_innodb.test | 78 ++++++++++++++++++++++++++++++++
> sql/opt_range.cc | 7 +++
> 5 files changed, 181 insertions(+), 5 deletions(-)
>
> diff --git a/mysql-test/include/index_merge1.inc b/mysql-test/include/index_merge1.inc
> index b168a76..440f1f7 100644
> --- a/mysql-test/include/index_merge1.inc
> +++ b/mysql-test/include/index_merge1.inc
> @@ -150,15 +150,19 @@ explain select * from t0 where
> (((key3 <7 and key7 < 6) or key5 < 2) and (key5 < 5 or key6 < 6));
>
> explain select * from t0 where
> - ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
> + ((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
> or
> ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
>
> explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
> - ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
> + ((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
> or
> ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
>
> +explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
> + ((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
> + or
> + ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
> # 8. Verify that "order by" after index merge uses filesort
> select * from t0 where key1 < 5 or key8 < 4 order by key1;
>
> diff --git a/mysql-test/r/index_merge_myisam.result b/mysql-test/r/index_merge_myisam.result
> index 5a23092..a096c34 100644
> --- a/mysql-test/r/index_merge_myisam.result
> +++ b/mysql-test/r/index_merge_myisam.result
> @@ -173,17 +173,23 @@ or
> id select_type table type possible_keys key key_len ref rows Extra
> 1 SIMPLE t0 index_merge i1,i2,i3,i5,i6,i7 i3,i5 4,4 NULL 11 Using sort_union(i3,i5); Using where
> explain select * from t0 where
> -((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
> +((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
> or
> ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
> id select_type table type possible_keys key key_len ref rows Extra
> 1 SIMPLE t0 ALL i1,i2,i3,i5,i6 NULL NULL NULL 1024 Using where
> explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
> -((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
> +((key3 < 4 or key5 < 4) and (key1 < 4 or key2 < 4))
> or
> ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
> id select_type table type possible_keys key key_len ref rows Extra
> -1 SIMPLE t0 index_merge i1,i2,i3,i5,i6 i3,i5 0,4 NULL 1024 Using sort_union(i3,i5); Using where
> +1 SIMPLE t0 index_merge i1,i2,i3,i5,i6 i3,i5 4,4 NULL 1024 Using sort_union(i3,i5); Using where
> +explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
> +((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
> +or
> +((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
> +id select_type table type possible_keys key key_len ref rows Extra
> +1 SIMPLE t0 ALL i1,i2,i3,i5,i6 NULL NULL NULL 1024 Using where
> select * from t0 where key1 < 5 or key8 < 4 order by key1;
> key1 key2 key3 key4 key5 key6 key7 key8
> 1 1 1 1 1 1 1 1023
> diff --git a/mysql-test/r/range_innodb.result b/mysql-test/r/range_innodb.result
> index f2349f2..ccb6da3 100644
> --- a/mysql-test/r/range_innodb.result
> +++ b/mysql-test/r/range_innodb.result
> @@ -108,3 +108,84 @@ DROP TABLE t0,t1;
> SET @@GLOBAL.debug_dbug = @saved_dbug;
> set @@optimizer_switch= @optimizer_switch_save;
> # End of 10.1 tests
> +#
> +# MDEV-27262: Index intersection with full scan over an index
> +#
> +CREATE TABLE t1 (
> +id int(10) unsigned NOT NULL AUTO_INCREMENT,
> +p char(32) DEFAULT NULL,
> +es tinyint(3) unsigned NOT NULL DEFAULT 0,
> +er tinyint(3) unsigned NOT NULL DEFAULT 0,
> +x mediumint(8) unsigned NOT NULL DEFAULT 0,
> +PRIMARY KEY (id),
> +INDEX es (es),
> +INDEX x (x),
> +INDEX er (er,x),
> +INDEX p (p)
> +) ENGINE=InnoDB DEFAULT CHARSET=latin1;
> +insert into t1(es,er) select 0, 1 from seq_1_to_45;
> +insert into t1(es,er) select 0, 2 from seq_1_to_49;
> +insert into t1(es,er) select 0, 3 from seq_1_to_951;
> +insert into t1(es,er) select 0, 3 from seq_1_to_1054;
> +insert into t1(es,er) select 0, 6 from seq_1_to_25;
> +insert into t1(es,er) select 0, 11 from seq_1_to_1;
> +insert into t1(es,er) select 1, 1 from seq_1_to_45;
> +insert into t1(es,er) select 1, 2 from seq_1_to_16;
> +insert into t1(es,er) select 1, 3 from seq_1_to_511;
> +insert into t1(es,er) select 1, 4 from seq_1_to_687;
> +insert into t1(es,er) select 1, 6 from seq_1_to_50;
> +insert into t1(es,er) select 1, 7 from seq_1_to_4;
> +insert into t1(es,er) select 1, 11 from seq_1_to_1;
> +insert into t1(es,er) select 2, 1 from seq_1_to_82;
> +insert into t1(es,er) select 2, 2 from seq_1_to_82;
> +insert into t1(es,er) select 2, 3 from seq_1_to_1626;
> +insert into t1(es,er) select 2, 4 from seq_1_to_977;
> +insert into t1(es,er) select 2, 6 from seq_1_to_33;
> +insert into t1(es,er) select 2, 11 from seq_1_to_1;
> +insert into t1(es,er) select 3, 1 from seq_1_to_245;
> +insert into t1(es,er) select 3, 2 from seq_1_to_81;
> +insert into t1(es,er) select 3, 3 from seq_1_to_852;
> +insert into t1(es,er) select 3, 4 from seq_1_to_2243;
> +insert into t1(es,er) select 3, 6 from seq_1_to_44;
> +insert into t1(es,er) select 3, 11 from seq_1_to_1;
> +insert into t1(es,er) select 4, 1 from seq_1_to_91;
> +insert into t1(es,er) select 4, 2 from seq_1_to_83;
> +insert into t1(es,er) select 4, 3 from seq_1_to_297;
> +insert into t1(es,er) select 4, 4 from seq_1_to_2456;
> +insert into t1(es,er) select 4, 6 from seq_1_to_19;
> +insert into t1(es,er) select 4, 11 from seq_1_to_1;
> +update t1 set p='foobar';
> +update t1 set x=0;
> +set @save_isp=@@innodb_stats_persistent;
> +set global innodb_stats_persistent= 1;
> +analyze table t1;
> +Table Op Msg_type Msg_text
> +test.t1 analyze status OK
> +set optimizer_switch='index_merge_sort_intersection=on';
> +SELECT * FROM t1
> +WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
> +id p es er x
> +14645 foobar 4 4 0
> +14646 foobar 4 4 0
> +EXPLAIN EXTENDED SELECT * FROM t1
> +WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
> +id select_type table type possible_keys key key_len ref rows filtered Extra
> +1 SIMPLE t1 range es,er,p es 1 NULL # 100.00 Using index condition; Using where
> +Warnings:
> +Note 1003 select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` <> 4 or `test`.`t1`.`er` = 4) and `test`.`t1`.`es` >= 4 limit 2
> +set optimizer_switch='index_merge_sort_intersection=off';
> +SELECT * FROM t1
> +WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
> +id p es er x
> +14645 foobar 4 4 0
> +14646 foobar 4 4 0
> +EXPLAIN EXTENDED SELECT * FROM t1
> +WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
> +id select_type table type possible_keys key key_len ref rows filtered Extra
> +1 SIMPLE t1 range es,er,p es 1 NULL # 100.00 Using index condition; Using where
> +Warnings:
> +Note 1003 select `test`.`t1`.`id` AS `id`,`test`.`t1`.`p` AS `p`,`test`.`t1`.`es` AS `es`,`test`.`t1`.`er` AS `er`,`test`.`t1`.`x` AS `x` from `test`.`t1` where (`test`.`t1`.`p` = 'foo' and `test`.`t1`.`er` <> 4 or `test`.`t1`.`er` = 4) and `test`.`t1`.`es` >= 4 limit 2
> +set optimizer_switch='index_merge_sort_intersection=default';
> +set global innodb_stats_persistent= @save_isp;
> +DROP TABLE t1;
> +# End of 10.2 tests
> diff --git a/mysql-test/t/range_innodb.test b/mysql-test/t/range_innodb.test
> index 428e5c2..7420e72 100644
> --- a/mysql-test/t/range_innodb.test
> +++ b/mysql-test/t/range_innodb.test
> @@ -116,3 +116,81 @@ SET @@GLOBAL.debug_dbug = @saved_dbug;
> set @@optimizer_switch= @optimizer_switch_save;
>
> --echo # End of 10.1 tests
> +
> +--echo #
> +--echo # MDEV-27262: Index intersection with full scan over an index
> +--echo #
> +
> +--source include/have_sequence.inc
> +
> +CREATE TABLE t1 (
> + id int(10) unsigned NOT NULL AUTO_INCREMENT,
> + p char(32) DEFAULT NULL,
> + es tinyint(3) unsigned NOT NULL DEFAULT 0,
> + er tinyint(3) unsigned NOT NULL DEFAULT 0,
> + x mediumint(8) unsigned NOT NULL DEFAULT 0,
> + PRIMARY KEY (id),
> + INDEX es (es),
> + INDEX x (x),
> + INDEX er (er,x),
> + INDEX p (p)
> +) ENGINE=InnoDB DEFAULT CHARSET=latin1;
> +
> +insert into t1(es,er) select 0, 1 from seq_1_to_45;
> +insert into t1(es,er) select 0, 2 from seq_1_to_49;
> +insert into t1(es,er) select 0, 3 from seq_1_to_951;
> +insert into t1(es,er) select 0, 3 from seq_1_to_1054;
> +insert into t1(es,er) select 0, 6 from seq_1_to_25;
> +insert into t1(es,er) select 0, 11 from seq_1_to_1;
> +insert into t1(es,er) select 1, 1 from seq_1_to_45;
> +insert into t1(es,er) select 1, 2 from seq_1_to_16;
> +insert into t1(es,er) select 1, 3 from seq_1_to_511;
> +insert into t1(es,er) select 1, 4 from seq_1_to_687;
> +insert into t1(es,er) select 1, 6 from seq_1_to_50;
> +insert into t1(es,er) select 1, 7 from seq_1_to_4;
> +insert into t1(es,er) select 1, 11 from seq_1_to_1;
> +insert into t1(es,er) select 2, 1 from seq_1_to_82;
> +insert into t1(es,er) select 2, 2 from seq_1_to_82;
> +insert into t1(es,er) select 2, 3 from seq_1_to_1626;
> +insert into t1(es,er) select 2, 4 from seq_1_to_977;
> +insert into t1(es,er) select 2, 6 from seq_1_to_33;
> +insert into t1(es,er) select 2, 11 from seq_1_to_1;
> +insert into t1(es,er) select 3, 1 from seq_1_to_245;
> +insert into t1(es,er) select 3, 2 from seq_1_to_81;
> +insert into t1(es,er) select 3, 3 from seq_1_to_852;
> +insert into t1(es,er) select 3, 4 from seq_1_to_2243;
> +insert into t1(es,er) select 3, 6 from seq_1_to_44;
> +insert into t1(es,er) select 3, 11 from seq_1_to_1;
> +insert into t1(es,er) select 4, 1 from seq_1_to_91;
> +insert into t1(es,er) select 4, 2 from seq_1_to_83;
> +insert into t1(es,er) select 4, 3 from seq_1_to_297;
> +insert into t1(es,er) select 4, 4 from seq_1_to_2456;
> +insert into t1(es,er) select 4, 6 from seq_1_to_19;
> +insert into t1(es,er) select 4, 11 from seq_1_to_1;
> +update t1 set p='foobar';
> +update t1 set x=0;
> +set @save_isp=@@innodb_stats_persistent;
> +set global innodb_stats_persistent= 1;
> +analyze table t1;
> +
> +let $q=
> +SELECT * FROM t1
> + WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
> +
> +set optimizer_switch='index_merge_sort_intersection=on';
> +eval $q;
> +--replace_column 9 #
> +eval EXPLAIN EXTENDED $q;
> +
> +set optimizer_switch='index_merge_sort_intersection=off';
> +# execution of $q and explain for it led to an assertion failure in 10.4
> +# (with the optimizer switch rowid_filter set to 'on')
> +eval $q;
> +--replace_column 9 #
> +eval EXPLAIN EXTENDED $q;
> +set optimizer_switch='index_merge_sort_intersection=default';
> +
> +set global innodb_stats_persistent= @save_isp;
> +DROP TABLE t1;
> +
> +--echo # End of 10.2 tests
> diff --git a/sql/opt_range.cc b/sql/opt_range.cc
> index f3f1843..2e05b88 100644
> --- a/sql/opt_range.cc
> +++ b/sql/opt_range.cc
> @@ -9413,6 +9413,13 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
> key2->copy_min(tmp);
> if (!(key1=key1->tree_delete(tmp)))
> { // Only one key in tree
> + if (key2->min_flag & NO_MIN_RANGE &&
> + key2->max_flag & NO_MAX_RANGE)
> + {
> + if (key2->maybe_flag)
> + return new SEL_ARG(SEL_ARG::MAYBE_KEY);
> + return 0; // Always true OR
> + }
> key1=key2;
> key1->make_root();
> key2=key2_next;
BR
Sergei
--
Sergei Petrunia, Software Developer
MariaDB Corporation | Skype: sergefp | Blog: http://petrunia.net
