summaryrefslogtreecommitdiffstats
path: root/sql/opt_range.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 18:07:14 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 18:07:14 +0000
commita175314c3e5827eb193872241446f2f8f5c9d33c (patch)
treecd3d60ca99ae00829c52a6ca79150a5b6e62528b /sql/opt_range.h
parentInitial commit. (diff)
downloadmariadb-10.5-a175314c3e5827eb193872241446f2f8f5c9d33c.tar.xz
mariadb-10.5-a175314c3e5827eb193872241446f2f8f5c9d33c.zip
Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--sql/opt_range.h1816
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