access_path.h File Reference

#include <assert.h>
#include <stdint.h>
#include <string>
#include <type_traits>
#include <vector>
#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_optimizer/relational_expression.h"
#include "sql/join_type.h"
#include "sql/mem_root_array.h"
#include "sql/sql_array.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
void	CopyBasicProperties (const AccessPath &from, AccessPath *to)
AccessPath *	NewTableScanAccessPath (THD *thd, TABLE *table, 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 (THD *thd)
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, bool rollup)
AccessPath *	NewTemptableAggregateAccessPath (THD *thd, AccessPath *subquery_path, 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::QueryBlock >	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::QueryBlock > query_blocks, 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)
AccessPath *	NewMaterializeInformationSchemaTableAccessPath (THD *thd, AccessPath *table_path, Table_ref *table_list, Item *condition)
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...
bool	FinalizeMaterializedSubqueries (THD *thd, JOIN *join, AccessPath *path)
	If the path is a FILTER path marked that subqueries are to be materialized, do so. 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...

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

Function Documentation

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”.

FinalizeMaterializedSubqueries()

bool FinalizeMaterializedSubqueries	(	THD *	thd,
		JOIN *	join,
		AccessPath *	path
	)

If the path is a FILTER path marked that subqueries are to be materialized, do so.

If not, do nothing.

It is important that this is not called until the entire plan is ready; not just when planning a single query block. The reason is that a query block A with materializable subqueries may itself be part of a materializable subquery B, so if one calls this when planning A, the subqueries in A will irrevocably be materialized, even if that is not the optimal plan given B. Thus, this is done when creating iterators.

FindTablesToGetRowidFor()

void FindTablesToGetRowidFor

(

AccessPath *

path

)

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

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.

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, bool  rollup  )

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::QueryBlock >  query_blocks, 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  )

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

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 ( THD *  thd )

inline

NewTemptableAggregateAccessPath()

AccessPath * NewTemptableAggregateAccessPath ( THD *  thd, AccessPath *  subquery_path, 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::QueryBlock > SingleMaterializeQueryBlock ( THD *  thd, AccessPath *  path, int  select_number, JOIN *  join, bool  copy_items, Temp_table_param *  temp_table_param  )

inline

Variable Documentation

kUnknownRowCount

constexpr double kUnknownRowCount = -1.0

constexpr

To indicate that a row estimate is not yet made.