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_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 single-element, single-field 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 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

param The 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

key	The 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

key	The 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

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)

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

key	The 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:

sql/range_optimizer/tree.h
sql/range_optimizer/tree.cc

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Enumeration Documentation

◆ Type

Constructor & Destructor Documentation

◆ SEL_ROOT() [1/2]

◆ SEL_ROOT() [2/2]

◆ ~SEL_ROOT()

Member Function Documentation

◆ clone_tree()

◆ find_range()

◆ free_tree()

◆ insert()

◆ is_always()

◆ simple_key()

◆ store_max_key()

◆ store_min_key()

◆ test_use_count()

◆ tree_delete()

Member Data Documentation

◆ elements

◆ root

◆ type

◆ use_count