Simple SQL optimizer. More...

#include "pars0opt.h"
#include <stddef.h>
#include "dict0boot.h"
#include "dict0dict.h"
#include "dict0mem.h"
#include "lock0lock.h"
#include "pars0grm.h"
#include "pars0pars.h"
#include "que0que.h"
#include "row0ins.h"
#include "row0sel.h"
#include "row0upd.h"

Macros
#define	OPT_EQUAL 1 /* comparison by = */

#define	OPT_COMPARISON 2 /* comparison by <, >, <=, or >= */

#define	OPT_NOT_COND 1

#define	OPT_END_COND 2

#define	OPT_TEST_COND 3

#define	OPT_SCROLL_COND 4

Functions
static int	opt_invert_cmp_op (int op)
	Inverts a comparison operator. More...

static bool	opt_check_exp_determined_before (que_node_t exp, sel_node_t sel_node, ulint nth_table)
	Checks if the value of an expression can be calculated BEFORE the nth table in a join is accessed. More...

static que_node_t *	opt_look_for_col_in_comparison_before (ulint cmp_type, ulint col_no, func_node_t search_cond, sel_node_t sel_node, ulint nth_table, ulint *op)
	Looks in a comparison condition if a column value is already restricted by it BEFORE the nth table is accessed. More...

static que_node_t *	opt_look_for_col_in_cond_before (ulint cmp_type, ulint col_no, func_node_t search_cond, sel_node_t sel_node, ulint nth_table, ulint *op)
	Looks in a search condition if a column value is already restricted by the search condition BEFORE the nth table is accessed. More...

static ulint	opt_calc_index_goodness (dict_index_t index, sel_node_t sel_node, ulint nth_table, que_node_t *index_plan, ulint last_op)
	Calculates the goodness for an index according to a select node. More...

static ulint	opt_calc_n_fields_from_goodness (ulint goodness)
	Calculates the number of matched fields based on an index goodness. More...

static page_cur_mode_t	opt_op_to_search_mode (bool asc, ulint op)
	Converts a comparison operator to the corresponding search mode PAGE_CUR_GE, ... More...

static bool	opt_is_arg (que_node_t arg_node, func_node_t func_node)
	Determines if a node is an argument node of a function node. More...

static void	opt_check_order_by (sel_node_t *sel_node)
	Decides if the fetching of rows should be made in a descending order, and also checks that the chosen query plan produces a result which satisfies the order-by. More...

static void	opt_search_plan_for_table (sel_node_t sel_node, ulint i, dict_table_t table)
	Optimizes a select. More...

static ulint	opt_classify_comparison (sel_node_t sel_node, ulint i, func_node_t cond)
	Looks at a comparison condition and decides if it can, and need, be tested for a table AFTER the table has been accessed. More...

static void	opt_find_test_conds (sel_node_t sel_node, ulint i, func_node_t cond)
	Recursively looks for test conditions for a table in a join. More...

static void	opt_normalize_cmp_conds (func_node_t cond, dict_table_t table)
	Normalizes a list of comparison conditions so that a column of the table appears on the left side of the comparison if possible. More...

static void	opt_determine_and_normalize_test_conds (sel_node_t *sel_node, ulint i)
	Finds out the search condition conjuncts we can, and need, to test as the ith table in a join is accessed. More...

void	opt_find_all_cols (bool copy_val, dict_index_t index, sym_node_list_t col_list, plan_t plan, que_node_t exp)
	Looks for occurrences of the columns of the table in the query subgraph and adds them to the list of columns if an occurrence of the same column does not already exist in the list. More...

static void	opt_find_copy_cols (sel_node_t sel_node, ulint i, func_node_t search_cond)
	Looks for occurrences of the columns of the table in conditions which are not yet determined AFTER the join operation has fetched a row in the ith table. More...

static void	opt_classify_cols (sel_node_t *sel_node, ulint i)
	Classifies the table columns according to whether we use the column only while holding the latch on the page, or whether we have to copy the column value to dynamic memory. More...

static void	opt_clust_access (sel_node_t *sel_node, ulint n)
	Fills in the info in plan which is used in accessing a clustered index record. More...

void	opt_search_plan (sel_node_t *sel_node)
	Optimizes a select. More...

Detailed Description

Simple SQL optimizer.

Created 12/21/1997 Heikki Tuuri

Macro Definition Documentation

◆ OPT_COMPARISON

#define OPT_COMPARISON 2 /* comparison by <, >, <=, or >= */

◆ OPT_END_COND

#define OPT_END_COND 2

◆ OPT_EQUAL

#define OPT_EQUAL 1 /* comparison by = */

◆ OPT_NOT_COND

#define OPT_NOT_COND 1

◆ OPT_SCROLL_COND

#define OPT_SCROLL_COND 4

◆ OPT_TEST_COND

