POSITION Struct Reference

A position of table within a join order. More...

#include <sql_select.h>

Public Member Functions
void	no_semijoin ()
	Even if the query has no semijoin, two sj-related members are read and must thus have been set, by this function. More...
void	set_prefix_cost (double cost, double rowcount)
	Set complete estimated cost and produced rowcount for the prefix of tables up to and including this table, in the join plan. More...
void	set_prefix_join_cost (uint idx, const Cost_model_server *cm)
	Set complete estimated cost and produced rowcount for the prefix of tables up to and including this table, calculated from the cost of the previous stage, the fanout of the current stage and the cost to process a row at the current stage. More...

Public Attributes
double	rows_fetched
	The number of rows that will be fetched by the chosen access method per each row combination of previous tables. More...
double	read_cost
	Cost of accessing the table in course of the entire complete join execution, i.e. More...
float	filter_effect
	The fraction of the 'rows_fetched' rows that will pass the table conditions that were NOT used by the access method. More...
double	prefix_rowcount
	prefix_rowcount and prefix_cost form a stack of partial join order costs and output sizes More...
double	prefix_cost
JOIN_TAB *	table
Key_use *	key
	NULL - 'index' or 'range' or 'index_merge' or 'ALL' access is used. More...
table_map	ref_depend_map
	If ref-based access is used: bitmap of tables this table depends on. More...
bool	use_join_buffer
uint	sj_strategy
	Current optimization state: Semi-join strategy to be used for this and preceding join tables. More...
uint	n_sj_tables
	Valid only after fix_semijoin_strategies_for_picked_join_order() call: if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that are covered by the specified semi-join strategy. More...
table_map	dups_producing_tables
	Bitmap of semi-join inner tables that are in the join prefix and for which there's no provision yet for how to eliminate semi-join duplicates which they produce. More...
uint	first_loosescan_table
table_map	loosescan_need_tables
uint	loosescan_key
uint	loosescan_parts
uint	first_firstmatch_table
nested_join_map	cur_embedding_map
	Value of Optimize_table_order::cur_embedding_map after this table has been added to the plan. More...
table_map	first_firstmatch_rtbl
table_map	firstmatch_need_tables
uint	first_dupsweedout_table
table_map	dupsweedout_tables
uint	sjm_scan_last_inner
table_map	sjm_scan_need_tables

Detailed Description

A position of table within a join order.

This structure is primarily used as a part of join->positions and join->best_positions arrays.

One POSITION element contains information about:

• Which table is accessed
• Which access method was chosen = Its cost and #of output records
• Semi-join strategy choice. Note that there are two different representation formats:
  1. The one used during join optimization
  2. The one used at plan refinement/code generation stage. We call fix_semijoin_strategies_for_picked_join_order() to switch between #1 and #2. See that function's comment for more details.
• Semi-join optimization state. When we're running join optimization, we main a state for every semi-join strategy which are various variables that tell us if/at which point we could consider applying the strategy. The variables are really a function of join prefix but they are too expensive to re-caclulate for every join prefix we consider, so we maintain current state in join->positions[#tables_in_prefix]. See advance_sj_state() for details.

This class has to stay a POD, because it is memcpy'd in many places.

Member Function Documentation

no_semijoin()

void POSITION::no_semijoin ( )

inline

Even if the query has no semijoin, two sj-related members are read and must thus have been set, by this function.

set_prefix_cost()

void POSITION::set_prefix_cost ( double  cost, double  rowcount  )

inline

Set complete estimated cost and produced rowcount for the prefix of tables up to and including this table, in the join plan.

Parameters

cost	Estimated cost
rowcount	Estimated row count

set_prefix_join_cost()

void POSITION::set_prefix_join_cost ( uint  idx, const Cost_model_server *  cm  )

inline

Set complete estimated cost and produced rowcount for the prefix of tables up to and including this table, calculated from the cost of the previous stage, the fanout of the current stage and the cost to process a row at the current stage.

Parameters

idx	Index of position object within array, if zero there is no "previous" stage that can be added.
cm	Cost model that provides the actual calculation

Member Data Documentation

cur_embedding_map

nested_join_map POSITION::cur_embedding_map

Value of Optimize_table_order::cur_embedding_map after this table has been added to the plan.

Used to constrain FirstMatch table orders.

dups_producing_tables

table_map POSITION::dups_producing_tables

Bitmap of semi-join inner tables that are in the join prefix and for which there's no provision yet for how to eliminate semi-join duplicates which they produce.

dupsweedout_tables

table_map POSITION::dupsweedout_tables

filter_effect

float POSITION::filter_effect

