MySQL 8.1.0
Source Code Documentation
tree.h
Go to the documentation of this file.
1/* Copyright (c) 2000, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef SQL_RANGE_OPTIMIZER_TREE_H_
24#define SQL_RANGE_OPTIMIZER_TREE_H_
25
26#include <assert.h>
27#include <string.h>
28#include <sys/types.h>
29
30#include "my_alloc.h"
31#include "my_base.h"
32#include "my_inttypes.h"
33#include "sql/field.h"
34#include "sql/mem_root_array.h"
37#include "sql/sql_bitmap.h"
38#include "sql/sql_const.h"
39#include "sql/sql_list.h"
40
41class Cost_estimate;
42class SEL_ARG;
43class SEL_ROOT;
44class SEL_TREE;
45struct KEY_PART;
46struct ROR_SCAN_INFO;
47
48// Note: tree1 and tree2 are not usable by themselves after tree_and() or
49// tree_or().
50SEL_TREE *tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2);
51SEL_TREE *tree_or(RANGE_OPT_PARAM *param, bool remove_jump_scans,
52 SEL_TREE *tree1, SEL_TREE *tree2);
55
56bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
57 RANGE_OPT_PARAM *param);
58
59/**
60 A graph of (possible multiple) key ranges, represented as a red-black
61 binary tree. There are three types (see the Type enum); if KEY_RANGE,
62 we have zero or more SEL_ARGs, described in the documentation on SEL_ARG.
63
64 As a special case, a nullptr SEL_ROOT means a range that is always true.
65 This is true both for keys[] and next_key_part.
66*/
67class SEL_ROOT {
68 public:
69 /**
70 Used to indicate if the range predicate for an index is always
71 true/false, depends on values from other tables or can be
72 evaluated as is.
73 */
74 enum class Type {
75 /** The range predicate for this index is always false. */
77 /**
78 There is a range predicate that refers to another table. The
79 range access method cannot be used on this index unless that
80 other table is earlier in the join sequence. The bit
81 representing the index is set in JOIN_TAB::needed_reg to
82 notify the join optimizer that there is a table dependency.
83 After deciding on join order, the optimizer may chose to rerun
84 the range optimizer for tables with such dependencies.
85 */
87 /**
88 There is a range condition that can be used on this index. The
89 range conditions for this index in stored in the SEL_ARG tree.
90 */
93
94 /**
95 Constructs a tree of type KEY_RANGE, using the given root.
96 (The root is allowed to have children.)
97 */
99
100 /**
101 Used to construct MAYBE_KEY and IMPOSSIBLE SEL_ARGs.
102 */
103 SEL_ROOT(MEM_ROOT *memroot, Type type_arg);
104
105 /**
106 Note that almost all SEL_ROOTs are created on the MEM_ROOT,
107 so this destructor will only rarely be called.
108 */
109 ~SEL_ROOT() { assert(use_count == 0); }
110
111 /**
112 Returns true iff we have a single node that has no max nor min.
113 Note that by convention, a nullptr SEL_ROOT means the same.
114 */
115 bool is_always() const;
116
117 /**
118 Returns a number of keypart values appended to the key buffer
119 for min key and max key. This function is used by both Range
120 Analysis and Partition pruning. For partition pruning we have
121 to ensure that we don't store also subpartition fields. Thus
122 we have to stop at the last partition part and not step into
123 the subpartition fields. For Range Analysis we set last_part
124 to MAX_KEY which we should never reach.
125 */
126 int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag,
127 uint last_part, bool start_key);
128
129 /* returns a number of keypart values appended to the key buffer */
130 int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag,
131 uint last_part, bool start_key);
132
133 /**
134 Signal to the tree that the caller will shortly be dropping it
135 on the floor; if others are still using it, this is a no-op,
136 but if the caller was the last one, it is now an orphan, and
137 references from it should not count.
138 */
139 void free_tree();
140
141 /**
142 Insert the given node into the tree, and update the root.
143
144 @param key The node to insert.
145 */
146 void insert(SEL_ARG *key);
147
148 /**
149 Delete the given node from the tree, and update the root.
150
151 @param key The node to delete. Must exist in the tree.
152 */
153 void tree_delete(SEL_ARG *key);
154
155 /**
156 Find best key with min <= given key.
157 Because of the call context, this should never return nullptr to get_range.
158
159 @param key The key to search for.
160 */
161 SEL_ARG *find_range(const SEL_ARG *key) const;
162
163 /**
164 Create a new tree that's a duplicate of this one.
165
166 @param param The parameters for the new tree. Used to find out which
167 MEM_ROOT to allocate the new nodes on.
168
169 @return The new tree, or nullptr in case of out of memory.
170 */
171 SEL_ROOT *clone_tree(RANGE_OPT_PARAM *param) const;
172
173 /**
174 Check if SEL_ROOT::use_count value is correct. See the definition
175 of use_count for what is "correct".
176
177 @param root The origin tree of the SEL_ARG graph (an RB-tree that
178 has the least value of root->sel_root->root->part in the
179 entire graph, and thus is the "origin" of the graph)
180
181 @return true iff an incorrect SEL_ARG::use_count is found.
182 */
183 bool test_use_count(const SEL_ROOT *root) const;
184
185 /** Returns true iff this is a single-element, single-field predicate. */
186 inline bool simple_key() const;
187
188 /**
189 The root node of the tree. Note that this may change as the result
190 of rotations during insertions or deletions, so pointers should be
191 to the SEL_ROOT, not individual SEL_ARG nodes.
192
193 This element can never be nullptr, but can be null_element
194 if type == KEY_RANGE and the tree is empty (which then means the same as
195 type == IMPOSSIBLE).
196
197 If type == IMPOSSIBLE or type == MAYBE_KEY, there's a single root
198 element which only serves to hold next_key_part (we don't really care
199 about root->part in this case); the actual min/max values etc.
200 do not matter and should not be accessed.
201 */
203
204 /**
205 Number of references to this SEL_ARG tree. References may be from
206 SEL_ARG::next_key_part of SEL_ARGs from earlier keyparts or
207 SEL_TREE::keys[i].
208
209 The SEL_ARG trees are re-used in a lazy-copy manner based on this
210 reference counting.
211 */
212 ulong use_count{0};
213
214 /**
215 Number of nodes in the RB-tree, not including sentinels.
216 */
218};
219
220int sel_cmp(Field *f, uchar *a, uchar *b, uint8 a_flag, uint8 b_flag);
221
222/**
223 A helper function to invert min flags to max flags for DESC key parts.
224 It changes NEAR_MIN, NO_MIN_RANGE to NEAR_MAX, NO_MAX_RANGE appropriately
225*/
226
227inline uint invert_min_flag(uint min_flag) {
228 uint max_flag_out = min_flag & ~(NEAR_MIN | NO_MIN_RANGE);
229 if (min_flag & NEAR_MIN) max_flag_out |= NEAR_MAX;
230 if (min_flag & NO_MIN_RANGE) max_flag_out |= NO_MAX_RANGE;
231 return max_flag_out;
232}
233
234/**
235 A helper function to invert max flags to min flags for DESC key parts.
236 It changes NEAR_MAX, NO_MAX_RANGE to NEAR_MIN, NO_MIN_RANGE appropriately
237*/
238
239inline uint invert_max_flag(uint max_flag) {
240 uint min_flag_out = max_flag & ~(NEAR_MAX | NO_MAX_RANGE);
241 if (max_flag & NEAR_MAX) min_flag_out |= NEAR_MIN;
242 if (max_flag & NO_MAX_RANGE) min_flag_out |= NO_MIN_RANGE;
243 return min_flag_out;
244}
245
246/*
247 A construction block of the SEL_ARG-graph.
248
249 One SEL_ARG object represents an "elementary interval" in form
250
251 min_value <=? table.keypartX <=? max_value
252
253 The interval is a non-empty interval of any kind: with[out] minimum/maximum
254 bound, [half]open/closed, single-point interval, etc.
255
256 1. SEL_ARG GRAPH STRUCTURE
257
258 SEL_ARG objects are linked together in a graph, represented by the SEL_ROOT.
259 The meaning of the graph is better demonstrated by an example:
260
261 tree->keys[i]
262 |
263 | $ $
264 | part=1 $ part=2 $ part=3
265 | $ $
266 | +-------+ $ +-------+ $ +--------+
267 | | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
268 | +-------+ $ +-------+ $ +--------+
269 | | $ $ |
270 | | $ $ +--------+
271 | | $ $ | kp3=12 |
272 | | $ $ +--------+
273 | +-------+ $ $
274 \->| kp1=2 |--$--------------$-+
275 +-------+ $ $ | +--------+
276 | $ $ ==>| kp3=11 |
277 +-------+ $ $ | +--------+
278 | kp1=3 |--$--------------$-+ |
279 +-------+ $ $ +--------+
280 | $ $ | kp3=14 |
281 ... $ $ +--------+
282
283 The entire graph is partitioned into "interval lists".
284
285 An interval list is a sequence of ordered disjoint intervals over
286 the same key part. SEL_ARG are linked via "next" and "prev" pointers
287 with NULL as sentinel.
288
289 In the example pic, there are 4 interval lists:
290 "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
291 The vertical lines represent SEL_ARG::next/prev pointers.
292
293 Additionally, all intervals in the list form a red-black (RB) tree,
294 linked via left/right/parent pointers with null_element as sentinel. The
295 red-black tree root SEL_ARG object will be further called "root of the
296 interval list".
297
298 A red-black tree with 7 SEL_ARGs will look similar to what is shown
299 below. Left/right/parent pointers are shown while next pointers go from a
300 node with number X to the node with number X+1 (and prev in the
301 opposite direction):
302
303 Root
304 +---+
305 | 4 |
306 +---+
307 left/ \ right
308 __/ \__
309 / \
310 +---+ +---+
311 | 2 | | 6 |
312 +---+ +---+
313 left / \ right left / \ right
314 | | | |
315 +---+ +---+ +---+ +---+
316 | 1 | | 3 | | 5 | | 7 |
317 +---+ +---+ +---+ +---+
318
319 In this tree,
320 * node1->prev == node7->next == NULL
321 * node1->left == node1->right ==
322 node3->left == ... node7->right == null_element
323
324 In an interval list, each member X may have SEL_ARG::next_key_part pointer
325 pointing to the root of another interval list Y. The pointed interval list
326 must cover a key part with greater number (i.e. Y->part > X->part).
327
328 In the example pic, the next_key_part pointers are represented by
329 horisontal lines.
330
331 2. SEL_ARG GRAPH SEMANTICS
332
333 It represents a condition in a special form (we don't have a name for it ATM)
334 The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
335
336 For example, the picture represents the condition in form:
337 (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
338 (kp1=2 AND (kp3=11 OR kp3=14)) OR
339 (kp1=3 AND (kp3=11 OR kp3=14))
340
341 In red-black tree form:
342
343 +-------+ +--------+
344 | kp1=2 |.................| kp3=14 |
345 +-------+ +--------+
346 / \ /
347 +---------+ +-------+ +--------+
348 | kp1 < 1 | | kp1=3 | | kp3=11 |
349 +---------+ +-------+ +--------+
350 . .
351 ...... .......
352 . .
353 +-------+ +--------+
354 | kp2=5 | | kp3=14 |
355 +-------+ +--------+
356 . /
357 . +--------+
358 (root of R-B tree | kp3=11 |
359 for "kp3={10|12}") +--------+
360
361
362 Where / and \ denote left and right pointers and ... denotes
363 next_key_part pointers to the root of the R-B tree of intervals for
364 consecutive key parts.
365
366 3. SEL_ARG GRAPH USE
367
368 Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
369 Then walk the SEL_ARG graph and get a list of dijsoint ordered key
370 intervals (i.e. intervals in form
371
372 (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
373
374 Those intervals can be used to access the index. The uses are in:
375 - check_quick_select() - Walk the SEL_ARG graph and find an estimate of
376 how many table records are contained within all
377 intervals.
378 - get_ranges_from_tree() - Walk the SEL_ARG, materialize the key intervals.
379
380 4. SPACE COMPLEXITY NOTES
381
382 SEL_ARG graph is a representation of an ordered disjoint sequence of
383 intervals over the ordered set of index tuple values.
384
385 For multi-part keys, one can construct a WHERE expression such that its
386 list of intervals will be of combinatorial size. Here is an example:
387
388 (keypart1 IN (1,2, ..., n1)) AND
389 (keypart2 IN (1,2, ..., n2)) AND
390 (keypart3 IN (1,2, ..., n3))
391
392 For this WHERE clause the list of intervals will have n1*n2*n3 intervals
393 of form
394
395 (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
396
397 SEL_ARG graph structure aims to reduce the amount of required space by
398 "sharing" the elementary intervals when possible (the pic at the
399 beginning of this comment has examples of such sharing). The sharing may
400 prevent combinatorial blowup:
401
402 There are WHERE clauses that have combinatorial-size interval lists but
403 will be represented by a compact SEL_ARG graph.
404 Example:
405 (keypartN IN (1,2, ..., n1)) AND
406 ...
407 (keypart2 IN (1,2, ..., n2)) AND
408 (keypart1 IN (1,2, ..., n3))
409
410 but not in all cases:
411
412 - There are WHERE clauses that do have a compact SEL_ARG-graph
413 representation but get_mm_tree() and its callees will construct a
414 graph of combinatorial size.
415 Example:
416 (keypart1 IN (1,2, ..., n1)) AND
417 (keypart2 IN (1,2, ..., n2)) AND
418 ...
419 (keypartN IN (1,2, ..., n3))
420
421 - There are WHERE clauses for which the minimal possible SEL_ARG graph
422 representation will have combinatorial size.
423 Example:
424 By induction: Let's take any interval on some keypart in the middle:
425
426 kp15=c0
427
428 Then let's AND it with this interval 'structure' from preceding and
429 following keyparts:
430
431 (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
432
433 We will obtain this SEL_ARG graph:
434
435 kp14 $ kp15 $ kp16
436 $ $
437 +---------+ $ +---------+ $ +---------+
438 | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
439 +---------+ $ +---------+ $ +---------+
440 | $ $
441 +---------+ $ +---------+ $
442 | kp14=c2 |--$-->| kp15=c0 | $
443 +---------+ $ +---------+ $
444 $ $
445
446 Note that we had to duplicate "kp15=c0" and there was no way to avoid
447 that.
448 The induction step: AND the obtained expression with another "wrapping"
449 expression like (*).
450 When the process ends because of the limit on max. number of keyparts
451 we'll have:
452
453 WHERE clause length is O(3*#max_keyparts)
454 SEL_ARG graph size is O(2^(#max_keyparts/2))
455
456 (it is also possible to construct a case where instead of 2 in 2^n we
457 have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
458 nodes)
459
460 We avoid consuming too much memory by setting a limit on the number of
461 SEL_ARG object we can construct during one range analysis invocation.
462*/
463
464class SEL_ARG {
465 public:
467
468 /**
469 maybe_flag signals that this range is AND-ed with some unknown range
470 (a MAYBE_KEY node). This means that the range could be smaller than
471 what it would otherwise denote; e.g., a range such as
472
473 (0 < x < 3) AND x=( SELECT ... )
474
475 could in reality be e.g. (1 < x < 2), depending on what the subselect
476 returns (and we don't know that when planning), but it could never be
477 bigger.
478
479 FIXME: It's unclear if this is really kept separately per SEL_ARG or is
480 meaningful only at the root node, and thus should be moved to the
481 SEL_ROOT. Most code seems to assume the latter, but a few select places,
482 non-root nodes appear to be modified.
483 */
484 bool maybe_flag{false};
485
486 /*
487 Which key part. TODO: This is the same for all values in a SEL_ROOT,
488 so we should move it there.
489 */
491
492 bool maybe_null() const { return field->is_nullable(); }
493
494 /**
495 The rtree index interval to scan, undefined unless
496 SEL_ARG::min_flag == GEOM_FLAG.
497 */
499
500 /*
501 TODO: This is the same for all values in a SEL_ROOT, so we should
502 move it there; however, be careful about cmp_* functions.
503 Note that this should never be nullptr except in the special case
504 where we have a dummy SEL_ARG to hold next_key_part only
505 (see SEL_ROOT::root for more information).
506 */
507 Field *field{nullptr};
508 uchar *min_value, *max_value; // Pointer to range
509
510 /*
511 eq_tree(), first(), last() etc require that left == right == NULL
512 if the type is MAYBE_KEY. Todo: fix this so SEL_ARGs without R-B
513 children are handled consistently. See related WL#5894.
514 */
515 SEL_ARG *left, *right; /* R-B tree children */
516 SEL_ARG *next, *prev; /* Links for bi-directional interval list */
517 SEL_ARG *parent{nullptr}; /* R-B tree parent (nullptr for root) */
518 /*
519 R-B tree of intervals covering keyparts consecutive to this
520 SEL_ARG. See documentation of SEL_ARG GRAPH semantics for details.
521 */
523
524 /**
525 Convenience function for removing the next_key_part. The typical
526 use for this function is to disconnect the next_key_part from the
527 root, send it to key_and() or key_or(), and then connect the
528 result of that function back to the SEL_ARG using set_next_key_part().
529
530 @return The previous value of next_key_part.
531 */
533 SEL_ROOT *ret = next_key_part;
534 if (next_key_part) {
535 assert(next_key_part->use_count > 0);
537 }
538 next_key_part = nullptr;
539 return ret;
540 }
541
542 /**
543 Convenience function for changing next_key_part, including
544 updating the use_count. The argument is allowed to be nullptr.
545
546 @param next_key_part_arg New value for next_key_part.
547 */
548 void set_next_key_part(SEL_ROOT *next_key_part_arg) {
550 next_key_part = next_key_part_arg;
552 }
553
555
556 bool is_ascending; ///< true - ASC order, false - DESC
557
558 SEL_ARG() = default;
559 SEL_ARG(SEL_ARG &);
560 SEL_ARG(Field *, const uchar *, const uchar *, bool asc);
562 uint8 min_flag, uint8 max_flag, bool maybe_flag, bool asc,
563 ha_rkey_function gis_flag);
564 /**
565 Note that almost all SEL_ARGs are created on the MEM_ROOT,
566 so this destructor will only rarely be called.
567 */
569
570 /**
571 returns true if a range predicate is equal. Use all_same()
572 to check for equality of all the predicates on this keypart.
573 */
574 inline bool is_same(const SEL_ARG *arg) const {
575 if (part != arg->part) return false;
576 return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
577 }
578
579 inline void merge_flags(SEL_ARG *arg) { maybe_flag |= arg->maybe_flag; }
580 inline void maybe_smaller() { maybe_flag = true; }
581 /* Return true iff it's a single-point null interval */
582 inline bool is_null_interval() { return maybe_null() && max_value[0] == 1; }
583 inline int cmp_min_to_min(const SEL_ARG *arg) const {
584 return sel_cmp(field, min_value, arg->min_value, min_flag, arg->min_flag);
585 }
586 inline int cmp_min_to_max(const SEL_ARG *arg) const {
587 return sel_cmp(field, min_value, arg->max_value, min_flag, arg->max_flag);
588 }
589 inline int cmp_max_to_max(const SEL_ARG *arg) const {
590 return sel_cmp(field, max_value, arg->max_value, max_flag, arg->max_flag);
591 }
592 inline int cmp_max_to_min(const SEL_ARG *arg) const {
593 return sel_cmp(field, max_value, arg->min_value, max_flag, arg->min_flag);
594 }
596 MEM_ROOT *mem_root) { // Get intersection of ranges.
597 uchar *new_min, *new_max;
598 uint8 flag_min, flag_max;
599 if (cmp_min_to_min(arg) >= 0) {
600 new_min = min_value;
601 flag_min = min_flag;
602 } else {
603 new_min = arg->min_value;
604 flag_min = arg->min_flag; /* purecov: deadcode */
605 }
606 if (cmp_max_to_max(arg) <= 0) {
607 new_max = max_value;
608 flag_max = max_flag;
609 } else {
610 new_max = arg->max_value;
611 flag_max = arg->max_flag;
612 }
613 return new (mem_root)
614 SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
617 }
619 MEM_ROOT *mem_root) { // arg->min <= X < arg->min
620 return new (mem_root) SEL_ARG(
622 arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag || arg->maybe_flag,
624 }
626 MEM_ROOT *mem_root) { // arg->min <= X <= key_max
627 return new (mem_root)
631 }
632 SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
633
634 bool copy_min(SEL_ARG *arg) { // max(this->min, arg->min) <= x <= this->max
635 if (cmp_min_to_min(arg) > 0) {
636 min_value = arg->min_value;
637 min_flag = arg->min_flag;
639 return true; // Full range
640 }
641 maybe_flag |= arg->maybe_flag;
642 return false;
643 }
644 bool copy_max(SEL_ARG *arg) { // this->min <= x <= min(this->max, arg->max)
645 if (cmp_max_to_max(arg) <= 0) {
646 max_value = arg->max_value;
647 max_flag = arg->max_flag;
649 return true; // Full range
650 }
651 maybe_flag |= arg->maybe_flag;
652 return false;
653 }
654
656 min_value = arg->min_value;
657 min_flag = arg->min_flag;
658 }
660 max_value = arg->min_value;
661 max_flag = arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
662 }
664 min_value = arg->max_value;
665 min_flag = arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
666 }
667
668 /**
669 Set spatial index range scan parameters. This object will be used to do
670 spatial index range scan after this call.
671
672 @param rkey_func The scan function to perform. It must be one of the
673 spatial index specific scan functions.
674 */
676 assert(rkey_func >= HA_READ_MBR_CONTAIN && rkey_func <= HA_READ_MBR_EQUAL);
678 rkey_func_flag = rkey_func;
680 }
681
682 /* returns a number of keypart values (0 or 1) appended to the key buffer */
683 int store_min_value(uint length, uchar **min_key, uint min_key_flag) {
684 /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
685 if ((min_flag & GEOM_FLAG) ||
686 (!(min_flag & NO_MIN_RANGE) &&
687 !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN)))) {
688 if (maybe_null() && *min_value) {
689 **min_key = 1;
690 memset(*min_key + 1, 0, length - 1);
691 } else
692 memcpy(*min_key, min_value, length);
693 (*min_key) += length;
694 return 1;
695 }
696 return 0;
697 }
698 /* returns a number of keypart values (0 or 1) appended to the key buffer */
699 int store_max_value(uint length, uchar **max_key, uint max_key_flag) {
700 if (!(max_flag & NO_MAX_RANGE) &&
701 !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX))) {
702 if (maybe_null() && *max_value) {
703 **max_key = 1;
704 memset(*max_key + 1, 0, length - 1);
705 } else
706 memcpy(*max_key, max_value, length);
707 (*max_key) += length;
708 return 1;
709 }
710 return 0;
711 }
712
713 /*
714 Returns a number of keypart values appended to the key buffer
715 for min key and max key. This function is used by both Range
716 Analysis and Partition pruning. For partition pruning we have
717 to ensure that we don't store also subpartition fields. Thus
718 we have to stop at the last partition part and not step into
719 the subpartition fields. For Range Analysis we set last_part
720 to MAX_KEY which we should never reach.
721
722 Note: Caller of this function should take care of sending the
723 correct flags and correct key to be stored into. In case of
724 ascending indexes, store_min_key() gets called to store the
725 min_value to range start_key. In case of descending indexes, it's
726 called for storing min_value to range end_key.
727 */
728 /**
729 Helper function for storing min/max values of SEL_ARG taking into account
730 key part's order.
731 */
732 void store_min_max_values(uint length, uchar **min_key, uint min_flag,
733 uchar **max_key, uint max_flag, int *min_part,
734 int *max_part) {
735 if (is_ascending) {
736 *min_part += store_min_value(length, min_key, min_flag);
737 *max_part += store_max_value(length, max_key, max_flag);
738 } else {
739 *max_part += store_min_value(length, max_key, min_flag);
740 *min_part += store_max_value(length, min_key, max_flag);
741 }
742 }
743
744 /**
745 Helper function for storing min/max keys of next SEL_ARG taking into
746 account key part's order.
747
748 @note On checking min/max flags: Flags are used to track whether there's
749 a partial key in the key buffer. So for ASC key parts the flag
750 corresponding to the key being added to should be checked, not
751 corresponding to the value being added. I.e min_flag for min_key.
752 For DESC key parts it's opposite - max_flag for min_key. It's flag
753 of prev key part that should be checked.
754
755 */
757 uint *cur_min_flag, uchar **cur_max_key,
758 uint *cur_max_flag, int *min_part,
759 int *max_part) {
760 assert(next_key_part);
761 const bool asc = next_key_part->root->is_ascending;
762 if (!get_min_flag()) {
763 if (asc)
764 *min_part += next_key_part->store_min_key(key, cur_min_key,
765 cur_min_flag, MAX_KEY, true);
766 else {
767 uint tmp_flag = invert_min_flag(*cur_min_flag);
768 *min_part += next_key_part->store_max_key(key, cur_min_key, &tmp_flag,
769 MAX_KEY, true);
770 *cur_min_flag = invert_max_flag(tmp_flag);
771 }
772 }
773 if (!get_max_flag()) {
774 if (asc)
775 *max_part += next_key_part->store_max_key(key, cur_max_key,
776 cur_max_flag, MAX_KEY, false);
777 else {
778 uint tmp_flag = invert_max_flag(*cur_max_flag);
779 *max_part += next_key_part->store_min_key(key, cur_max_key, &tmp_flag,
780 MAX_KEY, false);
781 *cur_max_flag = invert_min_flag(tmp_flag);
782 }
783 }
784 }
785
786 SEL_ARG *rb_insert(SEL_ARG *leaf);
787 friend SEL_ARG *rb_delete_fixup(SEL_ARG *root, SEL_ARG *key, SEL_ARG *par);
788#ifndef NDEBUG
789 friend int test_rb_tree(SEL_ARG *element, SEL_ARG *parent);
790#endif
791 SEL_ARG *first();
792 const SEL_ARG *first() const;
793 SEL_ARG *last();
794 void make_root() {
796 color = BLACK;
797 parent = next = prev = nullptr;
798 }
799
800 inline SEL_ARG **parent_ptr() {
801 return parent->left == this ? &parent->left : &parent->right;
802 }
803
804 /*
805 Check if this SEL_ARG object represents a single-point interval
806
807 SYNOPSIS
808 is_singlepoint()
809
810 DESCRIPTION
811 Check if this SEL_ARG object (not tree) represents a single-point
812 interval, i.e. if it represents a "keypart = const" or
813 "keypart IS NULL".
814
815 RETURN
816 true This SEL_ARG object represents a singlepoint interval
817 false Otherwise
818 */
819
820 bool is_singlepoint() const {
821 /*
822 Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
823 flags, and the same for right edge.
824 */
825 if (min_flag || max_flag) return false;
826 uchar *min_val = min_value;
827 uchar *max_val = max_value;
828
829 if (maybe_null()) {
830 /* First byte is a NULL value indicator */
831 if (*min_val != *max_val) return false;
832
833 if (*min_val) return true; /* This "x IS NULL" */
834 min_val++;
835 max_val++;
836 }
837 return !field->key_cmp(min_val, max_val);
838 }
839 /**
840 Return correct min_flag.
841
842 For DESC key parts max flag should be used as min flag, but in order to
843 be checked correctly, max flag should be flipped as code doesn't expect
844 e.g NEAR_MAX in min flag.
845 */
848 }
849 /**
850 Return correct max_flag.
851
852 For DESC key parts min flag should be used as max flag, but in order to
853 be checked correctly, min flag should be flipped as code doesn't expect
854 e.g NEAR_MIN in max flag.
855 */
858 }
859};
860
861inline bool SEL_ROOT::is_always() const {
862 return type == Type::KEY_RANGE && elements == 1 && !root->maybe_flag &&
864}
865
866inline bool SEL_ROOT::simple_key() const {
867 return elements == 1 && !root->next_key_part;
868}
869
870class SEL_TREE {
871 public:
872 /**
873 Starting an effort to document this field:
874
875 IMPOSSIBLE: if keys[i]->type == SEL_ROOT::Type::IMPOSSIBLE for some i,
876 then type == SEL_TREE::IMPOSSIBLE. Rationale: if the predicate for
877 one of the indexes is always false, then the full predicate is also
878 always false.
879
880 ALWAYS: if either (keys[i]->is_always()) or (keys[i] == NULL) for all i,
881 then type == SEL_TREE::ALWAYS. Rationale: the range access method
882 will not be able to filter out any rows when there are no range
883 predicates that can be used to filter on any index.
884
885 KEY: There are range predicates that can be used on at least one
886 index.
887 */
889
890 /**
891 Whether this SEL_TREE is an inexact (too broad) representation of the
892 predicates it is based on; that is, if it does not necessarily subsume
893 all of them. Note that a nullptr return from get_mm_tree() (which means
894 “could not generate a tree from this predicate”) is by definition inexact.
895
896 There are two main ways a SEL_TREE can become inexact:
897
898 - The predicate references fields not contained in any indexes tracked
899 by the SEL_TREE.
900 - The predicate could be of a form that is not representable as a range.
901 E.g., x > 30 is a range, x mod 2 = 1 is not (although it could
902 in theory be converted to a large amount of disjunct ranges).
903
904 If a SEL_TREE is inexact, the predicates must be rechecked after the
905 range scan, using a filter. (Note that it is never too narrow, only ever
906 exact or too broad.) The old join optimizer always does this, no matter
907 what the inexact flag is set to.
908
909 Note that additional checks are needed to subsume a predicate even if
910 inexact == false. In particular, SEL_TREE contains information for all
911 indexes over a table, but if a regular range scan is chosen, it can use
912 only one index. So one must then go through all predicates to see if they
913 refer to fields not contained in the given index. Furthermore, range scans
914 on composite (multi-part) indexes can drop predicates on the later keyparts
915 (making predicates on those keyparts inexact), since range scans only
916 support inequalities on the last keypart in any given range. This check
917 must be done in get_ranges_from_tree().
918 */
919 bool inexact = false;
920
921 SEL_TREE(enum Type type_arg, MEM_ROOT *root, size_t num_keys)
922 : type(type_arg), keys(root, num_keys), n_ror_scans(0) {}
923 SEL_TREE(MEM_ROOT *root, size_t num_keys)
924 : type(KEY), keys(root, num_keys), n_ror_scans(0) {}
925 /**
926 Constructor that performs deep-copy of the SEL_ARG trees in
927 'keys[]' and the index merge alternatives in 'merges'.
928
929 @param arg The SEL_TREE to copy
930 @param param Parameters for range analysis
931 */
932 SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param);
933 /*
934 Possible ways to read rows using a single index because the
935 conditions of the query consists of single-index conjunctions:
936
937 (ranges_for_idx_1) AND (ranges_for_idx_2) AND ...
938
939 The SEL_ARG graph for each non-NULL element in keys[] may consist
940 of many single-index ranges (disjunctions), so ranges_for_idx_1
941 may e.g. be:
942
943 "idx_field1 = 1 OR (idx_field1 > 5 AND idx_field2 = 10)"
944
945 assuming that index1 is a composite index covering
946 (idx_field1,...,idx_field2,..)
947
948 Index merge intersection intersects ranges on SEL_ARGs from two or
949 more indexes.
950
951 Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
952 keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
953 merit in range analyzer functions (e.g. get_mm_parts) returning a
954 pointer to such SEL_TREE instead of NULL)
955
956 Note: If you want to set an element in keys[], use set_key()
957 or release_key() to make sure the SEL_ARG's use_count is correctly
958 updated.
959 */
961 Key_map keys_map; /* bitmask of non-NULL elements in keys */
962
963 /*
964 Possible ways to read rows using Index merge (sort) union.
965
966 Each element in 'merges' consists of multi-index disjunctions,
967 which means that Index merge (sort) union must be applied to read
968 rows. The nodes in the 'merges' list forms a conjunction of such
969 multi-index disjunctions.
970
971 The list is non-empty only if type==KEY.
972 */
974
975 /* The members below are filled/used only after get_mm_tree is done */
976 Key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
977 uint n_ror_scans; /* number of set bits in ror_scans_map */
978
979 /**
980 Convenience function for removing an element in keys[]. The typical
981 use for this function is to disconnect the next_key_part from the
982 root, send it to key_and() or key_or(), and then connect the
983 result of that function back to the SEL_ROOT using set_key().
984
985 @param index Which index slot to release.
986 @return The value in the slot (before removal).
987 */
988 SEL_ROOT *release_key(int index) {
989 SEL_ROOT *ret = keys[index];
990 if (keys[index]) {
991 assert(keys[index]->use_count > 0);
992 --keys[index]->use_count;
993 }
994 keys[index] = nullptr;
995 return ret;
996 }
997
998 /**
999 Convenience function for changing an element in keys[], including
1000 updating the use_count.
1001
1002 @param index Which index slot to change.
1003 @param key The new contents of the index slot. Is allowed to be nullptr.
1004 */
1005 void set_key(int index, SEL_ROOT *key) {
1006 release_key(index);
1007 keys[index] = key;
1008 if (key) ++key->use_count;
1009 }
1010};
1011
1012#ifndef NDEBUG
1013void print_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree, Key_map *tree_map,
1014 const char *msg);
1015#endif
1016
1017/*
1018 Get the SEL_ARG tree 'tree' for the keypart covering 'field', if
1019 any. 'tree' must be a unique conjunction to ALL predicates in earlier
1020 keyparts of 'keypart_tree'.
1021
1022 E.g., if 'keypart_tree' is for a composite index (kp1,kp2) and kp2
1023 covers 'field', all these conditions satisfies the requirement:
1024
1025 1. "(kp1=2 OR kp1=3) AND kp2=10" => returns "kp2=10"
1026 2. "(kp1=2 AND kp2=10) OR (kp1=3 AND kp2=10)" => returns "kp2=10"
1027 3. "(kp1=2 AND (kp2=10 OR kp2=11)) OR (kp1=3 AND (kp2=10 OR kp2=11))"
1028 => returns "kp2=10 OR kp2=11"
1029
1030 whereas these do not
1031 1. "(kp1=2 AND kp2=10) OR kp1=3"
1032 2. "(kp1=2 AND kp2=10) OR (kp1=3 AND kp2=11)"
1033 3. "(kp1=2 AND kp2=10) OR (kp1=3 AND (kp2=10 OR kp2=11))"
1034
1035 This function effectively tests requirement WA2.
1036
1037 @param[in] key_part_num Key part number we want the SEL_ARG tree for
1038 @param[in] keypart_tree The SEL_ARG* tree for the index
1039 @param[out] cur_range The SEL_ARG tree, if any, for the keypart
1040
1041 @retval true 'keypart_tree' contained a predicate for key part that
1042 is not conjunction to all predicates on earlier keyparts
1043 @retval false otherwise
1044*/
1045bool get_sel_root_for_keypart(uint key_part_num, SEL_ROOT *keypart_tree,
1046 SEL_ROOT **cur_range);
1047
1048/*
1049 Find the SEL_ROOT tree that corresponds to the chosen index.
1050
1051 SYNOPSIS
1052 get_index_range_tree()
1053 index [in] The ID of the index being looked for
1054 range_tree[in] Tree of ranges being searched
1055 param [in] RANGE_OPT_PARAM from test_quick_select
1056
1057 DESCRIPTION
1058
1059 A SEL_TREE contains range trees for all usable indexes. This procedure
1060 finds the SEL_ROOT tree for 'index'. The members of a SEL_TREE are
1061 ordered in the same way as the members of RANGE_OPT_PARAM::key, thus we
1062 first find the corresponding index in the array RANGE_OPT_PARAM::key.
1063 This index is returned through the variable param_idx, to be used later
1064 as argument of check_quick_select().
1065
1066 RETURN
1067 Pointer to the SEL_ROOT tree that corresponds to index.
1068*/
1069
1070inline SEL_ROOT *get_index_range_tree(uint index, SEL_TREE *range_tree,
1071 RANGE_OPT_PARAM *param) {
1072 uint idx = 0; /* Index nr in param->key_parts */
1073 while (idx < param->keys) {
1074 if (index == param->real_keynr[idx]) break;
1075 idx++;
1076 }
1077 return (range_tree->keys[idx]);
1078}
1079
1080/**
1081 Print the ranges in a SEL_TREE to debug log.
1082
1083 @param tree_name Descriptive name of the tree
1084 @param tree The SEL_TREE that will be printed to debug log
1085 @param param RANGE_OPT_PARAM from test_quick_select
1086*/
1087inline void dbug_print_tree([[maybe_unused]] const char *tree_name,
1088 [[maybe_unused]] SEL_TREE *tree,
1089 [[maybe_unused]] const RANGE_OPT_PARAM *param) {
1090#ifndef NDEBUG
1091 if (_db_enabled_()) print_tree(nullptr, tree_name, tree, param, true);
1092#endif
1093}
1094
1095#endif // SQL_RANGE_OPTIMIZER_TREE_H_
Definition: sql_bitmap.h:144
Used to store optimizer cost estimates.
Definition: handler.h:3752
Definition: field.h:575
bool is_nullable() const
Definition: field.h:1288
virtual int key_cmp(const uchar *a, const uchar *b) const
Definition: field.h:1193
Definition: key.h:112
Definition: sql_list.h:433
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Definition: range_opt_param.h:28
uint * real_keynr
Definition: range_opt_param.h:68
Definition: tree.h:464
void set_next_key_part(SEL_ROOT *next_key_part_arg)
Convenience function for changing next_key_part, including updating the use_count.
Definition: tree.h:548
SEL_ARG * first()
This gives the first SEL_ARG in the interval list, and the minimal element in the red-black tree.
Definition: tree.cc:385
void copy_max_to_min(SEL_ARG *arg)
Definition: tree.h:663
bool copy_min(SEL_ARG *arg)
Definition: tree.h:634
SEL_ARG * last()
Definition: tree.cc:396
SEL_ARG * rb_insert(SEL_ARG *leaf)
Definition: tree.cc:1885
void set_gis_index_read_function(const enum ha_rkey_function rkey_func)
Set spatial index range scan parameters.
Definition: tree.h:675
bool is_same(const SEL_ARG *arg) const
returns true if a range predicate is equal.
Definition: tree.h:574
bool maybe_flag
maybe_flag signals that this range is AND-ed with some unknown range (a MAYBE_KEY node).
Definition: tree.h:484
SEL_ROOT * release_next_key_part()
Convenience function for removing the next_key_part.
Definition: tree.h:532
enum ha_rkey_function rkey_func_flag
The rtree index interval to scan, undefined unless SEL_ARG::min_flag == GEOM_FLAG.
Definition: tree.h:498
bool is_ascending
true - ASC order, false - DESC
Definition: tree.h:556
SEL_ARG * clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next)
Definition: tree.cc:344
void copy_min_to_min(SEL_ARG *arg)
Definition: tree.h:655
SEL_ROOT * next_key_part
Definition: tree.h:522
uchar * min_value
Definition: tree.h:508
void copy_min_to_max(SEL_ARG *arg)
Definition: tree.h:659
uint8 part
Definition: tree.h:490
Field * field
Definition: tree.h:507
SEL_ARG * prev
Definition: tree.h:516
void make_root()
Definition: tree.h:794
SEL_ARG * clone_and(SEL_ARG *arg, MEM_ROOT *mem_root)
Definition: tree.h:595
int store_min_value(uint length, uchar **min_key, uint min_key_flag)
Definition: tree.h:683
uint get_min_flag()
Return correct min_flag.
Definition: tree.h:846
bool maybe_null() const
Definition: tree.h:492
SEL_ARG * parent
Definition: tree.h:517
leaf_color
Definition: tree.h:554
@ RED
Definition: tree.h:554
@ BLACK
Definition: tree.h:554
bool is_null_interval()
Definition: tree.h:582
int cmp_max_to_max(const SEL_ARG *arg) const
Definition: tree.h:589
uchar * max_value
Definition: tree.h:508
void maybe_smaller()
Definition: tree.h:580
SEL_ARG * right
Definition: tree.h:515
~SEL_ARG()
Note that almost all SEL_ARGs are created on the MEM_ROOT, so this destructor will only rarely be cal...
Definition: tree.h:568
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)
Helper function for storing min/max values of SEL_ARG taking into account key part's order.
Definition: tree.h:732
enum SEL_ARG::leaf_color color
int store_max_value(uint length, uchar **max_key, uint max_key_flag)
Definition: tree.h:699
SEL_ARG()=default
uint8 max_flag
Definition: tree.h:466
SEL_ARG * left
Definition: tree.h:515
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)
Helper function for storing min/max keys of next SEL_ARG taking into account key part's order.
Definition: tree.h:756
SEL_ARG * next
Definition: tree.h:516
int cmp_max_to_min(const SEL_ARG *arg) const
Definition: tree.h:592
int cmp_min_to_max(const SEL_ARG *arg) const
Definition: tree.h:586
bool copy_max(SEL_ARG *arg)
Definition: tree.h:644
uint get_max_flag()
Return correct max_flag.
Definition: tree.h:856
uint8 min_flag
Definition: tree.h:466
bool is_singlepoint() const
Definition: tree.h:820
void merge_flags(SEL_ARG *arg)
Definition: tree.h:579
SEL_ARG ** parent_ptr()
Definition: tree.h:800
SEL_ARG * clone_last(SEL_ARG *arg, MEM_ROOT *mem_root)
Definition: tree.h:625
friend int test_rb_tree(SEL_ARG *element, SEL_ARG *parent)
Definition: tree.cc:2006
friend SEL_ARG * rb_delete_fixup(SEL_ARG *root, SEL_ARG *key, SEL_ARG *par)
Definition: tree.cc:1938
SEL_ARG * clone_first(SEL_ARG *arg, MEM_ROOT *mem_root)
Definition: tree.h:618
int cmp_min_to_min(const SEL_ARG *arg) const
Definition: tree.h:583
A graph of (possible multiple) key ranges, represented as a red-black binary tree.
Definition: tree.h:67
Type
Used to indicate if the range predicate for an index is always true/false, depends on values from oth...
Definition: tree.h:74
@ KEY_RANGE
There is a range condition that can be used on this index.
@ MAYBE_KEY
There is a range predicate that refers to another table.
@ IMPOSSIBLE
The range predicate for this index is always false.
uint16 elements
Number of nodes in the RB-tree, not including sentinels.
Definition: tree.h:217
bool test_use_count(const SEL_ROOT *root) const
Check if SEL_ROOT::use_count value is correct.
Definition: tree.cc:2101
SEL_ROOT(SEL_ARG *root)
Constructs a tree of type KEY_RANGE, using the given root.
Definition: tree.cc:459
~SEL_ROOT()
Note that almost all SEL_ROOTs are created on the MEM_ROOT, so this destructor will only rarely be ca...
Definition: tree.h:109
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 for min key and max key.
Definition: tree.cc:86
SEL_ROOT * clone_tree(RANGE_OPT_PARAM *param) const
Create a new tree that's a duplicate of this one.
Definition: tree.cc:474
SEL_ARG * find_range(const SEL_ARG *key) const
Find best key with min <= given key.
Definition: tree.cc:1766
void free_tree()
Signal to the tree that the caller will shortly be dropping it on the floor; if others are still usin...
Definition: tree.cc:150
SEL_ARG * root
The root node of the tree.
Definition: tree.h:202
bool simple_key() const
Returns true iff this is a single-element, single-field predicate.
Definition: tree.h:866
void insert(SEL_ARG *key)
Insert the given node into the tree, and update the root.
Definition: tree.cc:1716
bool is_always() const
Returns true iff we have a single node that has no max nor min.
Definition: tree.h:861
void tree_delete(SEL_ARG *key)
Delete the given node from the tree, and update the root.
Definition: tree.cc:1793
int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag, uint last_part, bool start_key)
Definition: tree.cc:123
enum SEL_ROOT::Type type
ulong use_count
Number of references to this SEL_ARG tree.
Definition: tree.h:212
Definition: tree.h:870
enum SEL_TREE::Type type
Key_map keys_map
Definition: tree.h:961
uint n_ror_scans
Definition: tree.h:977
bool inexact
Whether this SEL_TREE is an inexact (too broad) representation of the predicates it is based on; that...
Definition: tree.h:919
List< SEL_IMERGE > merges
Definition: tree.h:973
SEL_TREE(MEM_ROOT *root, size_t num_keys)
Definition: tree.h:923
SEL_ROOT * release_key(int index)
Convenience function for removing an element in keys[].
Definition: tree.h:988
Key_map ror_scans_map
Definition: tree.h:976
Type
Starting an effort to document this field:
Definition: tree.h:888
@ IMPOSSIBLE
Definition: tree.h:888
@ ALWAYS
Definition: tree.h:888
void set_key(int index, SEL_ROOT *key)
Convenience function for changing an element in keys[], including updating the use_count.
Definition: tree.h:1005
SEL_TREE(enum Type type_arg, MEM_ROOT *root, size_t num_keys)
Definition: tree.h:921
Mem_root_array< SEL_ROOT * > keys
Definition: tree.h:960
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
static uint16 key1[1001]
Definition: hp_test2.cc:49
static uint keys
Definition: hp_test2.cc:48
void print_tree(String *out, const char *tree_name, SEL_TREE *tree, const RANGE_OPT_PARAM *param, const bool print_full)
Definition: range_optimizer.cc:1689
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
This file includes constants used by all storage engines.
ha_rkey_function
Definition: my_base.h:77
@ HA_READ_MBR_EQUAL
Definition: my_base.h:90
@ HA_READ_INVALID
Definition: my_base.h:91
@ HA_READ_MBR_CONTAIN
Definition: my_base.h:86
@ NEAR_MIN
Definition: my_base.h:1081
@ NO_MIN_RANGE
from -inf
Definition: my_base.h:1078
@ NO_MAX_RANGE
to +inf
Definition: my_base.h:1079
@ NEAR_MAX
Definition: my_base.h:1083
@ GEOM_FLAG
This flag means that the index is an rtree index, and the interval is specified using HA_READ_MBR_XXX...
Definition: my_base.h:1105
int _db_enabled_()
Definition: dbug.cc:1278
Some integer typedefs for easier portability.
uint8_t uint8
Definition: my_inttypes.h:62
unsigned char uchar
Definition: my_inttypes.h:51
uint16_t uint16
Definition: my_inttypes.h:64
bool length(const dd::Spatial_reference_system *srs, const Geometry *g1, double *length, bool *null) noexcept
Computes the length of linestrings and multilinestrings.
Definition: length.cc:75
SEL_ARG * null_element
Definition: range_optimizer.cc:156
required string key
Definition: replication_asynchronous_connection_failover.proto:59
File containing constants that can be used throughout the server.
constexpr const unsigned int MAX_KEY
Definition: sql_const.h:45
Definition: range_optimizer.h:54
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Definition: rowid_ordered_retrieval_plan.h:43
void dbug_print_tree(const char *tree_name, SEL_TREE *tree, const RANGE_OPT_PARAM *param)
Print the ranges in a SEL_TREE to debug log.
Definition: tree.h:1087
SEL_ROOT * key_and(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2)
Definition: tree.cc:885
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM *param)
Definition: tree.cc:590
SEL_ROOT * get_index_range_tree(uint index, SEL_TREE *range_tree, RANGE_OPT_PARAM *param)
Definition: tree.h:1070
void print_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree, Key_map *tree_map, const char *msg)
Definition: tree.cc:2176
uint invert_min_flag(uint min_flag)
A helper function to invert min flags to max flags for DESC key parts.
Definition: tree.h:227
SEL_ROOT * key_or(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2)
Combine two range expression under a common OR.
Definition: tree.cc:1078
SEL_TREE * tree_or(RANGE_OPT_PARAM *param, bool remove_jump_scans, SEL_TREE *tree1, SEL_TREE *tree2)
Definition: tree.cc:682
uint invert_max_flag(uint max_flag)
A helper function to invert max flags to min flags for DESC key parts.
Definition: tree.h:239
int sel_cmp(Field *f, uchar *a, uchar *b, uint8 a_flag, uint8 b_flag)
Definition: tree.cc:408
bool get_sel_root_for_keypart(uint key_part_num, SEL_ROOT *keypart_tree, SEL_ROOT **cur_range)
Definition: tree.cc:2135
SEL_TREE * tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2)
Definition: tree.cc:501