/* Copyright (c) 2000, 2024, 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, version 2.0, as published by the Free Software Foundation. This program is designed to work with certain software (including but not limited to OpenSSL) that is licensed under separate terms, as designated in a particular file or component or in included license documentation. The authors of MySQL hereby grant you an additional permission to link the program and your derivative works with the separately licensed software that they have either included with the program or referenced in the documentation. 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, version 2.0, 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-1301 USA */ #ifndef SQL_RANGE_OPTIMIZER_TREE_H_ #define SQL_RANGE_OPTIMIZER_TREE_H_ #include #include #include #include "my_alloc.h" #include "my_base.h" #include "my_inttypes.h" #include "sql/field.h" #include "sql/mem_root_array.h" #include "sql/range_optimizer/internal.h" #include "sql/range_optimizer/range_opt_param.h" #include "sql/sql_bitmap.h" #include "sql/sql_const.h" #include "sql/sql_list.h" class Cost_estimate; class SEL_ARG; class SEL_ROOT; class SEL_TREE; struct KEY_PART; struct ROR_SCAN_INFO; // Note: tree1 and tree2 are not usable by themselves after tree_and() or // tree_or(). SEL_TREE *tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2); SEL_TREE *tree_or(RANGE_OPT_PARAM *param, bool remove_jump_scans, SEL_TREE *tree1, SEL_TREE *tree2); SEL_ROOT *key_or(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2); SEL_ROOT *key_and(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2); bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM *param); /** A graph of (possible multiple) key ranges, represented as a red-black binary tree. There are three types (see the Type enum); if KEY_RANGE, we have zero or more SEL_ARGs, described in the documentation on SEL_ARG. As a special case, a nullptr SEL_ROOT means a range that is always true. This is true both for keys[] and next_key_part. */ class SEL_ROOT { public: /** Used to indicate if the range predicate for an index is always true/false, depends on values from other tables or can be evaluated as is. */ enum class Type { /** The range predicate for this index is always false. */ IMPOSSIBLE, /** There is a range predicate that refers to another table. The range access method cannot be used on this index unless that other table is earlier in the join sequence. The bit representing the index is set in JOIN_TAB::needed_reg to notify the join optimizer that there is a table dependency. After deciding on join order, the optimizer may chose to rerun the range optimizer for tables with such dependencies. */ MAYBE_KEY, /** There is a range condition that can be used on this index. The range conditions for this index in stored in the SEL_ARG tree. */ KEY_RANGE } type; /** Constructs a tree of type KEY_RANGE, using the given root. (The root is allowed to have children.) */ SEL_ROOT(SEL_ARG *root); /** Used to construct MAYBE_KEY and IMPOSSIBLE SEL_ARGs. */ SEL_ROOT(MEM_ROOT *memroot, Type type_arg); /** Note that almost all SEL_ROOTs are created on the MEM_ROOT, so this destructor will only rarely be called. */ ~SEL_ROOT() { assert(use_count == 0); } /** Returns true iff we have a single node that has no max nor min. Note that by convention, a nullptr SEL_ROOT means the same. */ bool is_always() const; /** 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, bool start_key); /* 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, bool start_key); /** Signal to the tree that the caller will shortly be dropping it on the floor; if others are still using it, this is a no-op, but if the caller was the last one, it is now an orphan, and references from it should not count. */ void free_tree(); /** Insert the given node into the tree, and update the root. @param key The node to insert. */ void insert(SEL_ARG *key); /** Delete the given node from the tree, and update the root. @param key The node to delete. Must exist in the tree. */ void tree_delete(SEL_ARG *key); /** Find best key with min <= given key. Because of the call context, this should never return nullptr to get_range. @param key The key to search for. */ SEL_ARG *find_range(const SEL_ARG *key) const; /** Create a new tree that's a duplicate of this one. @param param The parameters for the new tree. Used to find out which MEM_ROOT to allocate the new nodes on. @return The new tree, or nullptr in case of out of memory. */ SEL_ROOT *clone_tree(RANGE_OPT_PARAM *param) const; /** Check if SEL_ROOT::use_count value is correct. See the definition of use_count for what is "correct". @param root The origin tree of the SEL_ARG graph (an RB-tree that has the least value of root->sel_root->root->part in the entire graph, and thus is the "origin" of the graph) @return true iff an incorrect SEL_ARG::use_count is found. */ bool test_use_count(const SEL_ROOT *root) const; /** Returns true iff this is a single-element, single-field predicate. */ inline bool simple_key() const; /** The root node of the tree. Note that this may change as the result of rotations during insertions or deletions, so pointers should be to the SEL_ROOT, not individual SEL_ARG nodes. This element can never be nullptr, but can be null_element if type == KEY_RANGE and the tree is empty (which then means the same as type == IMPOSSIBLE). If type == IMPOSSIBLE or type == MAYBE_KEY, there's a single root element which only serves to hold next_key_part (we don't really care about root->part in this case); the actual min/max values etc. do not matter and should not be accessed. */ SEL_ARG *root; /** Number of references to this SEL_ARG tree. References may be from SEL_ARG::next_key_part of SEL_ARGs from earlier keyparts or SEL_TREE::keys[i]. The SEL_ARG trees are re-used in a lazy-copy manner based on this reference counting. */ ulong use_count{0}; /** Number of nodes in the RB-tree, not including sentinels. */ uint16 elements{0}; }; int sel_cmp(Field *f, uchar *a, uchar *b, uint8 a_flag, uint8 b_flag); /** A helper function to invert min flags to max flags for DESC key parts. It changes NEAR_MIN, NO_MIN_RANGE to NEAR_MAX, NO_MAX_RANGE appropriately */ inline uint invert_min_flag(uint min_flag) { uint max_flag_out = min_flag & ~(NEAR_MIN | NO_MIN_RANGE); if (min_flag & NEAR_MIN) max_flag_out |= NEAR_MAX; if (min_flag & NO_MIN_RANGE) max_flag_out |= NO_MAX_RANGE; return max_flag_out; } /** A helper function to invert max flags to min flags for DESC key parts. It changes NEAR_MAX, NO_MAX_RANGE to NEAR_MIN, NO_MIN_RANGE appropriately */ inline uint invert_max_flag(uint max_flag) { uint min_flag_out = max_flag & ~(NEAR_MAX | NO_MAX_RANGE); if (max_flag & NEAR_MAX) min_flag_out |= NEAR_MIN; if (max_flag & NO_MAX_RANGE) min_flag_out |= NO_MIN_RANGE; return min_flag_out; } /* A construction block of the SEL_ARG-graph. 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, represented by the SEL_ROOT. The meaning of the graph is better demonstrated 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 with NULL as sentinel. 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. Additionally, all intervals in the list form a red-black (RB) tree, linked via left/right/parent pointers with null_element as sentinel. The red-black tree root SEL_ARG object will be further called "root of the interval list". A red-black tree with 7 SEL_ARGs will look similar to what is shown below. Left/right/parent pointers are shown while next pointers go from a node with number X to the node with number X+1 (and prev in the opposite direction): Root +---+ | 4 | +---+ left/ \ right __/ \__ / \ +---+ +---+ | 2 | | 6 | +---+ +---+ left / \ right left / \ right | | | | +---+ +---+ +---+ +---+ | 1 | | 3 | | 5 | | 7 | +---+ +---+ +---+ +---+ In this tree, * node1->prev == node7->next == NULL * node1->left == node1->right == node3->left == ... node7->right == null_element 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)) In red-black tree form: +-------+ +--------+ | kp1=2 |.................| kp3=14 | +-------+ +--------+ / \ / +---------+ +-------+ +--------+ | kp1 < 1 | | kp1=3 | | kp3=11 | +---------+ +-------+ +--------+ . . ...... ....... . . +-------+ +--------+ | kp2=5 | | kp3=14 | +-------+ +--------+ . / . +--------+ (root of R-B tree | kp3=11 | for "kp3={10|12}") +--------+ Where / and \ denote left and right pointers and ... denotes next_key_part pointers to the root of the R-B tree of intervals for consecutive key parts. 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_ranges_from_tree() - Walk the SEL_ARG, materialize the key 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: uint8 min_flag{0}, max_flag{0}; /** maybe_flag signals that this range is AND-ed with some unknown range (a MAYBE_KEY node). This means that the range could be smaller than what it would otherwise denote; e.g., a range such as (0 < x < 3) AND x=( SELECT ... ) could in reality be e.g. (1 < x < 2), depending on what the subselect returns (and we don't know that when planning), but it could never be bigger. FIXME: It's unclear if this is really kept separately per SEL_ARG or is meaningful only at the root node, and thus should be moved to the SEL_ROOT. Most code seems to assume the latter, but a few select places, non-root nodes appear to be modified. */ bool maybe_flag{false}; /* Which key part. TODO: This is the same for all values in a SEL_ROOT, so we should move it there. */ uint8 part{0}; bool maybe_null() const { return field->is_nullable(); } /** The rtree index interval to scan, undefined unless SEL_ARG::min_flag == GEOM_FLAG. */ enum ha_rkey_function rkey_func_flag; /* TODO: This is the same for all values in a SEL_ROOT, so we should move it there; however, be careful about cmp_* functions. Note that this should never be nullptr except in the special case where we have a dummy SEL_ARG to hold next_key_part only (see SEL_ROOT::root for more information). */ Field *field{nullptr}; uchar *min_value, *max_value; // Pointer to range /* eq_tree(), first(), last() etc require that left == right == NULL if the type is MAYBE_KEY. Todo: fix this so SEL_ARGs without R-B children are handled consistently. See related WL#5894. */ SEL_ARG *left, *right; /* R-B tree children */ SEL_ARG *next, *prev; /* Links for bi-directional interval list */ SEL_ARG *parent{nullptr}; /* R-B tree parent (nullptr for root) */ /* R-B tree of intervals covering keyparts consecutive to this SEL_ARG. See documentation of SEL_ARG GRAPH semantics for details. */ SEL_ROOT *next_key_part{nullptr}; /** Convenience function for removing the next_key_part. The typical use for this function is to disconnect the next_key_part from the root, send it to key_and() or key_or(), and then connect the result of that function back to the SEL_ARG using set_next_key_part(). @return The previous value of next_key_part. */ SEL_ROOT *release_next_key_part() { SEL_ROOT *ret = next_key_part; if (next_key_part) { assert(next_key_part->use_count > 0); --next_key_part->use_count; } next_key_part = nullptr; return ret; } /** Convenience function for changing next_key_part, including updating the use_count. The argument is allowed to be nullptr. @param next_key_part_arg New value for next_key_part. */ void set_next_key_part(SEL_ROOT *next_key_part_arg) { release_next_key_part(); next_key_part = next_key_part_arg; if (next_key_part) ++next_key_part->use_count; } enum leaf_color { BLACK, RED } color; bool is_ascending; ///< true - ASC order, false - DESC SEL_ARG() = default; SEL_ARG(SEL_ARG &); SEL_ARG(Field *, const uchar *, const uchar *, bool asc); SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, uint8 min_flag, uint8 max_flag, bool maybe_flag, bool asc, ha_rkey_function gis_flag); /** Note that almost all SEL_ARGs are created on the MEM_ROOT, so this destructor will only rarely be called. */ ~SEL_ARG() { release_next_key_part(); } /** 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 (part != arg->part) return false; return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0; } inline void merge_flags(SEL_ARG *arg) { maybe_flag |= arg->maybe_flag; } inline void maybe_smaller() { maybe_flag = true; } /* 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(SEL_ARG *arg, MEM_ROOT *mem_root) { // Get intersection of ranges. 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 (mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, flag_max, maybe_flag && arg->maybe_flag, is_ascending, min_flag & GEOM_FLAG ? rkey_func_flag : HA_READ_INVALID); } SEL_ARG *clone_first(SEL_ARG *arg, MEM_ROOT *mem_root) { // arg->min <= X < arg->min return new (mem_root) SEL_ARG( field, part, min_value, arg->min_value, min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag || arg->maybe_flag, is_ascending, min_flag & GEOM_FLAG ? rkey_func_flag : HA_READ_INVALID); } SEL_ARG *clone_last(SEL_ARG *arg, MEM_ROOT *mem_root) { // arg->min <= X <= key_max return new (mem_root) SEL_ARG(field, part, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag || arg->maybe_flag, is_ascending, min_flag & GEOM_FLAG ? rkey_func_flag : HA_READ_INVALID); } SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); bool copy_min(SEL_ARG *arg) { // max(this->min, arg->min) <= x <= this->max if (cmp_min_to_min(arg) > 0) { min_value = arg->min_value; min_flag = arg->min_flag; if ((max_flag & NO_MAX_RANGE) && (min_flag & NO_MIN_RANGE)) return true; // Full range } maybe_flag |= arg->maybe_flag; return false; } bool copy_max(SEL_ARG *arg) { // this->min <= x <= min(this->max, arg->max) if (cmp_max_to_max(arg) <= 0) { max_value = arg->max_value; max_flag = arg->max_flag; if ((max_flag & NO_MAX_RANGE) && (min_flag & NO_MIN_RANGE)) return true; // Full range } maybe_flag |= arg->maybe_flag; return false; } 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; } /** Set spatial index range scan parameters. This object will be used to do spatial index range scan after this call. @param rkey_func The scan function to perform. It must be one of the spatial index specific scan functions. */ void set_gis_index_read_function(const enum ha_rkey_function rkey_func) { assert(rkey_func >= HA_READ_MBR_CONTAIN && rkey_func <= HA_READ_MBR_EQUAL); min_flag = GEOM_FLAG; rkey_func_flag = rkey_func; max_flag = NO_MAX_RANGE; } /* returns a number of keypart values (0 or 1) appended to the key buffer */ int store_min_value(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; memset(*min_key + 1, 0, 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_value(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; memset(*max_key + 1, 0, 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. Note: Caller of this function should take care of sending the correct flags and correct key to be stored into. In case of ascending indexes, store_min_key() gets called to store the min_value to range start_key. In case of descending indexes, it's called for storing min_value to range end_key. */ /** Helper function for storing min/max values of SEL_ARG taking into account key part's order. */ void store_min_max_values(uint length, uchar **min_key, uint min_flag, uchar **max_key, uint max_flag, int *min_part, int *max_part) { if (is_ascending) { *min_part += store_min_value(length, min_key, min_flag); *max_part += store_max_value(length, max_key, max_flag); } else { *max_part += store_min_value(length, max_key, min_flag); *min_part += store_max_value(length, min_key, max_flag); } } /** Helper function for storing min/max keys of next SEL_ARG taking into account key part's order. @note On checking min/max flags: Flags are used to track whether there's a partial key in the key buffer. So for ASC key parts the flag corresponding to the key being added to should be checked, not corresponding to the value being added. I.e min_flag for min_key. For DESC key parts it's opposite - max_flag for min_key. It's flag of prev key part that should be checked. */ void store_next_min_max_keys(KEY_PART *key, uchar **cur_min_key, uint *cur_min_flag, uchar **cur_max_key, uint *cur_max_flag, int *min_part, int *max_part) { assert(next_key_part); const bool asc = next_key_part->root->is_ascending; if (!get_min_flag()) { if (asc) *min_part += next_key_part->store_min_key(key, cur_min_key, cur_min_flag, MAX_KEY, true); else { uint tmp_flag = invert_min_flag(*cur_min_flag); *min_part += next_key_part->store_max_key(key, cur_min_key, &tmp_flag, MAX_KEY, true); *cur_min_flag = invert_max_flag(tmp_flag); } } if (!get_max_flag()) { if (asc) *max_part += next_key_part->store_max_key(key, cur_max_key, cur_max_flag, MAX_KEY, false); else { uint tmp_flag = invert_max_flag(*cur_max_flag); *max_part += next_key_part->store_min_key(key, cur_max_key, &tmp_flag, MAX_KEY, false); *cur_max_flag = invert_min_flag(tmp_flag); } } } SEL_ARG *rb_insert(SEL_ARG *leaf); friend SEL_ARG *rb_delete_fixup(SEL_ARG *root, SEL_ARG *key, SEL_ARG *par); #ifndef NDEBUG friend int test_rb_tree(SEL_ARG *element, SEL_ARG *parent); #endif SEL_ARG *first(); const SEL_ARG *first() const; SEL_ARG *last(); void make_root() { left = right = opt_range::null_element; color = BLACK; parent = next = prev = nullptr; } 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); } /** Return correct min_flag. For DESC key parts max flag should be used as min flag, but in order to be checked correctly, max flag should be flipped as code doesn't expect e.g NEAR_MAX in min flag. */ uint get_min_flag() { return (is_ascending ? min_flag : invert_max_flag(max_flag)); } /** Return correct max_flag. For DESC key parts min flag should be used as max flag, but in order to be checked correctly, min flag should be flipped as code doesn't expect e.g NEAR_MIN in max flag. */ uint get_max_flag() { return (is_ascending ? max_flag : invert_min_flag(min_flag)); } }; inline bool SEL_ROOT::is_always() const { return type == Type::KEY_RANGE && elements == 1 && !root->maybe_flag && (root->min_flag & NO_MIN_RANGE) && (root->max_flag & NO_MAX_RANGE); } inline bool SEL_ROOT::simple_key() const { return elements == 1 && !root->next_key_part; } class SEL_TREE { public: /** Starting an effort to document this field: IMPOSSIBLE: if keys[i]->type == SEL_ROOT::Type::IMPOSSIBLE for some i, then type == SEL_TREE::IMPOSSIBLE. Rationale: if the predicate for one of the indexes is always false, then the full predicate is also always false. ALWAYS: if either (keys[i]->is_always()) or (keys[i] == NULL) for all i, then type == SEL_TREE::ALWAYS. Rationale: the range access method will not be able to filter out any rows when there are no range predicates that can be used to filter on any index. KEY: There are range predicates that can be used on at least one index. */ enum Type { IMPOSSIBLE, ALWAYS, KEY } type; /** Whether this SEL_TREE is an inexact (too broad) representation of the predicates it is based on; that is, if it does not necessarily subsume all of them. Note that a nullptr return from get_mm_tree() (which means “could not generate a tree from this predicate”) is by definition inexact. There are two main ways a SEL_TREE can become inexact: - The predicate references fields not contained in any indexes tracked by the SEL_TREE. - The predicate could be of a form that is not representable as a range. E.g., x > 30 is a range, x mod 2 = 1 is not (although it could in theory be converted to a large amount of disjunct ranges). If a SEL_TREE is inexact, the predicates must be rechecked after the range scan, using a filter. (Note that it is never too narrow, only ever exact or too broad.) The old join optimizer always does this, no matter what the inexact flag is set to. Note that additional checks are needed to subsume a predicate even if inexact == false. In particular, SEL_TREE contains information for all indexes over a table, but if a regular range scan is chosen, it can use only one index. So one must then go through all predicates to see if they refer to fields not contained in the given index. Furthermore, range scans on composite (multi-part) indexes can drop predicates on the later keyparts (making predicates on those keyparts inexact), since range scans only support inequalities on the last keypart in any given range. This check must be done in get_ranges_from_tree(). */ bool inexact = false; SEL_TREE(enum Type type_arg, MEM_ROOT *root, size_t num_keys) : type(type_arg), keys(root, num_keys), n_ror_scans(0) {} SEL_TREE(MEM_ROOT *root, size_t num_keys) : type(KEY), keys(root, num_keys), n_ror_scans(0) {} /** Constructor that performs deep-copy of the SEL_ARG trees in 'keys[]' and the index merge alternatives in 'merges'. @param arg The SEL_TREE to copy @param param Parameters for range analysis */ SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param); /* Possible ways to read rows using a single index because the conditions of the query consists of single-index conjunctions: (ranges_for_idx_1) AND (ranges_for_idx_2) AND ... The SEL_ARG graph for each non-NULL element in keys[] may consist of many single-index ranges (disjunctions), so ranges_for_idx_1 may e.g. be: "idx_field1 = 1 OR (idx_field1 > 5 AND idx_field2 = 10)" assuming that index1 is a composite index covering (idx_field1,...,idx_field2,..) Index merge intersection intersects ranges on SEL_ARGs from two or more indexes. Note: there may exist SEL_TREE objects with sel_tree->type=KEY and keys[i]=0 for all i. (SergeyP: it is not clear whether there is any merit in range analyzer functions (e.g. get_mm_parts) returning a pointer to such SEL_TREE instead of NULL) Note: If you want to set an element in keys[], use set_key() or release_key() to make sure the SEL_ARG's use_count is correctly updated. */ Mem_root_array keys; Key_map keys_map; /* bitmask of non-NULL elements in keys */ /* Possible ways to read rows using Index merge (sort) union. Each element in 'merges' consists of multi-index disjunctions, which means that Index merge (sort) union must be applied to read rows. The nodes in the 'merges' list forms a conjunction of such multi-index disjunctions. The list is non-empty only if type==KEY. */ List merges; /* The members below are filled/used only after get_mm_tree is done */ Key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */ uint n_ror_scans; /* number of set bits in ror_scans_map */ /** Convenience function for removing an element in keys[]. The typical use for this function is to disconnect the next_key_part from the root, send it to key_and() or key_or(), and then connect the result of that function back to the SEL_ROOT using set_key(). @param index Which index slot to release. @return The value in the slot (before removal). */ SEL_ROOT *release_key(int index) { SEL_ROOT *ret = keys[index]; if (keys[index]) { assert(keys[index]->use_count > 0); --keys[index]->use_count; } keys[index] = nullptr; return ret; } /** Convenience function for changing an element in keys[], including updating the use_count. @param index Which index slot to change. @param key The new contents of the index slot. Is allowed to be nullptr. */ void set_key(int index, SEL_ROOT *key) { release_key(index); keys[index] = key; if (key) ++key->use_count; } }; #ifndef NDEBUG void print_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree, Key_map *tree_map, const char *msg); #endif /* Get the SEL_ARG tree 'tree' for the keypart covering 'field', if any. 'tree' must be a unique conjunction to ALL predicates in earlier keyparts of 'keypart_tree'. E.g., if 'keypart_tree' is for a composite index (kp1,kp2) and kp2 covers 'field', all these conditions satisfies the requirement: 1. "(kp1=2 OR kp1=3) AND kp2=10" => returns "kp2=10" 2. "(kp1=2 AND kp2=10) OR (kp1=3 AND kp2=10)" => returns "kp2=10" 3. "(kp1=2 AND (kp2=10 OR kp2=11)) OR (kp1=3 AND (kp2=10 OR kp2=11))" => returns "kp2=10 OR kp2=11" whereas these do not 1. "(kp1=2 AND kp2=10) OR kp1=3" 2. "(kp1=2 AND kp2=10) OR (kp1=3 AND kp2=11)" 3. "(kp1=2 AND kp2=10) OR (kp1=3 AND (kp2=10 OR kp2=11))" This function effectively tests requirement WA2. @param[in] key_part_num Key part number we want the SEL_ARG tree for @param[in] keypart_tree The SEL_ARG* tree for the index @param[out] cur_range The SEL_ARG tree, if any, for the keypart @retval true 'keypart_tree' contained a predicate for key part that is not conjunction to all predicates on earlier keyparts @retval false otherwise */ bool get_sel_root_for_keypart(uint key_part_num, SEL_ROOT *keypart_tree, SEL_ROOT **cur_range); /* Find the SEL_ROOT tree that corresponds to the chosen index. SYNOPSIS get_index_range_tree() index [in] The ID of the index being looked for range_tree[in] Tree of ranges being searched param [in] RANGE_OPT_PARAM from test_quick_select DESCRIPTION A SEL_TREE contains range trees for all usable indexes. This procedure finds the SEL_ROOT tree for 'index'. The members of a SEL_TREE are ordered in the same way as the members of RANGE_OPT_PARAM::key, thus we first find the corresponding index in the array RANGE_OPT_PARAM::key. This index is returned through the variable param_idx, to be used later as argument of check_quick_select(). RETURN Pointer to the SEL_ROOT tree that corresponds to index. */ inline SEL_ROOT *get_index_range_tree(uint index, SEL_TREE *range_tree, RANGE_OPT_PARAM *param) { uint idx = 0; /* Index nr in param->key_parts */ while (idx < param->keys) { if (index == param->real_keynr[idx]) break; idx++; } return (range_tree->keys[idx]); } /** Print the ranges in a SEL_TREE to debug log. @param tree_name Descriptive name of the tree @param tree The SEL_TREE that will be printed to debug log @param param RANGE_OPT_PARAM from test_quick_select */ inline void dbug_print_tree([[maybe_unused]] const char *tree_name, [[maybe_unused]] SEL_TREE *tree, [[maybe_unused]] const RANGE_OPT_PARAM *param) { #ifndef NDEBUG if (_db_enabled_()) print_tree(nullptr, tree_name, tree, param, true); #endif } #endif // SQL_RANGE_OPTIMIZER_TREE_H_