dbs/mysql-server
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
mysql-server/sql/range_optimizer/tree.h
Ho Sy Tan 4a107fd10e 2025-03-05 14:31:08
2025-03-05 14:31:37 +07:00

1096 lines
39 KiB
C++
Raw Permalink Blame History

/* 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 <assert.h>
#include <string.h>
#include <sys/types.h>
#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}; ///< 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<SEL_ROOT *> 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<SEL_IMERGE> 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_
Reference in a new issue View git blame Copy permalink