diff options
Diffstat (limited to 'sql/opt_range.h')
| -rw-r--r-- | sql/opt_range.h | 1816 |
1 files changed, 1816 insertions, 0 deletions
diff --git a/sql/opt_range.h b/sql/opt_range.h new file mode 100644 index 00000000..1014176e --- /dev/null +++ b/sql/opt_range.h @@ -0,0 +1,1816 @@ +/* + Copyright (c) 2000, 2010, Oracle and/or its affiliates. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + + +/* classes to use when handling where clause */ + +#ifndef _opt_range_h +#define _opt_range_h + +#ifdef USE_PRAGMA_INTERFACE +#pragma interface /* gcc class implementation */ +#endif + +#include "records.h" /* READ_RECORD */ +#include "queues.h" /* QUEUE */ +#include "filesort.h" /* SORT_INFO */ + +/* + It is necessary to include set_var.h instead of item.h because there + are dependencies on include order for set_var.h and item.h. This + will be resolved later. +*/ +#include "sql_class.h" // set_var.h: THD +#include "set_var.h" /* Item */ + +class JOIN; +class Item_sum; + +struct KEY_PART { + uint16 key,part; + /* See KEY_PART_INFO for meaning of the next two: */ + uint16 store_length, length; + uint8 null_bit; + /* + Keypart flags (0 when this structure is used by partition pruning code + for fake partitioning index description) + */ + uint8 flag; + Field *field; + Field::imagetype image_type; +}; + + +class RANGE_OPT_PARAM; +/* + A construction block of the SEL_ARG-graph. + + The following description only covers graphs of SEL_ARG objects with + sel_arg->type==KEY_RANGE: + + One SEL_ARG object represents an "elementary interval" in form + + min_value <=? table.keypartX <=? max_value + + The interval is a non-empty interval of any kind: with[out] minimum/maximum + bound, [half]open/closed, single-point interval, etc. + + 1. SEL_ARG GRAPH STRUCTURE + + SEL_ARG objects are linked together in a graph. The meaning of the graph + is better demostrated by an example: + + tree->keys[i] + | + | $ $ + | part=1 $ part=2 $ part=3 + | $ $ + | +-------+ $ +-------+ $ +--------+ + | | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 | + | +-------+ $ +-------+ $ +--------+ + | | $ $ | + | | $ $ +--------+ + | | $ $ | kp3=12 | + | | $ $ +--------+ + | +-------+ $ $ + \->| kp1=2 |--$--------------$-+ + +-------+ $ $ | +--------+ + | $ $ ==>| kp3=11 | + +-------+ $ $ | +--------+ + | kp1=3 |--$--------------$-+ | + +-------+ $ $ +--------+ + | $ $ | kp3=14 | + ... $ $ +--------+ + + The entire graph is partitioned into "interval lists". + + An interval list is a sequence of ordered disjoint intervals over the same + key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally, + all intervals in the list form an RB-tree, linked via left/right/parent + pointers. The RB-tree root SEL_ARG object will be further called "root of the + interval list". + + In the example pic, there are 4 interval lists: + "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13". + The vertical lines represent SEL_ARG::next/prev pointers. + + In an interval list, each member X may have SEL_ARG::next_key_part pointer + pointing to the root of another interval list Y. The pointed interval list + must cover a key part with greater number (i.e. Y->part > X->part). + + In the example pic, the next_key_part pointers are represented by + horisontal lines. + + 2. SEL_ARG GRAPH SEMANTICS + + It represents a condition in a special form (we don't have a name for it ATM) + The SEL_ARG::next/prev is "OR", and next_key_part is "AND". + + For example, the picture represents the condition in form: + (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR + (kp1=2 AND (kp3=11 OR kp3=14)) OR + (kp1=3 AND (kp3=11 OR kp3=14)) + + + 3. SEL_ARG GRAPH USE + + Use get_mm_tree() to construct SEL_ARG graph from WHERE condition. + Then walk the SEL_ARG graph and get a list of dijsoint ordered key + intervals (i.e. intervals in form + + (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K) + + Those intervals can be used to access the index. The uses are in: + - check_quick_select() - Walk the SEL_ARG graph and find an estimate of + how many table records are contained within all + intervals. + - get_quick_select() - Walk the SEL_ARG, materialize the key intervals, + and create QUICK_RANGE_SELECT object that will + read records within these intervals. + + 4. SPACE COMPLEXITY NOTES + + SEL_ARG graph is a representation of an ordered disjoint sequence of + intervals over the ordered set of index tuple values. + + For multi-part keys, one can construct a WHERE expression such that its + list of intervals will be of combinatorial size. Here is an example: + + (keypart1 IN (1,2, ..., n1)) AND + (keypart2 IN (1,2, ..., n2)) AND + (keypart3 IN (1,2, ..., n3)) + + For this WHERE clause the list of intervals will have n1*n2*n3 intervals + of form + + (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i} + + SEL_ARG graph structure aims to reduce the amount of required space by + "sharing" the elementary intervals when possible (the pic at the + beginning of this comment has examples of such sharing). The sharing may + prevent combinatorial blowup: + + There are WHERE clauses that have combinatorial-size interval lists but + will be represented by a compact SEL_ARG graph. + Example: + (keypartN IN (1,2, ..., n1)) AND + ... + (keypart2 IN (1,2, ..., n2)) AND + (keypart1 IN (1,2, ..., n3)) + + but not in all cases: + + - There are WHERE clauses that do have a compact SEL_ARG-graph + representation but get_mm_tree() and its callees will construct a + graph of combinatorial size. + Example: + (keypart1 IN (1,2, ..., n1)) AND + (keypart2 IN (1,2, ..., n2)) AND + ... + (keypartN IN (1,2, ..., n3)) + + - There are WHERE clauses for which the minimal possible SEL_ARG graph + representation will have combinatorial size. + Example: + By induction: Let's take any interval on some keypart in the middle: + + kp15=c0 + + Then let's AND it with this interval 'structure' from preceding and + following keyparts: + + (kp14=c1 AND kp16=c3) OR keypart14=c2) (*) + + We will obtain this SEL_ARG graph: + + kp14 $ kp15 $ kp16 + $ $ + +---------+ $ +---------+ $ +---------+ + | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 | + +---------+ $ +---------+ $ +---------+ + | $ $ + +---------+ $ +---------+ $ + | kp14=c2 |--$-->| kp15=c0 | $ + +---------+ $ +---------+ $ + $ $ + + Note that we had to duplicate "kp15=c0" and there was no way to avoid + that. + The induction step: AND the obtained expression with another "wrapping" + expression like (*). + When the process ends because of the limit on max. number of keyparts + we'll have: + + WHERE clause length is O(3*#max_keyparts) + SEL_ARG graph size is O(2^(#max_keyparts/2)) + + (it is also possible to construct a case where instead of 2 in 2^n we + have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31 + nodes) + + We avoid consuming too much memory by setting a limit on the number of + SEL_ARG object we can construct during one range analysis invocation. + + 5. SEL_ARG GRAPH WEIGHT + + A SEL_ARG graph has a property we call weight, and we define it as follows: + + <definition> + If the SEL_ARG graph does not have any node with multiple incoming + next_key_part edges, then its weight is the number of SEL_ARG objects used. + + If there is a node with multiple incoming next_key_part edges, clone that + node, (and the nodes connected to it via prev/next links) and redirect one + of the incoming next_key_part edges to the clone. + + Continue with cloning until we get a graph that has no nodes with multiple + incoming next_key_part edges. Then, the number of SEL_ARG objects in the + graph is the weight of the original graph. + </definition> + + Example: + + kp1 $ kp2 $ kp3 + $ $ + | +-------+ $ $ + \->| kp1=2 |--$--------------$-+ + +-------+ $ $ | +--------+ + | $ $ ==>| kp3=11 | + +-------+ $ $ | +--------+ + | kp1>3 |--$--------------$-+ | + +-------+ $ $ +--------+ + $ $ | kp3=14 | + $ $ +--------+ + $ $ | + $ $ +--------+ + $ $ | kp3=14 | + $ $ +--------+ + + Here, the weight is 2 + 2*3=8. + + The rationale behind using this definition of weight is: + - it has the same order-of-magnitude as the number of ranges that the + SEL_ARG graph is describing, + - it is a lot easier to compute than computing the number of ranges, + - it can be updated incrementally when performing AND/OR operations on + parts of the graph. +*/ + +class SEL_ARG :public Sql_alloc +{ + static int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag, + uint8 b_flag); +public: + uint8 min_flag,max_flag,maybe_flag; + uint8 part; // Which key part + uint8 maybe_null; + /* + The ordinal number the least significant component encountered in + the ranges of the SEL_ARG tree (the first component has number 1) + + Note: this number is currently not precise, it is an upper bound. + @seealso SEL_ARG::get_max_key_part() + */ + uint16 max_part_no; + /* + Number of children of this element in the RB-tree, plus 1 for this + element itself. + */ + uint32 elements; + /* + Valid only for elements which are RB-tree roots: Number of times this + RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by + SEL_TREE::keys[i] or by a temporary SEL_ARG* variable) + */ + ulong use_count; + + Field *field; + uchar *min_value,*max_value; // Pointer to range + + /* + eq_tree() requires that left == right == 0 if the type is MAYBE_KEY. + */ + SEL_ARG *left,*right; /* R-B tree children */ + SEL_ARG *next,*prev; /* Links for bi-directional interval list */ + SEL_ARG *parent; /* R-B tree parent */ + SEL_ARG *next_key_part; + enum leaf_color { BLACK,RED } color; + enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; + + /* + For R-B root nodes only: the graph weight, as defined above in the + SEL_ARG GRAPH WEIGHT section. + */ + uint weight; + enum { MAX_WEIGHT = 32000 }; + + void update_weight_locally(); +#ifndef DBUG_OFF + uint verify_weight(); +#endif + + /* See RANGE_OPT_PARAM::alloced_sel_args */ + enum { MAX_SEL_ARGS = 16000 }; + + SEL_ARG() {} + SEL_ARG(SEL_ARG &); + SEL_ARG(Field *,const uchar *, const uchar *); + SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, + uint8 min_flag, uint8 max_flag, uint8 maybe_flag); + SEL_ARG(enum Type type_arg) + :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, + elements(1),use_count(1),left(0),right(0), + next_key_part(0), color(BLACK), type(type_arg), weight(1) + {} + /** + returns true if a range predicate is equal. Use all_same() + to check for equality of all the predicates on this keypart. + */ + inline bool is_same(const SEL_ARG *arg) const + { + if (type != arg->type || part != arg->part) + return false; + if (type != KEY_RANGE) + return true; + return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0; + } + + uint get_max_key_part() const; + + /** + returns true if all the predicates in the keypart tree are equal + */ + bool all_same(const SEL_ARG *arg) const + { + if (type != arg->type || part != arg->part) + return false; + if (type != KEY_RANGE) + return true; + if (arg == this) + return true; + const SEL_ARG *cmp_arg= arg->first(); + const SEL_ARG *cur_arg= first(); + for (; cur_arg && cmp_arg && cur_arg->is_same(cmp_arg); + cur_arg= cur_arg->next, cmp_arg= cmp_arg->next) ; + if (cur_arg || cmp_arg) + return false; + return true; + } + inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; } + inline void maybe_smaller() { maybe_flag=1; } + /* Return true iff it's a single-point null interval */ + inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } + inline int cmp_min_to_min(const SEL_ARG* arg) const + { + return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag); + } + inline int cmp_min_to_max(const SEL_ARG* arg) const + { + return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag); + } + inline int cmp_max_to_max(const SEL_ARG* arg) const + { + return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag); + } + inline int cmp_max_to_min(const SEL_ARG* arg) const + { + return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag); + } + SEL_ARG *clone_and(THD *thd, SEL_ARG* arg) + { // Get overlapping range + uchar *new_min,*new_max; + uint8 flag_min,flag_max; + if (cmp_min_to_min(arg) >= 0) + { + new_min=min_value; flag_min=min_flag; + } + else + { + new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */ + } + if (cmp_max_to_max(arg) <= 0) + { + new_max=max_value; flag_max=max_flag; + } + else + { + new_max=arg->max_value; flag_max=arg->max_flag; + } + return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, + flag_max, + MY_TEST(maybe_flag && arg->maybe_flag)); + } + SEL_ARG *clone_first(SEL_ARG *arg) + { // min <= X < arg->min + return new SEL_ARG(field,part, min_value, arg->min_value, + min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, + maybe_flag | arg->maybe_flag); + } + SEL_ARG *clone_last(SEL_ARG *arg) + { // min <= X <= key_max + return new SEL_ARG(field, part, min_value, arg->max_value, + min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); + } + SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); + + bool copy_min(SEL_ARG* arg) + { // Get overlapping range + if (cmp_min_to_min(arg) > 0) + { + min_value=arg->min_value; min_flag=arg->min_flag; + if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) == + (NO_MAX_RANGE | NO_MIN_RANGE)) + return 1; // Full range + } + maybe_flag|=arg->maybe_flag; + return 0; + } + bool copy_max(SEL_ARG* arg) + { // Get overlapping range + if (cmp_max_to_max(arg) <= 0) + { + max_value=arg->max_value; max_flag=arg->max_flag; + if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) == + (NO_MAX_RANGE | NO_MIN_RANGE)) + return 1; // Full range + } + maybe_flag|=arg->maybe_flag; + return 0; + } + + void copy_min_to_min(SEL_ARG *arg) + { + min_value=arg->min_value; min_flag=arg->min_flag; + } + void copy_min_to_max(SEL_ARG *arg) + { + max_value=arg->min_value; + max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX; + } + void copy_max_to_min(SEL_ARG *arg) + { + min_value=arg->max_value; + min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN; + } + /* returns a number of keypart values (0 or 1) appended to the key buffer */ + int store_min(uint length, uchar **min_key,uint min_key_flag) + { + /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */ + if ((min_flag & GEOM_FLAG) || + (!(min_flag & NO_MIN_RANGE) && + !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN)))) + { + if (maybe_null && *min_value) + { + **min_key=1; + bzero(*min_key+1,length-1); + } + else + memcpy(*min_key,min_value,length); + (*min_key)+= length; + return 1; + } + return 0; + } + /* returns a number of keypart values (0 or 1) appended to the key buffer */ + int store_max(uint length, uchar **max_key, uint max_key_flag) + { + if (!(max_flag & NO_MAX_RANGE) && + !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX))) + { + if (maybe_null && *max_value) + { + **max_key=1; + bzero(*max_key+1,length-1); + } + else + memcpy(*max_key,max_value,length); + (*max_key)+= length; + return 1; + } + return 0; + } + + /* + Returns a number of keypart values appended to the key buffer + for min key and max key. This function is used by both Range + Analysis and Partition pruning. For partition pruning we have + to ensure that we don't store also subpartition fields. Thus + we have to stop at the last partition part and not step into + the subpartition fields. For Range Analysis we set last_part + to MAX_KEY which we should never reach. + */ + int store_min_key(KEY_PART *key, + uchar **range_key, + uint *range_key_flag, + uint last_part) + { + SEL_ARG *key_tree= first(); + uint res= key_tree->store_min(key[key_tree->part].store_length, + range_key, *range_key_flag); + // add flags only if a key_part is written to the buffer + if (!res) + return 0; + *range_key_flag|= key_tree->min_flag; + if (key_tree->next_key_part && + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + key_tree->part != last_part && + key_tree->next_key_part->part == key_tree->part+1 && + !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) + res+= key_tree->next_key_part->store_min_key(key, + range_key, + range_key_flag, + last_part); + return res; + } + + /* returns a number of keypart values appended to the key buffer */ + int store_max_key(KEY_PART *key, + uchar **range_key, + uint *range_key_flag, + uint last_part) + { + SEL_ARG *key_tree= last(); + uint res=key_tree->store_max(key[key_tree->part].store_length, + range_key, *range_key_flag); + if (!res) + return 0; + *range_key_flag|= key_tree->max_flag; + if (key_tree->next_key_part && + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + key_tree->part != last_part && + key_tree->next_key_part->part == key_tree->part+1 && + !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) + res+= key_tree->next_key_part->store_max_key(key, + range_key, + range_key_flag, + last_part); + return res; + } + + SEL_ARG *insert(SEL_ARG *key); + SEL_ARG *tree_delete(SEL_ARG *key); + SEL_ARG *find_range(SEL_ARG *key); + SEL_ARG *rb_insert(SEL_ARG *leaf); + friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par); +#ifdef EXTRA_DEBUG + friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent); + void test_use_count(SEL_ARG *root); +#endif + SEL_ARG *first(); + const SEL_ARG *first() const; + SEL_ARG *last(); + void make_root(); + inline bool simple_key() + { + return !next_key_part && elements == 1; + } + void increment_use_count(long count) + { + if (next_key_part) + { + next_key_part->use_count+=count; + count*= (next_key_part->use_count-count); + for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next) + if (pos->next_key_part) + pos->increment_use_count(count); + } + } + void incr_refs() + { + increment_use_count(1); + use_count++; + } + void incr_refs_all() + { + for (SEL_ARG *pos=first(); pos ; pos=pos->next) + { + pos->increment_use_count(1); + } + use_count++; + } + void free_tree() + { + for (SEL_ARG *pos=first(); pos ; pos=pos->next) + if (pos->next_key_part) + { + pos->next_key_part->use_count--; + pos->next_key_part->free_tree(); + } + } + + inline SEL_ARG **parent_ptr() + { + return parent->left == this ? &parent->left : &parent->right; + } + + + /* + Check if this SEL_ARG object represents a single-point interval + + SYNOPSIS + is_singlepoint() + + DESCRIPTION + Check if this SEL_ARG object (not tree) represents a single-point + interval, i.e. if it represents a "keypart = const" or + "keypart IS NULL". + + RETURN + TRUE This SEL_ARG object represents a singlepoint interval + FALSE Otherwise + */ + + bool is_singlepoint() const + { + /* + Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) + flags, and the same for right edge. + */ + if (min_flag || max_flag) + return FALSE; + uchar *min_val= min_value; + uchar *max_val= max_value; + + if (maybe_null) + { + /* First byte is a NULL value indicator */ + if (*min_val != *max_val) + return FALSE; + + if (*min_val) + return TRUE; /* This "x IS NULL" */ + min_val++; + max_val++; + } + return !field->key_cmp(min_val, max_val); + } + SEL_ARG *clone_tree(RANGE_OPT_PARAM *param); +}; + +extern MYSQL_PLUGIN_IMPORT SEL_ARG null_element; + +class SEL_ARG_IMPOSSIBLE: public SEL_ARG +{ +public: + SEL_ARG_IMPOSSIBLE(Field *field) + :SEL_ARG(field, 0, 0) + { + type= SEL_ARG::IMPOSSIBLE; + } +}; + + +class RANGE_OPT_PARAM +{ +public: + THD *thd; /* Current thread handle */ + TABLE *table; /* Table being analyzed */ + table_map prev_tables; + table_map read_tables; + table_map current_table; /* Bit of the table being analyzed */ + + /* Array of parts of all keys for which range analysis is performed */ + KEY_PART *key_parts; + KEY_PART *key_parts_end; + MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */ + MEM_ROOT *old_root; /* Memory that will last until the query end */ + /* + Number of indexes used in range analysis (In SEL_TREE::keys only first + #keys elements are not empty) + */ + uint keys; + + /* + If true, the index descriptions describe real indexes (and it is ok to + call field->optimize_range(real_keynr[...], ...). + Otherwise index description describes fake indexes. + */ + bool using_real_indexes; + + /* + Aggressively remove "scans" that do not have conditions on first + keyparts. Such scans are usable when doing partition pruning but not + regular range optimization. + */ + bool remove_jump_scans; + + /* + TRUE <=> Range analyzer should remove parts of condition that are found + to be always FALSE. + */ + bool remove_false_where_parts; + + /* + used_key_no -> table_key_no translation table. Only makes sense if + using_real_indexes==TRUE + */ + uint real_keynr[MAX_KEY]; + + /* + Used to store 'current key tuples', in both range analysis and + partitioning (list) analysis + */ + uchar *min_key; + uchar *max_key; + + /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ + uint alloced_sel_args; + + bool force_default_mrr; + KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */ + + bool statement_should_be_aborted() const + { + return + thd->killed || + thd->is_fatal_error || + thd->is_error() || + alloced_sel_args > SEL_ARG::MAX_SEL_ARGS; + } +}; + + +class Explain_quick_select; +/* + A "MIN_TUPLE < tbl.key_tuple < MAX_TUPLE" interval. + + One of endpoints may be absent. 'flags' member has flags which tell whether + the endpoints are '<' or '<='. +*/ +class QUICK_RANGE :public Sql_alloc { + public: + uchar *min_key,*max_key; + uint16 min_length,max_length,flag; + key_part_map min_keypart_map, // bitmap of used keyparts in min_key + max_keypart_map; // bitmap of used keyparts in max_key +#ifdef HAVE_valgrind + uint16 dummy; /* Avoid warnings on 'flag' */ +#endif + QUICK_RANGE(); /* Full range */ + QUICK_RANGE(THD *thd, const uchar *min_key_arg, uint min_length_arg, + key_part_map min_keypart_map_arg, + const uchar *max_key_arg, uint max_length_arg, + key_part_map max_keypart_map_arg, + uint flag_arg) + : min_key((uchar*) thd->memdup(min_key_arg, min_length_arg + 1)), + max_key((uchar*) thd->memdup(max_key_arg, max_length_arg + 1)), + min_length((uint16) min_length_arg), + max_length((uint16) max_length_arg), + flag((uint16) flag_arg), + min_keypart_map(min_keypart_map_arg), + max_keypart_map(max_keypart_map_arg) + { +#ifdef HAVE_valgrind + dummy=0; +#endif + } + + /** + Initalizes a key_range object for communication with storage engine. + + This function facilitates communication with the Storage Engine API by + translating the minimum endpoint of the interval represented by this + QUICK_RANGE into an index range endpoint specifier for the engine. + + @param Pointer to an uninitialized key_range C struct. + + @param prefix_length The length of the search key prefix to be used for + lookup. + + @param keypart_map A set (bitmap) of keyparts to be used. + */ + void make_min_endpoint(key_range *kr, uint prefix_length, + key_part_map keypart_map) { + make_min_endpoint(kr); + kr->length= MY_MIN(kr->length, prefix_length); + kr->keypart_map&= keypart_map; + } + + /** + Initalizes a key_range object for communication with storage engine. + + This function facilitates communication with the Storage Engine API by + translating the minimum endpoint of the interval represented by this + QUICK_RANGE into an index range endpoint specifier for the engine. + + @param Pointer to an uninitialized key_range C struct. + */ + void make_min_endpoint(key_range *kr) { + kr->key= (const uchar*)min_key; + kr->length= min_length; + kr->keypart_map= min_keypart_map; + kr->flag= ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY : + (flag & EQ_RANGE) ? HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT); + } + + /** + Initalizes a key_range object for communication with storage engine. + + This function facilitates communication with the Storage Engine API by + translating the maximum endpoint of the interval represented by this + QUICK_RANGE into an index range endpoint specifier for the engine. + + @param Pointer to an uninitialized key_range C struct. + + @param prefix_length The length of the search key prefix to be used for + lookup. + + @param keypart_map A set (bitmap) of keyparts to be used. + */ + void make_max_endpoint(key_range *kr, uint prefix_length, + key_part_map keypart_map) { + make_max_endpoint(kr); + kr->length= MY_MIN(kr->length, prefix_length); + kr->keypart_map&= keypart_map; + } + + /** + Initalizes a key_range object for communication with storage engine. + + This function facilitates communication with the Storage Engine API by + translating the maximum endpoint of the interval represented by this + QUICK_RANGE into an index range endpoint specifier for the engine. + + @param Pointer to an uninitialized key_range C struct. + */ + void make_max_endpoint(key_range *kr) { + kr->key= (const uchar*)max_key; + kr->length= max_length; + kr->keypart_map= max_keypart_map; + /* + We use READ_AFTER_KEY here because if we are reading on a key + prefix we want to find all keys with this prefix + */ + kr->flag= (flag & NEAR_MAX ? HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY); + } +}; + + +/* + 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; + + NOTE + quick select doesn't use Sql_alloc/MEM_ROOT allocation because "range + checked for each record" functionality may create/destroy + O(#records_in_some_table) quick selects during query execution. +*/ + +class QUICK_SELECT_I +{ +public: + 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. + + For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts. + */ + 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; } + + /* + Request that this quick select produces sorted output. Not all quick + selects can do it, the caller is responsible for calling this function + only for those quick selects that can. + */ + virtual void need_sorted_output() = 0; + enum { + QS_TYPE_RANGE = 0, + 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 */ + 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, MEM_ROOT *alloc) + { DBUG_ASSERT(0); return 1; } + + /* + 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; + 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; + + void add_key_name(String *str, bool *first); + + /* Save information about quick select's query plan */ + virtual Explain_quick_select* get_explain(MEM_ROOT *alloc)= 0; + + /* + Return 1 if any index used by this quick select + uses field which is marked in passed bitmap. + */ + virtual bool is_keys_used(const MY_BITMAP *fields); + + /** + Simple sanity check that the quick select has been set up + correctly. Function is overridden by quick selects that merge + indices. + */ + virtual bool is_valid() { return index != MAX_KEY; }; + + /* + rowid of last row retrieved by this quick select. This is used only when + doing ROR-index_merge selects + */ + uchar *last_rowid; + + /* + Table record buffer used by this quick select. + */ + uchar *record; + + virtual void replace_handler(handler *new_file) + { + DBUG_ASSERT(0); /* Only supported in QUICK_RANGE_SELECT */ + } + +#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 + + /* + Returns a QUICK_SELECT with reverse order of to the index. + */ + virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) { return NULL; } + + /* + Add the key columns used by the quick select into table's read set. + + This is used by an optimization in filesort. + */ + virtual void add_used_key_part_to_set()=0; +}; + + +struct st_qsel_param; +class PARAM; + + +/* + MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal + context. +*/ +typedef struct st_quick_range_seq_ctx +{ + QUICK_RANGE **first; + QUICK_RANGE **cur; + QUICK_RANGE **last; +} QUICK_RANGE_SEQ_CTX; + +range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags); +bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); + + +/* + 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: + THD *thd; + bool no_alloc; + MEM_ROOT *parent_alloc; + + /* true if we enabled key only reads */ + handler *file; + + /* Members to deal with case when this quick select is a ROR-merged scan */ + bool in_ror_merged_scan; + MY_BITMAP column_bitmap; + bool free_file; /* TRUE <=> this->file is "owned" by this quick select */ + + /* Range pointers to be used when not using MRR interface */ + /* Members needed to use the MRR interface */ + QUICK_RANGE_SEQ_CTX qr_traversal_ctx; +public: + uint mrr_flags; /* Flags to be used with MRR interface */ +protected: + uint mrr_buf_size; /* copy from thd->variables.mrr_buff_size */ + HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */ + + /* Info about index we're scanning */ + + DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */ + QUICK_RANGE **cur_range; /* current element in ranges */ + + QUICK_RANGE *last_range; + + KEY_PART *key_parts; + KEY_PART_INFO *key_part_info; + + bool dont_free; /* Used by QUICK_SELECT_DESC */ + + int cmp_next(QUICK_RANGE *range); + int cmp_prev(QUICK_RANGE *range); + bool row_in_ranges(); +public: + MEM_ROOT alloc; + + QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc, + MEM_ROOT *parent_alloc, bool *create_err); + ~QUICK_RANGE_SELECT(); + virtual QUICK_RANGE_SELECT *clone(bool *create_error) + { return new QUICK_RANGE_SELECT(thd, head, index, no_alloc, parent_alloc, + create_error); } + + void need_sorted_output(); + int init(); + int reset(void); + int get_next(); + void range_end(); + int get_next_prefix(uint prefix_length, uint group_key_parts, + uchar *cur_prefix); + bool reverse_sorted() { return 0; } + bool unique_key_range(); + int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc); + 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); + Explain_quick_select *get_explain(MEM_ROOT *alloc); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + virtual void replace_handler(handler *new_file) { file= new_file; } + QUICK_SELECT_I *make_reverse(uint used_key_parts_arg); + + virtual void add_used_key_part_to_set(); + +private: + /* Default copy ctor used by QUICK_SELECT_DESC */ + 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(PARAM *param, QUICK_RANGE_SELECT *quick, + KEY_PART *key, SEL_ARG *key_tree, + uchar *min_key, uint min_key_flag, + uchar *max_key, uint max_key_flag); + friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx, + SEL_ARG *key_tree, + uint mrr_flags, + 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 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); + +}; + + +class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT +{ +public: + QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg, + bool no_alloc, MEM_ROOT *parent_alloc, + bool *create_err) + :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc, + create_err) + {}; + virtual QUICK_RANGE_SELECT *clone(bool *create_error) + { + DBUG_ASSERT(0); + return new QUICK_RANGE_SELECT_GEOM(thd, head, index, no_alloc, + parent_alloc, create_error); + } + virtual int get_next(); +}; + + +/* + 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_SORT_SELECT uses + * QUICK_RANGE_SELECTs to get 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 + be used, in particular: + + * 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 + 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'). + + + ROW RETRIEVAL ALGORITHM + + 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): + + 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 + (merging/intersecting them); + free Unique; + if (! intersection) + retrieve all rows for CPK scan; + } +*/ + +class QUICK_INDEX_SORT_SELECT : public QUICK_SELECT_I +{ +protected: + Unique *unique; +public: + 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); + bool reverse_sorted() { return false; } + bool unique_key_range() { return false; } + bool is_keys_used(const MY_BITMAP *fields); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + Explain_quick_select *get_explain(MEM_ROOT *alloc); + + bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); + + /* 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; + + MEM_ROOT alloc; + THD *thd; + virtual bool is_valid() + { + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + QUICK_RANGE_SELECT *quick; + bool valid= true; + while ((quick= it++)) + { + if (!quick->is_valid()) + { + valid= false; + break; + } + } + return valid; + } + virtual int read_keys_and_merge()= 0; + /* used to get rows collected in Unique */ + READ_RECORD read_record; + + virtual void add_used_key_part_to_set(); +}; + + + +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_arg, TABLE *table) + :QUICK_INDEX_SORT_SELECT(thd_arg, table) {} + + int get_next(); + int get_type() { return QS_TYPE_INDEX_MERGE; } + void add_keys_and_lengths(String *key_names, String *used_lengths); +}; + +class QUICK_INDEX_INTERSECT_SELECT : public QUICK_INDEX_SORT_SELECT +{ +protected: + int read_keys_and_merge(); + +public: + QUICK_INDEX_INTERSECT_SELECT(THD *thd_arg, TABLE *table) + :QUICK_INDEX_SORT_SELECT(thd_arg, 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); + Explain_quick_select *get_explain(MEM_ROOT *alloc); +}; + + +/* + 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(); + 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_ROR_INTERSECT; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + Explain_quick_select *get_explain(MEM_ROOT *alloc); + bool is_keys_used(const MY_BITMAP *fields); + void add_used_key_part_to_set(); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc); + 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_SELECT_WITH_RECORD> quick_selects; + + virtual bool is_valid() + { + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + QUICK_SELECT_WITH_RECORD *quick; + bool valid= true; + while ((quick= it++)) + { + if (!quick->quick->is_valid()) + { + valid= false; + break; + } + } + return valid; + } + + /* + 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_ROR_UNION_SELECT(THD *thd, TABLE *table); + ~QUICK_ROR_UNION_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_ROR_UNION; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + Explain_quick_select *get_explain(MEM_ROOT *alloc); + bool is_keys_used(const MY_BITMAP *fields); + void add_used_key_part_to_set(); +#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 */ + + virtual bool is_valid() + { + List_iterator_fast<QUICK_SELECT_I> it(quick_selects); + QUICK_SELECT_I *quick; + bool valid= true; + while ((quick= it++)) + { + if (!quick->is_valid()) + { + valid= false; + break; + } + } + return valid; + } + + QUEUE queue; /* Priority queue for merge operation */ + MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ + + THD *thd; /* current thread */ + uchar *cur_rowid; /* buffer used in get_next() */ + uchar *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: + 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 * const file; /* The handler used to get data. */ + JOIN *join; /* Descriptor of the current query */ + KEY *index_info; /* The index chosen for data access */ + uchar *record; /* Buffer where the next record is returned. */ + uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */ + uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */ + const uint group_prefix_len; /* Length of the group prefix. */ + uint group_key_parts; /* A number of keyparts in the group prefix */ + uchar *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 have_agg_distinct;/* aggregate_function(DISTINCT ...). */ + bool seen_first_key; /* Denotes whether the first key was retrieved.*/ + bool doing_key_read; /* true if we enabled key only reads */ + + 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 */ + uchar *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. */ + uint real_key_parts; /* A number of keyparts in the above value. */ + List<Item_sum> *min_functions; + List<Item_sum> *max_functions; + List_iterator<Item_sum> *min_functions_it; + List_iterator<Item_sum> *max_functions_it; + /* + Use index scan to get the next different key instead of jumping into it + through index read + */ + bool is_index_scan; +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(); + int cmp_min_max_key(const uchar *key, uint16 length); +public: + QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min, + bool have_max, bool have_agg_distinct, + KEY_PART_INFO *min_max_arg_part, + uint group_prefix_len, uint group_key_parts, + uint used_key_parts, KEY *index_info, uint + use_index, double read_cost, ha_rows records, uint + key_infix_len, uchar *key_infix, MEM_ROOT + *parent_alloc, bool is_index_scan); + ~QUICK_GROUP_MIN_MAX_SELECT(); + bool add_range(SEL_ARG *sel_range); + void update_key_stat(); + void adjust_prefix_ranges(); + bool alloc_buffers(); + int init(); + void need_sorted_output() { /* always do it */ } + 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); + void add_used_key_part_to_set(); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + bool is_agg_distinct() { return have_agg_distinct; } + bool loose_scan_is_scanning() { return is_index_scan; } + Explain_quick_select *get_explain(MEM_ROOT *alloc); +}; + + +class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT +{ +public: + QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts); + virtual QUICK_RANGE_SELECT *clone(bool *create_error) + { DBUG_ASSERT(0); return new QUICK_SELECT_DESC(this, used_key_parts); } + int get_next(); + bool reverse_sorted() { return 1; } + int get_type() { return QS_TYPE_RANGE_DESC; } + QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) + { + return this; // is already reverse sorted + } +private: + bool range_reads_after_key(QUICK_RANGE *range); + int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); } + List<QUICK_RANGE> rev_ranges; + List_iterator<QUICK_RANGE> rev_it; + uint used_key_parts; +}; + + +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 + double read_time; // Time to read rows + key_map quick_keys; // Possible quick keys + key_map needed_reg; // Possible quick keys after prev tables. + table_map const_tables,read_tables; + /* See PARAM::possible_keys */ + key_map possible_keys; + bool free_cond; /* Currently not used and always FALSE */ + + SQL_SELECT(); + ~SQL_SELECT(); + void cleanup(); + void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; } + bool check_quick(THD *thd, bool force_quick_range, ha_rows limit) + { + key_map tmp; + tmp.set_all(); + return test_quick_select(thd, tmp, 0, limit, force_quick_range, + FALSE, FALSE, FALSE) < 0; + } + /* + RETURN + 0 if record must be skipped <-> (cond && cond->val_int() == 0) + -1 if error + 1 otherwise + */ + inline int skip_record(THD *thd) + { + int rc= MY_TEST(!cond || cond->val_int()); + if (thd->is_error()) + rc= -1; + return rc; + } + int test_quick_select(THD *thd, key_map keys, table_map prev_tables, + ha_rows limit, bool force_quick_range, + bool ordered_output, bool remove_false_parts_of_where, + bool only_single_index_range_scan); +}; + + +class SQL_SELECT_auto +{ + SQL_SELECT *select; +public: + SQL_SELECT_auto(): select(NULL) + {} + ~SQL_SELECT_auto() + { + delete select; + } + SQL_SELECT_auto& + operator= (SQL_SELECT *_select) + { + select= _select; + return *this; + } + operator SQL_SELECT * () const + { + return select; + } + SQL_SELECT * + operator-> () const + { + return select; + } + operator bool () const + { + return select; + } +}; + + +class FT_SELECT: public QUICK_RANGE_SELECT +{ +public: + FT_SELECT(THD *thd, TABLE *table, uint key, bool *create_err) : + QUICK_RANGE_SELECT (thd, table, key, 1, NULL, create_err) + { (void) init(); } + ~FT_SELECT() { file->ft_end(); } + virtual QUICK_RANGE_SELECT *clone(bool *create_error) + { DBUG_ASSERT(0); return new FT_SELECT(thd, head, index, create_error); } + int init() { return file->ft_init(); } + int reset() { return 0; } + int get_next() { return file->ha_ft_read(record); } + int get_type() { return QS_TYPE_FULLTEXT; } +}; + +FT_SELECT *get_ft_select(THD *thd, TABLE *table, uint key); +QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, + struct st_table_ref *ref, + ha_rows records); +SQL_SELECT *make_select(TABLE *head, table_map const_tables, + table_map read_tables, COND *conds, + SORT_INFO* filesort, + bool allow_null_cond, int *error); + +bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond); + +bool eq_ranges_exceeds_limit(RANGE_SEQ_IF *seq, void *seq_init_param, + uint limit); + +#ifdef WITH_PARTITION_STORAGE_ENGINE +bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond); +#endif +void store_key_image_to_rec(Field *field, uchar *ptr, uint len); + +extern String null_string; + +/* check this number of rows (default value) */ +#define SELECTIVITY_SAMPLING_LIMIT 100 +/* but no more then this part of table (10%) */ +#define SELECTIVITY_SAMPLING_SHARE 0.10 +/* do not check if we are going check less then this number of records */ +#define SELECTIVITY_SAMPLING_THRESHOLD 10 + +#endif |