[Commits] d90f54d: MDEV-16188 Introduced the notion of adjusted filter gain.

revision-id: d90f54da28fbadf519900d4a696a1aee0b1177c7 (mariadb-10.3.6-114-gd90f54d) parent(s): cd00d03fe2d5b92d4451545e3b15477d027c83d0 author: Igor Babaev committer: Igor Babaev timestamp: 2019-02-14 00:15:48 -0800 message: MDEV-16188 Introduced the notion of adjusted filter gain. Due to inconsistent usage of different cost models to calculate the cost of ref accesses we have to make the calculation of the gain promising by usage a range filter more complex. --- mysql-test/main/key_cache.result | 6 +-- mysql-test/main/range.result | 2 +- mysql-test/main/select.result | 8 ++-- mysql-test/main/select_jcl6.result | 8 ++-- mysql-test/main/select_pkeycache.result | 8 ++-- mysql-test/main/subselect2.result | 2 +- mysql-test/main/subselect_sj2.result | 20 +++++----- mysql-test/main/subselect_sj2.test | 2 + mysql-test/main/subselect_sj2_jcl6.result | 20 +++++----- mysql-test/main/subselect_sj2_mat.result | 20 +++++----- sql/ha_partition.cc | 2 +- sql/rowid_filter.cc | 66 ++++++++++++++++++++++++++++--- sql/rowid_filter.h | 37 ++++++++++------- sql/sql_select.cc | 63 +++++++++++++++++++---------- sql/table.h | 3 +- 15 files changed, 178 insertions(+), 89 deletions(-) diff --git a/mysql-test/main/key_cache.result b/mysql-test/main/key_cache.result index e1f8892..36c75ad 100644 --- a/mysql-test/main/key_cache.result +++ b/mysql-test/main/key_cache.result @@ -739,13 +739,13 @@ p 1019 explain select i from t2 where a='yyyy' and i=3; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t2 ref|filter k1,k2 k1|k2 5|11 const 189 (27%) Using where; Using rowid filter +1 SIMPLE t2 ref k1,k2 k1 5 const 189 Using where select i from t2 where a='yyyy' and i=3; i 3 explain select a from t2 where a='yyyy' and i=3; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t2 ref|filter k1,k2 k1|k2 5|11 const 189 (27%) Using where; Using rowid filter +1 SIMPLE t2 ref k1,k2 k1 5 const 189 Using where select a from t2 where a='yyyy' and i=3 ; a yyyy @@ -753,7 +753,7 @@ select * from information_schema.key_caches where segment_number is null; KEY_CACHE_NAME SEGMENTS SEGMENT_NUMBER FULL_SIZE BLOCK_SIZE USED_BLOCKS UNUSED_BLOCKS DIRTY_BLOCKS READ_REQUESTS READS WRITE_REQUESTS WRITES default 2 NULL 32768 1024 # # 0 3178 24 1552 18 small NULL NULL 1048576 1024 # # 0 0 0 0 0 -keycache1 7 NULL 262143 2048 # # 0 3283 43 1594 30 +keycache1 7 NULL 262143 2048 # # 0 3231 43 1594 30 keycache2 NULL NULL 1048576 1024 # # 0 6 6 3 3 set global keycache1.key_cache_block_size=2*1024; insert into t2 values (7000, 3, 'yyyy'); diff --git a/mysql-test/main/range.result b/mysql-test/main/range.result index a0e04fc..bcb43d1 100644 --- a/mysql-test/main/range.result +++ b/mysql-test/main/range.result @@ -280,7 +280,7 @@ INSERT INTO t1 VALUES (33,5),(33,5),(33,5),(33,5),(34,5),(35,5); EXPLAIN SELECT * FROM t1 WHERE a IN(1,2) AND b=5; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range a,b a 5 NULL 2 Using index condition; Using where +1 SIMPLE t1 ref|filter a,b b|a 5|5 const 15 (5%) Using where; Using rowid filter SELECT * FROM t1 WHERE a IN(1,2) AND b=5; a b DROP TABLE t1; diff --git a/mysql-test/main/select.result b/mysql-test/main/select.result index 7a71c34..f1a976b 100644 --- a/mysql-test/main/select.result +++ b/mysql-test/main/select.result @@ -3475,13 +3475,13 @@ INSERT INTO t2 VALUES EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition -1 SIMPLE t2 ref c c 5 test.t1.a 2 +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using rowid filter EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6 AND a > 0; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition; Using where -1 SIMPLE t2 ref c c 5 test.t1.a 2 +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using rowid filter DROP TABLE t1, t2; create table t1 ( a int unsigned not null auto_increment primary key, diff --git a/mysql-test/main/select_jcl6.result b/mysql-test/main/select_jcl6.result index 8b49623..8f1539b 100644 --- a/mysql-test/main/select_jcl6.result +++ b/mysql-test/main/select_jcl6.result @@ -3486,13 +3486,13 @@ INSERT INTO t2 VALUES EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition; Rowid-ordered scan -1 SIMPLE t2 ref c c 5 test.t1.a 2 Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan; Using rowid filter EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6 AND a > 0; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition; Using where; Rowid-ordered scan -1 SIMPLE t2 ref c c 5 test.t1.a 2 Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan; Using rowid filter DROP TABLE t1, t2; create table t1 ( a int unsigned not null auto_increment primary key, diff --git a/mysql-test/main/select_pkeycache.result b/mysql-test/main/select_pkeycache.result index 7a71c34..f1a976b 100644 --- a/mysql-test/main/select_pkeycache.result +++ b/mysql-test/main/select_pkeycache.result @@ -3475,13 +3475,13 @@ INSERT INTO t2 VALUES EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition -1 SIMPLE t2 ref c c 5 test.t1.a 2 +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using rowid filter EXPLAIN SELECT a, c, d, f FROM t1,t2 WHERE a=c AND b BETWEEN 4 AND 6 AND a > 0; id select_type table type possible_keys key key_len ref rows Extra -1 SIMPLE t1 range PRIMARY,b b 5 NULL 3 Using index condition; Using where -1 SIMPLE t2 ref c c 5 test.t1.a 2 +1 SIMPLE t2 ALL c NULL NULL NULL 18 Using where +1 SIMPLE t1 eq_ref|filter PRIMARY,b PRIMARY|b 4|5 test.t2.c 1 (30%) Using where; Using rowid filter DROP TABLE t1, t2; create table t1 ( a int unsigned not null auto_increment primary key, diff --git a/mysql-test/main/subselect2.result b/mysql-test/main/subselect2.result index 7620842..21bf9aa 100644 --- a/mysql-test/main/subselect2.result +++ b/mysql-test/main/subselect2.result @@ -132,7 +132,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t3 eq_ref PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX PRIMARY 34 test.t3.PARENTID 1 Using where 1 PRIMARY t3 eq_ref PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX PRIMARY 34 test.t3.PARENTID 1 Using where 1 PRIMARY t3 eq_ref PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX PRIMARY 34 test.t3.PARENTID 1 Using where -1 PRIMARY t3 eq_ref PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX PRIMARY 34 test.t3.PARENTID 1 Using where +1 PRIMARY t3 ref|filter PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX FFOLDERID_IDX|CMFLDRPARNT_IDX 34|35 test.t3.PARENTID 1 (29%) Using where; Using rowid filter drop table t1, t2, t3, t4; CREATE TABLE t1 (a int(10) , PRIMARY KEY (a)) Engine=InnoDB; INSERT INTO t1 VALUES (1),(2); diff --git a/mysql-test/main/subselect_sj2.result b/mysql-test/main/subselect_sj2.result index 6b86f5a..649647d 100644 --- a/mysql-test/main/subselect_sj2.result +++ b/mysql-test/main/subselect_sj2.result @@ -1107,11 +1107,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias5.c != alias3.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3) -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3) +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 @@ -1128,11 +1128,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias3.c != alias5.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3) -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3) +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 diff --git a/mysql-test/main/subselect_sj2.test b/mysql-test/main/subselect_sj2.test index 9ed886d..e7dd6e7 100644 --- a/mysql-test/main/subselect_sj2.test +++ b/mysql-test/main/subselect_sj2.test @@ -1223,6 +1223,7 @@ INSERT INTO t2 VALUES (13,'b','b'),(14,'x','x'),(15,'g','g'),(16,'p','p'), (17,'q','q'),(18,'w','w'),(19,'d','d'); +--replace_column 9 # EXPLAIN SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( @@ -1242,6 +1243,7 @@ WHERE alias3.d IN ( # Do the same EXPLAIN SELECT and SELECT # with "alias3.c != alias5.c" instead of "alias5.c != alias3.c" +--replace_column 9 # EXPLAIN SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( diff --git a/mysql-test/main/subselect_sj2_jcl6.result b/mysql-test/main/subselect_sj2_jcl6.result index c523525..62866bd 100644 --- a/mysql-test/main/subselect_sj2_jcl6.result +++ b/mysql-test/main/subselect_sj2_jcl6.result @@ -1123,11 +1123,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias5.c != alias3.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index; Using join buffer (flat, BNL join) -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3); Using join buffer (incremental, BKA join); Key-ordered scan -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (incremental, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (incremental, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index; Using join buffer (flat, BNL join) +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3); Using join buffer (incremental, BKA join); Key-ordered scan +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (incremental, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (incremental, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 @@ -1144,11 +1144,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias3.c != alias5.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index; Using join buffer (flat, BNL join) -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3); Using join buffer (incremental, BKA join); Key-ordered scan -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (incremental, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (incremental, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index; Using join buffer (flat, BNL join) +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3); Using join buffer (incremental, BKA join); Key-ordered scan +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (incremental, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (incremental, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 diff --git a/mysql-test/main/subselect_sj2_mat.result b/mysql-test/main/subselect_sj2_mat.result index c05db8d..91ab00d 100644 --- a/mysql-test/main/subselect_sj2_mat.result +++ b/mysql-test/main/subselect_sj2_mat.result @@ -1109,11 +1109,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias5.c != alias3.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3) -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3) +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 @@ -1130,11 +1130,11 @@ WHERE alias5.b = alias4.b AND ( alias5.b >= alias3.b OR alias3.c != alias5.c ) ); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL 19 -1 PRIMARY alias5 index PRIMARY c 4 NULL 19 Using where; Using index -1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b 1 Using where; FirstMatch(alias3) -1 PRIMARY alias1 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) -1 PRIMARY alias2 ALL NULL NULL NULL NULL 14 Using join buffer (flat, BNL join) +1 PRIMARY alias3 ALL PRIMARY NULL NULL NULL # +1 PRIMARY alias5 index PRIMARY c 4 NULL # Using where; Using index +1 PRIMARY alias4 eq_ref PRIMARY,c PRIMARY 4 test.alias5.b # Using where; FirstMatch(alias3) +1 PRIMARY alias1 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) +1 PRIMARY alias2 ALL NULL NULL NULL NULL # Using join buffer (flat, BNL join) SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3 WHERE alias3.d IN ( SELECT alias4.c FROM t2 AS alias4, t2 AS alias5 diff --git a/sql/ha_partition.cc b/sql/ha_partition.cc index acf20b4..c13b26c 100644 --- a/sql/ha_partition.cc +++ b/sql/ha_partition.cc @@ -6345,7 +6345,7 @@ ha_rows ha_partition::multi_range_read_info(uint keyno, uint n_ranges, { uint i; handler **file; - ha_rows rows; + ha_rows rows= 0; Cost_estimate part_cost; DBUG_ENTER("ha_partition::multi_range_read_info"); DBUG_PRINT("enter", ("partition this: %p", this)); diff --git a/sql/rowid_filter.cc b/sql/rowid_filter.cc index cea0009..4a4869b 100644 --- a/sql/rowid_filter.cc +++ b/sql/rowid_filter.cc @@ -49,6 +49,54 @@ double Range_rowid_filter_cost_info::avg_access_and_eval_gain_per_row( lookup_cost(cont_type); } + +/** + @brief + The average adjusted gain in cost per row of using the filter + + @param access_cost_factor the adjusted cost of access a row + + @details + The current code to estimate the cost of a ref access is quite inconsistent: + in some cases the effect of page buffers is taken into account, for others + just the engine dependent read_time() is employed. That's why the average + cost of one random seek might differ from 1. + The parameter access_cost_factor can be considered as the cost of a random + seek that is used for the given ref access. Changing the cost of a random + seek we have to change the first coefficient in the linear formula by which + we calculate the gain of usage the given filter for a_adj. This function + calculates the value of a_adj. + + @note + Currently we require that access_cost_factor should be a number between + 0.0 and 1.0 +*/ + +inline +double Range_rowid_filter_cost_info::avg_adjusted_gain_per_row( + double access_cost_factor) +{ + return a - (1 - access_cost_factor) * (1 - selectivity); +} + + +/** + @brief + Set the parameters used to choose the filter with the best adjusted gain + + @note + This function must be called before the call of get_adjusted_gain() + for the given filter. +*/ + +inline void +Range_rowid_filter_cost_info::set_adjusted_gain_param(double access_cost_factor) +{ + a_adj= avg_adjusted_gain_per_row(access_cost_factor); + cross_x_adj= b / a_adj; +} + + /** @brief Initialize the cost info structure for a range filter @@ -358,6 +406,7 @@ void TABLE::init_cost_info_for_usable_range_rowid_filters(THD *thd) @param access_key_no The index by which the table is accessed @param records The estimated total number of key tuples with this access + @param access_cost_factor the cost of a random seek to access the table @details The function looks through the array of cost info for range filters @@ -365,8 +414,12 @@ void TABLE::init_cost_info_for_usable_range_rowid_filters(THD *thd) gain with the the ref or range access of the table by access_key_no. As the array is sorted by cross_x in ascending order the function stops the look through as soon as it reaches the first element with - cross_x > records because the range filter for this element and the - range filters for all remaining elements do not promise positive gains + cross_x_adj > records because the range filter for this element and the + range filters for all remaining elements do not promise positive gains. + + @note + It is easy to see that if cross_x[i] > cross_x[j] then + cross_x_adj[i] > cross_x_adj[j] @retval Pointer to the cost info for the range filter that promises the greatest gain, NULL if there is no such range filter @@ -374,7 +427,8 @@ void TABLE::init_cost_info_for_usable_range_rowid_filters(THD *thd) Range_rowid_filter_cost_info * TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, - double records) + double records, + double access_cost_factor) { if (!this || range_rowid_filter_cost_info_elems == 0 || covering_keys.is_set(access_key_no)) @@ -408,13 +462,15 @@ TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, no_filter_usage.is_set(filter->key_no)) continue; - if (records < filter->cross_x) + filter->set_adjusted_gain_param(access_cost_factor); + + if (records < filter->cross_x_adj) { /* Does not make sense to look through the remaining filters */ break; } - curr_gain= filter->get_gain(records); + curr_gain= filter->get_adjusted_gain(records); if (best_filter_gain < curr_gain) { best_filter_gain= curr_gain; diff --git a/sql/rowid_filter.h b/sql/rowid_filter.h index 3195e76..3f8faea 100644 --- a/sql/rowid_filter.h +++ b/sql/rowid_filter.h @@ -396,6 +396,13 @@ class Range_rowid_filter_cost_info : public Sql_alloc /* Used for pruning of the potential range filters */ key_map abs_independent; + /* + These two parameters are used to choose the best range filter + in the function TABLE::best_range_rowid_filter_for_partial_join + */ + double a_adj; + double cross_x_adj; + public: /* The type of the container of the range filter */ Rowid_filter_container_type container_type; @@ -416,30 +423,29 @@ class Range_rowid_filter_cost_info : public Sql_alloc inline double avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type); - /* Get the gain that usage of filter promises for 'rows' key tuples */ - inline double get_gain(double rows) + inline double avg_adjusted_gain_per_row(double access_cost_factor); + + inline void set_adjusted_gain_param(double access_cost_factor); + + /* Get the gain that usage of filter promises for r key tuples */ + inline double get_gain(double r) { - return rows * a - b; + return r * a - b; } - /* - The gain promised by usage of the filter at the assumption that - when the table is accessed without the filter at most worst_seeks - pages are fetched from disk to access the data rows of the table - */ - inline double get_adjusted_gain(double rows, double worst_seeks) + /* Get the adjusted gain that usage of filter promises for r key tuples */ + inline double get_adjusted_gain(double r) { - return get_gain(rows) - - (1 - selectivity) * (rows - MY_MIN(rows, worst_seeks)); + return r * a_adj - b; } /* - The gain promised by usage of the filter + The gain promised by usage of the filter for r key tuples due to less condition evaluations */ - inline double get_cmp_gain(double rows) + inline double get_cmp_gain(double r) { - return rows * (1 - selectivity) / TIME_FOR_COMPARE; + return r * (1 - selectivity) / TIME_FOR_COMPARE; } Rowid_filter_container *create_container(); @@ -455,7 +461,8 @@ class Range_rowid_filter_cost_info : public Sql_alloc friend Range_rowid_filter_cost_info * TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, - double records); + double records, + double access_cost_factor); }; #endif /* ROWID_FILTER_INCLUDED */ diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 3d23134..cec5ff7 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -6981,6 +6981,7 @@ best_access_path(JOIN *join, KEYUSE *hj_start_key= 0; SplM_plan_info *spl_plan= 0; Range_rowid_filter_cost_info *filter= 0; + double filter_cmp_gain= 0; disable_jbuf= disable_jbuf || idx == join->const_tables; @@ -7376,12 +7377,14 @@ best_access_path(JOIN *join, if (records < DBL_MAX) { double rows= record_count * records; + double access_cost_factor= MY_MIN(tmp / rows, 1.0); filter= - table->best_range_rowid_filter_for_partial_join(start_key->key, rows); + table->best_range_rowid_filter_for_partial_join(start_key->key, rows, + access_cost_factor); if (filter) { - tmp-= filter->get_adjusted_gain(rows, s->worst_seeks) - - filter->get_cmp_gain(rows); + filter->get_cmp_gain(rows); + tmp-= filter->get_adjusted_gain(rows) - filter->get_cmp_gain(rows); DBUG_ASSERT(tmp >= 0); } } @@ -7508,12 +7511,14 @@ best_access_path(JOIN *join, if ( s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE) { double rows= record_count * s->found_records; + double access_cost_factor= MY_MIN(tmp / rows, 1.0); uint key_no= s->quick->index; - filter= s->table->best_range_rowid_filter_for_partial_join(key_no, - rows); + filter= + s->table->best_range_rowid_filter_for_partial_join(key_no, rows, + access_cost_factor); if (filter) { - tmp-= filter->get_gain(rows); + tmp-= filter->get_adjusted_gain(rows); DBUG_ASSERT(tmp >= 0); } } @@ -7556,7 +7561,6 @@ best_access_path(JOIN *join, } } - double best_records= rnd_records; /* Splitting technique cannot be used with join cache */ if (s->table->is_splittable()) tmp+= s->table->get_materialization_cost(); @@ -7569,28 +7573,32 @@ best_access_path(JOIN *join, tmp give us total cost of using TABLE SCAN */ - double filter_cmp_gain= 0; - if (filter) + double best_filter_cmp_gain= 0; + if (best_filter) { - filter_cmp_gain= filter->get_cmp_gain(record_count * s->found_records); + best_filter_cmp_gain= best_filter->get_cmp_gain(record_count * records); } if (best == DBL_MAX || (tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records < (best_key->is_for_hash_join() ? best_time : best + record_count/(double) TIME_FOR_COMPARE*records - - filter_cmp_gain))) + best_filter_cmp_gain))) { /* If the table has a range (s->quick is set) make_join_select() will ensure that this will be used */ best= tmp; - records= best_records; + records= rnd_records; best_key= 0; best_filter= 0; - if (s->quick && s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE) + if (s->quick && s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE && + filter) + { best_filter= filter; + best_filter_cmp_gain= filter_cmp_gain; + } /* range/index_merge/ALL/index access method are "independent", so: */ best_ref_depends_map= 0; best_uses_jbuf= MY_TEST(!disable_jbuf && !((s->table->map & @@ -8091,14 +8099,22 @@ optimize_straight_join(JOIN *join, table_map join_tables) for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) { - /* Find the best access method from 's' to the current partial plan */ + POSITION *position= join->positions + idx; + /* Find the best access method from 's' to the current partial plan */ best_access_path(join, s, join_tables, idx, disable_jbuf, record_count, - join->positions + idx, &loose_scan_pos); + position, &loose_scan_pos); /* compute the cost of the new plan extended with 's' */ - record_count*= join->positions[idx].records_read; - read_time+= join->positions[idx].read_time + - record_count / (double) TIME_FOR_COMPARE; + record_count*= position->records_read; + double filter_cmp_gain= 0; + if (position->range_rowid_filter_info) + { + filter_cmp_gain= + position->range_rowid_filter_info->get_cmp_gain(record_count); + } + read_time+= position->read_time + + record_count / (double) TIME_FOR_COMPARE - + filter_cmp_gain; advance_sj_state(join, join_tables, idx, &record_count, &read_time, &loose_scan_pos); @@ -8107,7 +8123,7 @@ optimize_straight_join(JOIN *join, table_map join_tables) if (use_cond_selectivity > 1) pushdown_cond_selectivity= table_cond_selectivity(join, idx, s, join_tables); - join->positions[idx].cond_selectivity= pushdown_cond_selectivity; + position->cond_selectivity= pushdown_cond_selectivity; ++idx; } @@ -9006,8 +9022,15 @@ best_extension_by_limited_search(JOIN *join, current_record_count= record_count * position->records_read; else current_record_count= DBL_MAX; + double filter_cmp_gain= 0; + if (position->range_rowid_filter_info) + { + filter_cmp_gain= + position->range_rowid_filter_info->get_cmp_gain(current_record_count); + } current_read_time=read_time + position->read_time + - current_record_count / (double) TIME_FOR_COMPARE; + current_record_count / (double) TIME_FOR_COMPARE - + filter_cmp_gain; advance_sj_state(join, remaining_tables, idx, ¤t_record_count, ¤t_read_time, &loose_scan_pos); diff --git a/sql/table.h b/sql/table.h index 377176f..af38082 100644 --- a/sql/table.h +++ b/sql/table.h @@ -1524,7 +1524,8 @@ struct TABLE void prune_range_rowid_filters(); Range_rowid_filter_cost_info * best_range_rowid_filter_for_partial_join(uint access_key_no, - double records); + double records, + double access_cost_factor); /** System Versioning support