#define OPT_TEST_COND 3

Function Documentation

◆ opt_calc_index_goodness()

static ulint opt_calc_index_goodness	(	dict_index_t *	index,
		sel_node_t *	sel_node,
		ulint	nth_table,
		que_node_t **	index_plan,
		ulint *	last_op
	)

static

Calculates the goodness for an index according to a select node.

The goodness is 4 times the number of first fields in index whose values we already know exactly in the query. If we have a comparison condition for an additional field, 2 point are added. If the index is unique, and we know all the unique fields for the index we add 1024 points. For a clustered index we add 1 point.

Returns: goodness

Parameters

index	in: index
sel_node	in: parsed select node
nth_table	in: nth table in a join
index_plan	in/out: comparison expressions for this index
last_op	out: last comparison operator, if goodness > 1

◆ opt_calc_n_fields_from_goodness()

static ulint opt_calc_n_fields_from_goodness ( ulint goodness )

inlinestatic

Calculates the number of matched fields based on an index goodness.

Returns: number of exactly or partially matched fields

Parameters

goodness in: goodness

◆ opt_check_exp_determined_before()

static bool opt_check_exp_determined_before	(	que_node_t *	exp,
		sel_node_t *	sel_node,
		ulint	nth_table
	)

static

Checks if the value of an expression can be calculated BEFORE the nth table in a join is accessed.

If this is the case, it can possibly be used in an index search for the nth table.

Returns: true if already determined

Parameters

exp	in: expression
sel_node	in: select node
nth_table	in: nth table will be accessed

◆ opt_check_order_by()

static void opt_check_order_by ( sel_node_t * sel_node )

static

Decides if the fetching of rows should be made in a descending order, and also checks that the chosen query plan produces a result which satisfies the order-by.

Parameters

sel_node in: select node; asserts an error if the plan does not agree with the order-by

◆ opt_classify_cols()

static void opt_classify_cols	(	sel_node_t *	sel_node,
		ulint	i
	)

static

Classifies the table columns according to whether we use the column only while holding the latch on the page, or whether we have to copy the column value to dynamic memory.

Puts the first occurrence of a column to either list in the plan node, and puts indirections to later occurrences of the column.

Parameters

sel_node	in: select node
i	in: ith table in the join

◆ opt_classify_comparison()

static ulint opt_classify_comparison	(	sel_node_t *	sel_node,
		ulint	i,
		func_node_t *	cond
	)

static

Looks at a comparison condition and decides if it can, and need, be tested for a table AFTER the table has been accessed.

Returns: OPT_NOT_COND if not for this table, else OPT_END_COND, OPT_TEST_COND, or OPT_SCROLL_COND, where the last means that the condition need not be tested, except when scroll cursors are used

Parameters

sel_node	in: select node
i	in: ith table in the join
cond	in: comparison condition

◆ opt_clust_access()

static void opt_clust_access	(	sel_node_t *	sel_node,
		ulint	n
	)

static

Fills in the info in plan which is used in accessing a clustered index record.

The columns must already be classified for the plan node.

Parameters

sel_node	in: select node
n	in: nth table in select

◆ opt_determine_and_normalize_test_conds()

static void opt_determine_and_normalize_test_conds	(	sel_node_t *	sel_node,
		ulint	i
	)

static

Finds out the search condition conjuncts we can, and need, to test as the ith table in a join is accessed.

The search tuple can eliminate the need to test some conjuncts.

Parameters

sel_node	in: select node
i	in: ith table in the join

◆ opt_find_all_cols()

void opt_find_all_cols	(	bool	copy_val,
		dict_index_t *	index,
		sym_node_list_t *	col_list,
		plan_t *	plan,
		que_node_t *	exp
	)

Looks for occurrences of the columns of the table in the query subgraph and adds them to the list of columns if an occurrence of the same column does not already exist in the list.

If the column is already in the list, puts a value indirection to point to the occurrence in the column list, except if the column occurrence we are looking at is in the column list, in which case nothing is done.

Parameters

copy_val	in: if true, new found columns are added as columns to copy
index	in: index of the table to use
col_list	in: base node of a list where to add new found columns
plan	in: plan or NULL
exp	in: expression or condition or NULL

◆ opt_find_copy_cols()

static void opt_find_copy_cols	(	sel_node_t *	sel_node,
		ulint	i,
		func_node_t *	search_cond
	)

static

Looks for occurrences of the columns of the table in conditions which are not yet determined AFTER the join operation has fetched a row in the ith table.

The values for these column must be copied to dynamic memory for later use.

Parameters

sel_node	in: select node
i	in: ith table in the join
search_cond	in: search condition or NULL

◆ opt_find_test_conds()

static void opt_find_test_conds	(	sel_node_t *	sel_node,
		ulint	i,
		func_node_t *	cond
	)

