MySQL  8.0.20
Source Code Documentation
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_TABtable
 
Key_usekey
 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
costEstimated cost
rowcountEstimated 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
idxIndex of position object within array, if zero there is no "previous" stage that can be added.
cmCost 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: