From a121e2b0f8c6a7456016c0891e69716d9c4a483a Mon Sep 17 00:00:00 2001 From: hcduan Date: Tue, 6 Jun 2023 16:10:32 +0800 Subject: [PATCH] [bugfix] index merge intersect causes wrong query results Problem: ======= INDEX_MERGE_INTERSECTION causes wrong query results, when PK is in descending order. Due to the default PK order being in ascending order, the rowid is also sorted in ascending order of same prefix of key in the secondary index. While PK is sorted in descending order, when comparing rowids of the RowIDIntersectionIterator, there may be directional errors during recursive comparison. For example, the intersect operator is responsible for merging RowIterator child#1 and RowIterator child#2. When the rowid of child#1 is 6 and the rowid of child#2 is 5. If the PK is arranged in ascending order: it is necessary to continue iterating on child#2 to find a rowid greater than 5 to match child#1's rowid=6. If the PK is arranged in descending order: it is necessary to continue iterating on child#1 to find a rowid less than 6 to match child#2's rowid=5. Solution: ======== Identify the sorting order of the PK. When creating the RowIDIntersectionIterator, we identify the PK sorting order. If sorting in descending order, RowIDIntersectionIterator needs to reverse the iteration direction during READ execution. --- .../r/index_merge_intersect_in_pk_desc.result | 28 ++++++++++ mysql-test/t/index_merge_intersect_in_pk_desc.test | 60 ++++++++++++++++++++++ sql/join_optimizer/access_path.cc | 2 +- sql/join_optimizer/access_path.h | 3 ++ sql/range_optimizer/rowid_ordered_retrieval.cc | 9 +++- sql/range_optimizer/rowid_ordered_retrieval.h | 6 ++- .../rowid_ordered_retrieval_plan.cc | 6 +++ 7 files changed, 111 insertions(+), 3 deletions(-) create mode 100644 mysql-test/r/index_merge_intersect_in_pk_desc.result create mode 100644 mysql-test/t/index_merge_intersect_in_pk_desc.test diff --git a/mysql-test/r/index_merge_intersect_in_pk_desc.result b/mysql-test/r/index_merge_intersect_in_pk_desc.result new file mode 100644 index 0000000..f437f95 --- /dev/null +++ b/mysql-test/r/index_merge_intersect_in_pk_desc.result @@ -0,0 +1,28 @@ +# +# Bug# INDEX_MERGE_INTERSECTION causes wrong query results +# when PK is in descending order. +# +CREATE TABLE t1 ( +pk INT NOT NULL AUTO_INCREMENT, +a INT NOT NULL, +b INT NOT NULL, +c INT NOT NULL, +d INT NOT NULL, +PRIMARY KEY pk (pk desc), +KEY idx_a (a), +KEY idx_b (b), +KEY idx_c (c), +KEY idx_d (d) +); +ANALYZE TABLE t1; +Table Op Msg_type Msg_text +test.t1 analyze status OK +EXPLAIN SELECT COUNT(*), SUM(a) FROM t1 WHERE b=6 AND c=6; +id select_type table partitions type possible_keys key key_len ref rows filtered Extra +1 SIMPLE t1 NULL index_merge idx_b,idx_c idx_b,idx_c 4,4 NULL 1 100.00 Using intersect(idx_b,idx_c); Using where +Warnings: +Note 1003 /* select#1 */ select count(0) AS `COUNT(*)`,sum(`test`.`t1`.`a`) AS `SUM(a)` from `test`.`t1` where ((`test`.`t1`.`c` = 6) and (`test`.`t1`.`b` = 6)) +SELECT COUNT(*), SUM(a) FROM t1 WHERE b=6 AND c=6; +COUNT(*) SUM(a) +15 90 +DROP TABLE t1; diff --git a/mysql-test/t/index_merge_intersect_in_pk_desc.test b/mysql-test/t/index_merge_intersect_in_pk_desc.test new file mode 100644 index 0000000..d20e1a8 --- /dev/null +++ b/mysql-test/t/index_merge_intersect_in_pk_desc.test @@ -0,0 +1,60 @@ +--echo # +--echo # Bug# INDEX_MERGE_INTERSECTION causes wrong query results +--echo # when PK is in descending order. +--echo # +CREATE TABLE t1 ( + pk INT NOT NULL AUTO_INCREMENT, + a INT NOT NULL, + b INT NOT NULL, + c INT NOT NULL, + d INT NOT NULL, + PRIMARY KEY pk (pk desc), + KEY idx_a (a), + KEY idx_b (b), + KEY idx_c (c), + KEY idx_d (d) +); + +--disable_query_log + +# Inserting a lot of rows inorder to enable index_merge intersect + +INSERT INTO t1(a,b,c,d) VALUES + ( RAND()*5, RAND()*5, RAND()*5, RAND()*5 ); + +let $cnt=4; +while ($cnt) +{ + INSERT INTO t1(a,b,c,d) SELECT 6,6,6,6 FROM t1; + dec $cnt; +} + +INSERT INTO t1(a,b,c,d) SELECT 6, RAND()*5, RAND()*5, + RAND()*5 FROM t1 LIMIT 3; +INSERT INTO t1(a,b,c,d) SELECT RAND()*5, 6, RAND()*5, + RAND()*5 FROM t1 LIMIT 3; +INSERT INTO t1(a,b,c,d) SELECT RAND()*5, RAND()*5, 6, + RAND()*5 FROM t1 LIMIT 3; +INSERT INTO t1(a,b,c,d) SELECT RAND()*5, RAND()*5, + RAND()*5, 6 FROM t1 LIMIT 3; + +let $cnt=7; +while ($cnt) +{ + INSERT INTO t1(a,b,c,d) SELECT RAND()*5, RAND()*5, + RAND()*5, RAND()*5 FROM t1; + dec $cnt; +} + +--enable_query_log + +# The following statement analyzes and +# stores the key distribution for a table. + +ANALYZE TABLE t1; + +EXPLAIN SELECT COUNT(*), SUM(a) FROM t1 WHERE b=6 AND c=6; + +SELECT COUNT(*), SUM(a) FROM t1 WHERE b=6 AND c=6; + +DROP TABLE t1; diff --git a/sql/join_optimizer/access_path.cc b/sql/join_optimizer/access_path.cc index 1b9c908..469cc9c 100644 --- a/sql/join_optimizer/access_path.cc +++ b/sql/join_optimizer/access_path.cc @@ -684,7 +684,7 @@ unique_ptr_destroy_only CreateIteratorFromAccessPath( iterator = NewIterator( thd, mem_root, mem_root, param.table, param.retrieve_full_rows, param.need_rows_in_rowid_order, std::move(children), - std::move(cpk_child)); + std::move(cpk_child), param.pk_is_ascending); break; } case AccessPath::ROWID_UNION: { diff --git a/sql/join_optimizer/access_path.h b/sql/join_optimizer/access_path.h index 67bb569..747598c 100644 --- a/sql/join_optimizer/access_path.h +++ b/sql/join_optimizer/access_path.h @@ -1055,6 +1055,9 @@ struct AccessPath { // true if no row retrieval phase is necessary. bool is_covering; + + // false if PK in descending (reverse) order + bool pk_is_ascending; } rowid_intersection; struct { TABLE *table; diff --git a/sql/range_optimizer/rowid_ordered_retrieval.cc b/sql/range_optimizer/rowid_ordered_retrieval.cc index 5f127a2..966d391 100644 --- a/sql/range_optimizer/rowid_ordered_retrieval.cc +++ b/sql/range_optimizer/rowid_ordered_retrieval.cc @@ -47,12 +47,14 @@ RowIDIntersectionIterator::RowIDIntersectionIterator( THD *thd, MEM_ROOT *return_mem_root, TABLE *table_arg, bool retrieve_full_rows, bool need_rows_in_rowid_order, Mem_root_array> children, - unique_ptr_destroy_only cpk_child) + unique_ptr_destroy_only cpk_child, + bool pk_is_ascending) : RowIDCapableRowIterator(thd, table_arg), m_children(move(children)), m_cpk_child(move(cpk_child)), retrieve_full_rows(retrieve_full_rows), scans_inited(false), + pk_is_ascending(pk_is_ascending), need_rows_in_rowid_order(need_rows_in_rowid_order) { m_last_rowid = return_mem_root->ArrayAlloc(table()->file->ref_length); } @@ -366,6 +368,11 @@ int RowIDIntersectionIterator::Read() { return error; } cmp = table()->file->cmp_ref(child_rowid, m_last_rowid); + + if (!pk_is_ascending) { + cmp *= -1; + } + if (cmp < 0) { /* This row is being skipped. Release lock on * it. */ diff --git a/sql/range_optimizer/rowid_ordered_retrieval.h b/sql/range_optimizer/rowid_ordered_retrieval.h index 6007d64..0205783 100644 --- a/sql/range_optimizer/rowid_ordered_retrieval.h +++ b/sql/range_optimizer/rowid_ordered_retrieval.h @@ -65,7 +65,8 @@ class RowIDIntersectionIterator : public RowIDCapableRowIterator { THD *thd, MEM_ROOT *return_mem_root, TABLE *table_arg, bool retrieve_full_rows, bool need_rows_in_rowid_order, Mem_root_array> children, - unique_ptr_destroy_only cpk_child); + unique_ptr_destroy_only cpk_child, + bool pk_is_ascending); ~RowIDIntersectionIterator() override; bool Init() override; @@ -142,6 +143,9 @@ class RowIDIntersectionIterator : public RowIDCapableRowIterator { /* in top-level quick select, true if merged scans where initialized */ bool scans_inited; + // false if PK in descending (reverse) order + bool pk_is_ascending; + const bool need_rows_in_rowid_order; uchar *m_last_rowid; bool inited = false; diff --git a/sql/range_optimizer/rowid_ordered_retrieval_plan.cc b/sql/range_optimizer/rowid_ordered_retrieval_plan.cc index 204ade2..52fb944 100644 --- a/sql/range_optimizer/rowid_ordered_retrieval_plan.cc +++ b/sql/range_optimizer/rowid_ordered_retrieval_plan.cc @@ -1009,6 +1009,12 @@ AccessPath *get_best_ror_intersect( path->rowid_intersection().reuse_handler = reuse_handler; path->rowid_intersection().is_covering = intersect_best->is_covering; + if (table->s->key_info->key_part->key_part_flag & HA_REVERSE_SORT) { + path->rowid_intersection().pk_is_ascending = false; + } else { + path->rowid_intersection().pk_is_ascending = true; + } + trace_ror.add("rows", path->num_output_rows) .add("cost", path->cost) .add("covering", intersect_best->is_covering) -- 1.8.3.1