access_path.h File Reference

#include <assert.h>
#include <stdint.h>
#include <cmath>
#include <cstddef>
#include <type_traits>
#include <utility>
#include <vector>
#include "my_alloc.h"
#include "my_base.h"
#include "my_table_map.h"
#include "sql/item.h"
#include "sql/iterators/row_iterator.h"
#include "sql/join_optimizer/interesting_orders_defs.h"
#include "sql/join_optimizer/materialize_path_parameters.h"
#include "sql/join_optimizer/node_map.h"
#include "sql/join_optimizer/overflow_bitset.h"
#include "sql/join_type.h"
#include "sql/mem_root_array.h"
#include "sql/olap.h"
#include "sql/sql_class.h"
#include "sql/table.h"

Go to the source code of this file.

Classes
struct	JoinPredicate
	A specification that two specific relational expressions (e.g., two tables, or a table and a join between two other tables) should be joined together. More...
struct	Predicate
	A filter of some sort that is not a join condition (those are stored in JoinPredicate objects). More...
struct	AppendPathParameters
struct	AccessPath
	Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path contains pretty much exactly the information needed to instantiate given iterator, plus some information that is only needed during planning, such as costs. More...

Functions
double	FirstRowCost (double init_cost, double total_cost, double output_rows)
	Calculate the cost of reading the first row from an access path, given estimates for init cost, total cost and the number of rows returned. More...
void	CopyBasicProperties (const AccessPath &from, AccessPath *to)
AccessPath *	NewTableScanAccessPath (THD *thd, TABLE *table, bool count_examined_rows)
AccessPath *	NewSampleScanAccessPath (THD *thd, TABLE *table, double sampling_percentage, bool count_examined_rows)
AccessPath *	NewIndexScanAccessPath (THD *thd, TABLE *table, int idx, bool use_order, bool reverse, bool count_examined_rows)
AccessPath *	NewRefAccessPath (THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool reverse, bool count_examined_rows)
AccessPath *	NewRefOrNullAccessPath (THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool count_examined_rows)
AccessPath *	NewEQRefAccessPath (THD *thd, TABLE *table, Index_lookup *ref, bool count_examined_rows)
AccessPath *	NewPushedJoinRefAccessPath (THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool is_unique, bool count_examined_rows)
AccessPath *	NewFullTextSearchAccessPath (THD *thd, TABLE *table, Index_lookup *ref, Item_func_match *ft_func, bool use_order, bool use_limit, bool count_examined_rows)
AccessPath *	NewConstTableAccessPath (THD *thd, TABLE *table, Index_lookup *ref, bool count_examined_rows)
AccessPath *	NewMRRAccessPath (THD *thd, TABLE *table, Index_lookup *ref, int mrr_flags)
AccessPath *	NewFollowTailAccessPath (THD *thd, TABLE *table, bool count_examined_rows)
AccessPath *	NewDynamicIndexRangeScanAccessPath (THD *thd, TABLE *table, QEP_TAB *qep_tab, bool count_examined_rows)
AccessPath *	NewMaterializedTableFunctionAccessPath (THD *thd, TABLE *table, Table_function *table_function, AccessPath *table_path)
AccessPath *	NewUnqualifiedCountAccessPath (THD *thd)
AccessPath *	NewTableValueConstructorAccessPath (const THD *thd, const JOIN *join)
AccessPath *	NewNestedLoopSemiJoinWithDuplicateRemovalAccessPath (THD *thd, AccessPath *outer, AccessPath *inner, const TABLE *table, KEY *key, size_t key_len)
AccessPath *	NewFilterAccessPath (THD *thd, AccessPath *child, Item *condition)
AccessPath *	NewSortAccessPath (THD *thd, AccessPath *child, Filesort *filesort, ORDER *order, bool count_examined_rows)
AccessPath *	NewAggregateAccessPath (THD *thd, AccessPath *child, olap_type olap)
AccessPath *	NewTemptableAggregateAccessPath (THD *thd, AccessPath *subquery_path, JOIN *join, Temp_table_param *temp_table_param, TABLE *table, AccessPath *table_path, int ref_slice)
AccessPath *	NewLimitOffsetAccessPath (THD *thd, AccessPath *child, ha_rows limit, ha_rows offset, bool count_all_rows, bool reject_multiple_rows, ha_rows *send_records_override)
AccessPath *	NewFakeSingleRowAccessPath (THD *thd, bool count_examined_rows)
AccessPath *	NewZeroRowsAccessPath (THD *thd, AccessPath *child, const char *cause)
AccessPath *	NewZeroRowsAccessPath (THD *thd, const char *cause)
AccessPath *	NewZeroRowsAggregatedAccessPath (THD *thd, const char *cause)
AccessPath *	NewStreamingAccessPath (THD *thd, AccessPath *child, JOIN *join, Temp_table_param *temp_table_param, TABLE *table, int ref_slice)
Mem_root_array< MaterializePathParameters::Operand >	SingleMaterializeQueryBlock (THD *thd, AccessPath *path, int select_number, JOIN *join, bool copy_items, Temp_table_param *temp_table_param)
AccessPath *	NewMaterializeAccessPath (THD *thd, Mem_root_array< MaterializePathParameters::Operand > operands, Mem_root_array< const AccessPath * > *invalidators, TABLE *table, AccessPath *table_path, Common_table_expr *cte, Query_expression *unit, int ref_slice, bool rematerialize, ha_rows limit_rows, bool reject_multiple_rows, MaterializePathParameters::DedupType dedup_reason=MaterializePathParameters::NO_DEDUP)
AccessPath *	NewMaterializeInformationSchemaTableAccessPath (THD *thd, AccessPath *table_path, Table_ref *table_list, Item *condition)
double	AddCost (double c1, double c2)
	Add path costs c1 and c2, but handle kUnknownCost correctly. More...
