diff options
Diffstat (limited to 'sql/opt_range.h')
| -rw-r--r-- | sql/opt_range.h | 166 |
1 files changed, 115 insertions, 51 deletions
diff --git a/sql/opt_range.h b/sql/opt_range.h index 1340f0a5525..38a47dffc30 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -288,7 +288,6 @@ public: virtual bool reverse_sorted() = 0; virtual bool unique_key_range() { return false; } - virtual bool clustered_pk_range() { return false; } /* Request that this quick select produces sorted output. Not all quick @@ -298,12 +297,13 @@ public: virtual void need_sorted_output() = 0; enum { QS_TYPE_RANGE = 0, - QS_TYPE_INDEX_MERGE = 1, - QS_TYPE_RANGE_DESC = 2, - QS_TYPE_FULLTEXT = 3, - QS_TYPE_ROR_INTERSECT = 4, - QS_TYPE_ROR_UNION = 5, - QS_TYPE_GROUP_MIN_MAX = 6 + QS_TYPE_INDEX_INTERSECT = 1, + QS_TYPE_INDEX_MERGE = 2, + QS_TYPE_RANGE_DESC = 3, + QS_TYPE_FULLTEXT = 4, + QS_TYPE_ROR_INTERSECT = 5, + QS_TYPE_ROR_UNION = 6, + QS_TYPE_GROUP_MIN_MAX = 7 }; /* Get type of this quick select - one of the QS_TYPE_* values */ @@ -329,6 +329,10 @@ public: Save ROWID of last retrieved row in file->ref. This used in ROR-merging. */ virtual void save_last_pos(){}; + + void add_key_and_length(String *key_names, + String *used_lengths, + bool *first); /* Append comma-separated list of keys this quick select uses to key_names; @@ -338,13 +342,16 @@ public: virtual void add_keys_and_lengths(String *key_names, String *used_lengths)=0; + void add_key_name(String *str, bool *first); + /* Append text representation of quick select structure (what and how is merged) to str. The result is added to "Extra" field in EXPLAIN output. This function is implemented only by quick selects that merge other quick selects output and/or can produce output suitable for merging. */ - virtual void add_info_string(String *str) {}; + virtual void add_info_string(String *str) {} + /* Return 1 if any index used by this quick select uses field which is marked in passed bitmap. @@ -400,7 +407,7 @@ typedef struct st_quick_range_seq_ctx } QUICK_RANGE_SEQ_CTX; range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags); -uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); +bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); /* @@ -486,12 +493,23 @@ private: uint mrr_buf_size, MEM_ROOT *alloc); friend class QUICK_SELECT_DESC; + friend class QUICK_INDEX_SORT_SELECT; friend class QUICK_INDEX_MERGE_SELECT; friend class QUICK_ROR_INTERSECT_SELECT; + friend class QUICK_INDEX_INTERSECT_SELECT; friend class QUICK_GROUP_MIN_MAX_SELECT; - friend uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); + friend bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); friend range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags); + friend + int read_keys_and_merge_scans(THD *thd, TABLE *head, + List<QUICK_RANGE_SELECT> quick_selects, + QUICK_RANGE_SELECT *pk_quick_select, + READ_RECORD *read_record, + bool intersection, + key_map *filtered_scans, + Unique **unique_ptr); + }; @@ -509,40 +527,43 @@ public: /* - QUICK_INDEX_MERGE_SELECT - index_merge access method quick select. + QUICK_INDEX_SORT_SELECT is the base class for the common functionality of: + - QUICK_INDEX_MERGE_SELECT, access based on multi-index merge/union + - QUICK_INDEX_INTERSECT_SELECT, access based on multi-index intersection + - QUICK_INDEX_MERGE_SELECT uses + QUICK_INDEX_SORT_SELECT uses * QUICK_RANGE_SELECTs to get rows - * Unique class to remove duplicate rows + * Unique class + - to remove duplicate rows for QUICK_INDEX_MERGE_SELECT + - to intersect rows for QUICK_INDEX_INTERSECT_SELECT INDEX MERGE OPTIMIZER - Current implementation doesn't detect all cases where index_merge could + Current implementation doesn't detect all cases where index merge could be used, in particular: - * index_merge will never be used if range scan is possible (even if - range scan is more expensive) - * index_merge+'using index' is not supported (this the consequence of - the above restriction) + * index_merge+'using index' is not supported * If WHERE part contains complex nested AND and OR conditions, some ways - to retrieve rows using index_merge will not be considered. The choice + to retrieve rows using index merge will not be considered. The choice of read plan may depend on the order of conjuncts/disjuncts in WHERE part of the query, see comments near imerge_list_or_list and SEL_IMERGE::or_sel_tree_with_checks functions for details. - * There is no "index_merge_ref" method (but index_merge on non-first + * There is no "index_merge_ref" method (but index merge on non-first table in join is possible with 'range checked for each record'). - See comments around SEL_IMERGE class and test_quick_select for more - details. ROW RETRIEVAL ALGORITHM - index_merge uses Unique class for duplicates removal. index_merge takes - advantage of Clustered Primary Key (CPK) if the table has one. - The index_merge algorithm consists of two phases: + index merge/intersection uses Unique class for duplicates removal. + index merge/intersection takes advantage of Clustered Primary Key (CPK) + if the table has one. + The index merge/intersection algorithm consists of two phases: + + Phase 1 + (implemented by a QUICK_INDEX_MERGE_SELECT::read_keys_and_merge call): - Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique): prepare() { activate 'index only'; @@ -556,33 +577,32 @@ public: deactivate 'index only'; } - Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next - calls): + Phase 2 + (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next calls): fetch() { - retrieve all rows from row pointers stored in Unique; + retrieve all rows from row pointers stored in Unique + (merging/intersecting them); free Unique; - retrieve all rows for CPK scan; + if (! intersection) + retrieve all rows for CPK scan; } */ -class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I +class QUICK_INDEX_SORT_SELECT : public QUICK_SELECT_I { +protected: Unique *unique; public: - QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table); - ~QUICK_INDEX_MERGE_SELECT(); + QUICK_INDEX_SORT_SELECT(THD *thd, TABLE *table); + ~QUICK_INDEX_SORT_SELECT(); int init(); void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ } int reset(void); - int get_next(); bool reverse_sorted() { return false; } bool unique_key_range() { return false; } - int get_type() { return QS_TYPE_INDEX_MERGE; } - void add_keys_and_lengths(String *key_names, String *used_lengths); - void add_info_string(String *str); bool is_keys_used(const MY_BITMAP *fields); #ifndef DBUG_OFF void dbug_dump(int indent, bool verbose); @@ -590,21 +610,14 @@ public: bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); - /* range quick selects this index_merge read consists of */ + /* range quick selects this index merge/intersect consists of */ List<QUICK_RANGE_SELECT> quick_selects; /* quick select that uses clustered primary key (NULL if none) */ QUICK_RANGE_SELECT* pk_quick_select; - /* true if this select is currently doing a clustered PK scan */ - bool doing_pk_scan; - MEM_ROOT alloc; THD *thd; - int read_keys_and_merge(); - - bool clustered_pk_range() { return test(pk_quick_select); } - virtual bool is_valid() { List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); @@ -620,12 +633,48 @@ public: } return valid; } - + virtual int read_keys_and_merge()= 0; /* used to get rows collected in Unique */ READ_RECORD read_record; }; + +class QUICK_INDEX_MERGE_SELECT : public QUICK_INDEX_SORT_SELECT +{ +private: + /* true if this select is currently doing a clustered PK scan */ + bool doing_pk_scan; +protected: + int read_keys_and_merge(); + +public: + QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table) + :QUICK_INDEX_SORT_SELECT(thd, table) {} + + int get_next(); + int get_type() { return QS_TYPE_INDEX_MERGE; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); +}; + +class QUICK_INDEX_INTERSECT_SELECT : public QUICK_INDEX_SORT_SELECT +{ +protected: + int read_keys_and_merge(); + +public: + QUICK_INDEX_INTERSECT_SELECT(THD *thd, TABLE *table) + :QUICK_INDEX_SORT_SELECT(thd, table) {} + + key_map filtered_scans; + int get_next(); + int get_type() { return QS_TYPE_INDEX_INTERSECT; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); +}; + + /* Rowid-Ordered Retrieval (ROR) index intersection quick select. This quick select produces intersection of row sequences returned @@ -666,22 +715,30 @@ public: void dbug_dump(int indent, bool verbose); #endif int init_ror_merged_scan(bool reuse_handler); - bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); + bool push_quick_back(MEM_ROOT *alloc, QUICK_RANGE_SELECT *quick_sel_range); + + class QUICK_SELECT_WITH_RECORD : public Sql_alloc + { + public: + QUICK_RANGE_SELECT *quick; + uchar *key_tuple; + ~QUICK_SELECT_WITH_RECORD() { delete quick; } + }; /* Range quick selects this intersection consists of, not including cpk_quick. */ - List<QUICK_RANGE_SELECT> quick_selects; + List<QUICK_SELECT_WITH_RECORD> quick_selects; virtual bool is_valid() { - List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); - QUICK_RANGE_SELECT *quick; + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + QUICK_SELECT_WITH_RECORD *quick; bool valid= true; while ((quick= it++)) { - if (!quick->is_valid()) + if (!quick->quick->is_valid()) { valid= false; break; @@ -911,6 +968,13 @@ class SQL_SELECT :public Sql_alloc { public: QUICK_SELECT_I *quick; // If quick-select used COND *cond; // where condition + + /* + When using Index Condition Pushdown: condition that we've had before + extracting and pushing index condition. + In other cases, NULL. + */ + Item *pre_idx_push_select_cond; TABLE *head; IO_CACHE file; // Positions to used records ha_rows records; // Records in use if read from file |