static

Recursively looks for test conditions for a table in a join.

Parameters

sel_node	in: select node
i	in: ith table in the join
cond	in: conjunction of search conditions or NULL

◆ opt_invert_cmp_op()

static int opt_invert_cmp_op ( int op )

static

Inverts a comparison operator.

Returns: the equivalent operator when the order of the arguments is switched

Parameters

op	in: operator

◆ opt_is_arg()

static bool opt_is_arg	(	que_node_t *	arg_node,
		func_node_t *	func_node
	)

static

Determines if a node is an argument node of a function node.

Returns: true if is an argument

Parameters

arg_node	in: possible argument node
func_node	in: function node

◆ opt_look_for_col_in_comparison_before()

static que_node_t * opt_look_for_col_in_comparison_before	(	ulint	cmp_type,
		ulint	col_no,
		func_node_t *	search_cond,
		sel_node_t *	sel_node,
		ulint	nth_table,
		ulint *	op
	)

static

Looks in a comparison condition if a column value is already restricted by it BEFORE the nth table is accessed.

Returns: expression restricting the value of the column, or NULL if not known

Parameters

cmp_type	in: OPT_EQUAL, OPT_COMPARISON
col_no	in: column number
search_cond	in: comparison condition
sel_node	in: select node
nth_table	in: nth table in a join (a query from a single table is considered a join of 1 table)
op	out: comparison operator ('=', PARS_GE_TOKEN, ... ); this is inverted if the column appears on the right side

◆ opt_look_for_col_in_cond_before()

static que_node_t * opt_look_for_col_in_cond_before	(	ulint	cmp_type,
		ulint	col_no,
		func_node_t *	search_cond,
		sel_node_t *	sel_node,
		ulint	nth_table,
		ulint *	op
	)

static

Looks in a search condition if a column value is already restricted by the search condition BEFORE the nth table is accessed.

Takes into account that if we will fetch in an ascending order, we cannot utilize an upper limit for a column value; in a descending order, respectively, a lower limit.

Returns: expression restricting the value of the column, or NULL if not known

Parameters

cmp_type	in: OPT_EQUAL, OPT_COMPARISON
col_no	in: column number
search_cond	in: search condition or NULL
sel_node	in: select node
nth_table	in: nth table in a join (a query from a single table is considered a join of 1 table)
op	out: comparison operator ('=', PARS_GE_TOKEN, ... )

◆ opt_normalize_cmp_conds()

static void opt_normalize_cmp_conds	(	func_node_t *	cond,
		dict_table_t *	table
	)

static

Normalizes a list of comparison conditions so that a column of the table appears on the left side of the comparison if possible.

This is accomplished by switching the arguments of the operator.

Parameters

cond	in: first in a list of comparison conditions, or NULL
table	in: table

◆ opt_op_to_search_mode()

static page_cur_mode_t opt_op_to_search_mode	(	bool	asc,
		ulint	op
	)

inlinestatic

Converts a comparison operator to the corresponding search mode PAGE_CUR_GE, ...

Returns: search mode

Parameters

asc	in: true if the rows should be fetched in an ascending order
op	in: operator '=', PARS_GE_TOKEN, ...

◆ opt_search_plan()

void opt_search_plan ( sel_node_t * sel_node )

Optimizes a select.

Decides which indexes to tables to use. The tables are accessed in the order that they were written to the FROM part in the select statement.

Parameters

sel_node in: parsed select node

◆ opt_search_plan_for_table()

static void opt_search_plan_for_table	(	sel_node_t *	sel_node,
		ulint	i,
		dict_table_t *	table
	)

static

Optimizes a select.

Decides which indexes to tables to use. The tables are accessed in the order that they were written to the FROM part in the select statement.

Parameters

sel_node	in: parsed select node
i	in: this is the ith table
table	in: table

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ OPT_COMPARISON

◆ OPT_END_COND

◆ OPT_EQUAL

◆ OPT_NOT_COND

◆ OPT_SCROLL_COND

◆ OPT_TEST_COND

Function Documentation

◆ opt_calc_index_goodness()

◆ opt_calc_n_fields_from_goodness()

◆ opt_check_exp_determined_before()

◆ opt_check_order_by()

◆ opt_classify_cols()

◆ opt_classify_comparison()

◆ opt_clust_access()

◆ opt_determine_and_normalize_test_conds()

◆ opt_find_all_cols()

◆ opt_find_copy_cols()

◆ opt_find_test_conds()

◆ opt_invert_cmp_op()

◆ opt_is_arg()

◆ opt_look_for_col_in_comparison_before()

◆ opt_look_for_col_in_cond_before()

◆ opt_normalize_cmp_conds()

◆ opt_op_to_search_mode()

◆ opt_search_plan()

◆ opt_search_plan_for_table()