revision-id: c570e8bc2a8883167cf2f037ae9937c61d7ea07b (mariadb-10.4.28-75-gc570e8b) parent(s): a6780df49b443b172124e7e881ed0bea54d75907 author: Igor Babaev committer: Igor Babaev timestamp: 2023-04-10 20:51:27 -0700 message: MDEV-26301 Split optimization refills temporary table too many times This patch optimizes the number of refills for the lateral derived table to which a materialized derived table subject to split optimization is is converted. This optimized number of refills is now considered as the expected number of refills of the materialized derived table when searching for the best possible splitting of the table. --- mysql-test/main/derived_split_innodb.result | 261 ++++++++++++++++++++++++++++ mysql-test/main/derived_split_innodb.test | 136 +++++++++++++++ sql/opt_split.cc | 148 +++++++++++++--- sql/sql_select.cc | 27 ++- sql/sql_select.h | 29 +++- 5 files changed, 571 insertions(+), 30 deletions(-) diff --git a/mysql-test/main/derived_split_innodb.result b/mysql-test/main/derived_split_innodb.result index 04f79d3..8a6585d 100644 --- a/mysql-test/main/derived_split_innodb.result +++ b/mysql-test/main/derived_split_innodb.result @@ -284,3 +284,264 @@ id select_type table type possible_keys key key_len ref rows Extra 2 DERIVED t4 ALL NULL NULL NULL NULL 40 Using filesort drop table t3, t4; # End of 10.3 tests +# +# MDEV-26301: Split optimization refills temporary table too many times +# +create table t1(a int, b int); +insert into t1 select seq,seq from seq_1_to_5; +create table t2(a int, b int, key(a)); +insert into t2 +select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B; +create table t3(a int, b int, key(a)); +insert into t3 +select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B; +analyze table t1,t2,t3 persistent for all; +Table Op Msg_type Msg_text +test.t1 analyze status Engine-independent statistics collected +test.t1 analyze status OK +test.t2 analyze status Engine-independent statistics collected +test.t2 analyze status Table is already up to date +test.t3 analyze status Engine-independent statistics collected +test.t3 analyze status Table is already up to date +explain +select * from +(t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 5 +1 SIMPLE t2 ref a a 5 test.t1.b 2 Using where +1 SIMPLE t3 ref a a 5 test.t1.b 3 Using where +create table t10 ( +grp_id int, +col1 int, +key(grp_id) +); +insert into t10 +select +A.seq, +B.seq +from +seq_1_to_100 A, +seq_1_to_100 B; +create table t11 ( +col1 int, +col2 int +); +insert into t11 +select A.seq, A.seq from seq_1_to_10 A; +analyze table t10,t11 persistent for all; +Table Op Msg_type Msg_text +test.t10 analyze status Engine-independent statistics collected +test.t10 analyze status Table is already up to date +test.t11 analyze status Engine-independent statistics collected +test.t11 analyze status OK +explain select * from +( +(t1 left join t2 on t2.a=t1.b) +left join t3 on t3.a=t1.b +) left join (select grp_id, count(*) +from t10 left join t11 on t11.col1=t10.col1 +group by grp_id) T on T.grp_id=t1.b; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t1 ALL NULL NULL NULL NULL 5 +1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where +1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where +1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where +2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100 +2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join) +# The important part in the below output is: +# "lateral": 1, +# "query_block": { +# "select_id": 2, +# "r_loops": 5, <-- must be 5, not 30. +analyze format=json select * from +( +(t1 left join t2 on t2.a=t1.b) +left join t3 on t3.a=t1.b +) left join (select grp_id, count(*) +from t10 left join t11 on t11.col1=t10.col1 +group by grp_id) T on T.grp_id=t1.b; +ANALYZE +{ + "query_block": { + "select_id": 1, + "r_loops": 1, + "r_total_time_ms": "REPLACED", + "const_condition": "1", + "table": { + "table_name": "t1", + "access_type": "ALL", + "r_loops": 1, + "rows": 5, + "r_rows": 5, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100 + }, + "table": { + "table_name": "t2", + "access_type": "ref", + "possible_keys": ["a"], + "key": "a", + "key_length": "5", + "used_key_parts": ["a"], + "ref": ["test.t1.b"], + "r_loops": 5, + "rows": 2, + "r_rows": 2, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100, + "attached_condition": "trigcond(trigcond(t1.b is not null))" + }, + "table": { + "table_name": "t3", + "access_type": "ref", + "possible_keys": ["a"], + "key": "a", + "key_length": "5", + "used_key_parts": ["a"], + "ref": ["test.t1.b"], + "r_loops": 10, + "rows": 3, + "r_rows": 3, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100, + "attached_condition": "trigcond(trigcond(t1.b is not null))" + }, + "table": { + "table_name": "<derived2>", + "access_type": "ref", + "possible_keys": ["key0"], + "key": "key0", + "key_length": "5", + "used_key_parts": ["grp_id"], + "ref": ["test.t1.b"], + "r_loops": 30, + "rows": 10, + "r_rows": 1, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100, + "attached_condition": "trigcond(trigcond(t1.b is not null))", + "materialized": { + "lateral": 1, + "query_block": { + "select_id": 2, + "r_loops": 5, + "r_total_time_ms": "REPLACED", + "outer_ref_condition": "t1.b is not null", + "table": { + "table_name": "t10", + "access_type": "ref", + "possible_keys": ["grp_id"], + "key": "grp_id", + "key_length": "5", + "used_key_parts": ["grp_id"], + "ref": ["test.t1.b"], + "r_loops": 5, + "rows": 100, + "r_rows": 100, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100 + }, + "block-nl-join": { + "table": { + "table_name": "t11", + "access_type": "ALL", + "r_loops": 5, + "rows": 10, + "r_rows": 10, + "r_total_time_ms": "REPLACED", + "filtered": 100, + "r_filtered": 100 + }, + "buffer_type": "flat", + "buffer_size": "1Kb", + "join_type": "BNL", + "attached_condition": "trigcond(t11.col1 = t10.col1)", + "r_filtered": 10 + } + } + } + } + } +} +create table t21 (pk int primary key); +insert into t21 values (1),(2),(3); +create table t22 (pk int primary key); +insert into t22 values (1),(2),(3); +explain +select * from +t21, t22, +( +(t1 left join t2 on t2.a=t1.b) +left join t3 on t3.a=t1.b +) left join (select grp_id, count(*) +from t10 left join t11 on t11.col1=t10.col1 +group by grp_id) T on T.grp_id=t1.b +where +t21.pk=1 and t22.pk=2; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index +1 PRIMARY t22 const PRIMARY PRIMARY 4 const 1 Using index +1 PRIMARY t1 ALL NULL NULL NULL NULL 5 +1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where +1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where +1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where +2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100 +2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join) +explain +select * from +t21, +( +(t1 left join t2 on t2.a=t1.b) +left join t3 on t3.a=t1.b +) left join (select grp_id, count(*) +from +t22 join t10 left join t11 on t11.col1=t10.col1 +where +t22.pk=1 +group by grp_id) T on T.grp_id=t1.b +where +t21.pk=1; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index +1 PRIMARY t1 ALL NULL NULL NULL NULL 5 +1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where +1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where +1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where +2 LATERAL DERIVED t22 const PRIMARY PRIMARY 4 const 1 Using index +2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100 +2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join) +create table t5 ( +pk int primary key +); +insert into t5 select seq from seq_1_to_1000; +explain +select * from +t21, +( +(((t1 join t5 on t5.pk=t1.b)) left join t2 on t2.a=t1.b) +left join t3 on t3.a=t1.b +) left join (select grp_id, count(*) +from +t22 join t10 left join t11 on t11.col1=t10.col1 +where +t22.pk=1 +group by grp_id) T on T.grp_id=t1.b +where +t21.pk=1; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index +1 PRIMARY t1 ALL NULL NULL NULL NULL 5 Using where +1 PRIMARY t5 eq_ref PRIMARY PRIMARY 4 test.t1.b 1 Using index +1 PRIMARY t2 ref a a 5 test.t1.b 2 +1 PRIMARY t3 ref a a 5 test.t1.b 3 +1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where +2 LATERAL DERIVED t22 const PRIMARY PRIMARY 4 const 1 Using index +2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t5.pk 100 Using index condition +2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join) +drop table t1,t2,t3,t5, t10, t11, t21, t22; +# End of 10.4 tests diff --git a/mysql-test/main/derived_split_innodb.test b/mysql-test/main/derived_split_innodb.test index 2f74f5f..ab83850 100644 --- a/mysql-test/main/derived_split_innodb.test +++ b/mysql-test/main/derived_split_innodb.test @@ -227,3 +227,139 @@ where t3.b > 15; drop table t3, t4; --echo # End of 10.3 tests + +--source include/have_sequence.inc + +--echo # +--echo # MDEV-26301: Split optimization refills temporary table too many times +--echo # + +# 5 values +create table t1(a int, b int); +insert into t1 select seq,seq from seq_1_to_5; + +# 5 value groups of size 2 each +create table t2(a int, b int, key(a)); +insert into t2 +select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B; + +# 5 value groups of size 3 each +create table t3(a int, b int, key(a)); +insert into t3 +select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B; + +analyze table t1,t2,t3 persistent for all; + +explain +select * from + (t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b; + +# Now, create tables for Groups. + +create table t10 ( + grp_id int, + col1 int, + key(grp_id) +); + +# 100 groups of 100 values each +insert into t10 +select + A.seq, + B.seq +from + seq_1_to_100 A, + seq_1_to_100 B; + +# and X10 multiplier + +create table t11 ( + col1 int, + col2 int +); +insert into t11 +select A.seq, A.seq from seq_1_to_10 A; + +analyze table t10,t11 persistent for all; + +let $q1= +select * from + ( + (t1 left join t2 on t2.a=t1.b) + left join t3 on t3.a=t1.b + ) left join (select grp_id, count(*) + from t10 left join t11 on t11.col1=t10.col1 + group by grp_id) T on T.grp_id=t1.b; + +eval +explain $q1; + +--echo # The important part in the below output is: +--echo # "lateral": 1, +--echo # "query_block": { +--echo # "select_id": 2, +--echo # "r_loops": 5, <-- must be 5, not 30. +--source include/analyze-format.inc + +eval +analyze format=json $q1; + +create table t21 (pk int primary key); +insert into t21 values (1),(2),(3); + +create table t22 (pk int primary key); +insert into t22 values (1),(2),(3); + +# Same as above but throw in a couple of const tables. +explain +select * from + t21, t22, + ( + (t1 left join t2 on t2.a=t1.b) + left join t3 on t3.a=t1.b + ) left join (select grp_id, count(*) + from t10 left join t11 on t11.col1=t10.col1 + group by grp_id) T on T.grp_id=t1.b +where + t21.pk=1 and t22.pk=2; + +explain +select * from + t21, + ( + (t1 left join t2 on t2.a=t1.b) + left join t3 on t3.a=t1.b + ) left join (select grp_id, count(*) + from + t22 join t10 left join t11 on t11.col1=t10.col1 + where + t22.pk=1 + group by grp_id) T on T.grp_id=t1.b +where + t21.pk=1; + +# And also add a non-const table + +create table t5 ( + pk int primary key + ); +insert into t5 select seq from seq_1_to_1000; + +explain +select * from + t21, + ( + (((t1 join t5 on t5.pk=t1.b)) left join t2 on t2.a=t1.b) + left join t3 on t3.a=t1.b + ) left join (select grp_id, count(*) + from + t22 join t10 left join t11 on t11.col1=t10.col1 + where + t22.pk=1 + group by grp_id) T on T.grp_id=t1.b +where + t21.pk=1; + +drop table t1,t2,t3,t5, t10, t11, t21, t22; + +--echo # End of 10.4 tests diff --git a/sql/opt_split.cc b/sql/opt_split.cc index a356335..8d27688 100644 --- a/sql/opt_split.cc +++ b/sql/opt_split.cc @@ -65,7 +65,7 @@ If we have only one equi-join condition then we either push it as for Q1R or we don't. In a general case we may have much more options. Consider the query (Q3) - SELECT + SELECT * FROM t1,t2 (SELECT t3.a, t3.b, MIN(t3.c) as min FROM t3 GROUP BY a,b) t WHERE t.a = t1.a AND t.b = t2.b @@ -102,6 +102,45 @@ If we just drop the index on t3(a,b) the chances that the splitting will be used becomes much lower but they still exists providing that the fanout of the partial join of t1 and t2 is small enough. + + The lateral derived table LT formed as a result of SM optimization applied + to a materialized derived table DT must be joined after all parameters + of splitting has been evaluated, i.e. after all expressions used in the + equalities pushed into DT that make the employed splitting effective + could be evaluated. With the chosen join order all the parameters can be + evaluated after the last table LPT that contains any columns referenced in + the parameters has been joined and the table APT following LPT in the chosen + join order is accessed. + Usually the formed lateral derived table LT is accessed right after the table + LPT. As in such cases table LT must be refilled for each combination of + splitting parameters this table must be populated before each access to LT + and the estimate of the expected number of refills that could be suggested in + such cases is the number of rows in the partial join ending with table LPT. + However in other cases the chosen join order may contain tables between LPT + and LT. + Consider the query (Q4) + SELECT * + FROM t1 JOIN t2 ON t1.b = t2.b + LEFT JOIN (SELECT t3.a, t3.b, MIN(t3.c) as min + FROM t3 GROUP BY a,b) t + ON t.a = t1.a AND t.c > 0 + [WHERE P(t1,t2)]; + Let's assume that the join order t1,t2,t was chosen for this query and + SP optimization was applied to t with splitting over t3.a using the index + on column t3.a. Here the table t1 serves as LPT, t2 as APT while t with + pushed condition t.a = t1.a serves as LT. Note that here LT is accessed + after t2, not right after t1. Here the number of refills of the lateral + derived is not more that the number of key values of t1.a that might be + less than the cardinality of the partial join (t1,t2). That's why it makes + sense to signal that t3 has to be refilled just before t2 is accessed. + However if the cardinality of the partial join (t1,t2) happens to be less + than the cardinality of the partial join (t1) due to additional selective + condition P(t1,t2) then the flag informing about necessity of a new refill + can be set either when accessing t2 or right after it has been joined. + The current code sets such flag right after generating a record of the + partial join with minimal cardinality for all those partial joins that + end between APT and LT. It allows sometimes to push extra conditions + into the lateral derived without any increase of the number of refills. */ /* @@ -248,6 +287,7 @@ class SplM_opt_info : public Sql_alloc double unsplit_card; /* Lastly evaluated execution plan for 'join' with pushed equalities */ SplM_plan_info *last_plan; + double last_refills; SplM_plan_info *find_plan(TABLE *table, uint key, uint parts); }; @@ -831,13 +871,13 @@ SplM_plan_info *SplM_opt_info::find_plan(TABLE *table, uint key, uint parts) static void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start, TABLE *table, uint key, - table_map remaining_tables, + table_map excluded_tables, bool validity_val) { KEYUSE_EXT *keyuse_ext= key_keyuse_ext_start; do { - if (!(keyuse_ext->needed_in_prefix & remaining_tables)) + if (!(keyuse_ext->needed_in_prefix & excluded_tables)) { /* The enabling/disabling flags are set just in KEYUSE_EXT structures. @@ -857,8 +897,11 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start, Choose the best splitting to extend the evaluated partial join @param - record_count estimated cardinality of the extended partial join + idx index for joined table T in current partial join P remaining_tables tables not joined yet + spl_pd_boundary OUT bitmap of the table from P extended by T that + starts the sub-sequence of tables S from which + no conditions are allowed to be pushed into T. @details This function is called during the search for the best execution @@ -873,17 +916,19 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start, splitting the function set it as the true plan of materialization of the table T. The function caches the found plans for materialization of table T - together if the info what key was used for splitting. Next time when + together with the info what key was used for splitting. Next time when the optimizer prefers to use the same key the plan is taken from the cache of plans @retval Pointer to the info on the found plan that employs the pushed equalities if the plan has been chosen, NULL - otherwise. + If the function returns NULL the value of spl_param_tables is set to 0. */ -SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, - table_map remaining_tables) +SplM_plan_info * JOIN_TAB::choose_best_splitting(uint idx, + table_map remaining_tables, + table_map *spl_pd_boundary) { SplM_opt_info *spl_opt_info= table->spl_opt_info; DBUG_ASSERT(spl_opt_info != NULL); @@ -898,6 +943,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, SplM_plan_info *spl_plan= 0; uint best_key= 0; uint best_key_parts= 0; + table_map best_param_tables; /* Check whether there are keys that can be used to join T employing splitting @@ -916,6 +962,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, uint key= keyuse_ext->key; KEYUSE_EXT *key_keyuse_ext_start= keyuse_ext; key_part_map found_parts= 0; + table_map needed_in_prefix= 0; do { if (keyuse_ext->needed_in_prefix & remaining_tables) @@ -941,6 +988,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, KEY *key_info= table->key_info + key; double rec_per_key= key_info->actual_rec_per_key(keyuse_ext->keypart); + needed_in_prefix|= keyuse_ext->needed_in_prefix; if (rec_per_key < best_rec_per_key) { best_table= keyuse_ext->table; @@ -948,6 +996,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, best_key_parts= keyuse_ext->keypart + 1; best_rec_per_key= rec_per_key; best_key_keyuse_ext_start= key_keyuse_ext_start; + best_param_tables= needed_in_prefix; } keyuse_ext++; } @@ -956,8 +1005,30 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, while (keyuse_ext->table == table); } spl_opt_info->last_plan= 0; + double refills= DBL_MAX; + table_map excluded_tables= remaining_tables | this->join->sjm_lookup_tables; if (best_table) { + *spl_pd_boundary= this->table->map; + if (!best_param_tables) + refills= 1; + else + { + table_map last_found= this->table->map; + for (POSITION *pos= &this->join->positions[idx - 1]; ; pos--) + { + if (pos->table->table->map & excluded_tables) + continue; + if (pos->partial_join_cardinality < refills) + { + *spl_pd_boundary= last_found; + refills= pos->partial_join_cardinality; + } + last_found= pos->table->table->map; + if (last_found & best_param_tables) + break; + } + } /* The key for splitting was chosen, look for the plan for this key in the cache @@ -971,7 +1042,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, */ table_map all_table_map= (((table_map) 1) << join->table_count) - 1; reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table, - best_key, remaining_tables, true); + best_key, excluded_tables, true); choose_plan(join, all_table_map & ~join->const_table_map); /* @@ -990,7 +1061,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, spl_opt_info->plan_cache.push_back(spl_plan)) { reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table, - best_key, remaining_tables, false); + best_key, excluded_tables, false); return 0; } @@ -1014,17 +1085,19 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, (char *) join->best_positions, sizeof(POSITION) * join->table_count); reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table, - best_key, remaining_tables, false); + best_key, excluded_tables, false); } + if (spl_plan) { - if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost) + if (refills * spl_plan->cost < spl_opt_info->unsplit_cost) { /* The best plan that employs splitting is cheaper than the plan without splitting */ spl_opt_info->last_plan= spl_plan; + spl_opt_info->last_refills= refills; } } } @@ -1034,11 +1107,14 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, spl_plan= spl_opt_info->last_plan; if (spl_plan) { - startup_cost= record_count * spl_plan->cost; + startup_cost= spl_opt_info->last_refills * spl_plan->cost; records= (ha_rows) (records * spl_plan->split_sel); } else + { startup_cost= spl_opt_info->unsplit_cost; + *spl_pd_boundary= 0; + } return spl_plan; } @@ -1048,8 +1124,8 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, Inject equalities for splitting used by the materialization join @param - excluded_tables used to filter out the equalities that cannot - be pushed. + excluded_tables used to filter out the equalities that are not + to be pushed. @details This function injects equalities pushed into a derived table T for which @@ -1142,7 +1218,7 @@ bool is_eq_cond_injected_for_split_opt(Item_func_eq *eq_item) @param spl_plan info on the splitting plan chosen for the splittable table T - remaining_tables the table T is joined just before these tables + excluded_tables tables that cannot be used in equalities pushed into T is_const_table the table T is a constant table @details @@ -1157,7 +1233,7 @@ bool is_eq_cond_injected_for_split_opt(Item_func_eq *eq_item) */ bool JOIN_TAB::fix_splitting(SplM_plan_info *spl_plan, - table_map remaining_tables, + table_map excluded_tables, bool is_const_table) { SplM_opt_info *spl_opt_info= table->spl_opt_info; @@ -1165,6 +1241,7 @@ bool JOIN_TAB::fix_splitting(SplM_plan_info *spl_plan, JOIN *md_join= spl_opt_info->join; if (spl_plan && !is_const_table) { + is_split_derived= true; memcpy((char *) md_join->best_positions, (char *) spl_plan->best_positions, sizeof(POSITION) * md_join->table_count); @@ -1175,7 +1252,7 @@ bool JOIN_TAB::fix_splitting(SplM_plan_info *spl_plan, reset_validity_vars_for_keyuses(spl_plan->keyuse_ext_start, spl_plan->table, spl_plan->key, - remaining_tables, + excluded_tables, true); } else if (md_join->save_qep) @@ -1211,8 +1288,21 @@ bool JOIN::fix_all_splittings_in_plan() if (tab->table->is_splittable()) { SplM_plan_info *spl_plan= cur_pos->spl_plan; + table_map excluded_tables= (all_tables & ~prev_tables) | + sjm_lookup_tables; + ; + if (spl_plan) + { + POSITION *pos= cur_pos; + table_map spl_pd_boundary= pos->spl_pd_boundary; + do + { + excluded_tables|= pos->table->table->map; + } + while (!((pos--)->table->table->map & spl_pd_boundary)); + } if (tab->fix_splitting(spl_plan, - all_tables & ~prev_tables, + excluded_tables, tablenr < const_tables )) return true; } @@ -1251,13 +1341,21 @@ bool JOIN::inject_splitting_cond_for_all_tables_with_split_opt() continue; SplM_opt_info *spl_opt_info= tab->table->spl_opt_info; JOIN *join= spl_opt_info->join; - /* - Currently the equalities referencing columns of SJM tables with - look-up access cannot be pushed into materialized derived. - */ - if (join->inject_best_splitting_cond((all_tables & ~prev_tables) | - sjm_lookup_tables)) - return true; + table_map excluded_tables= (all_tables & ~prev_tables) | sjm_lookup_tables; + table_map spl_pd_boundary= cur_pos->spl_pd_boundary; + for (POSITION *pos= cur_pos; ; pos--) + { + excluded_tables|= pos->table->table->map; + pos->use_join_buffer= false; + if (pos->table->table->map & spl_pd_boundary) + { + pos->table->split_derived_to_update|= tab->table->map; + break; + } + } + + if (join->inject_best_splitting_cond(excluded_tables)) + return true; } return false; } diff --git a/sql/sql_select.cc b/sql/sql_select.cc index c4fc2d1..ce4a1af 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -7431,6 +7431,7 @@ best_access_path(JOIN *join, MY_BITMAP *eq_join_set= &s->table->eq_join_set; KEYUSE *hj_start_key= 0; SplM_plan_info *spl_plan= 0; + table_map spl_pd_boundary= 0; Range_rowid_filter_cost_info *filter= 0; const char* cause= NULL; enum join_type best_type= JT_UNKNOWN, type= JT_UNKNOWN; @@ -7448,7 +7449,9 @@ best_access_path(JOIN *join, loose_scan_opt.init(join, s, remaining_tables); if (s->table->is_splittable()) - spl_plan= s->choose_best_splitting(record_count, remaining_tables); + spl_plan= s->choose_best_splitting(idx, + remaining_tables, + &spl_pd_boundary); if (s->keyuse) { /* Use key if possible */ @@ -8266,6 +8269,7 @@ best_access_path(JOIN *join, pos->loosescan_picker.loosescan_key= MAX_KEY; pos->use_join_buffer= best_uses_jbuf; pos->spl_plan= spl_plan; + pos->spl_pd_boundary= !spl_plan ? 0 : spl_pd_boundary; pos->range_rowid_filter_info= best_filter; loose_scan_opt.save_to_position(s, loose_scan_pos); @@ -8795,6 +8799,9 @@ optimize_straight_join(JOIN *join, table_map join_tables) pushdown_cond_selectivity= table_cond_selectivity(join, idx, s, join_tables); position->cond_selectivity= pushdown_cond_selectivity; + double partial_join_cardinality= record_count * + pushdown_cond_selectivity; + join->positions[idx].partial_join_cardinality= partial_join_cardinality; ++idx; } @@ -9833,6 +9840,8 @@ best_extension_by_limited_search(JOIN *join, double partial_join_cardinality= current_record_count * pushdown_cond_selectivity; + join->positions[idx].partial_join_cardinality= partial_join_cardinality; + if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables ) { /* Recursively expand the current partial plan */ swap_variables(JOIN_TAB*, join->best_ref[idx], *pos); @@ -13825,7 +13834,8 @@ bool JOIN_TAB::preread_init() DBUG_RETURN(TRUE); if (!(derived->get_unit()->uncacheable & UNCACHEABLE_DEPENDENT) || - derived->is_nonrecursive_derived_with_rec_ref()) + derived->is_nonrecursive_derived_with_rec_ref() || + is_split_derived) preread_init_done= TRUE; if (select && select->quick) select->quick->replace_handler(table->file); @@ -17276,6 +17286,9 @@ void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab, reopt_remaining_tables & ~real_table_bit); } + double partial_join_cardinality= rec_count * + pushdown_cond_selectivity; + join->positions[i].partial_join_cardinality= partial_join_cardinality; (*outer_rec_count) *= pushdown_cond_selectivity; if (!rs->emb_sj_nest) *outer_rec_count= COST_MULT(*outer_rec_count, pos.records_read); @@ -20764,6 +20777,16 @@ sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records) { DBUG_ENTER("sub_select"); + if (join_tab->split_derived_to_update && !end_of_records) + { + table_map tab_map= join_tab->split_derived_to_update; + for (uint i= 0; tab_map; i++, tab_map>>= 1) + { + if (tab_map & 1) + join->map2table[i]->preread_init_done= false; + } + } + if (join_tab->last_inner) { JOIN_TAB *last_inner_tab= join_tab->last_inner; diff --git a/sql/sql_select.h b/sql/sql_select.h index 0dfecc9..638bf73 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -520,6 +520,16 @@ typedef struct st_join_table { bool preread_init_done; + /* true <=> split optimization has been applied to this materialized table */ + bool is_split_derived; + + /* + Bitmap of split materialized derived tables that can be filled just before + this join table is to be joined. All parameters of the split derived tables + belong to tables preceding this join table. + */ + table_map split_derived_to_update; + /* Cost info to the range filter used when joining this join table (Defined when the best join order has been already chosen) @@ -680,9 +690,10 @@ typedef struct st_join_table { void partial_cleanup(); void add_keyuses_for_splitting(); - SplM_plan_info *choose_best_splitting(double record_count, - table_map remaining_tables); - bool fix_splitting(SplM_plan_info *spl_plan, table_map remaining_tables, + SplM_plan_info *choose_best_splitting(uint idx, + table_map remaining_tables, + table_map *spl_pd_boundary); + bool fix_splitting(SplM_plan_info *spl_plan, table_map excluded_tables, bool is_const_table); } JOIN_TAB; @@ -947,9 +958,21 @@ class POSITION */ KEYUSE *key; + /* Cardinality of current partial join ending with this position */ + double partial_join_cardinality; + /* Info on splitting plan used at this position */ SplM_plan_info *spl_plan; + /* + If spl_plan is NULL the value of spl_pd_boundary is 0. Otherwise + spl_pd_boundary contains the bitmap of the table from the current + partial join ending at this position that starts the sub-sequence of + tables S from which no conditions are allowed to be used in the plan + spl_plan for the split table joined at this position. + */ + table_map spl_pd_boundary; + /* Cost info for the range filter used at this position */ Range_rowid_filter_cost_info *range_rowid_filter_info;