MySQL 8.0.30
Source Code Documentation
SEL_ROOT Class Reference

A graph of (possible multiple) key ranges, represented as a red-black binary tree. More...

#include <tree.h>

Public Types

enum class  Type { IMPOSSIBLE , MAYBE_KEY , KEY_RANGE }
 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. More...
 

Public Member Functions

 SEL_ROOT (SEL_ARG *root)
 Constructs a tree of type KEY_RANGE, using the given root. More...
 
 SEL_ROOT (MEM_ROOT *memroot, Type type_arg)
 Used to construct MAYBE_KEY and IMPOSSIBLE SEL_ARGs. More...
 
 ~SEL_ROOT ()
 Note that almost all SEL_ROOTs are created on the MEM_ROOT, so this destructor will only rarely be called. More...
 
bool is_always () const
 Returns true iff we have a single node that has no max nor min. More...
 
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. More...
 
int store_max_key (KEY_PART *key, uchar **range_key, uint *range_key_flag, uint last_part, bool start_key)
 
void free_tree ()
 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. More...
 
void insert (SEL_ARG *key)
 Insert the given node into the tree, and update the root. More...
 
void tree_delete (SEL_ARG *key)
 Delete the given node from the tree, and update the root. More...
 
SEL_ARGfind_range (const SEL_ARG *key) const
 Find best key with min <= given key. More...
 
SEL_ROOTclone_tree (RANGE_OPT_PARAM *param) const
 Create a new tree that's a duplicate of this one. More...
 
bool test_use_count (const SEL_ROOT *root) const
 Check if SEL_ROOT::use_count value is correct. More...
 
bool simple_key () const
 Returns true iff this is a single-element, single-field predicate. More...
 

Public Attributes

enum SEL_ROOT::Type type
 
SEL_ARGroot
 The root node of the tree. More...
 
ulong use_count {0}
 Number of references to this SEL_ARG tree. More...
 
uint16 elements {0}
 Number of nodes in the RB-tree, not including sentinels. More...
 

Detailed Description

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.

Member Enumeration Documentation

◆ Type

enum class SEL_ROOT::Type
strong

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.

Enumerator
IMPOSSIBLE 

The range predicate for this index is always false.

MAYBE_KEY 

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.

KEY_RANGE 

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.

Constructor & Destructor Documentation

◆ SEL_ROOT() [1/2]

SEL_ROOT::SEL_ROOT ( SEL_ARG root)

Constructs a tree of type KEY_RANGE, using the given root.

(The root is allowed to have children.)

◆ SEL_ROOT() [2/2]

SEL_ROOT::SEL_ROOT ( MEM_ROOT memroot,
Type  type_arg 
)

Used to construct MAYBE_KEY and IMPOSSIBLE SEL_ARGs.

◆ ~SEL_ROOT()

SEL_ROOT::~SEL_ROOT ( )
inline

Note that almost all SEL_ROOTs are created on the MEM_ROOT, so this destructor will only rarely be called.

Member Function Documentation

◆ clone_tree()

SEL_ROOT * SEL_ROOT::clone_tree ( RANGE_OPT_PARAM param) const

Create a new tree that's a duplicate of this one.

Parameters
paramThe parameters for the new tree. Used to find out which MEM_ROOT to allocate the new nodes on.
Returns
The new tree, or nullptr in case of out of memory.

◆ find_range()

SEL_ARG * SEL_ROOT::find_range ( const SEL_ARG key) const

Find best key with min <= given key.

Because of the call context, this should never return nullptr to get_range.

Parameters
keyThe key to search for.

◆ free_tree()

void SEL_ROOT::free_tree ( )

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.

◆ insert()

void SEL_ROOT::insert ( SEL_ARG key)

Insert the given node into the tree, and update the root.

Parameters
keyThe node to insert.

◆ is_always()

bool SEL_ROOT::is_always ( ) const
inline

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.

◆ simple_key()

bool SEL_ROOT::simple_key ( ) const
inline

Returns true iff this is a single-element, single-field predicate.

◆ store_max_key()

int SEL_ROOT::store_max_key ( KEY_PART key,
uchar **  range_key,
uint range_key_flag,
uint  last_part,
bool  start_key 
)

◆ store_min_key()

int SEL_ROOT::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.

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.

◆ test_use_count()

bool SEL_ROOT::test_use_count ( const SEL_ROOT root) const

Check if SEL_ROOT::use_count value is correct.

See the definition of use_count for what is "correct".

Parameters
rootThe 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)
Returns
true iff an incorrect SEL_ARG::use_count is found.

◆ tree_delete()

void SEL_ROOT::tree_delete ( SEL_ARG key)

Delete the given node from the tree, and update the root.

Parameters
keyThe node to delete. Must exist in the tree.

Member Data Documentation

◆ elements

uint16 SEL_ROOT::elements {0}

Number of nodes in the RB-tree, not including sentinels.

◆ root

SEL_ARG* SEL_ROOT::root

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.

◆ type

enum SEL_ROOT::Type SEL_ROOT::type

◆ use_count

ulong SEL_ROOT::use_count {0}

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.


The documentation for this class was generated from the following files: