MySQL 8.2.0
Source Code Documentation

A graph of (possible multiple) key ranges, represented as a redblack 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 noop, 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_ARG *  find_range (const SEL_ARG *key) const 
Find best key with min <= given key. More...  
SEL_ROOT *  clone_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 singleelement, singlefield predicate. More...  
Public Attributes  
enum SEL_ROOT::Type  type 
SEL_ARG *  root 
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 RBtree, not including sentinels. More...  
A graph of (possible multiple) key ranges, represented as a redblack 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.

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.
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.)
Used to construct MAYBE_KEY and IMPOSSIBLE SEL_ARGs.

inline 
Note that almost all SEL_ROOTs are created on the MEM_ROOT, so this destructor will only rarely be called.
SEL_ROOT * SEL_ROOT::clone_tree  (  RANGE_OPT_PARAM *  param  )  const 
Create a new tree that's a duplicate of this one.
param  The parameters for the new tree. Used to find out which MEM_ROOT to allocate the new nodes on. 
Find best key with min <= given key.
Because of the call context, this should never return nullptr to get_range.
key  The key to search for. 
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 noop, but if the caller was the last one, it is now an orphan, and references from it should not count.
void SEL_ROOT::insert  (  SEL_ARG *  key  ) 
Insert the given node into the tree, and update the root.
key  The node to insert. 

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.

inline 
Returns true iff this is a singleelement, singlefield predicate.
int SEL_ROOT::store_max_key  (  KEY_PART *  key, 
uchar **  range_key,  
uint *  range_key_flag,  
uint  last_part,  
bool  start_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.
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".
root  The origin tree of the SEL_ARG graph (an RBtree that has the least value of root>sel_root>root>part in the entire graph, and thus is the "origin" of the graph) 
void SEL_ROOT::tree_delete  (  SEL_ARG *  key  ) 
Delete the given node from the tree, and update the root.
key  The node to delete. Must exist in the tree. 
uint16 SEL_ROOT::elements {0} 
Number of nodes in the RBtree, not including sentinels.
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.
enum SEL_ROOT::Type SEL_ROOT::type 
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 reused in a lazycopy manner based on this reference counting.