revision-id: f6640f37ed701160b0e51f20f5d75d306bbe3f27 (mariadb-10.4.11-421-gf6640f37ed7) parent(s): 7cdd4fe6440879e9309d036362414d483c642122 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2020-11-05 23:46:42 +0300 message: MDEV-21958: Query having many NOT-IN clauses running forever Basic variant of the fix: do not consider conditions in form unique_key NOT IN (c1,c2...) to be sargable. If there are only a few constants, the condition is not selective. If there are a lot constants, the overhead of processing such a huge range list is not worth it. --- mysql-test/main/range.result | 30 ++++++++++++++++++++++++++++++ mysql-test/main/range.test | 24 ++++++++++++++++++++++++ mysql-test/main/range_mrr_icp.result | 30 ++++++++++++++++++++++++++++++ sql/opt_range.cc | 24 ++++++++++++++++++++++++ 4 files changed, 108 insertions(+) diff --git a/mysql-test/main/range.result b/mysql-test/main/range.result index 9800d931dd6..b429a4146ad 100644 --- a/mysql-test/main/range.result +++ b/mysql-test/main/range.result @@ -3181,6 +3181,36 @@ left(@json, 500) " set optimizer_trace=@tmp_9750; drop table t1; +# +# MDEV-21958: Query having many NOT-IN clauses running forever +# +create table t2 ( +pk int primary key, +key1 int, +col1 int, +key (key1, pk) +); +insert into t2 (pk, key1) values (1,1),(2,2),(3,3),(4,4),(5,5); +set @tmp_21958=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t2 where key1 in (1,2,3) and pk not in (1,2,3); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 ALL PRIMARY,key1 NULL NULL NULL 5 Using where +# This should show only ranges in form "(1) <= (key1) <= (1)" +# ranges over "pk" should not be constructed. +select json_detailed(JSON_EXTRACT(trace, '$**.ranges')) +from information_schema.optimizer_trace; +json_detailed(JSON_EXTRACT(trace, '$**.ranges')) +[ + + [ + "(1) <= (key1) <= (1)", + "(2) <= (key1) <= (2)", + "(3) <= (key1) <= (3)" + ] +] +set optimizer_trace=@tmp_21958; +drop table t2; set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/mysql-test/main/range.test b/mysql-test/main/range.test index 642ae3f8a08..cd48d9d7935 100644 --- a/mysql-test/main/range.test +++ b/mysql-test/main/range.test @@ -2153,6 +2153,30 @@ select left(@json, 500); set optimizer_trace=@tmp_9750; drop table t1; +--echo # +--echo # MDEV-21958: Query having many NOT-IN clauses running forever +--echo # +create table t2 ( + pk int primary key, + key1 int, + col1 int, + key (key1, pk) +); + +insert into t2 (pk, key1) values (1,1),(2,2),(3,3),(4,4),(5,5); + +set @tmp_21958=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t2 where key1 in (1,2,3) and pk not in (1,2,3); + +--echo # This should show only ranges in form "(1) <= (key1) <= (1)" +--echo # ranges over "pk" should not be constructed. +select json_detailed(JSON_EXTRACT(trace, '$**.ranges')) +from information_schema.optimizer_trace; +set optimizer_trace=@tmp_21958; + +drop table t2; + set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/mysql-test/main/range_mrr_icp.result b/mysql-test/main/range_mrr_icp.result index 128f23d71f6..1c5ab1443da 100644 --- a/mysql-test/main/range_mrr_icp.result +++ b/mysql-test/main/range_mrr_icp.result @@ -3178,6 +3178,36 @@ left(@json, 500) " set optimizer_trace=@tmp_9750; drop table t1; +# +# MDEV-21958: Query having many NOT-IN clauses running forever +# +create table t2 ( +pk int primary key, +key1 int, +col1 int, +key (key1, pk) +); +insert into t2 (pk, key1) values (1,1),(2,2),(3,3),(4,4),(5,5); +set @tmp_21958=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t2 where key1 in (1,2,3) and pk not in (1,2,3); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 ALL PRIMARY,key1 NULL NULL NULL 5 Using where +# This should show only ranges in form "(1) <= (key1) <= (1)" +# ranges over "pk" should not be constructed. +select json_detailed(JSON_EXTRACT(trace, '$**.ranges')) +from information_schema.optimizer_trace; +json_detailed(JSON_EXTRACT(trace, '$**.ranges')) +[ + + [ + "(1) <= (key1) <= (1)", + "(2) <= (key1) <= (2)", + "(3) <= (key1) <= (3)" + ] +] +set optimizer_trace=@tmp_21958; +drop table t2; set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 7af555dbd17..3dcdb225b77 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -7787,6 +7787,30 @@ SEL_TREE *Item_func_in::get_func_mm_tree(RANGE_OPT_PARAM *param, if (array->count > NOT_IN_IGNORE_THRESHOLD || !value_item) DBUG_RETURN(0); + /* + If this is "unique_key NOT IN (...)", do not consider it sargable (for + any index, not just the unique one). The logic is as follows: + - if there are only a few constants, this condition is not selective + (unless the table is also very small in which case we won't gain + anything) + - If there are a lot of constants, the overhead of building and + processing enormous range list is not worth it. + */ + if (param->using_real_indexes) + { + key_map::Iterator it(field->key_start); + uint key_no; + while ((key_no= it.next_bit()) != key_map::Iterator::BITMAP_END) + { + KEY *key_info= ¶m->table->key_info[key_no]; + if (key_info->user_defined_key_parts == 1 && + (key_info->flags & HA_NOSAME)) + { + DBUG_RETURN(0); + } + } + } + /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */ uint i=0; do