commit bc61ad987f5fc6ccc5b2b8fc437702d7460765a6 Author: Laurynas Biveinis Date: Mon Jan 16 11:23:02 2017 +0200 Fix Bug#20618309 ASSERT SLOT1->PAGE_LEVEL == SLOT2->PAGE_LEVEL, BTR_ESTIMATE_N_ROWS_IN_RANGE() Relax a too strict assert. If the tree is changed between both dives for the left boundary and the right boundary, then our markers (slot1 and slot2) could end up on different levels in the tree. If we detect that this has happened - then retry a few times and if still unsuccessful then return an arbitrary number for an estimate. Reviewed-by: Marko Mäkelä Reviewed-by: Jimmy Yang RB: 8570 Fix bug 84366 (InnoDB index dives do not detect concurrent tree changes, return bogus estimates) In btr_estimate_n_rows_in_range_low, consider that the tree structure has changed, if the two dive paths have crossed, and the same node in the two paths appears to contain a different number of records. If the paths have crossed without a detected tree structure change, return zero estimate immediately. Add waits for purge to complete to stabilize main.index_merge_innodb test. diff --git a/mysql-test/include/index_merge1.inc b/mysql-test/include/index_merge1.inc index da2b9d862c1..031aedda1ed 100644 --- a/mysql-test/include/index_merge1.inc +++ b/mysql-test/include/index_merge1.inc @@ -453,6 +453,10 @@ alter table t3 add keyB int not null, add index iB(keyB); alter table t3 add keyC int not null, add index iC(keyC); update t3 set key9=key1,keyA=key1,keyB=key1,keyC=key1; +# Force complete purge +SET @@GLOBAL.innodb_fast_shutdown = 0; +--source include/restart_mysqld.inc + -- disable_query_log -- disable_result_log analyze table t3; diff --git a/mysql-test/include/index_merge2.inc b/mysql-test/include/index_merge2.inc index e08e9cbcf55..9ae2c82a375 100644 --- a/mysql-test/include/index_merge2.inc +++ b/mysql-test/include/index_merge2.inc @@ -371,6 +371,10 @@ alter table t1 add index i2(key2); alter table t1 add index i3(key3); update t1 set key2=key1,key3=key1; +# Force complete purge +SET @@GLOBAL.innodb_fast_shutdown = 0; +--source include/restart_mysqld.inc + -- disable_query_log -- disable_result_log analyze table t1; diff --git a/mysql-test/include/index_merge_ror.inc b/mysql-test/include/index_merge_ror.inc index e9926e3ed46..bd2a781a748 100644 --- a/mysql-test/include/index_merge_ror.inc +++ b/mysql-test/include/index_merge_ror.inc @@ -183,6 +183,10 @@ select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=1 delete from t1 where key3=100 and key4=100; +# Force complete purge +SET @@GLOBAL.innodb_fast_shutdown = 0; +--source include/restart_mysqld.inc + -- disable_query_log -- disable_result_log analyze table t1; diff --git a/mysql-test/r/index_merge_innodb.result b/mysql-test/r/index_merge_innodb.result index 98d69097140..85d15f77489 100644 --- a/mysql-test/r/index_merge_innodb.result +++ b/mysql-test/r/index_merge_innodb.result @@ -294,6 +294,7 @@ alter table t3 add keyA int not null, add index iA(keyA); alter table t3 add keyB int not null, add index iB(keyB); alter table t3 add keyC int not null, add index iC(keyC); update t3 set key9=key1,keyA=key1,keyB=key1,keyC=key1; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select * from t3 where key1=1 or key2=2 or key3=3 or key4=4 or key5=5 or key6=6 or key7=7 or key8=8 or @@ -702,6 +703,7 @@ select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=1 key1 key2 key3 key4 filler1 -1 -1 100 100 key4-key3 delete from t1 where key3=100 and key4=100; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index_merge key1,key2,key3,key4 key1,key2,key3,key4 5,5,5,5 NULL 4 Using union(intersect(key1,key2),intersect(key3,key4)); Using where @@ -1132,6 +1134,7 @@ set @d=@d*2; alter table t1 add index i2(key2); alter table t1 add index i3(key3); update t1 set key2=key1,key3=key1; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select * from t1 where (key3 > 30 and key3<35) or (key2 >32 and key2 < 40); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index_merge i2,i3 i3,i2 4,4 NULL # Using sort_union(i3,i2); Using where diff --git a/mysql-test/r/index_merge_myisam.result b/mysql-test/r/index_merge_myisam.result index 60463b4aeba..505b59a43dc 100644 --- a/mysql-test/r/index_merge_myisam.result +++ b/mysql-test/r/index_merge_myisam.result @@ -300,6 +300,7 @@ alter table t3 add keyA int not null, add index iA(keyA); alter table t3 add keyB int not null, add index iB(keyB); alter table t3 add keyC int not null, add index iC(keyC); update t3 set key9=key1,keyA=key1,keyB=key1,keyC=key1; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select * from t3 where key1=1 or key2=2 or key3=3 or key4=4 or key5=5 or key6=6 or key7=7 or key8=8 or @@ -732,6 +733,7 @@ select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=1 key1 key2 key3 key4 filler1 -1 -1 100 100 key4-key3 delete from t1 where key3=100 and key4=100; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index_merge key1,key2,key3,key4 key1,key2,key3,key4 5,5,5,5 NULL 152 Using union(intersect(key1,key2),intersect(key3,key4)); Using where @@ -1171,6 +1173,7 @@ set @d=@d*2; alter table t1 add index i2(key2); alter table t1 add index i3(key3); update t1 set key2=key1,key3=key1; +SET @@GLOBAL.innodb_fast_shutdown = 0; explain select * from t1 where (key3 > 30 and key3<35) or (key2 >32 and key2 < 40); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index_merge i2,i3 i3,i2 4,4 NULL 11 Using sort_union(i3,i2); Using where diff --git a/mysql-test/suite/innodb/r/bug84366.result b/mysql-test/suite/innodb/r/bug84366.result new file mode 100644 index 00000000000..9987f860c84 --- /dev/null +++ b/mysql-test/suite/innodb/r/bug84366.result @@ -0,0 +1,26 @@ +# +# Bug 84366: InnoDB index dives do not detect concurrent tree changes, return +# bogus estimates +# +CREATE TABLE t1 (key1 INT NOT NULL, key2 INT NOT NULL, +INDEX i1(key1), INDEX i2(key2)) ENGINE = InnoDB; +SET @@GLOBAL.innodb_purge_stop_now = TRUE; +ALTER TABLE t1 ADD keyC INT NOT NULL, ADD INDEX iC(keyC); +UPDATE t1 SET keyC = key1; +ANALYZE TABLE t1; +Table Op Msg_type Msg_text +test.t1 analyze status OK +EXPLAIN SELECT * FROM t1 WHERE key1 = 1 OR key2 = 2 OR keyC = 12; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index_merge i1,i2,iC i1,i2,iC 4,4,4 NULL 3 Using union(i1,i2,iC); Using where +SET DEBUG_SYNC = "btr_estimate_n_rows_in_range_between_dives SIGNAL estimate_ready WAIT_FOR estimate_finish"; +EXPLAIN SELECT * FROM t1 WHERE key1 = 1 OR key2 = 2 OR keyC = 12; +SET DEBUG_SYNC = "now WAIT_FOR estimate_ready"; +SET @@GLOBAL.innodb_purge_run_now = TRUE; +SET DEBUG_SYNC = "now SIGNAL estimate_finish"; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index_merge i1,i2,iC i1,i2,iC 4,4,4 NULL 3 Using union(i1,i2,iC); Using where +EXPLAIN SELECT * FROM t1 WHERE key1=1 or key2=2 or keyC=12; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index_merge i1,i2,iC i1,i2,iC 4,4,4 NULL 3 Using union(i1,i2,iC); Using where +DROP TABLE t1; diff --git a/mysql-test/suite/innodb/t/bug84366.test b/mysql-test/suite/innodb/t/bug84366.test new file mode 100644 index 00000000000..af13e28b53a --- /dev/null +++ b/mysql-test/suite/innodb/t/bug84366.test @@ -0,0 +1,66 @@ +--source include/have_debug.inc +--source include/have_debug_sync.inc +--source include/have_innodb.inc + +--echo # +--echo # Bug 84366: InnoDB index dives do not detect concurrent tree changes, return +--echo # bogus estimates +--echo # + +--source include/count_sessions.inc + +CREATE TABLE t1 (key1 INT NOT NULL, key2 INT NOT NULL, + INDEX i1(key1), INDEX i2(key2)) ENGINE = InnoDB; + +--disable_query_log +INSERT INTO t1 VALUES (1, 1), (2, 2); + +let $1=9; +SET @d=2; +while ($1) +{ + INSERT INTO t1 SELECT key1 + @d, key2 + @d FROM t1; + SET @d=@d*2; + dec $1; +} +--enable_query_log + +SET @@GLOBAL.innodb_purge_stop_now = TRUE; + +ALTER TABLE t1 ADD keyC INT NOT NULL, ADD INDEX iC(keyC); +UPDATE t1 SET keyC = key1; + +ANALYZE TABLE t1; + +--connect(con1,localhost,root,,) + +EXPLAIN SELECT * FROM t1 WHERE key1 = 1 OR key2 = 2 OR keyC = 12; + +SET DEBUG_SYNC = "btr_estimate_n_rows_in_range_between_dives SIGNAL estimate_ready WAIT_FOR estimate_finish"; + +send EXPLAIN SELECT * FROM t1 WHERE key1 = 1 OR key2 = 2 OR keyC = 12; + +connection default; +SET DEBUG_SYNC = "now WAIT_FOR estimate_ready"; + +SET @@GLOBAL.innodb_purge_run_now = TRUE; + +# wait_innodb_all_purged.inc is not used directly as we wait for the trx age +# to become one, not zero, due to one open transaction +--let $status_var= innodb_purge_trx_id_age +--let $status_var_value= 1 +--source include/wait_for_status_var.inc + +SET DEBUG_SYNC = "now SIGNAL estimate_finish"; + +connection con1; +reap; + +EXPLAIN SELECT * FROM t1 WHERE key1=1 or key2=2 or keyC=12; + +disconnect con1; +connection default; + +DROP TABLE t1; + +--source include/wait_until_count_sessions.inc diff --git a/storage/innobase/btr/btr0cur.cc b/storage/innobase/btr/btr0cur.cc index 1f43fc62b16..45fe805d97c 100644 --- a/storage/innobase/btr/btr0cur.cc +++ b/storage/innobase/btr/btr0cur.cc @@ -3661,18 +3661,40 @@ inexact: return(n_rows); } -/*******************************************************************//** -Estimates the number of rows in a given index range. -@return estimated number of rows */ -UNIV_INTERN -ib_int64_t -btr_estimate_n_rows_in_range( -/*=========================*/ - dict_index_t* index, /*!< in: index */ - const dtuple_t* tuple1, /*!< in: range start, may also be empty tuple */ - ulint mode1, /*!< in: search mode for range start */ - const dtuple_t* tuple2, /*!< in: range end, may also be empty tuple */ - ulint mode2) /*!< in: search mode for range end */ +/** If the tree gets changed too much between the two dives for the left +and right boundary then btr_estimate_n_rows_in_range_low() will retry +that many times before giving up and returning the value stored in +rows_in_range_arbitrary_ret_val. */ +static const unsigned rows_in_range_max_retries = 4; + +/** We pretend that a range has that many records if the tree keeps changing +for rows_in_range_max_retries retries while we try to estimate the records +in a given range. */ +static const int64_t rows_in_range_arbitrary_ret_val = 10; + +/** Estimates the number of rows in a given index range. +@param[in] index index +@param[in] tuple1 range start, may also be empty tuple +@param[in] mode1 search mode for range start +@param[in] tuple2 range end, may also be empty tuple +@param[in] mode2 search mode for range end +@param[in] nth_attempt if the tree gets modified too much while +we are trying to analyze it, then we will retry (this function will call +itself, incrementing this parameter) +@return estimated number of rows; if after rows_in_range_max_retries +retries the tree keeps changing, then we will just return +rows_in_range_arbitrary_ret_val as a result (if +nth_attempt >= rows_in_range_max_retries and the tree is modified between +the two dives). */ +static +int64_t +btr_estimate_n_rows_in_range_low( + dict_index_t* index, + const dtuple_t* tuple1, + ulint mode1, + const dtuple_t* tuple2, + ulint mode2, + unsigned nth_attempt) { btr_path_t path1[BTR_PATH_ARRAY_N_SLOTS]; btr_path_t path2[BTR_PATH_ARRAY_N_SLOTS]; @@ -3708,6 +3730,12 @@ btr_estimate_n_rows_in_range( mtr_commit(&mtr); +#ifdef UNIV_DEBUG + if (!strcmp(index->name, "iC")) { + DEBUG_SYNC_C("btr_estimate_n_rows_in_range_between_dives"); + } +#endif + mtr_start(&mtr); cursor.path_arr = path2; @@ -3776,6 +3804,32 @@ btr_estimate_n_rows_in_range( if (!diverged && slot1->nth_rec != slot2->nth_rec) { + /* If both slots do not point to the same page or if + the paths have crossed and the same page on both + apparently contains a different number of records, + this means that the tree must have changed between + the dive for slot1 and the dive for slot2 at the + beginning of this function. */ + if (slot1->page_no != slot2->page_no + || slot1->page_level != slot2->page_level + || (slot1->nth_rec >= slot2->nth_rec + && slot1->n_recs != slot2->n_recs)) { + + /* If the tree keeps changing even after a + few attempts, then just return some arbitrary + number. */ + if (nth_attempt >= rows_in_range_max_retries) { + return(rows_in_range_arbitrary_ret_val); + } + + const int64_t ret = + btr_estimate_n_rows_in_range_low( + index, tuple1, mode1, + tuple2, mode2, nth_attempt + 1); + + return(ret); + } + diverged = TRUE; if (slot1->nth_rec < slot2->nth_rec) { @@ -3794,7 +3848,7 @@ btr_estimate_n_rows_in_range( in this case slot1->nth_rec will point to the supr record and slot2->nth_rec will point to 6 */ - n_rows = 0; + return(0); } } else if (diverged && !diverged_lot) { @@ -3825,6 +3879,27 @@ btr_estimate_n_rows_in_range( } } +/** Estimates the number of rows in a given index range. +@param[in] index index +@param[in] tuple1 range start, may also be empty tuple +@param[in] mode1 search mode for range start +@param[in] tuple2 range end, may also be empty tuple +@param[in] mode2 search mode for range end +@return estimated number of rows */ +int64_t +btr_estimate_n_rows_in_range( + dict_index_t* index, + const dtuple_t* tuple1, + ulint mode1, + const dtuple_t* tuple2, + ulint mode2) +{ + const int64_t ret = btr_estimate_n_rows_in_range_low( + index, tuple1, mode1, tuple2, mode2, 1 /* first attempt */); + + return(ret); +} + /*******************************************************************//** Record the number of non_null key values in a given index for each n-column prefix of the index where 1 <= n <= dict_index_get_n_unique(index).