double	AddRowCount (double c1, double c2)
	Add row counts c1 and c2, but handle kUnknownRowCount correctly. More...
AccessPath *	NewAppendAccessPath (THD *thd, Mem_root_array< AppendPathParameters > *children)
AccessPath *	NewWindowAccessPath (THD *thd, AccessPath *child, Window *window, Temp_table_param *temp_table_param, int ref_slice, bool needs_buffering)
AccessPath *	NewWeedoutAccessPath (THD *thd, AccessPath *child, SJ_TMP_TABLE *weedout_table)
AccessPath *	NewRemoveDuplicatesAccessPath (THD *thd, AccessPath *child, Item **group_items, int group_items_size)
AccessPath *	NewRemoveDuplicatesOnIndexAccessPath (THD *thd, AccessPath *child, TABLE *table, KEY *key, unsigned loosescan_key_len)
AccessPath *	NewAlternativeAccessPath (THD *thd, AccessPath *child, AccessPath *table_scan_path, Index_lookup *used_ref)
AccessPath *	NewInvalidatorAccessPath (THD *thd, AccessPath *child, const char *name)
AccessPath *	NewDeleteRowsAccessPath (THD *thd, AccessPath *child, table_map delete_tables, table_map immediate_tables)
AccessPath *	NewUpdateRowsAccessPath (THD *thd, AccessPath *child, table_map delete_tables, table_map immediate_tables)
void	FindTablesToGetRowidFor (AccessPath *path)
	Modifies "path" and the paths below it so that they provide row IDs for all tables. More...
unique_ptr_destroy_only< RowIterator >	CreateIteratorFromAccessPath (THD *thd, MEM_ROOT *mem_root, AccessPath *path, JOIN *join, bool eligible_for_batch_mode)
unique_ptr_destroy_only< RowIterator >	CreateIteratorFromAccessPath (THD *thd, AccessPath *path, JOIN *join, bool eligible_for_batch_mode)
void	SetCostOnTableAccessPath (const Cost_model_server &cost_model, const POSITION *pos, bool is_after_filter, AccessPath *path)
TABLE *	GetBasicTable (const AccessPath *path)
	Return the TABLE* referred from 'path' if it is a basic access path, else a nullptr is returned. More...
