tree.h File Reference

#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"

Go to the source code of this file.

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

Functions
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)
	Combine two range expression under a common OR. More...
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)
int	sel_cmp (Field *f, uchar *a, uchar *b, uint8 a_flag, uint8 b_flag)
uint	invert_min_flag (uint min_flag)
	A helper function to invert min flags to max flags for DESC key parts. More...
uint	invert_max_flag (uint max_flag)
	A helper function to invert max flags to min flags for DESC key parts. More...
void	print_sel_tree (RANGE_OPT_PARAM *param, SEL_TREE *tree, Key_map *tree_map, const char *msg)
bool	get_sel_root_for_keypart (uint key_part_num, SEL_ROOT *keypart_tree, SEL_ROOT **cur_range)
SEL_ROOT *	get_index_range_tree (uint index, SEL_TREE *range_tree, RANGE_OPT_PARAM *param)
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. More...

Function Documentation

dbug_print_tree()

void dbug_print_tree ( const char *  tree_name, SEL_TREE *  tree, const RANGE_OPT_PARAM *  param  )

inline

Print the ranges in a SEL_TREE to debug log.

Parameters

tree_name	Descriptive name of the tree
tree	The SEL_TREE that will be printed to debug log
param	RANGE_OPT_PARAM from test_quick_select

get_index_range_tree()

SEL_ROOT * get_index_range_tree ( uint  index, SEL_TREE *  range_tree, RANGE_OPT_PARAM *  param  )

inline

get_sel_root_for_keypart()

bool get_sel_root_for_keypart	(	uint	key_part_num,
		SEL_ROOT *	keypart_tree,
		SEL_ROOT **	cur_range
	)

Check if the SEL_ARG tree for 'field' is identical for all ranges in 'keypart_tree'.

invert_max_flag()

uint invert_max_flag ( uint  max_flag )

inline

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

invert_min_flag()

uint invert_min_flag ( uint  min_flag )

inline

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

key_and()

SEL_ROOT * key_and	(	RANGE_OPT_PARAM *	param,
		SEL_ROOT *	key1,
		SEL_ROOT *	key2
	)

key_or()

SEL_ROOT * key_or	(	RANGE_OPT_PARAM *	param,
		SEL_ROOT *	key1,
		SEL_ROOT *	key2
	)

Combine two range expression under a common OR.

On a logical level, the transformation is key_or( expr1, expr2 ) => expr1 OR expr2.

Both expressions are assumed to be in the SEL_ARG format. In a logic sense, the format is reminiscent of DNF, since an expression such as the following

( 1 < kp1 < 10 AND p1 ) OR ( 10 <= kp2 < 20 AND p2 )

where there is a key consisting of keyparts ( kp1, kp2, ..., kpn ) and p1 and p2 are valid SEL_ARG expressions over keyparts kp2 ... kpn, is a valid SEL_ARG condition. The disjuncts appear ordered by the minimum endpoint of the first range and ranges must not overlap. It follows that they are also ordered by maximum endpoints. Thus

( 1 < kp1 <= 2 AND ( kp2 = 2 OR kp2 = 3 ) ) OR kp1 = 3

Is a a valid SER_ARG expression for a key of at least 2 keyparts.

For simplicity, we will assume that expr2 is a single range predicate, i.e. on the form ( a < x < b AND ... ). It is easy to generalize to a disjunction of several predicates by subsequently call key_or for each disjunct.

The algorithm iterates over each disjunct of expr1, and for each disjunct where the first keypart's range overlaps with the first keypart's range in expr2:

If the predicates are equal for the rest of the keyparts, or if there are no more, the range in expr2 has its endpoints copied in, and the SEL_ARG node in expr2 is deallocated. If more ranges became connected in expr1, the surplus is also dealocated. If they differ, two ranges are created.

• The range leading up to the overlap. Empty if endpoints are equal.
• The overlapping sub-range. May be the entire range if they are equal.

Finally, there may be one more range if expr2's first keypart's range has a greater maximum endpoint than the last range in expr1.

For the overlapping sub-range, we recursively call key_or. Thus in order to compute key_or of

(1) ( 1 < kp1 < 10 AND 1 < kp2 < 10 )

(2) ( 2 < kp1 < 20 AND 4 < kp2 < 20 )

We create the ranges 1 < kp <= 2, 2 < kp1 < 10, 10 <= kp1 < 20. For the first one, we simply hook on the condition for the second keypart from (1) : 1 < kp2 < 10. For the second range 2 < kp1 < 10, key_or( 1 < kp2 < 10, 4 < kp2 < 20 ) is called, yielding 1 < kp2 < 20. For the last range, we reuse the range 4 < kp2 < 20 from (2) for the second keypart. The result is thus

( 1 < kp1 <= 2 AND 1 < kp2 < 10 ) OR ( 2 < kp1 < 10 AND 1 < kp2 < 20 ) OR ( 10 <= kp1 < 20 AND 4 < kp2 < 20 )

key_or() does not modify key1 nor key2 if they are in use by other roots (although typical use is that key1 has been disconnected from its root and thus can be modified in-place). Thus, it does not change their use_count.

The returned node will not have its use_count increased; you are supposed to do that yourself when you connect it to a root.

Parameters

param	RANGE_OPT_PARAM from test_quick_select
key1	Root of RB-tree of SEL_ARGs to be ORed with key2
key2	Root of RB-tree of SEL_ARGs to be ORed with key1

print_sel_tree()

void print_sel_tree	(	RANGE_OPT_PARAM *	param,
		SEL_TREE *	tree,
		Key_map *	tree_map,
		const char *	msg
	)

sel_cmp()

int sel_cmp	(	Field *	f,
		uchar *	a,
		uchar *	b,
		uint8	a_flag,
		uint8	b_flag
	)

sel_trees_can_be_ored()

bool sel_trees_can_be_ored	(	SEL_TREE *	tree1,
		SEL_TREE *	tree2,
		RANGE_OPT_PARAM *	param
	)

tree_and()

SEL_TREE * tree_and	(	RANGE_OPT_PARAM *	param,
		SEL_TREE *	tree1,
		SEL_TREE *	tree2
	)

tree_or()

SEL_TREE * tree_or	(	RANGE_OPT_PARAM *	param,
		bool	remove_jump_scans,
		SEL_TREE *	tree1,
		SEL_TREE *	tree2
	)