Ref Optimizer

This module analyzes all equality predicates to determine the best independent ref/eq_ref/ref_or_null index access methods. More...

Classes
struct	Key_field
	A Key_field is a descriptor of a predicate of the form (column <op> val). More...

Functions
	Key_field::Key_field (Item_field *item_field, Item *val, uint level, uint optimize, bool eq_func, bool null_rejecting, bool *cond_guard, uint sj_pred_no)
bool	add_key_fields (THD *thd, JOIN *join, Key_field **key_fields, uint *and_level, Item *cond, table_map usable_tables, SARGABLE_PARAM **sargables)
	The guts of the ref optimizer. More...

Variables
Item_field *	Key_field::item_field
	Item representing the column. More...
Item *	Key_field::val
	May be empty if diff constant. More...
uint	Key_field::level
uint	Key_field::optimize
	KEY_OPTIMIZE_*. More...
bool	Key_field::eq_func
bool	Key_field::null_rejecting
	If true, the condition this struct represents will not be satisfied when val IS NULL. More...
bool *	Key_field::cond_guard
uint	Key_field::sj_pred_no

Detailed Description

This module analyzes all equality predicates to determine the best independent ref/eq_ref/ref_or_null index access methods.

The 'ref' optimizer determines the columns (and expressions over them) that reference columns in other tables via an equality, and analyzes which keys and key parts can be used for index lookup based on these references. The main outcomes of the 'ref' optimizer are:

• A bi-directional graph of all equi-join conditions represented as an array of Key_use elements. This array is stored in JOIN::keyuse_array in table, key, keypart order. Each JOIN_TAB::keyuse points to the first Key_use element with the same table as JOIN_TAB::table.
• The table dependencies needed by the optimizer to determine what tables must be before certain table so that they provide the necessary column bindings for the equality predicates.
• Computed properties of the equality predicates such as null_rejecting and the result size of each separate condition.

Updates in JOIN_TAB:

• JOIN_TAB::keys Bitmap of all used keys.
• JOIN_TAB::const_keys Bitmap of all keys that may be used with quick_select.
• JOIN_TAB::keyuse Pointer to possible keys.

Function Documentation

Key_field()

Key_field::Key_field ( Item_field *  item_field, Item *  val, uint  level, uint  optimize, bool  eq_func, bool  null_rejecting, bool *  cond_guard, uint  sj_pred_no  )

inline

add_key_fields()

bool add_key_fields	(	THD *	thd,
		JOIN *	join,
		Key_field **	key_fields,
		uint *	and_level,
		Item *	cond,
		table_map	usable_tables,
		SARGABLE_PARAM **	sargables
	)

The guts of the ref optimizer.

This function, along with the other add_key_* functions, make up a recursive procedure that analyzes a condition expression (a tree of AND and OR predicates) and does many things.

Parameters

	thd	session context
	join	The query block involving the condition.
[in,out]	key_fields	Start of memory buffer, see below.
[in,out]	and_level	Current 'and level', see below.
	cond	The conditional expression to analyze.
	usable_tables	Tables not in this bitmap will not be examined.
[in,out]	sargables	End of memory buffer, see below.

Returns

false if success, true if error

This documentation is the result of reverse engineering and may therefore not capture the full gist of the procedure, but it is known to do the following:

• Populate a raw memory buffer from two directions at the same time. An 'array' of Key_field objects fill the buffer from low to high addresses whilst an 'array' of SARGABLE_PARAM's fills the buffer from high to low addresses. At the first call to this function, it is assumed that key_fields points to the beginning of the buffer and sargables point to the end (except for a poor-mans 'null element' at the very end).
• Update a number of properties in the JOIN_TAB's that can be used to find search keys (sargables).
  • JOIN_TAB::keys
  • JOIN_TAB::key_dependent
  • JOIN_TAB::const_keys (dictates if the range optimizer will be run later.)

The Key_field objects are marked with something called an 'and_level', which does not correspond to their nesting depth within the expression tree. It is rather a tag to group conjunctions together. For instance, in the conditional expression

a = 0 AND b = 0

two Key_field's are produced, both having an and_level of 0.

In an expression such as

a = 0 AND b = 0 OR a = 1

three Key_field's are produced, the first two corresponding to 'a = 0' and 'b = 0', respectively, both with and_level 0. The third one corresponds to 'a = 1' and has an and_level of 1.

A separate function, merge_key_fields() performs ref access validation on the Key_field array on the recursice ascent. If some Key_field's cannot be used for ref access, the key_fields pointer is rolled back. All other modifications to the query plan remain.

Variable Documentation

cond_guard

bool* Key_field::cond_guard

See also

Key_use::cond_guard

eq_func

bool Key_field::eq_func

item_field

Item_field* Key_field::item_field

Item representing the column.

level

uint Key_field::level

null_rejecting

bool Key_field::null_rejecting

If true, the condition this struct represents will not be satisfied when val IS NULL.

See also

Key_use::null_rejecting .

optimize

uint Key_field::optimize

KEY_OPTIMIZE_*.

sj_pred_no

uint Key_field::sj_pred_no

See also

Key_use::sj_pred_no

val

Item* Key_field::val

May be empty if diff constant.