table_map	GetUsedTableMap (const AccessPath *path, bool include_pruned_tables)
	Returns a map of all tables read when path or any of its children are executed. More...
Mem_root_array< TABLE * >	CollectTables (THD *thd, AccessPath *root_path)
	Find the list of all tables used by this root, stopping at materializations. More...
void	ExpandFilterAccessPaths (THD *thd, AccessPath *path, const JOIN *join, const Mem_root_array< Predicate > &predicates, unsigned num_where_predicates)
	For each access path in the (sub)tree rooted at “path”, expand any use of “filter_predicates” into newly-inserted FILTER access paths, using the given predicate list. More...
Item *	ConditionFromFilterPredicates (const Mem_root_array< Predicate > &predicates, OverflowBitset mask, int num_where_predicates)
	Extracts the Item expression from the given “filter_predicates” corresponding to the given “mask”. More...
void	ExpandSingleFilterAccessPath (THD *thd, AccessPath *path, const JOIN *join, const Mem_root_array< Predicate > &predicates, unsigned num_where_predicates)
	Like ExpandFilterAccessPaths(), but expands only the single access path at “path”. More...
table_map	GetHashJoinTables (AccessPath *path)
	Returns the tables that are part of a hash join. More...
const Mem_root_array< Item * > *	GetExtraHashJoinConditions (MEM_ROOT *mem_root, bool using_hypergraph_optimizer, const std::vector< HashJoinCondition > &equijoin_conditions, const Mem_root_array< Item * > &other_conditions)
	Get the conditions to put into the extra conditions of the HashJoinIterator. More...
void	CollectStatusVariables (THD *thd, const JOIN *top_join, const AccessPath &top_path)
	Update status variables which count how many scans of various types are used in a query plan. More...

Variables
constexpr double	kUnknownRowCount = -1.0
	To indicate that a row estimate is not yet made. More...
constexpr double	kUnknownCost = -1e12
	To indicate that a cost estimate is not yet made. More...

Function Documentation

AddCost()

double AddCost ( double  c1, double  c2  )

inline

Add path costs c1 and c2, but handle kUnknownCost correctly.

AddRowCount()

double AddRowCount ( double  c1, double  c2  )

inline

Add row counts c1 and c2, but handle kUnknownRowCount correctly.

CollectStatusVariables()

void CollectStatusVariables	(	THD *	thd,
		const JOIN *	top_join,
		const AccessPath &	top_path
	)

Update status variables which count how many scans of various types are used in a query plan.

The following status variables are updated: Select_scan, Select_full_join, Select_range, Select_full_range_join, Select_range_check. They are also stored as performance schema statement events with the same names.

In addition, the performance schema statement events NO_INDEX_USED and NO_GOOD_INDEX_USED are updated, if appropriate.

CollectTables()

Mem_root_array< TABLE * > CollectTables	(	THD *	thd,
		AccessPath *	root_path
	)

Find the list of all tables used by this root, stopping at materializations.

Used for knowing which tables to sort.

ConditionFromFilterPredicates()

Item * ConditionFromFilterPredicates	(	const Mem_root_array< Predicate > &	predicates,
		OverflowBitset	mask,
		int	num_where_predicates
	)

Extracts the Item expression from the given “filter_predicates” corresponding to the given “mask”.

CopyBasicProperties()

void CopyBasicProperties ( const AccessPath &  from, AccessPath *  to  )

inline

CreateIteratorFromAccessPath() [1/2]

unique_ptr_destroy_only< RowIterator > CreateIteratorFromAccessPath ( THD *  thd, AccessPath *  path, JOIN *  join, bool  eligible_for_batch_mode  )

inline

CreateIteratorFromAccessPath() [2/2]

unique_ptr_destroy_only< RowIterator > CreateIteratorFromAccessPath	(	THD *	thd,
		MEM_ROOT *	mem_root,
		AccessPath *	path,
		JOIN *	join,
		bool	eligible_for_batch_mode
	)

ExpandFilterAccessPaths()

void ExpandFilterAccessPaths	(	THD *	thd,
		AccessPath *	path,
		const JOIN *	join,
		const Mem_root_array< Predicate > &	predicates,
		unsigned	num_where_predicates
	)

