[Commits] 322f916: MDEV-16188: Rearchitected the classes for rowid filters.

revision-id: 322f91664bac5692e86e986778bcd7adfb743ede (mariadb-10.3.6-103-g322f916) parent(s): 8a9532f2cc1a8eeb53ff04ca2c28b4756afc845b author: Igor Babaev committer: Igor Babaev timestamp: 2019-01-19 23:53:47 -0800 message: MDEV-16188: Rearchitected the classes for rowid filters. Also consistently renamed variables and functions where rowid filters were used. --- mysql-test/main/show_explain.cc | 0 mysql-test/main/show_explain.result | 8 - mysql-test/main/show_explain.test | 10 - mysql-test/main/subselect_sj2.result | 5 + mysql-test/main/subselect_sj2.test | 2 + mysql-test/main/subselect_sj2_jcl6.result | 13 ++ mysql-test/main/subselect_sj2_jcl6.test | 11 + mysql-test/main/subselect_sj2_mat.result | 5 + sql/opt_subselect.h | 2 +- sql/rowid_filter.cc | 158 ++++++++------ sql/rowid_filter.h | 330 ++++++++++++++---------------- sql/sql_select.cc | 65 +++--- sql/sql_select.h | 14 +- sql/table.cc | 6 +- sql/table.h | 17 +- 15 files changed, 332 insertions(+), 314 deletions(-) diff --git a/mysql-test/main/show_explain.cc b/mysql-test/main/show_explain.cc new file mode 100644 index 0000000..e69de29 diff --git a/mysql-test/main/show_explain.result b/mysql-test/main/show_explain.result index 4cf6b66..32364d0 100644 --- a/mysql-test/main/show_explain.result +++ b/mysql-test/main/show_explain.result @@ -1,8 +1,3 @@ -set @innodb_stats_persistent_save= @@innodb_stats_persistent; -set @innodb_stats_persistent_sample_pages_save= -@@innodb_stats_persistent_sample_pages; -set global innodb_stats_persistent= 1; -set global innodb_stats_persistent_sample_pages=100; drop table if exists t0, t1, t2, t3, t4; drop view if exists v1; SET @old_debug= @@session.debug; @@ -1320,6 +1315,3 @@ drop table t0,t1,t2; connection default; disconnect con1; set debug_sync='RESET'; -set global innodb_stats_persistent= @innodb_stats_persistent_save; -set global innodb_stats_persistent_sample_pages= -@innodb_stats_persistent_sample_pages_save; diff --git a/mysql-test/main/show_explain.test b/mysql-test/main/show_explain.test index 4145e79..6647ca0 100644 --- a/mysql-test/main/show_explain.test +++ b/mysql-test/main/show_explain.test @@ -4,12 +4,6 @@ --source include/have_debug.inc --source include/have_innodb.inc -set @innodb_stats_persistent_save= @@innodb_stats_persistent; -set @innodb_stats_persistent_sample_pages_save= - @@innodb_stats_persistent_sample_pages; - -set global innodb_stats_persistent= 1; -set global innodb_stats_persistent_sample_pages=100; --disable_warnings drop table if exists t0, t1, t2, t3, t4; @@ -1211,7 +1205,3 @@ connection default; disconnect con1; set debug_sync='RESET'; -set global innodb_stats_persistent= @innodb_stats_persistent_save; -set global innodb_stats_persistent_sample_pages= - @innodb_stats_persistent_sample_pages_save; - diff --git a/mysql-test/main/subselect_sj2.result b/mysql-test/main/subselect_sj2.result index 9025dce..e5ed30c 100644 --- a/mysql-test/main/subselect_sj2.result +++ b/mysql-test/main/subselect_sj2.result @@ -1251,6 +1251,11 @@ INSERT IGNORE INTO t2 (t2id, t1idref) SELECT t1id, t1id FROM t1; INSERT IGNORE INTO t1 VALUES (200001, 'a'); INSERT IGNORE INTO t2 (t2id, t1idref) VALUES (200011, 200001),(200012, 200001),(200013, 200001); INSERT IGNORE INTO t3 VALUES (1, 200011, 1), (1, 200012, 2), (1, 200013, 3); +ANALYZE TABLE t1,t2,t3; +Table Op Msg_type Msg_text +test.t1 analyze status OK +test.t2 analyze status OK +test.t3 analyze status OK set @tmp7474= @@optimizer_search_depth; SET SESSION optimizer_search_depth = 1; SELECT SQL_NO_CACHE diff --git a/mysql-test/main/subselect_sj2.test b/mysql-test/main/subselect_sj2.test index e04c15f..9ed886d 100644 --- a/mysql-test/main/subselect_sj2.test +++ b/mysql-test/main/subselect_sj2.test @@ -1395,6 +1395,8 @@ INSERT IGNORE INTO t1 VALUES (200001, 'a'); INSERT IGNORE INTO t2 (t2id, t1idref) VALUES (200011, 200001),(200012, 200001),(200013, 200001); INSERT IGNORE INTO t3 VALUES (1, 200011, 1), (1, 200012, 2), (1, 200013, 3); +ANALYZE TABLE t1,t2,t3; + set @tmp7474= @@optimizer_search_depth; SET SESSION optimizer_search_depth = 1; diff --git a/mysql-test/main/subselect_sj2_jcl6.result b/mysql-test/main/subselect_sj2_jcl6.result index 5dcaa08..b930bdc 100644 --- a/mysql-test/main/subselect_sj2_jcl6.result +++ b/mysql-test/main/subselect_sj2_jcl6.result @@ -1267,6 +1267,11 @@ INSERT IGNORE INTO t2 (t2id, t1idref) SELECT t1id, t1id FROM t1; INSERT IGNORE INTO t1 VALUES (200001, 'a'); INSERT IGNORE INTO t2 (t2id, t1idref) VALUES (200011, 200001),(200012, 200001),(200013, 200001); INSERT IGNORE INTO t3 VALUES (1, 200011, 1), (1, 200012, 2), (1, 200013, 3); +ANALYZE TABLE t1,t2,t3; +Table Op Msg_type Msg_text +test.t1 analyze status OK +test.t2 analyze status OK +test.t3 analyze status OK set @tmp7474= @@optimizer_search_depth; SET SESSION optimizer_search_depth = 1; SELECT SQL_NO_CACHE @@ -1371,6 +1376,11 @@ set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; set optimizer_switch=@subselect_sj2_tmp; +set @innodb_stats_persistent_save= @@innodb_stats_persistent; +set @innodb_stats_persistent_sample_pages_save= +@@innodb_stats_persistent_sample_pages; +set global innodb_stats_persistent= 1; +set global innodb_stats_persistent_sample_pages=100; # # Bug #898073: potential incremental join cache for semijoin # @@ -1463,6 +1473,9 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 2 +set global innodb_stats_persistent= @innodb_stats_persistent_save; +set global innodb_stats_persistent_sample_pages= +@innodb_stats_persistent_sample_pages_save; set @@optimizer_switch=@save_optimizer_switch_jcl6; set @optimizer_switch_for_subselect_sj2_test=NULL; set @join_cache_level_subselect_sj2_test=NULL; diff --git a/mysql-test/main/subselect_sj2_jcl6.test b/mysql-test/main/subselect_sj2_jcl6.test index 7ff0871..9be6102 100644 --- a/mysql-test/main/subselect_sj2_jcl6.test +++ b/mysql-test/main/subselect_sj2_jcl6.test @@ -16,6 +16,13 @@ set @join_cache_level_for_subselect_sj2_test=@@join_cache_level; --source subselect_sj2.test +set @innodb_stats_persistent_save= @@innodb_stats_persistent; +set @innodb_stats_persistent_sample_pages_save= + @@innodb_stats_persistent_sample_pages; + +set global innodb_stats_persistent= 1; +set global innodb_stats_persistent_sample_pages=100; + --echo # --echo # Bug #898073: potential incremental join cache for semijoin --echo # @@ -107,6 +114,10 @@ DROP TABLE t1,t2; set join_cache_level=default; show variables like 'join_cache_level'; +set global innodb_stats_persistent= @innodb_stats_persistent_save; +set global innodb_stats_persistent_sample_pages= + @innodb_stats_persistent_sample_pages_save; + set @@optimizer_switch=@save_optimizer_switch_jcl6; set @optimizer_switch_for_subselect_sj2_test=NULL; set @join_cache_level_subselect_sj2_test=NULL; diff --git a/mysql-test/main/subselect_sj2_mat.result b/mysql-test/main/subselect_sj2_mat.result index 29a3737..65dfddc 100644 --- a/mysql-test/main/subselect_sj2_mat.result +++ b/mysql-test/main/subselect_sj2_mat.result @@ -1253,6 +1253,11 @@ INSERT IGNORE INTO t2 (t2id, t1idref) SELECT t1id, t1id FROM t1; INSERT IGNORE INTO t1 VALUES (200001, 'a'); INSERT IGNORE INTO t2 (t2id, t1idref) VALUES (200011, 200001),(200012, 200001),(200013, 200001); INSERT IGNORE INTO t3 VALUES (1, 200011, 1), (1, 200012, 2), (1, 200013, 3); +ANALYZE TABLE t1,t2,t3; +Table Op Msg_type Msg_text +test.t1 analyze status OK +test.t2 analyze status OK +test.t3 analyze status OK set @tmp7474= @@optimizer_search_depth; SET SESSION optimizer_search_depth = 1; SELECT SQL_NO_CACHE diff --git a/sql/opt_subselect.h b/sql/opt_subselect.h index 846add7..e81b100 100644 --- a/sql/opt_subselect.h +++ b/sql/opt_subselect.h @@ -303,7 +303,7 @@ class Loose_scan_opt pos->loosescan_picker.loosescan_parts= best_max_loose_keypart + 1; pos->use_join_buffer= FALSE; pos->table= tab; - pos->filter= tab->filter; + pos->range_rowid_filter_info= tab->range_rowid_filter_info; // todo need ref_depend_map ? DBUG_PRINT("info", ("Produced a LooseScan plan, key %s, %s", tab->table->key_info[best_loose_scan_key].name.str, diff --git a/sql/rowid_filter.cc b/sql/rowid_filter.cc index 7af9c4e..6b357e1 100644 --- a/sql/rowid_filter.cc +++ b/sql/rowid_filter.cc @@ -6,11 +6,11 @@ #include "sql_select.h" inline -double Range_filter_cost_info::lookup_cost( - Rowid_filter_container_type cont_type) +double Range_rowid_filter_cost_info::lookup_cost( + Rowid_filter_container_type cont_type) { switch (cont_type) { - case ORDERED_ARRAY_CONTAINER: + case SORTED_ARRAY_CONTAINER: return log(est_elements)*0.01; default: DBUG_ASSERT(0); @@ -20,8 +20,8 @@ double Range_filter_cost_info::lookup_cost( inline -double Range_filter_cost_info::avg_access_and_eval_gain_per_row( - Rowid_filter_container_type cont_type) +double Range_rowid_filter_cost_info::avg_access_and_eval_gain_per_row( + Rowid_filter_container_type cont_type) { return (1+1.0/TIME_FOR_COMPARE) * (1 - selectivity) - lookup_cost(cont_type); @@ -33,8 +33,8 @@ double Range_filter_cost_info::avg_access_and_eval_gain_per_row( and gets slope and interscept values. */ -void Range_filter_cost_info::init(Rowid_filter_container_type cont_type, - TABLE *tab, uint idx) +void Range_rowid_filter_cost_info::init(Rowid_filter_container_type cont_type, + TABLE *tab, uint idx) { container_type= cont_type; table= tab; @@ -49,15 +49,15 @@ void Range_filter_cost_info::init(Rowid_filter_container_type cont_type, } double -Range_filter_cost_info::build_cost(Rowid_filter_container_type container_type) +Range_rowid_filter_cost_info::build_cost(Rowid_filter_container_type cont_type) { double cost= 0; cost+= table->quick_index_only_costs[key_no]; - switch (container_type) { + switch (cont_type) { - case ORDERED_ARRAY_CONTAINER: + case SORTED_ARRAY_CONTAINER: cost+= ARRAY_WRITE_COST * est_elements; /* cost filling the container */ cost+= ARRAY_SORT_C * est_elements * log(est_elements); /* sorting cost */ break; @@ -68,10 +68,27 @@ Range_filter_cost_info::build_cost(Rowid_filter_container_type container_type) return cost; } + +Rowid_filter_container *Range_rowid_filter_cost_info::create_container() +{ + THD *thd= table->in_use; + uint elem_sz= table->file->ref_length; + Rowid_filter_container *res= 0; + + switch (container_type) { + case SORTED_ARRAY_CONTAINER: + res= new (thd->mem_root) Rowid_filter_sorted_array(est_elements, elem_sz); + break; + default: + DBUG_ASSERT(0); + } + return res; +} static -int compare_range_filter_cost_info_by_a(Range_filter_cost_info **filter_ptr_1, - Range_filter_cost_info **filter_ptr_2) +int compare_range_rowid_filter_cost_info_by_a( + Range_rowid_filter_cost_info **filter_ptr_1, + Range_rowid_filter_cost_info **filter_ptr_2) { double diff= (*filter_ptr_2)->a - (*filter_ptr_1)->a; return (diff < 0 ? -1 : (diff > 0 ? 1 : 0)); @@ -83,16 +100,16 @@ int compare_range_filter_cost_info_by_a(Range_filter_cost_info **filter_ptr_1, @details */ -void TABLE::prune_range_filters() +void TABLE::prune_range_rowid_filters() { uint i, j; - Range_filter_cost_info **filter_ptr_1= range_filter_cost_info_ptr; - for (i= 0; i < range_filter_cost_info_elems; i++, filter_ptr_1++) + Range_rowid_filter_cost_info **filter_ptr_1= range_rowid_filter_cost_info_ptr; + for (i= 0; i < range_rowid_filter_cost_info_elems; i++, filter_ptr_1++) { uint key_no= (*filter_ptr_1)->key_no; - Range_filter_cost_info **filter_ptr_2= filter_ptr_1 + 1; - for (j= i+1; j < range_filter_cost_info_elems; j++, filter_ptr_2++) + Range_rowid_filter_cost_info **filter_ptr_2= filter_ptr_1 + 1; + for (j= i+1; j < range_rowid_filter_cost_info_elems; j++, filter_ptr_2++) { key_map map= key_info[key_no].overlapped; map.intersect(key_info[(*filter_ptr_2)->key_no].overlapped); @@ -105,16 +122,18 @@ void TABLE::prune_range_filters() } /* Sort the array range_filter_cost_info by 'a' */ - my_qsort(range_filter_cost_info_ptr, - range_filter_cost_info_elems, - sizeof(Range_filter_cost_info *), - (qsort_cmp) compare_range_filter_cost_info_by_a); - - Range_filter_cost_info **cand_filter_ptr= range_filter_cost_info_ptr; - for (i= 0; i < range_filter_cost_info_elems; i++, cand_filter_ptr++) + my_qsort(range_rowid_filter_cost_info_ptr, + range_rowid_filter_cost_info_elems, + sizeof(Range_rowid_filter_cost_info *), + (qsort_cmp) compare_range_rowid_filter_cost_info_by_a); + + Range_rowid_filter_cost_info **cand_filter_ptr= + range_rowid_filter_cost_info_ptr; + for (i= 0; i < range_rowid_filter_cost_info_elems; i++, cand_filter_ptr++) { bool is_pruned= false; - Range_filter_cost_info **usable_filter_ptr= range_filter_cost_info_ptr; + Range_rowid_filter_cost_info **usable_filter_ptr= + range_rowid_filter_cost_info_ptr; key_map abs_indep; abs_indep.clear_all(); for (uint j= 0; j < i; j++, usable_filter_ptr++) @@ -130,29 +149,30 @@ void TABLE::prune_range_filters() } else { - Range_filter_cost_info *moved= *cand_filter_ptr; + Range_rowid_filter_cost_info *moved= *cand_filter_ptr; memmove(usable_filter_ptr+1, usable_filter_ptr, - sizeof(Range_filter_cost_info *) * (i-j-1)); + sizeof(Range_rowid_filter_cost_info *) * (i-j-1)); *usable_filter_ptr= moved; } } if (is_pruned) { memmove(cand_filter_ptr, cand_filter_ptr+1, - sizeof(Range_filter_cost_info *) * - (range_filter_cost_info_elems - 1 - i)); - range_filter_cost_info_elems--; + sizeof(Range_rowid_filter_cost_info *) * + (range_rowid_filter_cost_info_elems - 1 - i)); + range_rowid_filter_cost_info_elems--; } } } static uint -get_max_range_filter_elements_for_table(THD *thd, TABLE *tab, - Rowid_filter_container_type cont_type) +get_max_range_rowid_filter_elems_for_table( + THD *thd, TABLE *tab, + Rowid_filter_container_type cont_type) { switch (cont_type) { - case ORDERED_ARRAY_CONTAINER : + case SORTED_ARRAY_CONTAINER : return thd->variables.max_rowid_filter_size/tab->file->ref_length; default : DBUG_ASSERT(0); @@ -160,7 +180,7 @@ get_max_range_filter_elements_for_table(THD *thd, TABLE *tab, } } -void TABLE::init_cost_info_for_usable_range_filters(THD *thd) +void TABLE::init_cost_info_for_usable_range_rowid_filters(THD *thd) { uint key_no; key_map usable_range_filter_keys; @@ -173,60 +193,64 @@ void TABLE::init_cost_info_for_usable_range_filters(THD *thd) if (key_no == s->primary_key && file->primary_key_is_clustered()) continue; if (quick_rows[key_no] > - get_max_range_filter_elements_for_table(thd, this, - ORDERED_ARRAY_CONTAINER)) + get_max_range_rowid_filter_elems_for_table(thd, this, + SORTED_ARRAY_CONTAINER)) continue; usable_range_filter_keys.set_bit(key_no); } - range_filter_cost_info_elems= usable_range_filter_keys.bits_set(); - if (!range_filter_cost_info_elems) + range_rowid_filter_cost_info_elems= usable_range_filter_keys.bits_set(); + if (!range_rowid_filter_cost_info_elems) return; - range_filter_cost_info_ptr= - (Range_filter_cost_info **) thd->calloc(sizeof(Range_filter_cost_info *) * - range_filter_cost_info_elems); - range_filter_cost_info= - new (thd->mem_root) Range_filter_cost_info[range_filter_cost_info_elems]; - if (!range_filter_cost_info_ptr || !range_filter_cost_info) + range_rowid_filter_cost_info_ptr= + (Range_rowid_filter_cost_info **) + thd->calloc(sizeof(Range_rowid_filter_cost_info *) * + range_rowid_filter_cost_info_elems); + range_rowid_filter_cost_info= + new (thd->mem_root) + Range_rowid_filter_cost_info[range_rowid_filter_cost_info_elems]; + if (!range_rowid_filter_cost_info_ptr || !range_rowid_filter_cost_info) { - range_filter_cost_info_elems= 0; + range_rowid_filter_cost_info_elems= 0; return; } - Range_filter_cost_info **curr_ptr= range_filter_cost_info_ptr; - Range_filter_cost_info *curr_filter_cost_info= range_filter_cost_info; + Range_rowid_filter_cost_info **curr_ptr= range_rowid_filter_cost_info_ptr; + Range_rowid_filter_cost_info *curr_filter_cost_info= + range_rowid_filter_cost_info; key_map::Iterator li(usable_range_filter_keys); while ((key_no= li++) != key_map::Iterator::BITMAP_END) { *curr_ptr= curr_filter_cost_info; - curr_filter_cost_info->init(ORDERED_ARRAY_CONTAINER, this, key_no); + curr_filter_cost_info->init(SORTED_ARRAY_CONTAINER, this, key_no); curr_ptr++; curr_filter_cost_info++; } - prune_range_filters(); + prune_range_rowid_filters(); } -Range_filter_cost_info *TABLE::best_filter_for_partial_join(uint access_key_no, - double records) +Range_rowid_filter_cost_info * +TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, + double records) { - if (!this || range_filter_cost_info_elems == 0 || + if (!this || range_rowid_filter_cost_info_elems == 0 || covering_keys.is_set(access_key_no)) return 0; if (access_key_no == s->primary_key && file->primary_key_is_clustered()) return 0; - Range_filter_cost_info *best_filter= 0; + Range_rowid_filter_cost_info *best_filter= 0; double best_filter_gain= 0; key_map *overlapped= &key_info[access_key_no].overlapped; - for (uint i= 0; i < range_filter_cost_info_elems ; i++) + for (uint i= 0; i < range_rowid_filter_cost_info_elems ; i++) { double curr_gain = 0; - Range_filter_cost_info *filter= range_filter_cost_info_ptr[i]; + Range_rowid_filter_cost_info *filter= range_rowid_filter_cost_info_ptr[i]; if ((filter->key_no == access_key_no) || overlapped->is_set(filter->key_no)) continue; @@ -243,7 +267,7 @@ Range_filter_cost_info *TABLE::best_filter_for_partial_join(uint access_key_no, } -bool Range_filter_ordered_array::fill() +bool Range_rowid_filter::fill() { int rc= 0; handler *file= table->file; @@ -275,7 +299,7 @@ bool Range_filter_ordered_array::fill() if (!rc) { file->position(quick->record); - if (refpos_container.add((char*) file->ref)) + if (container->add(NULL, (char*) file->ref)) rc= 1; } } @@ -288,21 +312,19 @@ bool Range_filter_ordered_array::fill() file->in_range_check_pushed_down= in_range_check_pushed_down_save; if (rc != HA_ERR_END_OF_FILE) return 1; - container_is_filled= true; table->file->rowid_filter_is_active= true; return 0; } -bool Range_filter_ordered_array::sort() -{ - refpos_container.sort(refpos_order_cmp, (void *) (table->file)); - return false; -} - - -bool Range_filter_ordered_array::check(char *elem) +bool Rowid_filter_sorted_array::check(void *ctxt, char *elem) { + TABLE *table= (TABLE *) ctxt; + if (!is_checked) + { + refpos_container.sort(refpos_order_cmp, (void *) (table->file)); + is_checked= true; + } int l= 0; int r= refpos_container.elements()-1; while (l <= r) @@ -321,8 +343,10 @@ bool Range_filter_ordered_array::check(char *elem) } -Range_filter_ordered_array::~Range_filter_ordered_array() +Range_rowid_filter::~Range_rowid_filter() { + delete container; + container= 0; if (select) { if (select->quick) diff --git a/sql/rowid_filter.h b/sql/rowid_filter.h index 7cec865..3578866 100644 --- a/sql/rowid_filter.h +++ b/sql/rowid_filter.h @@ -1,117 +1,66 @@ #ifndef ROWID_FILTER_INCLUDED #define ROWID_FILTER_INCLUDED -/** - It makes sense to apply filters for a certain join order when the following - inequality holds: - - #T + c4*#T > #T*sel(Fi) + c4*#T*sel(Fi) + - I/O(Fi) + c1*#(Fi) + c2*#(Fi)*log(#(Fi)) + - c3*#T (1), - - where #T - the fanout of the partial join - Fi - a filter for the index with the number i in - the key_map of available indexes for this table - sel(Fi) - the selectivity of the index with the number - i - c4*#T, - c4*#T*sel(Fi) - a cost to apply available predicates - c4 - a constant to apply available predicates - I/O(Fi) - a cost of the I/O accesses to Fi - #(Fi) - a number of estimated records that range - access would use - c1*#(Fi) - a cost to write in Fi - c1 - a constant to write one element in Fi - c2*#(Fi)*log(#(Fi)) - a cost to sort in Fi - c2 - a sorting constant - c3*(#T) - a cost to look-up into a current partial join - c3 - a constant to look-up into Fi - - Let's set a new variable FBCi (filter building cost for the filter with - index i): - - FBCi = I/O(Fi) + c1*#(Fi) + c2*#(Fi)*log(#(Fi)) - - It can be seen that FBCi doesn't depend on #T. - - So using this variable (1) can be rewritten: - - #T + c4*#T > #T*sel(Fi) + c4*#T*sel(Fi) + - FBCi + - c3*#T - - To get a possible cost improvement when a filter is used right part - of the (1) inequality should be deducted from the left part. - Denote it as G(#T): - - G(#T)= #T + c4*#T - (#T*sel(Fi) + c4*#T*sel(Fi) + FBCi + c3*#T) (2) - - On the prepare stage when filters are created #T value isn't known. - - To find out what filter is the best among available one for the table - (what filter gives the biggest gain) a knowledge about linear functions - can be used. Consider filter gain as a linear function: - - Gi(#T)= ai*#T + bi (3) - - where ai= 1+c4-c3-sel(Fi)*(1+c4), - bi= -FBCi - - Filter gain can be interpreted as an ordinate, #T as abscissa. - - So the aim is to find the linear function that has the biggest ordinate value - for each positive abscissa (because #T can't be negative) comparing with - the other available functions. - - Consider two filters Fi, Fj or linear functions with a positive slope. - To find out which linear function is better let's find their intersection - point coordinates. - - Gi(#T0)= Gj(#T0) (using (2))=> - #T0= (bj - bi)/(ai - aj) (using (3)) - => - #T0= (BCFj-BCFi)/((sel(Fj)-sel(Fi))*(1+c4)) - - If put #T0 value into the (3) formula G(#T0) can be easily found. - - It can be seen that if two linear functions intersect in II, III or IV - quadrants the linear function with a bigger slope value will always - be better. - - If two functions intersect in the I quadrant for #T1 < #T0 a function - with a smaller slope value will give a better gain and when #T1 > #T0 - function with a bigger slope will give better gain. - - for each #T1 > #T0 if (ai > aj) => (Gi(#T1) >= Gj(#T1)) - #T1 <= #T0 if (ai > aj) => (Gi(#T1) <= Gj(#T1)) - - So both linear functions should be saved. - - Interesting cases: - - 1. For Fi,Fj filters ai=aj. - - In this case intercepts bi and bj should be compared. - The filter with the biggest intercept will give a better result. - - 2. Only one filter remains after the calculations and for some join order - it is equal to the index that is used to access table. Therefore, this - filter can't be used. - - In this case the gain is computed for every filter that can be constructed - for this table. - - After information about filters is computed for each partial join order - it is checked if the filter can be applied to the current table. - If it gives a cost improvement it is saved as the best plan for this - partial join. -*/ #include "mariadb.h" #include "sql_array.h" +/** + @class Rowid_filter + + What rowid / primary filters are + -------------------------------- + + Consider a join query Q of the form + SELECT * FROM T1, ... , Tk WHERE P. + + For any of the table reference Ti(Q) from the from clause of Q different + rowid / primary key filters (pk-filters for short) can be built. + A pk-filter F built for Ti(Q) is a set of rowids / primary keys of Ti + F= {pk1,...,pkN} such that for any row r=r1||...||rk from the result set of Q + ri's rowid / primary key pk(ri) is contained in F. + + When pk-filters are useful + -------------------------- + + If building a pk-filter F for Ti(Q )is not too costly and its cardinality #F + is much less than the cardinality of T - #T then using the pk-filter when + executing Q might be quite beneficial. + + Let r be a random row from Ti. Let s(F) be the probability that pk(r) + belongs to F. Let BC(F) be the cost of building F. + + Suppose that the optimizer has chosen for Q a plan with this join order + T1 => ... Tk and that the table Ti is accessed by a ref access using index I. + Let K = {k1,...,kM} be the set of all rowid/primary keys values used to access + rows of Ti when looking for matches in this table.to join Ti by index I. + + Let's assume that two set sets K and F are uncorrelated. With this assumption + if before accessing data from Ti by the rowid / primary key k we first + check whether k is in F then we can expect saving on M*(1-s(S)) accesses of + data rows from Ti. If we can guarantee that test whether k is in F is + relatively cheap then we can gain a lot assuming that BC(F) is much less + then the cost of fetching M*(1-s(S)) records from Ti and following + evaluation of conditions pushed into Ti. + + Making pk-filter test cheap + --------------------------- + + If the search structure to test whether an element is in F can be fully + placed in RAM then this test is expected to be be much cheaper than a random + access of a record from Ti. We'll consider two search structures for + pk-filters: ordered array and bloom filter. Ordered array is easy to + implement, but it's space consuming. If a filter contains primary keys + then at least space for each primary key from the filter must be allocated + in the search structure. On a the opposite a bloom filter requires a + fixed number of bits and this number does not depend on the cardinality + of the pk-filter (10 bits per element will serve pk-filter of any size). +*/ + class TABLE; class SQL_SELECT; +class Rowid_filter_container; +class Range_rowid_filter_cost_info; /* Cost to write rowid into array */ #define ARRAY_WRITE_COST 0.005 @@ -122,73 +71,76 @@ class SQL_SELECT; typedef enum { - ORDERED_ARRAY_CONTAINER, + SORTED_ARRAY_CONTAINER, BLOOM_FILTER_CONTAINER } Rowid_filter_container_type; -class Range_filter_cost_info : public Sql_alloc +class Rowid_filter_container : public Sql_alloc { public: - Rowid_filter_container_type container_type; - TABLE *table; - uint key_no; - double est_elements; - double b; // intercept of the linear function - double a; // slope of the linear function - double selectivity; - double cross_x; - key_map abs_independent; + virtual Rowid_filter_container_type get_type() = 0; + virtual bool alloc() = 0; + virtual bool add(void *ctxt, char *elem) = 0; + virtual bool check(void *ctxt, char *elem) = 0; + virtual ~Rowid_filter_container() {} +}; - /** - Filter cost functions - */ - Range_filter_cost_info() : table(0), key_no(0) {} +class Rowid_filter : public Sql_alloc +{ +protected: + Rowid_filter_container *container; +public: + Rowid_filter(Rowid_filter_container *container_arg) + : container(container_arg) {} + + virtual bool build() = 0; + virtual bool check(char *elem) = 0; - void init(Rowid_filter_container_type cont_type, - TABLE *tab, uint key_numb); + virtual ~Rowid_filter() {} - double build_cost(Rowid_filter_container_type container_type); + Rowid_filter_container *get_container() { return container; } +}; - inline double lookup_cost(Rowid_filter_container_type cont_type); - inline double - avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type); +class Range_rowid_filter: public Rowid_filter +{ + TABLE *table; + SQL_SELECT *select; + Range_rowid_filter_cost_info *cost_info; - /** - Get the gain that usage of filter promises for 'rows' key entries - */ - inline double get_gain(double rows) - { - return rows * a - b; - } +public: + Range_rowid_filter(TABLE *tab, + Range_rowid_filter_cost_info *cost_arg, + Rowid_filter_container *container_arg, + SQL_SELECT *sel) + : Rowid_filter(container_arg), table(tab), select(sel), cost_info(cost_arg) + {} - inline double get_adjusted_gain(double rows, double worst_seeks) - { - return get_gain(rows) - - (1 - selectivity) * (rows - MY_MIN(rows, worst_seeks)); - } + ~Range_rowid_filter(); - inline double get_cmp_gain(double rows) - { - return rows * (1 - selectivity) / TIME_FOR_COMPARE; - } + bool build() { return fill(); } + + bool check(char *elem) { return container->check(table, elem); } + + bool fill(); + SQL_SELECT *get_select() { return select; } }; -class Refpos_container_ordered_array : public Sql_alloc +class Refpos_container_sorted_array : public Sql_alloc { - uint elem_size; uint max_elements; + uint elem_size; Dynamic_array<char> *array; public: - Refpos_container_ordered_array(uint elem_sz, uint max_elems) - : elem_size(elem_sz), max_elements(max_elems), array(0) {} + Refpos_container_sorted_array(uint max_elems, uint elem_sz) + : max_elements(max_elems), elem_size(elem_sz), array(0) {} - ~Refpos_container_ordered_array() + ~Refpos_container_sorted_array() { delete array; array= 0; @@ -226,57 +178,77 @@ class Refpos_container_ordered_array : public Sql_alloc } }; -class Range_filter_ordered_array : public Sql_alloc +class Rowid_filter_sorted_array: public Rowid_filter_container { - TABLE *table; - SQL_SELECT *select; - bool container_is_filled; - Refpos_container_ordered_array refpos_container; - + Refpos_container_sorted_array refpos_container; + bool is_checked; + public: - Range_filter_ordered_array(TABLE *tab, SQL_SELECT *sel, uint elems) - : table(tab), select(sel), container_is_filled(false), - refpos_container(table->file->ref_length, elems) - {} - - ~Range_filter_ordered_array(); + Rowid_filter_sorted_array(uint elems, uint elem_size) + : refpos_container(elems, elem_size), is_checked(false) {} - SQL_SELECT *get_select() { return select; } + Rowid_filter_container_type get_type() + { return SORTED_ARRAY_CONTAINER; } bool alloc() { return refpos_container.alloc(); } - bool is_filled() { return container_is_filled; } - - bool fill(); + bool add(void *ctxt, char *elem) { return refpos_container.add(elem); } - bool sort(); - - bool check(char *elem); + bool check(void *ctxt, char *elem); }; -class Rowid_filter : public Sql_alloc -{ - Range_filter_cost_info *cost_info; - Range_filter_ordered_array *container; +class Range_rowid_filter_cost_info : public Sql_alloc +{ public: - Rowid_filter(Range_filter_cost_info *cost_arg, - Range_filter_ordered_array *container_arg) - : cost_info(cost_arg), container(container_arg) {} + Rowid_filter_container_type container_type; + TABLE *table; + uint key_no; + double est_elements; + double b; // intercept of the linear function + double a; // slope of the linear function + double selectivity; + double cross_x; + key_map abs_independent; + + /** + Filter cost functions + */ + + Range_rowid_filter_cost_info() : table(0), key_no(0) {} + + void init(Rowid_filter_container_type cont_type, + TABLE *tab, uint key_numb); + + double build_cost(Rowid_filter_container_type container_type); + + inline double lookup_cost(Rowid_filter_container_type cont_type); + + inline double + avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type); - Range_filter_ordered_array *get_container() { return container; } + /** + Get the gain that usage of filter promises for 'rows' key entries + */ + inline double get_gain(double rows) + { + return rows * a - b; + } - ~Rowid_filter() + inline double get_adjusted_gain(double rows, double worst_seeks) { - delete container; + return get_gain(rows) - + (1 - selectivity) * (rows - MY_MIN(rows, worst_seeks)); } - bool is_active() + inline double get_cmp_gain(double rows) { - return get_container()->is_filled(); + return rows * (1 - selectivity) / TIME_FOR_COMPARE; } - bool check(char *buf) { return get_container()->check(buf); } + Rowid_filter_container *create_container(); + }; + #endif /* ROWID_FILTER_INCLUDED */ diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 724e156..531fe5f 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -1465,9 +1465,9 @@ int JOIN::optimize() } -bool JOIN::make_range_filters() +bool JOIN::make_range_rowid_filters() { - DBUG_ENTER("make_range_filters"); + DBUG_ENTER("make_range_rowid_filters"); JOIN_TAB *tab; @@ -1475,12 +1475,11 @@ bool JOIN::make_range_filters() tab; tab= next_linear_tab(this, tab, WITH_BUSH_ROOTS)) { - if (tab->filter) + if (tab->range_rowid_filter_info) { int err; SQL_SELECT *sel; - uint elems; - Range_filter_ordered_array *filter_container= NULL; + Rowid_filter_container *filter_container= NULL; Item **sargable_cond= get_sargable_cond(this, tab->table); sel= make_select(tab->table, const_table_map, const_table_map, *sargable_cond, (SORT_INFO*) 0, 1, &err); @@ -1489,7 +1488,7 @@ bool JOIN::make_range_filters() key_map filter_map; filter_map.clear_all(); - filter_map.set_bit(tab->filter->key_no); + filter_map.set_bit(tab->range_rowid_filter_info->key_no); filter_map.merge(tab->table->with_impossible_ranges); bool force_index_save= tab->table->force_index; tab->table->force_index= true; @@ -1500,13 +1499,15 @@ bool JOIN::make_range_filters() if (thd->is_error()) DBUG_RETURN(1); DBUG_ASSERT(sel->quick); - elems= (uint) tab->filter->est_elements; filter_container= - new (thd->mem_root) Range_filter_ordered_array(tab->table, sel, elems); + tab->range_rowid_filter_info->create_container(); if (filter_container) { tab->rowid_filter= - new (thd->mem_root) Rowid_filter(tab->filter, filter_container); + new (thd->mem_root) Range_rowid_filter( + tab->table, + tab->range_rowid_filter_info, + filter_container, sel); } } } @@ -1515,9 +1516,9 @@ bool JOIN::make_range_filters() bool -JOIN::init_range_filters() +JOIN::init_range_rowid_filters() { - DBUG_ENTER("init_range_filters"); + DBUG_ENTER("init_range_rowid_filters"); JOIN_TAB *tab; @@ -1534,7 +1535,7 @@ JOIN::init_range_filters() continue; } tab->table->file->rowid_filter_push(tab->rowid_filter); - tab->is_rowid_filter_filled= false; + tab->is_rowid_filter_built= false; } DBUG_RETURN(0); } @@ -2058,7 +2059,7 @@ int JOIN::optimize_stage2() if (get_best_combination()) DBUG_RETURN(1); - if (make_range_filters()) + if (make_range_rowid_filters()) DBUG_RETURN(1); if (select_lex->handle_derived(thd->lex, DT_OPTIMIZE)) @@ -2725,7 +2726,7 @@ int JOIN::optimize_stage2() if (init_join_caches()) DBUG_RETURN(1); - if (init_range_filters()) + if (init_range_rowid_filters()) DBUG_RETURN(1); error= 0; @@ -5120,7 +5121,7 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, impossible_range= records == 0 && s->table->reginfo.impossible_range; if (join->thd->lex->sql_command == SQLCOM_SELECT && optimizer_flag(join->thd, OPTIMIZER_SWITCH_USE_ROWID_FILTER)) - s->table->init_cost_info_for_usable_range_filters(join->thd); + s->table->init_cost_info_for_usable_range_rowid_filters(join->thd); } if (!impossible_range) { @@ -6926,14 +6927,14 @@ best_access_path(JOIN *join, double best_time= DBL_MAX; double records= DBL_MAX; table_map best_ref_depends_map= 0; - Range_filter_cost_info *best_filter= 0; + Range_rowid_filter_cost_info *best_filter= 0; double tmp; ha_rows rec; bool best_uses_jbuf= FALSE; MY_BITMAP *eq_join_set= &s->table->eq_join_set; KEYUSE *hj_start_key= 0; SplM_plan_info *spl_plan= 0; - Range_filter_cost_info *filter= 0; + Range_rowid_filter_cost_info *filter= 0; disable_jbuf= disable_jbuf || idx == join->const_tables; @@ -7329,7 +7330,8 @@ best_access_path(JOIN *join, if (records < DBL_MAX) { double rows= record_count * records; - filter= table->best_filter_for_partial_join(start_key->key, rows); + filter= + table->best_range_rowid_filter_for_partial_join(start_key->key, rows); if (filter) { tmp-= filter->get_adjusted_gain(rows, s->worst_seeks) - @@ -7461,7 +7463,8 @@ best_access_path(JOIN *join, { double rows= record_count * s->found_records; uint key_no= s->quick->index; - filter= s->table->best_filter_for_partial_join(key_no, rows); + filter= s->table->best_range_rowid_filter_for_partial_join(key_no, + rows); if (filter) { tmp-= filter->get_gain(rows); @@ -7559,7 +7562,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->filter= best_filter; + pos->range_rowid_filter_info= best_filter; loose_scan_opt.save_to_position(s, loose_scan_pos); @@ -9825,7 +9828,7 @@ bool JOIN::get_best_combination() is_hash_join_key_no(j->ref.key)) hash_join= TRUE; - j->filter= best_positions[tablenr].filter; + j->range_rowid_filter_info= best_positions[tablenr].range_rowid_filter_info; loop_end: /* @@ -12566,14 +12569,13 @@ bool error_if_full_join(JOIN *join) } -void JOIN_TAB::fill_range_filter_if_needed() +void JOIN_TAB::build_range_rowid_filter_if_needed() { - if (rowid_filter && !is_rowid_filter_filled) + if (rowid_filter && !is_rowid_filter_built) { - if (!rowid_filter->get_container()->fill()) + if (!rowid_filter->build()) { - rowid_filter->get_container()->sort(); - is_rowid_filter_filled= true; + is_rowid_filter_built= true; } else { @@ -19493,7 +19495,7 @@ sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records) if (!join_tab->preread_init_done && join_tab->preread_init()) DBUG_RETURN(NESTED_LOOP_ERROR); - join_tab->fill_range_filter_if_needed(); + join_tab->build_range_rowid_filter_if_needed(); join->return_tab= join_tab; @@ -20439,7 +20441,7 @@ int join_init_read_record(JOIN_TAB *tab) if (tab->filesort && tab->sort_table()) // Sort table. return 1; - tab->fill_range_filter_if_needed(); + tab->build_range_rowid_filter_if_needed(); DBUG_EXECUTE_IF("kill_join_init_read_record", tab->join->thd->set_killed(KILL_QUERY);); @@ -22490,7 +22492,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit, tab->use_quick=1; tab->ref.key= -1; tab->ref.key_parts=0; // Don't use ref key. - tab->filter= 0; + tab->range_rowid_filter_info= 0; if (tab->rowid_filter) { delete tab->rowid_filter; @@ -25331,11 +25333,12 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta, if (rowid_filter) { - QUICK_SELECT_I *quick= rowid_filter->get_container()->get_select()->quick; + Range_rowid_filter *range_filter= (Range_rowid_filter *) rowid_filter; + QUICK_SELECT_I *quick= range_filter->get_select()->quick; Explain_rowid_filter *erf= new (thd->mem_root) Explain_rowid_filter; erf->quick= quick->get_explain(thd->mem_root); - erf->selectivity= filter->selectivity; + erf->selectivity= range_rowid_filter_info->selectivity; erf->rows= quick->records; eta->rowid_filter= erf; //psergey-todo: also do setup for ANALYZE here. diff --git a/sql/sql_select.h b/sql/sql_select.h index 2fea84d..bfa4274 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -510,11 +510,11 @@ typedef struct st_join_table { uint n_sj_tables; bool preread_init_done; - Range_filter_cost_info *filter; + Range_rowid_filter_cost_info *range_rowid_filter_info; Rowid_filter *rowid_filter; - bool is_rowid_filter_filled; + bool is_rowid_filter_built; - void fill_range_filter_if_needed(); + void build_range_rowid_filter_if_needed(); void cleanup(); inline bool is_using_loose_index_scan() { @@ -889,7 +889,7 @@ class Sj_materialization_picker : public Semi_join_strategy_picker }; -class Range_filter_cost_info; +class Range_rowid_filter_cost_info; class Rowid_filter; @@ -976,7 +976,7 @@ typedef struct st_position /* Info on splitting plan used at this position */ SplM_plan_info *spl_plan; /* The index for which filter can be built */ - Range_filter_cost_info *filter; + Range_rowid_filter_cost_info *range_rowid_filter_info; } POSITION; typedef Bounds_checked_array<Item_null_result*> Item_null_array; @@ -1626,8 +1626,8 @@ class JOIN :public Sql_alloc bool optimize_unflattened_subqueries(); bool optimize_constant_subqueries(); int init_join_caches(); - bool make_range_filters(); - bool init_range_filters(); + bool make_range_rowid_filters(); + bool init_range_rowid_filters(); bool make_sum_func_list(List<Item> &all_fields, List<Item> &send_fields, bool before_group_by, bool recompute= FALSE); diff --git a/sql/table.cc b/sql/table.cc index 67c369f..bb18940 100644 --- a/sql/table.cc +++ b/sql/table.cc @@ -4695,9 +4695,9 @@ void TABLE::init(THD *thd, TABLE_LIST *tl) created= TRUE; cond_selectivity= 1.0; cond_selectivity_sampling_explain= NULL; - range_filter_cost_info_elems= 0; - range_filter_cost_info_ptr= NULL; - range_filter_cost_info= NULL; + range_rowid_filter_cost_info_elems= 0; + range_rowid_filter_cost_info_ptr= NULL; + range_rowid_filter_cost_info= NULL; #ifdef HAVE_REPLICATION /* used in RBR Triggers */ master_had_triggers= 0; diff --git a/sql/table.h b/sql/table.h index feeb9ee..9918758 100644 --- a/sql/table.h +++ b/sql/table.h @@ -55,7 +55,7 @@ class Virtual_column_info; class Table_triggers_list; class TMP_TABLE_PARAM; class SEQUENCE; -class Range_filter_cost_info; +class Range_rowid_filter_cost_info; /* Used to identify NESTED_JOIN structures within a join (applicable only to @@ -1504,13 +1504,14 @@ struct TABLE void add_splitting_info_for_key_field(struct KEY_FIELD *key_field); key_map with_impossible_ranges; - uint range_filter_cost_info_elems; - Range_filter_cost_info **range_filter_cost_info_ptr; - Range_filter_cost_info *range_filter_cost_info; - void init_cost_info_for_usable_range_filters(THD *thd); - void prune_range_filters(); - Range_filter_cost_info *best_filter_for_partial_join(uint access_key_no, - double records); + uint range_rowid_filter_cost_info_elems; + Range_rowid_filter_cost_info **range_rowid_filter_cost_info_ptr; + Range_rowid_filter_cost_info *range_rowid_filter_cost_info; + void init_cost_info_for_usable_range_rowid_filters(THD *thd); + void prune_range_rowid_filters(); + Range_rowid_filter_cost_info * + best_range_rowid_filter_for_partial_join(uint access_key_no, + double records); /** System Versioning support */