revision-id: 51d01dc578f3d3ab0ccf0dda72bd500c80484766 (mariadb-10.1.41-35-g51d01dc) parent(s): 031c695b8c865e5eb6c4c09ced404ae08f98430f author: Igor Babaev committer: Igor Babaev timestamp: 2019-09-12 23:00:49 -0700 message: MDEV-20576 A new assertion added to check validity of calculated selectivity values fails After having set the assertion that checks validity of selectivity values returned by the function table_cond_selectivity() a test case from order_by.tesst failed. The failure occurred because range optimizer could return as an estimate of the cardinality of the ranges built for an index a number exceeding the total number of records in the table. The second bug is more subtle. It may happen when there are several indexes with same prefix defined on the first joined table t accessed by a constant ref access. In this case the range optimizer estimates the number of accessed records of t for each usable index and these estimates can be different. Only the first of these estimates is taken into account when the selectivity of the ref access is calculated. However the optimizer later can choose a different index that provides a different estimate. The function table_condition_selectivity() could use this estimate to discount the selectivity of the ref access. This could lead to an selectivity value returned by this function that was greater that 1. --- mysql-test/r/innodb_icp.result | 4 +- mysql-test/r/range_vs_index_merge.result | 2 +- mysql-test/r/range_vs_index_merge_innodb.result | 2 +- mysql-test/r/selectivity.result | 85 +++++++++++++++++++++++++ mysql-test/r/selectivity_innodb.result | 85 +++++++++++++++++++++++++ mysql-test/t/selectivity.test | 81 +++++++++++++++++++++++ sql/opt_range.cc | 10 +++ sql/sql_select.cc | 15 +++++ 8 files changed, 280 insertions(+), 4 deletions(-) diff --git a/mysql-test/r/innodb_icp.result b/mysql-test/r/innodb_icp.result index a5215bf..0c95f31 100644 --- a/mysql-test/r/innodb_icp.result +++ b/mysql-test/r/innodb_icp.result @@ -679,7 +679,7 @@ EXPLAIN SELECT t1.b, t1.c FROM t1, t2 WHERE t1.a = t2.a AND t1.b != 0 HAVING t1.c != 5 ORDER BY t1.c; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY PRIMARY 4 NULL 2 Using where; Using filesort +1 SIMPLE t1 range PRIMARY PRIMARY 4 NULL 1 Using where; Using filesort 1 SIMPLE t2 ref a a 515 test.t1.a 1 Using where SELECT t1.b, t1.c FROM t1, t2 WHERE t1.a = t2.a AND t1.b != 0 HAVING t1.c != 5 ORDER BY t1.c; @@ -690,7 +690,7 @@ EXPLAIN SELECT t1.b, t1.c FROM t1, t2 WHERE t1.a = t2.a AND t1.b != 0 HAVING t1.c != 5 ORDER BY t1.c; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY PRIMARY 4 NULL 2 Using where; Using filesort +1 SIMPLE t1 range PRIMARY PRIMARY 4 NULL 1 Using where; Using filesort 1 SIMPLE t2 ref a a 515 test.t1.a 1 Using where SELECT t1.b, t1.c FROM t1, t2 WHERE t1.a = t2.a AND t1.b != 0 HAVING t1.c != 5 ORDER BY t1.c; diff --git a/mysql-test/r/range_vs_index_merge.result b/mysql-test/r/range_vs_index_merge.result index bc46a4f..4f3c36b 100644 --- a/mysql-test/r/range_vs_index_merge.result +++ b/mysql-test/r/range_vs_index_merge.result @@ -1795,7 +1795,7 @@ SELECT * FROM t1 FORCE KEY (state,capital) WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range state,capital state 71 NULL 12 Using index condition; Using where +1 SIMPLE t1 range state,capital state 71 NULL 8 Using index condition; Using where SELECT * FROM t1 FORCE KEY (state,capital) WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; diff --git a/mysql-test/r/range_vs_index_merge_innodb.result b/mysql-test/r/range_vs_index_merge_innodb.result index a6ec200..08b7df6 100644 --- a/mysql-test/r/range_vs_index_merge_innodb.result +++ b/mysql-test/r/range_vs_index_merge_innodb.result @@ -1796,7 +1796,7 @@ SELECT * FROM t1 FORCE KEY (state,capital) WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range state,capital state 71 NULL 10 Using index condition; Using where +1 SIMPLE t1 range state,capital state 71 NULL 8 Using index condition; Using where SELECT * FROM t1 FORCE KEY (state,capital) WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; diff --git a/mysql-test/r/selectivity.result b/mysql-test/r/selectivity.result index 3f5db42..d8b2d46 100644 --- a/mysql-test/r/selectivity.result +++ b/mysql-test/r/selectivity.result @@ -1668,4 +1668,89 @@ Note 1003 select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` drop table t1; set use_stat_tables= @save_use_stat_tables; set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +# +# MDEV-20576: failing assertion DBUG_ASSERT(0.0 < sel && sel <= 1) +# +set @@optimizer_use_condition_selectivity=2; +set names utf8; +CREATE DATABASE world; +use world; +CREATE TABLE Country ( +Code char(3) NOT NULL default '', +Name char(52) NOT NULL default '', +SurfaceArea float(10,2) NOT NULL default '0.00', +Population int(11) NOT NULL default '0', +Capital int(11) default NULL, +PRIMARY KEY (Code), +UNIQUE INDEX (Name) +); +CREATE TABLE City ( +ID int(11) NOT NULL auto_increment, +Name char(35) NOT NULL default '', +Country char(3) NOT NULL default '', +Population int(11) NOT NULL default '0', +PRIMARY KEY (ID), +INDEX (Population), +INDEX (Country) +); +CREATE TABLE CountryLanguage ( +Country char(3) NOT NULL default '', +Language char(30) NOT NULL default '', +Percentage float(3,1) NOT NULL default '0.0', +PRIMARY KEY (Country, Language), +INDEX (Percentage) +); +CREATE INDEX Name ON City(Name); +CREATE INDEX CountryPopulation ON City(Country,Population); +CREATE INDEX CountryName ON City(Country,Name); +set @@optimizer_use_condition_selectivity=2; +EXPLAIN +SELECT * FROM City WHERE Country='FIN'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City ref Country,CountryPopulation,CountryName CountryName 3 const 5 Using index condition +DROP DATABASE world; +use test; +CREATE TABLE t1 ( +a INT, +b INT NOT NULL, +c char(100), +KEY (b, c), +KEY (b, a, c) +) +DEFAULT CHARSET = utf8; +INSERT INTO t1 VALUES +(1, 1, 1), +(2, 2, 2), +(3, 3, 3), +(4, 4, 4), +(5, 5, 5), +(6, 6, 6), +(7, 7, 7), +(8, 8, 8), +(9, 9, 9); +INSERT INTO t1 SELECT a + 10, b, c FROM t1; +INSERT INTO t1 SELECT a + 20, b, c FROM t1; +INSERT INTO t1 SELECT a + 40, b, c FROM t1; +INSERT INTO t1 SELECT a + 80, b, c FROM t1; +INSERT INTO t1 SELECT a + 160, b, c FROM t1; +INSERT INTO t1 SELECT a + 320, b, c FROM t1; +INSERT INTO t1 SELECT a + 640, b, c FROM t1; +INSERT INTO t1 SELECT a + 1280, b, c FROM t1 LIMIT 80; +EXPLAIN +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range b,b_2 b 4 NULL 226 Using where +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; +a +2071 +2061 +2051 +2041 +2031 +2021 +2011 +2001 +1991 +set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +DROP TABLE t1; # End of 10.1 tests diff --git a/mysql-test/r/selectivity_innodb.result b/mysql-test/r/selectivity_innodb.result index 1d73c2f..56a7900 100644 --- a/mysql-test/r/selectivity_innodb.result +++ b/mysql-test/r/selectivity_innodb.result @@ -1678,6 +1678,91 @@ Note 1003 select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` drop table t1; set use_stat_tables= @save_use_stat_tables; set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +# +# MDEV-20576: failing assertion DBUG_ASSERT(0.0 < sel && sel <= 1) +# +set @@optimizer_use_condition_selectivity=2; +set names utf8; +CREATE DATABASE world; +use world; +CREATE TABLE Country ( +Code char(3) NOT NULL default '', +Name char(52) NOT NULL default '', +SurfaceArea float(10,2) NOT NULL default '0.00', +Population int(11) NOT NULL default '0', +Capital int(11) default NULL, +PRIMARY KEY (Code), +UNIQUE INDEX (Name) +); +CREATE TABLE City ( +ID int(11) NOT NULL auto_increment, +Name char(35) NOT NULL default '', +Country char(3) NOT NULL default '', +Population int(11) NOT NULL default '0', +PRIMARY KEY (ID), +INDEX (Population), +INDEX (Country) +); +CREATE TABLE CountryLanguage ( +Country char(3) NOT NULL default '', +Language char(30) NOT NULL default '', +Percentage float(3,1) NOT NULL default '0.0', +PRIMARY KEY (Country, Language), +INDEX (Percentage) +); +CREATE INDEX Name ON City(Name); +CREATE INDEX CountryPopulation ON City(Country,Population); +CREATE INDEX CountryName ON City(Country,Name); +set @@optimizer_use_condition_selectivity=2; +EXPLAIN +SELECT * FROM City WHERE Country='FIN'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City ref Country,CountryPopulation,CountryName Country 3 const 7 Using index condition +DROP DATABASE world; +use test; +CREATE TABLE t1 ( +a INT, +b INT NOT NULL, +c char(100), +KEY (b, c), +KEY (b, a, c) +) +DEFAULT CHARSET = utf8; +INSERT INTO t1 VALUES +(1, 1, 1), +(2, 2, 2), +(3, 3, 3), +(4, 4, 4), +(5, 5, 5), +(6, 6, 6), +(7, 7, 7), +(8, 8, 8), +(9, 9, 9); +INSERT INTO t1 SELECT a + 10, b, c FROM t1; +INSERT INTO t1 SELECT a + 20, b, c FROM t1; +INSERT INTO t1 SELECT a + 40, b, c FROM t1; +INSERT INTO t1 SELECT a + 80, b, c FROM t1; +INSERT INTO t1 SELECT a + 160, b, c FROM t1; +INSERT INTO t1 SELECT a + 320, b, c FROM t1; +INSERT INTO t1 SELECT a + 640, b, c FROM t1; +INSERT INTO t1 SELECT a + 1280, b, c FROM t1 LIMIT 80; +EXPLAIN +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ref b,b_2 b_2 4 const 207 Using where; Using index; Using filesort +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; +a +2071 +81 +71 +61 +51 +41 +31 +21 +11 +set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +DROP TABLE t1; # End of 10.1 tests set optimizer_switch=@save_optimizer_switch_for_selectivity_test; set @tmp_ust= @@use_stat_tables; diff --git a/mysql-test/t/selectivity.test b/mysql-test/t/selectivity.test index f1c9d6b..6e93e60 100644 --- a/mysql-test/t/selectivity.test +++ b/mysql-test/t/selectivity.test @@ -1124,5 +1124,86 @@ drop table t1; set use_stat_tables= @save_use_stat_tables; set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; + +--echo # +--echo # MDEV-20576: failing assertion DBUG_ASSERT(0.0 < sel && sel <= 1) +--echo # + +set @@optimizer_use_condition_selectivity=2; + +set names utf8; + +CREATE DATABASE world; + +use world; + +--source include/world_schema.inc + +--disable_query_log +--disable_result_log +--disable_warnings +--source include/world.inc +--enable_warnings +--enable_result_log +--enable_query_log + +CREATE INDEX Name ON City(Name); +CREATE INDEX CountryPopulation ON City(Country,Population); +CREATE INDEX CountryName ON City(Country,Name); + +--disable_query_log +--disable_result_log +--disable_warnings +ANALYZE TABLE City; +--enable_warnings +--enable_result_log +--enable_query_log + +set @@optimizer_use_condition_selectivity=2; + +EXPLAIN +SELECT * FROM City WHERE Country='FIN'; + +DROP DATABASE world; + +use test; + +CREATE TABLE t1 ( + a INT, + b INT NOT NULL, + c char(100), + KEY (b, c), + KEY (b, a, c) +) +DEFAULT CHARSET = utf8; + +INSERT INTO t1 VALUES +(1, 1, 1), +(2, 2, 2), +(3, 3, 3), +(4, 4, 4), +(5, 5, 5), +(6, 6, 6), +(7, 7, 7), +(8, 8, 8), +(9, 9, 9); + +INSERT INTO t1 SELECT a + 10, b, c FROM t1; +INSERT INTO t1 SELECT a + 20, b, c FROM t1; +INSERT INTO t1 SELECT a + 40, b, c FROM t1; +INSERT INTO t1 SELECT a + 80, b, c FROM t1; +INSERT INTO t1 SELECT a + 160, b, c FROM t1; +INSERT INTO t1 SELECT a + 320, b, c FROM t1; +INSERT INTO t1 SELECT a + 640, b, c FROM t1; +INSERT INTO t1 SELECT a + 1280, b, c FROM t1 LIMIT 80; + +EXPLAIN +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; +SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9; + +set optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; + +DROP TABLE t1; + --echo # End of 10.1 tests diff --git a/sql/opt_range.cc b/sql/opt_range.cc index e8421ad..45dad88 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -10179,6 +10179,16 @@ ha_rows check_quick_select(PARAM *param, uint idx, bool index_only, bufsize, mrr_flags, cost); if (rows != HA_POS_ERROR) { + ha_rows table_records= param->table->stat_records(); + if (rows > table_records) + { + /* + For any index the total number of records within all ranges + cannot be be bigger than the number of records in the table + */ + rows= table_records; + set_if_bigger(rows, 1); + } param->quick_rows[keynr]= rows; param->possible_keys.set_bit(keynr); if (update_tbl_stats) diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 5b96c15..c6e70c2 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -7643,7 +7643,19 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, } keyparts++; } + /* + Here we discount selectivity of the constant range CR. To calculate + this selectivity we use elements from the quick_rows[] array. + If we have indexes i1,...,ik with the same prefix compatible + with CR any of the estimate quick_rows[i1], ... quick_rows[ik] could + be used for this calculation but here we don't know which one was + actually used. So sel could be greater than 1 and we have to cap it. + However if sel becomes greater than 2 then with high probability + something went wrong. + */ sel /= (double)table->quick_rows[key] / (double) table->stat_records(); + DBUG_ASSERT(0 < sel && sel <= 2.0); + set_if_smaller(sel, 1.0); used_range_selectivity= true; } } @@ -7691,6 +7703,7 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, if (table->field[fldno]->cond_selectivity > 0) { sel /= table->field[fldno]->cond_selectivity; + DBUG_ASSERT(0 < sel && sel <= 2.0); set_if_smaller(sel, 1.0); } /* @@ -7748,6 +7761,7 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, if (field->cond_selectivity > 0) { sel/= field->cond_selectivity; + DBUG_ASSERT(0 < sel && sel <= 2.0); set_if_smaller(sel, 1.0); } break; @@ -7759,6 +7773,7 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, sel*= table_multi_eq_cond_selectivity(join, idx, s, rem_tables, keyparts, ref_keyuse_steps); + DBUG_ASSERT(0.0 < sel && sel <= 1.0); return sel; }