The fraction of the 'rows_fetched' rows that will pass the table conditions that were NOT used by the access method.

If, e.g.,

"SELECT ... WHERE t1.colx = 4 and t1.coly @> 5"

is resolved by ref access on t1.colx, filter_effect will be the fraction of rows that will pass the "t1.coly @> 5" predicate. The valid range is 0..1, where 0.0 means that no rows will pass the table conditions and 1.0 means that all rows will pass.

It is used to calculate how many row combinations will be joined with the next table,

See also

prefix_rowcount below.

Note

With condition filtering enabled, it is possible to get a fanout = rows_fetched * filter_effect that is less than 1.0. Consider, e.g., a join between t1 and t2:

"SELECT ... WHERE t1.col1=t2.colx and t2.coly OP @<something@>"

where t1 is a prefix table and the optimizer currently calculates the cost of adding t2 to the join. Assume that the chosen access method on t2 is a 'ref' access on 'colx' that is estimated to produce 2 rows per row from t1 (i.e., rows_fetched = 2). It will in this case be perfectly fine to calculate a filtering effect <0.5 (resulting in "rows_fetched * filter_effect @< 1.0") from the predicate "t2.coly OP @<something@>". If so, the number of row combinations from (t1,t2) is lower than the prefix_rowcount of t1.

The above is just an example of how the fanout of a table can become less than one. It can happen for any access method.

first_dupsweedout_table

uint POSITION::first_dupsweedout_table

first_firstmatch_rtbl

table_map POSITION::first_firstmatch_rtbl

first_firstmatch_table

uint POSITION::first_firstmatch_table

first_loosescan_table

uint POSITION::first_loosescan_table

firstmatch_need_tables

table_map POSITION::firstmatch_need_tables

key

Key_use* POSITION::key

NULL - 'index' or 'range' or 'index_merge' or 'ALL' access is used.

Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}

loosescan_key

uint POSITION::loosescan_key

loosescan_need_tables

table_map POSITION::loosescan_need_tables

loosescan_parts

uint POSITION::loosescan_parts

n_sj_tables

uint POSITION::n_sj_tables

Valid only after fix_semijoin_strategies_for_picked_join_order() call: if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that are covered by the specified semi-join strategy.

prefix_cost

double POSITION::prefix_cost

prefix_rowcount

double POSITION::prefix_rowcount

prefix_rowcount and prefix_cost form a stack of partial join order costs and output sizes

prefix_rowcount: The number of row combinations that will be joined to the next table in the join sequence.

For a joined table it is calculated as prefix_rowcount = last_table.prefix_rowcount * rows_fetched * filter_effect

See also

filter_effect

For a semijoined table it may be less than this formula due to duplicate elimination.

read_cost

double POSITION::read_cost

Cost of accessing the table in course of the entire complete join execution, i.e.

cost of one access method use (e.g. 'range' or 'ref' scan ) multiplied by estimated number of rows from tables earlier in the join sequence.

read_cost does NOT include cost of processing rows within the executor (row_evaluate_cost).

ref_depend_map

table_map POSITION::ref_depend_map

If ref-based access is used: bitmap of tables this table depends on.

rows_fetched

double POSITION::rows_fetched

The number of rows that will be fetched by the chosen access method per each row combination of previous tables.

That is:

rows_fetched = selectivity(access_condition) * cardinality(table)

where 'access_condition' is whatever condition was chosen for index access, depending on the access method ('ref', 'range', etc.)

Note

For index/table scans, rows_fetched may be less than the number of rows in the table because the cost of evaluating constant conditions is included in the scan cost, and the number of rows produced by these scans is the estimated number of rows that pass the constant conditions.

See also

Optimize_table_order::calculate_scan_cost() . But this is only during planning; make_join_readinfo() simplifies it for EXPLAIN.

sj_strategy

uint POSITION::sj_strategy

Current optimization state: Semi-join strategy to be used for this and preceding join tables.

Join optimizer sets this for the last join_tab in the duplicate-generating range. That is, in order to interpret this field, one needs to traverse join->[best_]positions array from right to left. When you see a join table with sj_strategy!= SJ_OPT_NONE, some other field (depending on the strategy) tells how many preceding positions this applies to. The values of covered_preceding_positions->sj_strategy must be ignored.

sjm_scan_last_inner

uint POSITION::sjm_scan_last_inner

sjm_scan_need_tables

table_map POSITION::sjm_scan_need_tables

table

JOIN_TAB* POSITION::table

use_join_buffer

bool POSITION::use_join_buffer

---

The documentation for this struct was generated from the following file:

• sql/sql_select.h