For each access path in the (sub)tree rooted at “path”, expand any use of “filter_predicates” into newly-inserted FILTER access paths, using the given predicate list.

This is used after finding an optimal set of access paths, to normalize the tree so that the remaining consumers do not need to worry about filter_predicates and cost_before_filter.

“join” is the join that “path” is part of.

ExpandSingleFilterAccessPath()

void ExpandSingleFilterAccessPath	(	THD *	thd,
		AccessPath *	path,
		const JOIN *	join,
		const Mem_root_array< Predicate > &	predicates,
		unsigned	num_where_predicates
	)

Like ExpandFilterAccessPaths(), but expands only the single access path at “path”.

FindTablesToGetRowidFor()

void FindTablesToGetRowidFor

(

AccessPath *

path

)

Modifies "path" and the paths below it so that they provide row IDs for all tables.

This also figures out how the row IDs should be retrieved for each table in the input to the path. If the handler of the table is positioned on the correct row while reading the input, handler::position() can be called to get the row ID from the handler. However, if the input iterator returns rows without keeping the position of the underlying handlers in sync, calling handler::position() will not be able to provide the row IDs. Specifically, hash join and BKA join do not keep the underlying handlers positioned on the right row. Therefore, this function will instruct every hash join or BKA join below "path" to maintain row IDs in the join buffer, and updating handler::ref in every input table for each row they return. Then "path" does not need to call handler::position() to get it (nor should it, since calling it would overwrite the correct row ID with a stale one).

The tables on which "path" should call handler::position() are stored in a tables_to_get_rowid_for bitset in "path". For all the other tables, it can assume that handler::ref already contains the correct row ID.

FirstRowCost()

double FirstRowCost ( double  init_cost, double  total_cost, double  output_rows  )

inline

Calculate the cost of reading the first row from an access path, given estimates for init cost, total cost and the number of rows returned.

GetBasicTable()

TABLE * GetBasicTable

(

const AccessPath *

path

)

Return the TABLE* referred from 'path' if it is a basic access path, else a nullptr is returned.

Temporary tables, such as those used by sorting, aggregate and subquery materialization are not returned.

GetExtraHashJoinConditions()

const Mem_root_array< Item * > * GetExtraHashJoinConditions	(	MEM_ROOT *	mem_root,
		bool	using_hypergraph_optimizer,
		const std::vector< HashJoinCondition > &	equijoin_conditions,
		const Mem_root_array< Item * > &	other_conditions
	)

Get the conditions to put into the extra conditions of the HashJoinIterator.

This includes the non-equijoin conditions, as well as any equijoin conditions on columns that are too big to include in the hash table. (The old optimizer handles equijoin conditions on long columns elsewhere, so the last part only applies to the hypergraph optimizer.)

Parameters

mem_root	The root on which to allocate memory, if needed.
using_hypergraph_optimizer	True if using the hypergraph optimizer.
equijoin_conditions	All the equijoin conditions of the join.
other_conditions	All the non-equijoin conditions of the join.

Returns

All the conditions to evaluate as "extra conditions" in HashJoinIterator, or nullptr on OOM.

GetHashJoinTables()

table_map GetHashJoinTables

(

AccessPath *

path

)

Returns the tables that are part of a hash join.

GetUsedTableMap()

table_map GetUsedTableMap	(	const AccessPath *	path,
		bool	include_pruned_tables
	)

Returns a map of all tables read when path or any of its children are executed.

Only iterators that are part of the same query block as path are considered.

If a table is read that doesn't have a map, specifically the temporary tables made as part of materialization within the same query block, RAND_TABLE_BIT will be set as a convention and none of that access path's children will be included in the map. In this case, the caller will need to manually go in and find said access path, to ask it for its TABLE object.

If include_pruned_tables = true, tables that are hidden under a ZERO_ROWS access path (ie., pruned away due to impossible join conditions) will be included in the map. This is normally what you want, as those tables need to be included whenever you store NULL flags and the likes, but if you don't want them (perhaps to specifically check for conditions referring to pruned tables), you can set it to false.

