diff options
Diffstat (limited to 'sql/opt_range.h')
| -rw-r--r-- | sql/opt_range.h | 643 |
1 files changed, 596 insertions, 47 deletions
diff --git a/sql/opt_range.h b/sql/opt_range.h index 15f0bf02b34..cdb00ea7d0c 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -24,16 +24,6 @@ #pragma interface /* gcc class implementation */ #endif -#define NO_MIN_RANGE 1 -#define NO_MAX_RANGE 2 -#define NEAR_MIN 4 -#define NEAR_MAX 8 -#define UNIQUE_RANGE 16 -#define EQ_RANGE 32 -#define NULL_RANGE 64 -#define GEOM_FLAG 128 - - typedef struct st_key_part { uint16 key,part, store_length, length; uint8 null_bit; @@ -66,61 +56,619 @@ class QUICK_RANGE :public Sql_alloc { }; -class QUICK_SELECT { +/* + Quick select interface. + This class is a parent for all QUICK_*_SELECT and FT_SELECT classes. + + The usage scenario is as follows: + 1. Create quick select + quick= new QUICK_XXX_SELECT(...); + + 2. Perform lightweight initialization. This can be done in 2 ways: + 2.a: Regular initialization + if (quick->init()) + { + //the only valid action after failed init() call is delete + delete quick; + } + 2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT + if (quick->init_ror_merged_scan()) + delete quick; + + 3. Perform zero, one, or more scans. + while (...) + { + // initialize quick select for scan. This may allocate + // buffers and/or prefetch rows. + if (quick->reset()) + { + //the only valid action after failed reset() call is delete + delete quick; + //abort query + } + + // perform the scan + do + { + res= quick->get_next(); + } while (res && ...) + } + + 4. Delete the select: + delete quick; + +*/ + +class QUICK_SELECT_I +{ +public: + bool sorted; + ha_rows records; /* estimate of # of records to be retrieved */ + double read_time; /* time to perform this retrieval */ + TABLE *head; + /* + Index this quick select uses, or MAX_KEY for quick selects + that use several indexes + */ + uint index; + + /* + Total length of first used_key_parts parts of the key. + Applicable if index!= MAX_KEY. + */ + uint max_used_key_length; + + /* + Max. number of (first) key parts this quick select uses for retrieval. + eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2. + Applicable if index!= MAX_KEY. + */ + uint used_key_parts; + + QUICK_SELECT_I(); + virtual ~QUICK_SELECT_I(){}; + + /* + Do post-constructor initialization. + SYNOPSIS + init() + + init() performs initializations that should have been in constructor if + it was possible to return errors from constructors. The join optimizer may + create and then delete quick selects without retrieving any rows so init() + must not contain any IO or CPU intensive code. + + If init() call fails the only valid action is to delete this quick select, + reset() and get_next() must not be called. + + RETURN + 0 OK + other Error code + */ + virtual int init() = 0; + + /* + Initialize quick select for row retrieval. + SYNOPSIS + reset() + + reset() should be called when it is certain that row retrieval will be + necessary. This call may do heavyweight initialization like buffering first + N records etc. If reset() call fails get_next() must not be called. + Note that reset() may be called several times if + * the quick select is executed in a subselect + * a JOIN buffer is used + + RETURN + 0 OK + other Error code + */ + virtual int reset(void) = 0; + + virtual int get_next() = 0; /* get next record to retrieve */ + + /* Range end should be called when we have looped over the whole index */ + virtual void range_end() {} + + virtual bool reverse_sorted() = 0; + virtual bool unique_key_range() { return false; } + + 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 + }; + + /* Get type of this quick select - one of the QS_TYPE_* values */ + virtual int get_type() = 0; + + /* + Initialize this quick select as a merged scan inside a ROR-union or a ROR- + intersection scan. The caller must not additionally call init() if this + function is called. + SYNOPSIS + init_ror_merged_scan() + reuse_handler If true, the quick select may use table->handler, otherwise + it must create and use a separate handler object. + RETURN + 0 Ok + other Error + */ + virtual int init_ror_merged_scan(bool reuse_handler) + { DBUG_ASSERT(0); return 1; } + + /* + Save ROWID of last retrieved row in file->ref. This used in ROR-merging. + */ + virtual void save_last_pos(){}; + + /* + Append comma-separated list of keys this quick select uses to key_names; + append comma-separated list of corresponding used lengths to used_lengths. + This is used by select_describe. + */ + virtual void add_keys_and_lengths(String *key_names, + String *used_lengths)=0; + + /* + 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) {}; + /* + Return 1 if any index used by this quick select + a) uses field that is listed in passed field list or + b) is automatically updated (like a timestamp) + */ + virtual bool check_if_keys_used(List<Item> *fields); + + /* + rowid of last row retrieved by this quick select. This is used only when + doing ROR-index_merge selects + */ + byte *last_rowid; + + /* + Table record buffer used by this quick select. + */ + byte *record; +#ifndef DBUG_OFF + /* + Print quick select information to DBUG_FILE. Caller is responsible + for locking DBUG_FILE before this call and unlocking it afterwards. + */ + virtual void dbug_dump(int indent, bool verbose)= 0; +#endif +}; + + +struct st_qsel_param; +class SEL_ARG; + +/* + Quick select that does a range scan on a single key. The records are + returned in key order. +*/ +class QUICK_RANGE_SELECT : public QUICK_SELECT_I +{ +protected: + bool next,dont_free; public: - bool next,dont_free,sorted; int error; - uint index, max_used_key_length, used_key_parts; - TABLE *head; +protected: handler *file; - byte *record; - List<QUICK_RANGE> ranges; - List_iterator<QUICK_RANGE> it; - QUICK_RANGE *range; - MEM_ROOT alloc; + /* + If true, this quick select has its "own" handler object which should be + closed no later then this quick select is deleted. + */ + bool free_file; + bool in_range; + uint multi_range_count; /* copy from thd->variables.multi_range_count */ + uint multi_range_length; /* the allocated length for the array */ + uint multi_range_bufsiz; /* copy from thd->variables.read_rnd_buff_size */ + KEY_MULTI_RANGE *multi_range; /* the multi-range array (allocated and + freed by QUICK_RANGE_SELECT) */ + HANDLER_BUFFER *multi_range_buff; /* the handler buffer (allocated and + freed by QUICK_RANGE_SELECT) */ +protected: + friend class TRP_ROR_INTERSECT; + friend + QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, + struct st_table_ref *ref, + ha_rows records); + friend bool get_quick_keys(struct st_qsel_param *param, + QUICK_RANGE_SELECT *quick,KEY_PART *key, + SEL_ARG *key_tree, + char *min_key, uint min_key_flag, + char *max_key, uint max_key_flag); + friend QUICK_RANGE_SELECT *get_quick_select(struct st_qsel_param*,uint idx, + SEL_ARG *key_tree, + MEM_ROOT *alloc); + friend class QUICK_SELECT_DESC; + friend class QUICK_INDEX_MERGE_SELECT; + friend class QUICK_ROR_INTERSECT_SELECT; + + DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */ + QUICK_RANGE **cur_range; /* current element in ranges */ + + QUICK_RANGE *range; KEY_PART *key_parts; KEY_PART_INFO *key_part_info; - ha_rows records; - double read_time; + int cmp_next(QUICK_RANGE *range); + int cmp_prev(QUICK_RANGE *range); + bool row_in_ranges(); +public: + MEM_ROOT alloc; - QUICK_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc=0); - virtual ~QUICK_SELECT(); - void reset(void) { next=0; it.rewind(); } - int init() + QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc=0, + MEM_ROOT *parent_alloc=NULL); + ~QUICK_RANGE_SELECT(); + + int init(); + int reset(void); + int get_next(); + void range_end(); + int get_next_prefix(uint prefix_length, byte *cur_prefix); + bool reverse_sorted() { return 0; } + bool unique_key_range(); + int init_ror_merged_scan(bool reuse_handler); + void save_last_pos() + { file->position(record); } + int get_type() { return QS_TYPE_RANGE; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif +private: + /* Used only by QUICK_SELECT_DESC */ + QUICK_RANGE_SELECT(const QUICK_RANGE_SELECT& org) : QUICK_SELECT_I() { - key_part_info= head->key_info[index].key_part; - return error=file->ha_index_init(index); + bcopy(&org, this, sizeof(*this)); + multi_range_length= 0; + multi_range= NULL; + multi_range_buff= NULL; } - virtual int get_next(); - virtual bool reverse_sorted() { return 0; } - bool unique_key_range(); }; -class QUICK_SELECT_GEOM: public QUICK_SELECT +class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT { public: - QUICK_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg, bool no_alloc) - :QUICK_SELECT(thd, table, index_arg, no_alloc) + QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg, + bool no_alloc, MEM_ROOT *parent_alloc) + :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc) {}; virtual int get_next(); }; -class QUICK_SELECT_DESC: public QUICK_SELECT +/* + QUICK_INDEX_MERGE_SELECT - index_merge access method quick select. + + QUICK_INDEX_MERGE_SELECT uses + * QUICK_RANGE_SELECTs to get rows + * Unique class to remove duplicate rows + + INDEX MERGE OPTIMIZER + 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) + + * If WHERE part contains complex nested AND and OR conditions, some ways + 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 + 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: + + Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique): + prepare() + { + activate 'index only'; + while(retrieve next row for non-CPK scan) + { + if (there is a CPK scan and row will be retrieved by it) + skip this row; + else + put its rowid into Unique; + } + deactivate 'index only'; + } + + Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next + calls): + + fetch() + { + retrieve all rows from row pointers stored in Unique; + free Unique; + retrieve all rows for CPK scan; + } +*/ + +class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I +{ +public: + QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table); + ~QUICK_INDEX_MERGE_SELECT(); + + int init(); + 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 check_if_keys_used(List<Item> *fields); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + + bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); + + /* range quick selects this index_merge read 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(); + + /* used to get rows collected in Unique */ + READ_RECORD read_record; +}; + + +/* + Rowid-Ordered Retrieval (ROR) index intersection quick select. + This quick select produces intersection of row sequences returned + by several QUICK_RANGE_SELECTs it "merges". + + All merged QUICK_RANGE_SELECTs must return rowids in rowid order. + QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too. + + All merged quick selects retrieve {rowid, covered_fields} tuples (not full + table records). + QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used + by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't + cover needed all fields. + + If one of the merged quick selects is a Clustered PK range scan, it is + used only to filter rowid sequence produced by other merged quick selects. +*/ + +class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I +{ +public: + QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table, + bool retrieve_full_rows, + MEM_ROOT *parent_alloc); + ~QUICK_ROR_INTERSECT_SELECT(); + + int init(); + int reset(void); + int get_next(); + bool reverse_sorted() { return false; } + bool unique_key_range() { return false; } + int get_type() { return QS_TYPE_ROR_INTERSECT; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); + bool check_if_keys_used(List<Item> *fields); +#ifndef DBUG_OFF + 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); + + /* + Range quick selects this intersection consists of, not including + cpk_quick. + */ + List<QUICK_RANGE_SELECT> quick_selects; + + /* + Merged quick select that uses Clustered PK, if there is one. This quick + select is not used for row retrieval, it is used for row retrieval. + */ + QUICK_RANGE_SELECT *cpk_quick; + + MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ + THD *thd; /* current thread */ + bool need_to_fetch_row; /* if true, do retrieve full table records. */ + /* in top-level quick select, true if merged scans where initialized */ + bool scans_inited; +}; + + +/* + Rowid-Ordered Retrieval index union select. + This quick select produces union of row sequences returned by several + quick select it "merges". + + All merged quick selects must return rowids in rowid order. + QUICK_ROR_UNION_SELECT will return rows in rowid order, too. + + All merged quick selects are set not to retrieve full table records. + ROR-union quick select always retrieves full records. + +*/ + +class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I { public: - QUICK_SELECT_DESC(QUICK_SELECT *q, uint used_key_parts); + QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table); + ~QUICK_ROR_UNION_SELECT(); + + int init(); + int reset(void); + int get_next(); + bool reverse_sorted() { return false; } + bool unique_key_range() { return false; } + int get_type() { return QS_TYPE_ROR_UNION; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); + bool check_if_keys_used(List<Item> *fields); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + + bool push_quick_back(QUICK_SELECT_I *quick_sel_range); + + List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */ + + QUEUE queue; /* Priority queue for merge operation */ + MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ + + THD *thd; /* current thread */ + byte *cur_rowid; /* buffer used in get_next() */ + byte *prev_rowid; /* rowid of last row returned by get_next() */ + bool have_prev_rowid; /* true if prev_rowid has valid data */ + uint rowid_length; /* table rowid length */ +private: + static int queue_cmp(void *arg, byte *val1, byte *val2); + bool scans_inited; +}; + + +/* + Index scan for GROUP-BY queries with MIN/MAX aggregate functions. + + This class provides a specialized index access method for GROUP-BY queries + of the forms: + + SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)] + FROM T + WHERE [RNG(A_1,...,A_p ; where p <= k)] + [AND EQ(B_1,...,B_m)] + [AND PC(C)] + [AND PA(A_i1,...,A_iq)] + GROUP BY A_1,...,A_k; + + or + + SELECT DISTINCT A_i1,...,A_ik + FROM T + WHERE [RNG(A_1,...,A_p ; where p <= k)] + [AND PA(A_i1,...,A_iq)]; + + where all selected fields are parts of the same index. + The class of queries that can be processed by this quick select is fully + specified in the description of get_best_trp_group_min_max() in opt_range.cc. + + The get_next() method directly produces result tuples, thus obviating the + need to call end_send_group() because all grouping is already done inside + get_next(). + + Since one of the requirements is that all select fields are part of the same + index, this class produces only index keys, and not complete records. +*/ + +class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I +{ +private: + handler *file; /* The handler used to get data. */ + JOIN *join; /* Descriptor of the current query */ + KEY *index_info; /* The index chosen for data access */ + byte *record; /* Buffer where the next record is returned. */ + byte *tmp_record; /* Temporary storage for next_min(), next_max(). */ + byte *group_prefix; /* Key prefix consisting of the GROUP fields. */ + uint group_prefix_len; /* Length of the group prefix. */ + byte *last_prefix; /* Prefix of the last group for detecting EOF. */ + bool have_min; /* Specify whether we are computing */ + bool have_max; /* a MIN, a MAX, or both. */ + bool seen_first_key; /* Denotes whether the first key was retrieved.*/ + KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */ + /* of all MIN/MAX functions. */ + uint min_max_arg_len; /* The length of the MIN/MAX argument field */ + byte *key_infix; /* Infix of constants from equality predicates. */ + uint key_infix_len; + DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */ + uint real_prefix_len; /* Length of key prefix extended with key_infix. */ + List<Item_sum> *min_functions; + List<Item_sum> *max_functions; + List_iterator<Item_sum> *min_functions_it; + List_iterator<Item_sum> *max_functions_it; +public: + /* + The following two members are public to allow easy access from + TRP_GROUP_MIN_MAX::make_quick() + */ + MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */ + QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */ +private: + int next_prefix(); + int next_min_in_range(); + int next_max_in_range(); + int next_min(); + int next_max(); + void update_min_result(); + void update_max_result(); +public: + QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min, + bool have_max, KEY_PART_INFO *min_max_arg_part, + uint group_prefix_len, uint used_key_parts, + KEY *index_info, uint use_index, double read_cost, + ha_rows records, uint key_infix_len, + byte *key_infix, MEM_ROOT *parent_alloc); + ~QUICK_GROUP_MIN_MAX_SELECT(); + bool add_range(SEL_ARG *sel_range); + void update_key_stat(); + bool alloc_buffers(); + int init(); + int reset(); + int get_next(); + bool reverse_sorted() { return false; } + bool unique_key_range() { return false; } + int get_type() { return QS_TYPE_GROUP_MIN_MAX; } + void add_keys_and_lengths(String *key_names, String *used_lengths); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif +}; + + +class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT +{ +public: + QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts); int get_next(); bool reverse_sorted() { return 1; } + int get_type() { return QS_TYPE_RANGE_DESC; } private: - int cmp_prev(QUICK_RANGE *range); bool range_reads_after_key(QUICK_RANGE *range); #ifdef NOT_USED bool test_if_null_range(QUICK_RANGE *range, uint used_key_parts); #endif - void reset(void) { next=0; rev_it.rewind(); } + int reset(void) { next=0; rev_it.rewind(); return 0; } List<QUICK_RANGE> rev_ranges; List_iterator<QUICK_RANGE> rev_it; }; @@ -128,7 +676,7 @@ private: class SQL_SELECT :public Sql_alloc { public: - QUICK_SELECT *quick; // If quick-select used + QUICK_SELECT_I *quick; // If quick-select used COND *cond; // where condition TABLE *head; IO_CACHE file; // Positions to used records @@ -154,19 +702,20 @@ class SQL_SELECT :public Sql_alloc { }; -class FT_SELECT: public QUICK_SELECT { +class FT_SELECT: public QUICK_RANGE_SELECT { public: - FT_SELECT(THD *thd, TABLE *table, uint key): - QUICK_SELECT (thd, table, key, 1) { init(); } + FT_SELECT(THD *thd, TABLE *table, uint key) : + QUICK_RANGE_SELECT (thd, table, key, 1) { VOID(init()); } ~FT_SELECT() { file->ft_end(); } - int init() { return error= file->ft_init(); } - int get_next() { return error= file->ft_read(record); } + int init() { return error=file->ft_init(); } + int reset() { return 0; } + int get_next() { return error=file->ft_read(record); } + int get_type() { return QS_TYPE_FULLTEXT; } }; - -QUICK_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, - struct st_table_ref *ref); - +QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, + struct st_table_ref *ref, + ha_rows records); uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit); #endif |