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@mariadb.com>
--- 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