NewAggregateAccessPath()

AccessPath * NewAggregateAccessPath ( THD *  thd, AccessPath *  child, olap_type  olap  )

inline

NewAlternativeAccessPath()

AccessPath * NewAlternativeAccessPath ( THD *  thd, AccessPath *  child, AccessPath *  table_scan_path, Index_lookup *  used_ref  )

inline

NewAppendAccessPath()

AccessPath * NewAppendAccessPath ( THD *  thd, Mem_root_array< AppendPathParameters > *  children  )

inline

NewConstTableAccessPath()

AccessPath * NewConstTableAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, bool  count_examined_rows  )

inline

NewDeleteRowsAccessPath()

AccessPath * NewDeleteRowsAccessPath	(	THD *	thd,
		AccessPath *	child,
		table_map	delete_tables,
		table_map	immediate_tables
	)

NewDynamicIndexRangeScanAccessPath()

AccessPath * NewDynamicIndexRangeScanAccessPath ( THD *  thd, TABLE *  table, QEP_TAB *  qep_tab, bool  count_examined_rows  )

inline

NewEQRefAccessPath()

AccessPath * NewEQRefAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, bool  count_examined_rows  )

inline

NewFakeSingleRowAccessPath()

AccessPath * NewFakeSingleRowAccessPath ( THD *  thd, bool  count_examined_rows  )

inline

NewFilterAccessPath()

AccessPath * NewFilterAccessPath ( THD *  thd, AccessPath *  child, Item *  condition  )

inline

NewFollowTailAccessPath()

AccessPath * NewFollowTailAccessPath ( THD *  thd, TABLE *  table, bool  count_examined_rows  )

inline

NewFullTextSearchAccessPath()

AccessPath * NewFullTextSearchAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, Item_func_match *  ft_func, bool  use_order, bool  use_limit, bool  count_examined_rows  )

inline

NewIndexScanAccessPath()

AccessPath * NewIndexScanAccessPath ( THD *  thd, TABLE *  table, int  idx, bool  use_order, bool  reverse, bool  count_examined_rows  )

inline

NewInvalidatorAccessPath()

AccessPath * NewInvalidatorAccessPath ( THD *  thd, AccessPath *  child, const char *  name  )

inline

NewLimitOffsetAccessPath()

AccessPath * NewLimitOffsetAccessPath ( THD *  thd, AccessPath *  child, ha_rows  limit, ha_rows  offset, bool  count_all_rows, bool  reject_multiple_rows, ha_rows *  send_records_override  )

inline

NewMaterializeAccessPath()

AccessPath * NewMaterializeAccessPath ( THD *  thd, Mem_root_array< MaterializePathParameters::Operand >  operands, Mem_root_array< const AccessPath * > *  invalidators, TABLE *  table, AccessPath *  table_path, Common_table_expr *  cte, Query_expression *  unit, int  ref_slice, bool  rematerialize, ha_rows  limit_rows, bool  reject_multiple_rows, MaterializePathParameters::DedupType  dedup_reason = MaterializePathParameters::NO_DEDUP  )

inline

NewMaterializedTableFunctionAccessPath()

AccessPath * NewMaterializedTableFunctionAccessPath ( THD *  thd, TABLE *  table, Table_function *  table_function, AccessPath *  table_path  )

inline

NewMaterializeInformationSchemaTableAccessPath()

AccessPath * NewMaterializeInformationSchemaTableAccessPath ( THD *  thd, AccessPath *  table_path, Table_ref *  table_list, Item *  condition  )

inline

NewMRRAccessPath()

AccessPath * NewMRRAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, int  mrr_flags  )

inline

NewNestedLoopSemiJoinWithDuplicateRemovalAccessPath()

AccessPath * NewNestedLoopSemiJoinWithDuplicateRemovalAccessPath ( THD *  thd, AccessPath *  outer, AccessPath *  inner, const TABLE *  table, KEY *  key, size_t  key_len  )

inline

NewPushedJoinRefAccessPath()

