revision-id: 90708fc15cf835d03b511a953ae6939081a0f9e1 (mariadb-10.3.6-98-g90708fc) parent(s): 6aaa69f37360200c4807282c8df1b2c21c707d2d author: Igor Babaev committer: Igor Babaev timestamp: 2018-12-01 00:42:10 -0800 message: MDEV-16188: Added an implementation of rowid filters that uses dynamic array as the container for rowids / primary keys. Supported creation of filters for sargable range conditions. Implemented pushdown of filters into InnoDB and MyISAM engines. Filters are not supported yet when MRR is used. That's why some tests from main test suite fail. --- include/my_compare.h | 1 + sql/handler.cc | 23 +++++++ sql/handler.h | 17 +++++ sql/rowid_filter.cc | 98 ++++++++++++++++++++++++++ sql/rowid_filter.h | 114 +++++++++++++++++++++++++++++-- sql/sql_array.h | 13 ++++ sql/sql_select.cc | 84 +++++++++++++++++++---- sql/sql_select.h | 9 ++- sql/structs.h | 10 +++ sql/table.cc | 33 +++++++++ sql/table.h | 2 + storage/innobase/handler/ha_innodb.cc | 42 ++++++++++++ storage/innobase/handler/ha_innodb.h | 6 ++ storage/innobase/include/ha_prototypes.h | 17 +++++ storage/innobase/include/row0mysql.h | 4 ++ storage/innobase/include/srv0mon.h | 5 ++ storage/innobase/row/row0sel.cc | 28 ++++++-- storage/innobase/srv/srv0mon.cc | 18 +++++ storage/myisam/ha_myisam.cc | 17 ++++- storage/myisam/ha_myisam.h | 2 + storage/myisam/mi_extra.c | 10 +++ storage/myisam/mi_key.c | 13 ++++ storage/myisam/mi_rkey.c | 4 +- storage/myisam/mi_rnext.c | 4 +- storage/myisam/mi_rnext_same.c | 4 +- storage/myisam/mi_rprev.c | 4 +- storage/myisam/myisamdef.h | 11 ++- 27 files changed, 559 insertions(+), 34 deletions(-) diff --git a/include/my_compare.h b/include/my_compare.h index 4387105..0f48771 100644 --- a/include/my_compare.h +++ b/include/my_compare.h @@ -152,5 +152,6 @@ typedef enum icp_result { } ICP_RESULT; typedef ICP_RESULT (*index_cond_func_t)(void *param); +typedef int (*rowid_filter_func_t)(void *param); #endif /* _my_compare_h */ diff --git a/sql/handler.cc b/sql/handler.cc index e5081ac..2713601 100644 --- a/sql/handler.cc +++ b/sql/handler.cc @@ -43,6 +43,7 @@ #include "debug_sync.h" // DEBUG_SYNC #include "sql_audit.h" #include "ha_sequence.h" +#include "rowid_filter.h" #ifdef WITH_PARTITION_STORAGE_ENGINE #include "ha_partition.h" @@ -5766,6 +5767,27 @@ extern "C" enum icp_result handler_index_cond_check(void* h_arg) return res; } + +/** + Rowid filter callback - to be called by an engine to check rowid / primary + keys of the rows whose data is to be fetched against the set rowid filter +*/ +extern "C" int handler_rowid_filter_check(void *h_arg) +{ + handler *h= (handler*) h_arg; + TABLE *tab= h->get_table(); + h->position(tab->record[0]); + return h->pushed_rowid_filter->check((char *) h->ref); +} + +extern "C" int handler_rowid_filter_is_active(void *h_arg) +{ + if (!h_arg) + return false; + handler *h= (handler*) h_arg; + return h->rowid_filter_is_active; +} + int handler::index_read_idx_map(uchar * buf, uint index, const uchar * key, key_part_map keypart_map, enum ha_rkey_function find_flag) @@ -6230,6 +6252,7 @@ int handler::ha_reset() /* Reset information about pushed engine conditions */ cancel_pushed_idx_cond(); /* Reset information about pushed index conditions */ + cancel_pushed_rowid_filter(); clear_top_table_fields(); DBUG_RETURN(reset()); } diff --git a/sql/handler.h b/sql/handler.h index e5a6deb..141c05c 100644 --- a/sql/handler.h +++ b/sql/handler.h @@ -47,6 +47,7 @@ class Alter_info; class Virtual_column_info; class sequence_definition; +class Rowid_filter; // the following is for checking tables @@ -2790,6 +2791,9 @@ class ha_statistics extern "C" enum icp_result handler_index_cond_check(void* h_arg); +extern "C" int handler_rowid_filter_check(void* h_arg); +extern "C" int handler_rowid_filter_is_active(void* h_arg); + uint calculate_key_len(TABLE *, uint, const uchar *, key_part_map); /* bitmap with first N+1 bits set @@ -2956,6 +2960,9 @@ class handler :public Sql_alloc Item *pushed_idx_cond; uint pushed_idx_cond_keyno; /* The index which the above condition is for */ + Rowid_filter *pushed_rowid_filter; + bool rowid_filter_is_active; + Discrete_interval auto_inc_interval_for_cur_row; /** Number of reserved auto-increment intervals. Serves as a heuristic @@ -3020,6 +3027,8 @@ class handler :public Sql_alloc tracker(NULL), pushed_idx_cond(NULL), pushed_idx_cond_keyno(MAX_KEY), + pushed_rowid_filter(NULL), + rowid_filter_is_active(0), auto_inc_intervals_count(0), m_psi(NULL), set_top_table_fields(FALSE), top_table(0), top_table_field(0), top_table_fields(0), @@ -4046,6 +4055,14 @@ class handler :public Sql_alloc in_range_check_pushed_down= false; } + virtual void cancel_pushed_rowid_filter() + { + pushed_rowid_filter= NULL; + rowid_filter_is_active= false; + } + + virtual bool rowid_filter_push(Rowid_filter *rowid_filter) { return true; } + /* Needed for partition / spider */ virtual TABLE_LIST *get_next_global_for_child() { return NULL; } diff --git a/sql/rowid_filter.cc b/sql/rowid_filter.cc index aa8194d..5144319 100644 --- a/sql/rowid_filter.cc +++ b/sql/rowid_filter.cc @@ -1,4 +1,9 @@ +#include "mariadb.h" +#include "table.h" +#include "sql_class.h" +#include "opt_range.h" #include "rowid_filter.h" +#include "sql_select.h" /** @@ -89,6 +94,7 @@ void TABLE::prune_range_filters() range_filter_cost_info_elements--; swap_variables(Range_filter_cost_info, range_filter_cost_info[i], range_filter_cost_info[range_filter_cost_info_elements]); + i--; continue; } for (uint j= i+1; j < range_filter_cost_info_elements; j++) @@ -203,9 +209,12 @@ Range_filter_cost_info double best_filter_improvement= 0.0; best_filter= 0; + key_map *intersected_with= &key_info->intersected_with; for (uint i= best_filter_count; i < range_filter_cost_info_elements; i++) { Range_filter_cost_info *filter= &range_filter_cost_info[i]; + if (intersected_with->is_set(filter->key_no)) + continue; if (card < filter->intersect_x_axis_abcissa) break; if (best_filter_improvement < filter->get_filter_gain(card)) @@ -217,3 +226,92 @@ Range_filter_cost_info return best_filter; } + +bool Range_filter_ordered_array::fill() +{ + int rc= 0; + handler *file= table->file; + THD *thd= table->in_use; + QUICK_RANGE_SELECT* quick= (QUICK_RANGE_SELECT*) select->quick; + Item *pushed_idx_cond_save = file->pushed_idx_cond; + uint pushed_idx_cond_keyno_save= file->pushed_idx_cond_keyno; + bool in_range_check_pushed_down_save= file->in_range_check_pushed_down; + + file->pushed_idx_cond= 0; + file->pushed_idx_cond_keyno= MAX_KEY; + file->in_range_check_pushed_down= false; + + /* We're going to just read rowids. */ + table->prepare_for_position(); + + table->file->ha_start_keyread(quick->index); + + if (quick->init() || quick->reset()) + rc= 1; + + while (!rc) + { + rc= quick->get_next(); + if (thd->killed) + rc= 1; + if (!rc) + { + file->position(quick->record); + if (refpos_container.add((char*) file->ref)) + rc= 1; + } + } + + quick->range_end(); + table->file->ha_end_keyread(); + file->pushed_idx_cond= pushed_idx_cond_save; + file->pushed_idx_cond_keyno= pushed_idx_cond_keyno_save; + 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) +{ + int l= 0; + int r= refpos_container.elements()-1; + while (l <= r) + { + int m= (l + r) / 2; + int cmp= refpos_order_cmp((void *) (table->file), + refpos_container.get_pos(m), elem); + if (cmp == 0) + return true; + if (cmp < 0) + l= m + 1; + else + r= m-1; + } + return false; +} + + +Range_filter_ordered_array::~Range_filter_ordered_array() +{ + if (select) + { + if (select->quick) + { + delete select->quick; + select->quick= 0; + } + delete select; + select= 0; + } +} diff --git a/sql/rowid_filter.h b/sql/rowid_filter.h index 3097522..4e3d7de 100644 --- a/sql/rowid_filter.h +++ b/sql/rowid_filter.h @@ -108,8 +108,10 @@ */ #include "mariadb.h" -#include "sql_class.h" -#include "table.h" +#include "sql_array.h" + +class TABLE; +class SQL_SELECT; /* Cost to write into filter */ #define COST_WRITE 0.01 @@ -118,8 +120,6 @@ /* Cost to evaluate condition */ #define COST_COND_EVAL 0.2 -class QUICK_RANGE_SELECT; - class Range_filter_cost_info : public Sql_alloc { public: @@ -130,7 +130,6 @@ class Range_filter_cost_info : public Sql_alloc double a; // slope of the linear function double selectivity; double intersect_x_axis_abcissa; - SQL_SELECT *select; /** Filter cost functions @@ -156,7 +155,7 @@ class Range_filter_cost_info : public Sql_alloc } /* End of filter cost functions */ - Range_filter_cost_info() : table(0), key_no(0), select(0) {} + Range_filter_cost_info() : table(0), key_no(0) {} void init(TABLE *tab, uint key_numb); @@ -181,4 +180,107 @@ class Range_filter_cost_info : public Sql_alloc { return card*a - b; } }; + +class Refpos_container_ordered_array : public Sql_alloc +{ + uint elem_size; + uint max_elements; + Dynamic_array<char> *array; + +public: + + Refpos_container_ordered_array(uint elem_sz, uint max_elems) + : elem_size(elem_sz), max_elements(max_elems) {} + + ~Refpos_container_ordered_array() + { + delete array; + array= 0; + } + + bool alloc() + { + array= new Dynamic_array<char> (elem_size * max_elements, + elem_size * max_elements/8 + 1); + return array == NULL; + } + + bool add(char *elem) + { + for (uint i= 0; i < elem_size; i++) + { + if (array->append(elem[i])) + return true; + } + return false; + } + + char *get_pos(uint n) + { + return array->get_pos(n * elem_size); + } + + uint elements() { return array->elements() / elem_size; } + + void sort (int (*cmp) (void *ctxt, const void *el1, const void *el2), + void *cmp_arg) + { + my_qsort2(array->front(), array->elements()/elem_size, + elem_size, (qsort2_cmp) cmp, cmp_arg); + } +}; + +class Range_filter_ordered_array : public Sql_alloc +{ + TABLE *table; + SQL_SELECT *select; + bool container_is_filled; + Refpos_container_ordered_array refpos_container; + +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(); + + SQL_SELECT *get_select() { return select; } + + bool alloc() { return refpos_container.alloc(); } + + bool is_filled() { return container_is_filled; } + + bool fill(); + + bool sort(); + + bool check(char *elem); +}; + +class Rowid_filter : public Sql_alloc +{ + Range_filter_cost_info *cost_info; + Range_filter_ordered_array *container; + +public: + Rowid_filter(Range_filter_cost_info *cost_arg, + Range_filter_ordered_array *container_arg) + : cost_info(cost_arg), container(container_arg) {} + + Range_filter_ordered_array *get_container() { return container; } + + ~Rowid_filter() + { + delete container; + } + + bool is_active() + { + return get_container()->is_filled(); + } + + bool check(char *buf) { return get_container()->check(buf); } +}; + #endif /* ROWID_FILTER_INCLUDED */ diff --git a/sql/sql_array.h b/sql/sql_array.h index 0e5246b..4a49ade 100644 --- a/sql/sql_array.h +++ b/sql/sql_array.h @@ -166,6 +166,19 @@ template <class Elem> class Dynamic_array return ((const Elem*)array.buffer) + array.elements - 1; } + /// @returns pointer to n-th element + Elem *get_pos(size_t idx) + { + return ((Elem*)array.buffer) + idx; + } + + /// @returns pointer to n-th element + const Elem *get_pos(size_t idx) const + { + return ((const Elem*)array.buffer) + idx; + } + + /** @retval false ok @retval true OOM, @c my_error() has been called. diff --git a/sql/sql_select.cc b/sql/sql_select.cc index f23a6b4..c194fdb 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -1465,10 +1465,9 @@ int JOIN::optimize() } -bool -JOIN::make_range_filter_select(SQL_SELECT *select) +bool JOIN::make_range_filters() { - DBUG_ENTER("make_range_filter_selects"); + DBUG_ENTER("make_range_filters"); JOIN_TAB *tab; @@ -1480,12 +1479,13 @@ JOIN::make_range_filter_select(SQL_SELECT *select) { int err; SQL_SELECT *sel; + uint elems; + Range_filter_ordered_array *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); if (!sel) DBUG_RETURN(1); - tab->filter->select= sel; key_map filter_map; filter_map.clear_all(); @@ -1499,11 +1499,46 @@ JOIN::make_range_filter_select(SQL_SELECT *select) if (thd->is_error()) DBUG_RETURN(1); DBUG_ASSERT(sel->quick); + elems= (uint) tab->filter->cardinality; + filter_container= + new (thd->mem_root) Range_filter_ordered_array(tab->table, sel, elems); + if (filter_container) + { + tab->rowid_filter= + new (thd->mem_root) Rowid_filter(tab->filter, filter_container); + } + } + } + DBUG_RETURN(0); +} + + +bool +JOIN::init_range_filters() +{ + DBUG_ENTER("init_range_filters"); + + JOIN_TAB *tab; + + for (tab= first_linear_tab(this, WITH_BUSH_ROOTS, WITHOUT_CONST_TABLES); + tab; + tab= next_linear_tab(this, tab, WITH_BUSH_ROOTS)) + { + if (!tab->rowid_filter) + continue; + if (tab->rowid_filter->get_container()->alloc()) + { + delete tab->rowid_filter; + tab->rowid_filter= 0; + continue; } + tab->table->file->rowid_filter_push(tab->rowid_filter); + tab->is_rowid_filter_filled= false; } DBUG_RETURN(0); } + int JOIN::init_join_caches() { JOIN_TAB *tab; @@ -2022,7 +2057,7 @@ int JOIN::optimize_stage2() if (get_best_combination()) DBUG_RETURN(1); - if (make_range_filter_select(select)) + if (make_range_filters()) DBUG_RETURN(1); if (select_lex->handle_derived(thd->lex, DT_OPTIMIZE)) @@ -2689,6 +2724,9 @@ int JOIN::optimize_stage2() if (init_join_caches()) DBUG_RETURN(1); + if (init_range_filters()) + DBUG_RETURN(1); + error= 0; if (select_options & SELECT_DESCRIBE) @@ -12508,6 +12546,24 @@ bool error_if_full_join(JOIN *join) } +void JOIN_TAB::fill_range_filter_if_needed() +{ + if (rowid_filter && !is_rowid_filter_filled) + { + if (!rowid_filter->get_container()->fill()) + { + rowid_filter->get_container()->sort(); + is_rowid_filter_filled= true; + } + else + { + delete rowid_filter; + rowid_filter= 0; + } + } +} + + /** cleanup JOIN_TAB. @@ -12531,15 +12587,10 @@ void JOIN_TAB::cleanup() select= 0; delete quick; quick= 0; - if (filter && filter->select) + if (rowid_filter) { - if (filter->select->quick) - { - delete filter->select->quick; - filter->select->quick= 0; - } - delete filter->select; - filter->select= 0; + delete rowid_filter; + rowid_filter= 0; } if (cache) { @@ -19424,6 +19475,8 @@ 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->return_tab= join_tab; if (join_tab->last_inner) @@ -20382,6 +20435,9 @@ int join_init_read_record(JOIN_TAB *tab) tab->join->thd->reset_killed();); if (!tab->preread_init_done && tab->preread_init()) return 1; + + tab->fill_range_filter_if_needed(); + if (init_read_record(&tab->read_record, tab->join->thd, tab->table, tab->select, tab->filesort_result, 1,1, FALSE)) return 1; @@ -25267,7 +25323,7 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta, { eta->key.set_filter(thd->mem_root, &filter->table->key_info[filter->key_no], - filter->select->quick->max_used_key_length); + rowid_filter->get_container()->get_select()->quick->max_used_key_length); } if (tab_type == JT_NEXT) diff --git a/sql/sql_select.h b/sql/sql_select.h index cb0b7c3..1df7e5e 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -510,10 +510,11 @@ typedef struct st_join_table { uint n_sj_tables; bool preread_init_done; - /* Copy of POSITION::filter, set by get_best_combination() */ Range_filter_cost_info *filter; - Dynamic_array<char*> rowid_filter_pk; + Rowid_filter *rowid_filter; + bool is_rowid_filter_filled; + void fill_range_filter_if_needed(); void cleanup(); inline bool is_using_loose_index_scan() { @@ -890,6 +891,7 @@ class Sj_materialization_picker : public Semi_join_strategy_picker class Range_filter_cost_info; +class Rowid_filter; /** @@ -1625,7 +1627,8 @@ class JOIN :public Sql_alloc bool optimize_unflattened_subqueries(); bool optimize_constant_subqueries(); int init_join_caches(); - bool make_range_filter_select(SQL_SELECT *select); + bool make_range_filters(); + bool init_range_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/structs.h b/sql/structs.h index 9ff52bc..5cc64c1 100644 --- a/sql/structs.h +++ b/sql/structs.h @@ -27,6 +27,15 @@ #include "thr_lock.h" /* thr_lock_type */ #include "my_base.h" /* ha_rows, ha_key_alg */ #include <mysql_com.h> /* USERNAME_LENGTH */ +#include "sql_bitmap.h" + +#if MAX_INDEXES <= 64 +typedef Bitmap<64> key_map; /* Used for finding keys */ +#elif MAX_INDEXES > 128 +#error "MAX_INDEXES values greater than 128 is not supported." +#else +typedef Bitmap<((MAX_INDEXES+7)/8*8)> key_map; /* Used for finding keys */ +#endif struct TABLE; class Type_handler; @@ -111,6 +120,7 @@ typedef struct st_key { */ LEX_CSTRING name; key_part_map ext_key_part_map; + key_map intersected_with; uint block_size; enum ha_key_alg algorithm; /* diff --git a/sql/table.cc b/sql/table.cc index 18be06c..a2408d6 100644 --- a/sql/table.cc +++ b/sql/table.cc @@ -1228,6 +1228,37 @@ static const Type_handler *old_frm_type_handler(uint pack_flag, } +void TABLE_SHARE::set_intersected_keys() +{ + KEY *key1= key_info; + for (uint i= 0; i < keys; i++, key1++) + { + key1->intersected_with.clear_all(); + } + key1= key_info; + for (uint i= 0; i < keys; i++, key1++) + { + KEY *key2= key1 + 1; + for (uint j= i+1; j < keys; j++, key2++) + { + KEY_PART_INFO *key_part1= key1->key_part; + KEY_PART_INFO *key_part2= key2->key_part; + uint n= key1->user_defined_key_parts; + set_if_smaller(n, key2->user_defined_key_parts); + for (uint k= 0; k < n; k++, key_part1++, key_part2++) + { + if (key_part1->fieldnr == key_part2->fieldnr) + { + key1->intersected_with.set_bit(j); + key2->intersected_with.set_bit(i); + break; + } + } + } + } +} + + /** Read data from a binary .frm file image into a TABLE_SHARE @@ -2522,6 +2553,8 @@ int TABLE_SHARE::init_from_binary_frm_image(THD *thd, bool write, null_length, 255); } + set_intersected_keys(); + /* Handle virtual expressions */ if (vcol_screen_length && share->frm_version >= FRM_VER_EXPRESSSIONS) { diff --git a/sql/table.h b/sql/table.h index 3c782c3..f5b32c3 100644 --- a/sql/table.h +++ b/sql/table.h @@ -1002,6 +1002,8 @@ struct TABLE_SHARE /* frees the memory allocated in read_frm_image */ void free_frm_image(const uchar *frm); + + void set_intersected_keys(); }; diff --git a/storage/innobase/handler/ha_innodb.cc b/storage/innobase/handler/ha_innodb.cc index 6dedef2..c521f9c 100644 --- a/storage/innobase/handler/ha_innodb.cc +++ b/storage/innobase/handler/ha_innodb.cc @@ -3461,6 +3461,10 @@ ha_innobase::reset_template(void) in ha_innobase::write_row(). */ m_prebuilt->template_type = ROW_MYSQL_NO_TEMPLATE; } + if (m_prebuilt->pk_filter) { + m_prebuilt->pk_filter = NULL; + m_prebuilt->template_type = ROW_MYSQL_NO_TEMPLATE; + } } /*****************************************************************//** @@ -7553,6 +7557,13 @@ ha_innobase::build_template( /* Below we check column by column if we need to access the clustered index. */ + if (pushed_rowid_filter) { + fetch_primary_key_cols = TRUE; + m_prebuilt->pk_filter = this; + } else { + m_prebuilt->pk_filter = NULL; + } + n_fields = (ulint) mysql_fields(table); if (!m_prebuilt->mysql_template) { @@ -20318,6 +20329,22 @@ innobase_index_cond( return handler_index_cond_check(file); } +bool +innobase_pk_filter( +/*===============*/ + void* file) /*!< in/out: pointer to ha_innobase */ +{ + return handler_rowid_filter_check(file); +} + +bool +innobase_pk_filter_is_active( +/*==========================*/ + void* file) /*!< in/out: pointer to ha_innobase */ +{ + return handler_rowid_filter_is_active(file); +} + /** Parse the table file name into table name and database name. @param[in] tbl_name InnoDB table name @param[out] dbname database name buffer (NAME_LEN + 1 bytes) @@ -20853,6 +20880,21 @@ ha_innobase::idx_cond_push( DBUG_RETURN(NULL); } + +/** Push primary key filter. +@param[in] pk_filter PK filter against which primary keys + are to be checked */ + +bool +ha_innobase::rowid_filter_push( + class Rowid_filter* pk_filter) +{ + DBUG_ENTER("ha_innobase::rowid_filter_push"); + DBUG_ASSERT(pk_filter != NULL); + pushed_rowid_filter= pk_filter; + DBUG_RETURN(FALSE); +} + /******************************************************************//** Use this when the args are passed to the format string from errmsg-utf8.txt directly as is. diff --git a/storage/innobase/handler/ha_innodb.h b/storage/innobase/handler/ha_innodb.h index 7bec858..d6c1154 100644 --- a/storage/innobase/handler/ha_innodb.h +++ b/storage/innobase/handler/ha_innodb.h @@ -417,6 +417,12 @@ class ha_innobase: public handler Item* idx_cond_push(uint keyno, Item* idx_cond); /* @} */ + /** Attempt to push down a rowid filter + @param[in] pk_filter Handle of the rowid filter to be pushed. + #return 0 pk-filter is pushed; NULL if not pushed */ + bool rowid_filter_push(class Rowid_filter *rowid_filter); + /* @} */ + protected: /** diff --git a/storage/innobase/include/ha_prototypes.h b/storage/innobase/include/ha_prototypes.h index 15107a9..574526e 100644 --- a/storage/innobase/include/ha_prototypes.h +++ b/storage/innobase/include/ha_prototypes.h @@ -556,6 +556,23 @@ innobase_index_cond( void* file) /*!< in/out: pointer to ha_innobase */ MY_ATTRIBUTE((warn_unused_result)); +/*************************************************************//** +InnoDB Rowid filter check defined in ha_innodb.cc */ + +bool +innobase_pk_filter( +/*================*/ + void* file) /*!< in/out: pointer to ha_innobase */ + MY_ATTRIBUTE((warn_unused_result)); + +/*************************************************************//** +InnoDB check whether pk-filter is active */ + +bool +innobase_pk_filter_is_active( +/*==========================*/ + void* file); /*!< in/out: pointer to ha_innobase */ + /******************************************************************//** Gets information on the durability property requested by thread. Used when writing either a prepare or commit record to the log diff --git a/storage/innobase/include/row0mysql.h b/storage/innobase/include/row0mysql.h index cabca56..c5c9681 100644 --- a/storage/innobase/include/row0mysql.h +++ b/storage/innobase/include/row0mysql.h @@ -828,6 +828,10 @@ struct row_prebuilt_t { 0 if and only if idx_cond == NULL. */ /*----------------------*/ + void* pk_filter; /*!< In PK-filters, pointer to a ha_innobase, + passed to innobase_pk_filter(). + NULL if no PK-filter is pushed. */ + /*----------------------*/ rtr_info_t* rtr_info; /*!< R-tree Search Info */ /*----------------------*/ diff --git a/storage/innobase/include/srv0mon.h b/storage/innobase/include/srv0mon.h index 48dffe0..0433ed5 100644 --- a/storage/innobase/include/srv0mon.h +++ b/storage/innobase/include/srv0mon.h @@ -444,6 +444,11 @@ enum monitor_id_t { MONITOR_ICP_OUT_OF_RANGE, MONITOR_ICP_MATCH, + MONITOR_MODULE_PK_FILTER, + MONITOR_PK_FILTER_CHECKS, + MONITOR_PK_FILTER_POSITIVE, + MONITOR_PK_FILTER_NEGATIVE, + /* Mutex/RW-Lock related counters */ MONITOR_MODULE_LATCHES, MONITOR_LATCHES, diff --git a/storage/innobase/row/row0sel.cc b/storage/innobase/row/row0sel.cc index a878757..2f2e74c 100644 --- a/storage/innobase/row/row0sel.cc +++ b/storage/innobase/row/row0sel.cc @@ -3920,10 +3920,12 @@ row_search_idx_cond_check( ut_ad(rec_offs_validate(rec, prebuilt->index, offsets)); if (!prebuilt->idx_cond) { - return(ICP_MATCH); - } - - MONITOR_INC(MONITOR_ICP_ATTEMPTS); + if (!(innobase_pk_filter_is_active(prebuilt->pk_filter))) { + return(ICP_MATCH); + } + } else { + MONITOR_INC(MONITOR_ICP_ATTEMPTS); + } /* Convert to MySQL format those fields that are needed for evaluating the index condition. */ @@ -3954,9 +3956,25 @@ row_search_idx_cond_check( index, if the case of the column has been updated in the past, or a record has been deleted and a record inserted in a different case. */ - result = innobase_index_cond(prebuilt->idx_cond); + if (prebuilt->idx_cond) { + result = innobase_index_cond(prebuilt->idx_cond); + } else { + result = ICP_MATCH; + } switch (result) { case ICP_MATCH: + if (innobase_pk_filter_is_active(prebuilt->pk_filter)) { + bool pkf_result; + MONITOR_INC(MONITOR_PK_FILTER_CHECKS); + pkf_result = innobase_pk_filter(prebuilt->pk_filter); + if (pkf_result) { + MONITOR_INC(MONITOR_PK_FILTER_POSITIVE); + } else { + MONITOR_INC(MONITOR_PK_FILTER_NEGATIVE); + MONITOR_INC(MONITOR_ICP_MATCH); + return(ICP_NO_MATCH); + } + } /* Convert the remaining fields to MySQL format. If this is a secondary index record, we must defer this until we have fetched the clustered index record. */ diff --git a/storage/innobase/srv/srv0mon.cc b/storage/innobase/srv/srv0mon.cc index 8c62d61..9215a46 100644 --- a/storage/innobase/srv/srv0mon.cc +++ b/storage/innobase/srv/srv0mon.cc @@ -1405,6 +1405,24 @@ static monitor_info_t innodb_counter_info[] = MONITOR_NONE, MONITOR_DEFAULT_START, MONITOR_ICP_MATCH}, + /* ===== Counters for PK-filters Module ===== */ + {"module_pk-filter", "pk-filter", "Primary Keys Filtering", + MONITOR_MODULE, + MONITOR_DEFAULT_START, MONITOR_MODULE_PK_FILTER}, + + {"pk-filter checks", "pk-filter", + "Number of lookups into PK-filters", + MONITOR_NONE, + MONITOR_DEFAULT_START, MONITOR_PK_FILTER_CHECKS}, + + {"pk-filter_positive", "pk-filter", "PK-filter test is positive", + MONITOR_NONE, + MONITOR_DEFAULT_START, MONITOR_PK_FILTER_POSITIVE}, + + {"pk-filter_negarive", "pk-filter", "PK-filter test is negative", + MONITOR_NONE, + MONITOR_DEFAULT_START, MONITOR_PK_FILTER_NEGATIVE}, + /* ========== Mutex monitoring on/off ========== */ {"latch_status", "Latch counters", "Collect latch counters to display via SHOW ENGING INNODB MUTEX", diff --git a/storage/myisam/ha_myisam.cc b/storage/myisam/ha_myisam.cc index 9ab7d15..de7a71d 100644 --- a/storage/myisam/ha_myisam.cc +++ b/storage/myisam/ha_myisam.cc @@ -1880,6 +1880,9 @@ int ha_myisam::index_init(uint idx, bool sorted) active_index=idx; if (pushed_idx_cond_keyno == idx) mi_set_index_cond_func(file, handler_index_cond_check, this); + if (pushed_rowid_filter) + mi_set_rowid_filter_func(file, handler_rowid_filter_check, + handler_rowid_filter_is_active, this); return 0; } @@ -1891,6 +1894,7 @@ int ha_myisam::index_end() //pushed_idx_cond_keyno= MAX_KEY; mi_set_index_cond_func(file, NULL, 0); in_range_check_pushed_down= FALSE; + mi_set_rowid_filter_func(file, NULL, NULL, 0); ds_mrr.dsmrr_close(); #if !defined(DBUG_OFF) && defined(SQL_SELECT_FIXED_FOR_UPDATE) file->update&= ~HA_STATE_AKTIV; // Forget active row @@ -1926,6 +1930,9 @@ int ha_myisam::index_read_idx_map(uchar *buf, uint index, const uchar *key, end_range= NULL; if (index == pushed_idx_cond_keyno) mi_set_index_cond_func(file, handler_index_cond_check, this); + if (pushed_rowid_filter) + mi_set_rowid_filter_func(file, handler_rowid_filter_check, + handler_rowid_filter_is_active, this); res= mi_rkey(file, buf, index, key, keypart_map, find_flag); mi_set_index_cond_func(file, NULL, 0); return res; @@ -2591,6 +2598,14 @@ Item *ha_myisam::idx_cond_push(uint keyno_arg, Item* idx_cond_arg) return NULL; } +bool ha_myisam::rowid_filter_push(Rowid_filter* rowid_filter) +{ + pushed_rowid_filter= rowid_filter; + mi_set_rowid_filter_func(file, handler_rowid_filter_check, + handler_rowid_filter_is_active, this); + return false; +} + struct st_mysql_storage_engine myisam_storage_engine= { MYSQL_HANDLERTON_INTERFACE_VERSION }; @@ -2681,7 +2696,7 @@ my_bool ha_myisam::register_query_cache_table(THD *thd, const char *table_name, If the table size is unknown the SELECT statement can't be cached. - When concurrent inserts are disabled at table open, mi_open() + When concurrent inserts are disabled at table open, mi_ondopen() does not assign a get_status() function. In this case the local ("current") status is never updated. We would wrongly think that we cannot cache the statement. diff --git a/storage/myisam/ha_myisam.h b/storage/myisam/ha_myisam.h index 804963f..f9f11b6 100644 --- a/storage/myisam/ha_myisam.h +++ b/storage/myisam/ha_myisam.h @@ -172,6 +172,8 @@ class ha_myisam: public handler /* Index condition pushdown implementation */ Item *idx_cond_push(uint keyno, Item* idx_cond); + bool rowid_filter_push(Rowid_filter* rowid_filter); + private: DsMrr_impl ds_mrr; friend ICP_RESULT index_cond_func_myisam(void *arg); diff --git a/storage/myisam/mi_extra.c b/storage/myisam/mi_extra.c index c10bf61..e28b9be 100644 --- a/storage/myisam/mi_extra.c +++ b/storage/myisam/mi_extra.c @@ -418,6 +418,16 @@ void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t func, info->index_cond_func_arg= func_arg; } +void mi_set_rowid_filter_func(MI_INFO *info, + rowid_filter_func_t check_func, + rowid_filter_func_t is_active_func, + void *func_arg) +{ + info->rowid_filter_func= check_func; + info->rowid_filter_is_active_func= is_active_func; + info->rowid_filter_func_arg= func_arg; +} + /* Start/Stop Inserting Duplicates Into a Table, WL#1648. */ diff --git a/storage/myisam/mi_key.c b/storage/myisam/mi_key.c index 4bd01dc..8bf63af 100644 --- a/storage/myisam/mi_key.c +++ b/storage/myisam/mi_key.c @@ -529,6 +529,19 @@ ICP_RESULT mi_check_index_cond(register MI_INFO *info, uint keynr, return res; } + +int mi_check_rowid_filter(MI_INFO *info) +{ + return info->rowid_filter_func(info->rowid_filter_func_arg); +} + +int mi_check_rowid_filter_is_active(MI_INFO *info) +{ + if (info->rowid_filter_is_active_func == NULL) + return 0; + return info->rowid_filter_is_active_func(info->rowid_filter_func_arg); +} + /* Retrieve auto_increment info diff --git a/storage/myisam/mi_rkey.c b/storage/myisam/mi_rkey.c index 1dddb8b..c0f9b20 100644 --- a/storage/myisam/mi_rkey.c +++ b/storage/myisam/mi_rkey.c @@ -120,7 +120,9 @@ int mi_rkey(MI_INFO *info, uchar *buf, int inx, const uchar *key, (search_flag != HA_READ_KEY_EXACT || last_used_keyseg != keyinfo->seg + keyinfo->keysegs)) || (info->index_cond_func && - (res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH)) + (res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) || + (mi_check_rowid_filter_is_active(info) && + !mi_check_rowid_filter(info))) { uint not_used[2]; /* diff --git a/storage/myisam/mi_rnext.c b/storage/myisam/mi_rnext.c index 6e3701a..c3af209 100644 --- a/storage/myisam/mi_rnext.c +++ b/storage/myisam/mi_rnext.c @@ -102,7 +102,9 @@ int mi_rnext(MI_INFO *info, uchar *buf, int inx) while ((info->s->concurrent_insert && info->lastpos >= info->state->data_file_length) || (info->index_cond_func && - (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH)) + (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) || + (mi_check_rowid_filter_is_active(info) && + !mi_check_rowid_filter(info))) { /* If we are at the last key on the key page, allow writers to diff --git a/storage/myisam/mi_rnext_same.c b/storage/myisam/mi_rnext_same.c index d685645..ac818bf 100644 --- a/storage/myisam/mi_rnext_same.c +++ b/storage/myisam/mi_rnext_same.c @@ -95,7 +95,9 @@ int mi_rnext_same(MI_INFO *info, uchar *buf) */ if (info->lastpos < info->state->data_file_length && (!info->index_cond_func || - (icp_res= mi_check_index_cond(info, inx, buf)) != ICP_NO_MATCH)) + (icp_res= mi_check_index_cond(info, inx, buf)) != ICP_NO_MATCH) && + (!mi_check_rowid_filter_is_active(info) || + mi_check_rowid_filter(info))) break; } } diff --git a/storage/myisam/mi_rprev.c b/storage/myisam/mi_rprev.c index 27fbda9..2103003 100644 --- a/storage/myisam/mi_rprev.c +++ b/storage/myisam/mi_rprev.c @@ -59,7 +59,9 @@ int mi_rprev(MI_INFO *info, uchar *buf, int inx) while ((share->concurrent_insert && info->lastpos >= info->state->data_file_length) || (info->index_cond_func && - (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH)) + (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) || + (mi_check_rowid_filter_is_active(info) && + !mi_check_rowid_filter(info))) { /* If we are at the last (i.e. first?) key on the key page, diff --git a/storage/myisam/myisamdef.h b/storage/myisam/myisamdef.h index e350626..8eca504 100644 --- a/storage/myisam/myisamdef.h +++ b/storage/myisam/myisamdef.h @@ -305,6 +305,9 @@ struct st_myisam_info my_bool create_unique_index_by_sort; index_cond_func_t index_cond_func; /* Index condition function */ void *index_cond_func_arg; /* parameter for the func */ + rowid_filter_func_t rowid_filter_func; /* rowid filter check function */ + rowid_filter_func_t rowid_filter_is_active_func; /* is activefunction */ + void *rowid_filter_func_arg; /* parameter for the func */ THR_LOCK_DATA lock; uchar *rtree_recursion_state; /* For RTREE */ int rtree_recursion_depth; @@ -724,14 +727,20 @@ int mi_munmap_file(MI_INFO *info); void mi_remap_file(MI_INFO *info, my_off_t size); ICP_RESULT mi_check_index_cond(MI_INFO *info, uint keynr, uchar *record); +int mi_check_rowid_filter(MI_INFO *info); +int mi_check_rowid_filter_is_active(MI_INFO *info); /* Functions needed by mi_check */ int killed_ptr(HA_CHECK *param); void mi_check_print_error(HA_CHECK *param, const char *fmt, ...); void mi_check_print_warning(HA_CHECK *param, const char *fmt, ...); void mi_check_print_info(HA_CHECK *param, const char *fmt, ...); pthread_handler_t thr_find_all_keys(void *arg); -extern void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t func, +extern void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t check_func, void *func_arg); +extern void mi_set_rowid_filter_func(MI_INFO *info, + rowid_filter_func_t check_func, + rowid_filter_func_t is_active_func, + void *func_arg); int flush_blocks(HA_CHECK *param, KEY_CACHE *key_cache, File file, ulonglong *dirty_part_map);