revision-id: 6c9919baaf1e45830cd10f7c4d139c0746c2fc30 (mariadb-10.4.4-377-g6c9919baaf1) parent(s): 4512fe80b9b0cdc6d540f85b3d37934b0edd4bba author: Varun Gupta committer: Varun Gupta timestamp: 2019-12-17 03:09:48 +0530 message: Extend the join prefix to ensure all tables in the duplicate range either are inside or outside the sort nest --- mysql-test/main/sort_nest.result | 73 ++++++++++++++++++++++++++++++++++++++++ mysql-test/main/sort_nest.test | 46 +++++++++++++++++++++++++ sql/opt_subselect.cc | 13 +++++++ sql/sql_select.cc | 9 ++--- sql/sql_select.h | 14 ++++++-- sql/sql_sort_nest.cc | 44 ++++++++++++++++++++++-- 6 files changed, 188 insertions(+), 11 deletions(-) diff --git a/mysql-test/main/sort_nest.result b/mysql-test/main/sort_nest.result index 08e5b557a2f..a9de5b8b156 100644 --- a/mysql-test/main/sort_nest.result +++ b/mysql-test/main/sort_nest.result @@ -2919,3 +2919,76 @@ a b a b 1 1 1 1 0 0 0 0 DROP TABLE t0,t1,t2,t3; +# +# Ensure all tables in Duplicate weedout range are either inside +# or outside the sort nest +# +CREATE TABLE t0(a int); +CREATE TABLE t1 (a int, b int, c int, key(b)); +CREATE TABLE t2 (a int, b int, c int); +CREATE TABLE t3 (a int, b int, c int, key(a)); +CREATE TABLE t4 (a int, b int, c int, key(a)); +INSERT INTO t0 SELECT seq-1 FROM seq_1_to_10; +INSERT INTO t1 SELECT seq-1, seq-1, seq-1 FROM seq_1_to_100; +INSERT INTO t2 SELECT a,a,a FROM t0; +INSERT INTO t2 (a,b,c) values (9,9,9); +INSERT INTO t3 SELECT a,a,a FROM t0; +INSERT INTO t4 SELECT a,a,a FROM t0; +ANALYZE TABLE t0 PERSISTENT FOR ALL; +ANALYZE TABLE t1 PERSISTENT FOR ALL; +ANALYZE TABLE t2 PERSISTENT FOR ALL; +ANALYZE TABLE t3 PERSISTENT FOR ALL; +ANALYZE TABLE t4 PERSISTENT FOR ALL; +set optimizer_switch='cost_based_order_by_limit=on'; +EXPLAIN SELECT t1.a, t2.a, t1.b,t2.b +FROM t1, t2 +WHERE t1.a=t2.a AND +t1.b IN (SELECT t3.b FROM t3,t4 +WHERE t3.c < 10 AND t4.a=t2.b) +ORDER BY t1.b DESC +LIMIT 5; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t3 ALL NULL NULL NULL NULL 10 Using where; Start temporary; Using temporary; Using filesort +1 PRIMARY t1 ref b b 5 test.t3.b 1 +1 PRIMARY t2 ALL NULL NULL NULL NULL 11 Using where; Using join buffer (flat, BNL join) +1 PRIMARY t4 ref a a 5 test.t2.b 1 Using index; End temporary +SELECT t1.a, t2.a, t1.b,t2.b +FROM t1, t2 +WHERE t1.a=t2.a AND +t1.b IN (SELECT t3.b FROM t3,t4 +WHERE t3.c < 10 AND t4.a=t2.b) +ORDER BY t1.b DESC +LIMIT 5; +a a b b +9 9 9 9 +9 9 9 9 +8 8 8 8 +7 7 7 7 +6 6 6 6 +set optimizer_switch='cost_based_order_by_limit=off'; +EXPLAIN SELECT t1.a, t2.a, t1.b,t2.b +FROM t1, t2 +WHERE t1.a=t2.a AND +t1.b IN (SELECT t3.b FROM t3,t4 +WHERE t3.c < 10 AND t4.a=t2.b) +ORDER BY t1.b DESC +LIMIT 5; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t3 ALL NULL NULL NULL NULL 10 Using where; Start temporary; Using temporary; Using filesort +1 PRIMARY t1 ref b b 5 test.t3.b 1 +1 PRIMARY t2 ALL NULL NULL NULL NULL 11 Using where; Using join buffer (flat, BNL join) +1 PRIMARY t4 ref a a 5 test.t2.b 1 Using index; End temporary +SELECT t1.a, t2.a, t1.b,t2.b +FROM t1, t2 +WHERE t1.a=t2.a AND +t1.b IN (SELECT t3.b FROM t3,t4 +WHERE t3.c < 10 AND t4.a=t2.b) +ORDER BY t1.b DESC +LIMIT 5; +a a b b +9 9 9 9 +9 9 9 9 +8 8 8 8 +7 7 7 7 +6 6 6 6 +drop table t0,t1,t2,t3,t4; diff --git a/mysql-test/main/sort_nest.test b/mysql-test/main/sort_nest.test index ef50167d412..952d0bc8c5a 100644 --- a/mysql-test/main/sort_nest.test +++ b/mysql-test/main/sort_nest.test @@ -1177,3 +1177,49 @@ eval EXPLAIN FORMAT=JSON $query; eval $query; DROP TABLE t0,t1,t2,t3; + +--echo # +--echo # Ensure all tables in Duplicate weedout range are either inside +--echo # or outside the sort nest +--echo # + +CREATE TABLE t0(a int); +CREATE TABLE t1 (a int, b int, c int, key(b)); +CREATE TABLE t2 (a int, b int, c int); +CREATE TABLE t3 (a int, b int, c int, key(a)); +CREATE TABLE t4 (a int, b int, c int, key(a)); + +INSERT INTO t0 SELECT seq-1 FROM seq_1_to_10; +INSERT INTO t1 SELECT seq-1, seq-1, seq-1 FROM seq_1_to_100; +INSERT INTO t2 SELECT a,a,a FROM t0; +INSERT INTO t2 (a,b,c) values (9,9,9); +INSERT INTO t3 SELECT a,a,a FROM t0; +INSERT INTO t4 SELECT a,a,a FROM t0; + +--disable_result_log +ANALYZE TABLE t0 PERSISTENT FOR ALL; +ANALYZE TABLE t1 PERSISTENT FOR ALL; +ANALYZE TABLE t2 PERSISTENT FOR ALL; +ANALYZE TABLE t3 PERSISTENT FOR ALL; +ANALYZE TABLE t4 PERSISTENT FOR ALL; +--enable_result_log + +let $query= SELECT t1.a, t2.a, t1.b,t2.b + FROM t1, t2 + WHERE t1.a=t2.a AND + t1.b IN (SELECT t3.b FROM t3,t4 + WHERE t3.c < 10 AND t4.a=t2.b) + ORDER BY t1.b DESC + LIMIT 5; + + +set optimizer_switch='cost_based_order_by_limit=on'; +eval EXPLAIN $query; +eval $query; + +set optimizer_switch='cost_based_order_by_limit=off'; +eval EXPLAIN $query; +eval $query; + +drop table t0,t1,t2,t3,t4; + diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc index 822240dcfac..d7e2760394d 100644 --- a/sql/opt_subselect.cc +++ b/sql/opt_subselect.cc @@ -3513,6 +3513,19 @@ bool Duplicate_weedout_picker::check_qep(JOIN *join, } +bool +Duplicate_weedout_picker::sort_nest_allowed_for_sj(table_map prefix_tables) +{ + /* + The check here is to ensure that either all the tables involve in + the duplicate weedout strategy are COMPLETELY outside the join prefix + or are COMPLETELY inside the join prefix + */ + if (!dupsweedout_tables || !(~prefix_tables & dupsweedout_tables)) + return TRUE; + return FALSE; +} + /* Remove the last join tab from from join->cur_sj_inner_tables bitmap we assume remaining_tables doesnt contain @tab. diff --git a/sql/sql_select.cc b/sql/sql_select.cc index b87dc39fc06..2e120067229 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -9611,7 +9611,7 @@ best_extension_by_limited_search(JOIN *join, } /* - Join buffering should be not considered in 2 cases + Join buffering should not be considered in 2 cases 1) if join_cache_level = 0 that is join buffering is disabled 2) if the limit was pushed to a prefix of the join that can resolve the ORDER BY clause @@ -9761,15 +9761,10 @@ best_extension_by_limited_search(JOIN *join, s->check_if_index_satisfies_ordering(index_used)) limit_applied_to_nest= TRUE; - /* - TODO varun: - 1) get an optimizer switch to enable or disable the sort - nest instead of a system variable - */ if (!nest_created && (join->prefix_resolves_ordering || join->consider_adding_sort_nest(sort_nest_tables | - real_table_bit))) + real_table_bit, idx))) { // SORT_NEST branch join->positions[idx].sort_nest_operation_here= TRUE; diff --git a/sql/sql_select.h b/sql/sql_select.h index ec86ae346ed..686cf237a40 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -739,6 +739,12 @@ class Semi_join_strategy_picker virtual void mark_used() = 0; + /* + Check if a sort nest can be added to a prefix of the join(which may + include the inner tables of a semi join). + */ + virtual bool sort_nest_allowed_for_sj(table_map prefix_tables) = 0; + virtual ~Semi_join_strategy_picker() {} }; @@ -779,6 +785,7 @@ class Duplicate_weedout_picker : public Semi_join_strategy_picker struct st_position *loose_scan_pos); void mark_used() { is_used= TRUE; } + bool sort_nest_allowed_for_sj(table_map remaining_tables); friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join); }; @@ -824,6 +831,7 @@ class Firstmatch_picker : public Semi_join_strategy_picker struct st_position *loose_scan_pos); void mark_used() { is_used= TRUE; } + bool sort_nest_allowed_for_sj(table_map remaining_tables) { return TRUE; } friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join); }; @@ -866,7 +874,7 @@ class LooseScan_picker : public Semi_join_strategy_picker sj_strategy_enum *strategy, struct st_position *loose_scan_pos); void mark_used() { is_used= TRUE; } - + bool sort_nest_allowed_for_sj(table_map remaining_tables) { return TRUE; } friend class Loose_scan_opt; friend void best_access_path(JOIN *join, JOIN_TAB *s, @@ -916,6 +924,7 @@ class Sj_materialization_picker : public Semi_join_strategy_picker sj_strategy_enum *strategy, struct st_position *loose_scan_pos); void mark_used() { is_used= TRUE; } + bool sort_nest_allowed_for_sj(table_map remaining_tables) { return TRUE; } friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join); }; @@ -1956,7 +1965,8 @@ class JOIN :public Sql_alloc void setup_range_scan(JOIN_TAB *tab, uint idx, double records); bool is_join_buffering_allowed(JOIN_TAB *tab); bool check_join_prefix_resolves_ordering(table_map previous_tables); - bool consider_adding_sort_nest(table_map previous_tables); + bool consider_adding_sort_nest(table_map previous_tables, uint idx); + bool is_duplicate_removal_ensured(table_map prefix_tables, uint idx); void set_fraction_output_for_nest(); double sort_nest_oper_cost(double join_record_count, uint idx, ulong rec_len); diff --git a/sql/sql_sort_nest.cc b/sql/sql_sort_nest.cc index 18d2a596587..847d047126c 100644 --- a/sql/sql_sort_nest.cc +++ b/sql/sql_sort_nest.cc @@ -1446,18 +1446,58 @@ bool JOIN::sort_nest_allowed() FALSE otherwise */ -bool JOIN::consider_adding_sort_nest(table_map prefix_tables) +bool JOIN::consider_adding_sort_nest(table_map prefix_tables, uint idx) { if (!sort_nest_possible || // (1) get_cardinality_estimate || // (2) cur_embedding_map || // (3) - cur_sj_inner_tables) // (4) + cur_sj_inner_tables || // (4) + !is_duplicate_removal_ensured(prefix_tables, idx)) return FALSE; return check_join_prefix_resolves_ordering(prefix_tables); // (5) } +/* + @brief + Check if the join prefix ensures duplicate removal for semi joins + + @details + This function checks for all the semi join strategies, if the join + prefix can ensure duplicate removal if a sort nest is considered + on the join prefix. + + @retval + TRUE Duplicate removal is ensured + FALSE Otherwise +*/ + +bool +JOIN::is_duplicate_removal_ensured(table_map prefix_tables, uint idx) +{ + if (!select_lex->have_merged_subqueries) + return TRUE; + + POSITION *pos= positions + idx; + Semi_join_strategy_picker *pickers[]= + { + &pos->firstmatch_picker, + &pos->loosescan_picker, + &pos->sjmat_picker, + &pos->dups_weedout_picker, + NULL, + }; + Semi_join_strategy_picker **strategy; + for (strategy= pickers; *strategy != NULL; strategy++) + { + if (!(*strategy)->sort_nest_allowed_for_sj(prefix_tables)) + return FALSE; + } + return TRUE; +} + + /* @brief Check if indexes on a table are allowed to resolve the ORDER BY clause