AccessPath * NewPushedJoinRefAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, bool  use_order, bool  is_unique, bool  count_examined_rows  )

inline

NewRefAccessPath()

AccessPath * NewRefAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, bool  use_order, bool  reverse, bool  count_examined_rows  )

inline

NewRefOrNullAccessPath()

AccessPath * NewRefOrNullAccessPath ( THD *  thd, TABLE *  table, Index_lookup *  ref, bool  use_order, bool  count_examined_rows  )

inline

NewRemoveDuplicatesAccessPath()

AccessPath * NewRemoveDuplicatesAccessPath ( THD *  thd, AccessPath *  child, Item **  group_items, int  group_items_size  )

inline

NewRemoveDuplicatesOnIndexAccessPath()

AccessPath * NewRemoveDuplicatesOnIndexAccessPath ( THD *  thd, AccessPath *  child, TABLE *  table, KEY *  key, unsigned  loosescan_key_len  )

inline

NewSampleScanAccessPath()

AccessPath * NewSampleScanAccessPath ( THD *  thd, TABLE *  table, double  sampling_percentage, bool  count_examined_rows  )

inline

NewSortAccessPath()

AccessPath * NewSortAccessPath	(	THD *	thd,
		AccessPath *	child,
		Filesort *	filesort,
		ORDER *	order,
		bool	count_examined_rows
	)

NewStreamingAccessPath()

AccessPath * NewStreamingAccessPath ( THD *  thd, AccessPath *  child, JOIN *  join, Temp_table_param *  temp_table_param, TABLE *  table, int  ref_slice  )

inline

NewTableScanAccessPath()

AccessPath * NewTableScanAccessPath ( THD *  thd, TABLE *  table, bool  count_examined_rows  )

inline

NewTableValueConstructorAccessPath()

AccessPath * NewTableValueConstructorAccessPath	(	const THD *	thd,
		const JOIN *	join
	)

NewTemptableAggregateAccessPath()

AccessPath * NewTemptableAggregateAccessPath ( THD *  thd, AccessPath *  subquery_path, JOIN *  join, Temp_table_param *  temp_table_param, TABLE *  table, AccessPath *  table_path, int  ref_slice  )

inline

NewUnqualifiedCountAccessPath()

AccessPath * NewUnqualifiedCountAccessPath ( THD *  thd )

inline

NewUpdateRowsAccessPath()

AccessPath * NewUpdateRowsAccessPath	(	THD *	thd,
		AccessPath *	child,
		table_map	delete_tables,
		table_map	immediate_tables
	)

NewWeedoutAccessPath()

AccessPath * NewWeedoutAccessPath ( THD *  thd, AccessPath *  child, SJ_TMP_TABLE *  weedout_table  )

inline

NewWindowAccessPath()

AccessPath * NewWindowAccessPath ( THD *  thd, AccessPath *  child, Window *  window, Temp_table_param *  temp_table_param, int  ref_slice, bool  needs_buffering  )

inline

NewZeroRowsAccessPath() [1/2]

AccessPath * NewZeroRowsAccessPath ( THD *  thd, AccessPath *  child, const char *  cause  )

inline

NewZeroRowsAccessPath() [2/2]

AccessPath * NewZeroRowsAccessPath ( THD *  thd, const char *  cause  )

inline

NewZeroRowsAggregatedAccessPath()

AccessPath * NewZeroRowsAggregatedAccessPath ( THD *  thd, const char *  cause  )

inline

SingleMaterializeQueryBlock()

Mem_root_array< MaterializePathParameters::Operand > SingleMaterializeQueryBlock ( THD *  thd, AccessPath *  path, int  select_number, JOIN *  join, bool  copy_items, Temp_table_param *  temp_table_param  )

inline

Variable Documentation

kUnknownCost

constexpr double kUnknownCost = -1e12

inlineconstexpr

To indicate that a cost estimate is not yet made.

We use a large negative value to avoid getting a positive result if we by mistake add this to a real (positive) cost.

kUnknownRowCount

constexpr double kUnknownRowCount = -1.0

inlineconstexpr

To indicate that a row estimate is not yet made.