diff options
| -rw-r--r-- | mysql-test/r/gis-rtree.result | 24 | ||||
| -rw-r--r-- | mysql-test/t/gis-rtree.test | 14 | ||||
| -rw-r--r-- | sql/item_geofunc.cc | 73 | ||||
| -rw-r--r-- | sql/item_geofunc.h | 3 | ||||
| -rw-r--r-- | sql/opt_range.cc | 668 | ||||
| -rw-r--r-- | sql/opt_range.h | 611 |
6 files changed, 729 insertions, 664 deletions
diff --git a/mysql-test/r/gis-rtree.result b/mysql-test/r/gis-rtree.result index 345914c9e51..0506a0b2a0a 100644 --- a/mysql-test/r/gis-rtree.result +++ b/mysql-test/r/gis-rtree.result @@ -1618,5 +1618,29 @@ id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 range a a 34 NULL 1 Using where DROP TABLE t1; # +# MDEV-8610 "WHERE CONTAINS(indexed_geometry_column,1)" causes full table scan +# +CREATE TABLE t1 (a GEOMETRY NOT NULL, SPATIAL KEY(a)) ENGINE=MyISAM; +INSERT INTO t1 VALUES (Point(1,1)),(Point(2,2)),(Point(3,3)); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1.0); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1e0); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,TIME'00:00:00'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,DATE'2001-01-01'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,TIMESTAMP'2001-01-01 00:00:00'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +DROP TABLE t1; +# # End of 10.1 tests # diff --git a/mysql-test/t/gis-rtree.test b/mysql-test/t/gis-rtree.test index 9c8dce50127..acd91a91c27 100644 --- a/mysql-test/t/gis-rtree.test +++ b/mysql-test/t/gis-rtree.test @@ -994,5 +994,19 @@ EXPLAIN SELECT * FROM t1 WHERE ST_INTERSECTS(Point(1,2),a); DROP TABLE t1; --echo # +--echo # MDEV-8610 "WHERE CONTAINS(indexed_geometry_column,1)" causes full table scan +--echo # +CREATE TABLE t1 (a GEOMETRY NOT NULL, SPATIAL KEY(a)) ENGINE=MyISAM; +INSERT INTO t1 VALUES (Point(1,1)),(Point(2,2)),(Point(3,3)); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1.0); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,1e0); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,TIME'00:00:00'); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,DATE'2001-01-01'); +EXPLAIN SELECT * FROM t1 WHERE CONTAINS(a,TIMESTAMP'2001-01-01 00:00:00'); +DROP TABLE t1; + + +--echo # --echo # End of 10.1 tests --echo # diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc index 55e69c68adb..a048462c7aa 100644 --- a/sql/item_geofunc.cc +++ b/sql/item_geofunc.cc @@ -38,6 +38,7 @@ #include "set_var.h" #ifdef HAVE_SPATIAL #include <m_ctype.h> +#include "opt_range.h" Field *Item_geometry_func::tmp_table_field(TABLE *t_arg) @@ -929,6 +930,78 @@ err: Functions for spatial relations */ +static SEL_ARG sel_arg_impossible(SEL_ARG::IMPOSSIBLE); + +SEL_ARG * +Item_func_spatial_rel::get_mm_leaf(RANGE_OPT_PARAM *param, + Field *field, KEY_PART *key_part, + Item_func::Functype type, Item *value) +{ + DBUG_ENTER("Item_func_spatial_rel::get_mm_leaf"); + if (key_part->image_type != Field::itMBR) + DBUG_RETURN(0); + if (value->cmp_type() != STRING_RESULT) + DBUG_RETURN(&sel_arg_impossible); + + if (param->using_real_indexes && + !field->optimize_range(param->real_keynr[key_part->key], + key_part->part)) + DBUG_RETURN(0); + + if (value->save_in_field_no_warnings(field, 1)) + DBUG_RETURN(&sel_arg_impossible); // Bad GEOMETRY value + + DBUG_ASSERT(!field->real_maybe_null()); // SPATIAL keys do not support NULL + + uchar *str= (uchar*) alloc_root(param->mem_root, key_part->store_length + 1); + if (!str) + DBUG_RETURN(0); // out of memory + field->get_key_image(str, key_part->length, key_part->image_type); + SEL_ARG *tree; + if (!(tree= new (param->mem_root) SEL_ARG(field, str, str))) + DBUG_RETURN(0); // out of memory + + switch (type) { + case SP_EQUALS_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_EQUAL;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_DISJOINT_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_DISJOINT;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_INTERSECTS_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_TOUCHES_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_CROSSES_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_WITHIN_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_WITHIN;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_CONTAINS_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_CONTAIN;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + case SP_OVERLAPS_FUNC: + tree->min_flag= GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; + tree->max_flag= NO_MAX_RANGE; + break; + default: + DBUG_ASSERT(0); + break; + } + DBUG_RETURN(tree); +} + + const char *Item_func_spatial_mbr_rel::func_name() const { switch (spatial_rel) { diff --git a/sql/item_geofunc.h b/sql/item_geofunc.h index 4ae3be73da1..e88fd266af7 100644 --- a/sql/item_geofunc.h +++ b/sql/item_geofunc.h @@ -277,6 +277,9 @@ class Item_func_spatial_rel: public Item_bool_func2 protected: enum Functype spatial_rel; String tmp_value1, tmp_value2; + SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param, Field *field, + KEY_PART *key_part, + Item_func::Functype type, Item *value); public: Item_func_spatial_rel(Item *a, Item *b, enum Functype sp_rel) :Item_bool_func2(a, b), spatial_rel(sp_rel) diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 3ff73bccaba..d0b66c6189b 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -132,8 +132,6 @@ */ #define double2rows(x) ((ha_rows)(x)) -static int sel_cmp(Field *f,uchar *a,uchar *b,uint8 a_flag,uint8 b_flag); - /* this should be long enough so that any memcmp with a string that starts from '\0' won't cross is_null_string boundaries, even @@ -141,543 +139,6 @@ static int sel_cmp(Field *f,uchar *a,uchar *b,uint8 a_flag,uint8 b_flag); */ static uchar is_null_string[20]= {1,0}; -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. -*/ - -class SEL_ARG :public Sql_alloc -{ -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) - */ - uint16 max_part_no; - /* - Number of children of this element in the RB-tree, plus 1 for this - element itself. - */ - uint16 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; - - 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) - {} - /** - 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; - } - /** - 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); - *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); - (*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() - { - /* - 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); -}; - /** Helper function to compare two SEL_ARG's. */ @@ -832,73 +293,6 @@ public: bool without_imerges() { return merges.is_empty(); } }; -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[MAX_KEY_LENGTH+MAX_FIELD_WIDTH], - max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; - - /* 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->is_fatal_error || - thd->is_error() || - alloced_sel_args > SEL_ARG::MAX_SEL_ARGS; - } -}; class PARAM : public RANGE_OPT_PARAM { @@ -2571,8 +1965,8 @@ SEL_ARG *SEL_ARG::last() Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2 */ -static int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag, - uint8 b_flag) +int SEL_ARG::sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag, + uint8 b_flag) { int cmp; /* First check if there was a compare to a min or max element */ @@ -8410,6 +7804,9 @@ Item_bool_func::get_mm_leaf(RANGE_OPT_PARAM *param, DBUG_ASSERT(value); // IS NULL and IS NOT NULL are handled separately + if (key_part->image_type != Field::itRAW) + DBUG_RETURN(0); // e.g. SPATIAL index + /* 1. Usually we can't use an index if the column collation differ from the operation collation. @@ -8425,7 +7822,6 @@ Item_bool_func::get_mm_leaf(RANGE_OPT_PARAM *param, if (field->result_type() == STRING_RESULT && field->match_collation_to_optimize_range() && value->result_type() == STRING_RESULT && - key_part->image_type == Field::itRAW && field->charset() != compare_collation() && !((type == EQUAL_FUNC || type == EQ_FUNC) && compare_collation()->state & MY_CS_BINSORT)) @@ -8433,28 +7829,6 @@ Item_bool_func::get_mm_leaf(RANGE_OPT_PARAM *param, if (value->cmp_type() == TIME_RESULT && field->cmp_type() != TIME_RESULT) goto end; - if (key_part->image_type == Field::itMBR) - { - // @todo: use is_spatial_operator() instead? - switch (type) { - case SP_EQUALS_FUNC: - case SP_DISJOINT_FUNC: - case SP_INTERSECTS_FUNC: - case SP_TOUCHES_FUNC: - case SP_CROSSES_FUNC: - case SP_WITHIN_FUNC: - case SP_CONTAINS_FUNC: - case SP_OVERLAPS_FUNC: - break; - default: - /* - We cannot involve spatial indexes for queries that - don't use MBREQUALS(), MBRDISJOINT(), etc. functions. - */ - goto end; - } - } - if (param->using_real_indexes && !field->optimize_range(param->real_keynr[key_part->key], key_part->part) && @@ -8632,38 +8006,6 @@ Item_bool_func::get_mm_leaf(RANGE_OPT_PARAM *param, tree->min_flag= NEAR_MIN; tree->max_flag=NO_MAX_RANGE; break; - case SP_EQUALS_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_EQUAL;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_DISJOINT_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_DISJOINT;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_INTERSECTS_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_TOUCHES_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_CROSSES_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_WITHIN_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_WITHIN;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_CONTAINS_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_CONTAIN;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; - case SP_OVERLAPS_FUNC: - tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; - tree->max_flag=NO_MAX_RANGE; - break; case EQ_FUNC: case EQUAL_FUNC: break; diff --git a/sql/opt_range.h b/sql/opt_range.h index 2f108c1f6b5..d47fe765184 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -52,6 +52,616 @@ struct KEY_PART { 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. +*/ + +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) + */ + uint16 max_part_no; + /* + Number of children of this element in the RB-tree, plus 1 for this + element itself. + */ + uint16 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; + + 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) + {} + /** + 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; + } + /** + 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); + *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); + (*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() + { + /* + 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); +}; + + +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[MAX_KEY_LENGTH+MAX_FIELD_WIDTH], + max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; + + /* 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->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. @@ -401,7 +1011,6 @@ public: struct st_qsel_param; class PARAM; -class SEL_ARG; /* |