access_path.cc File Reference

#include "sql/join_optimizer/access_path.h"
#include "my_base.h"
#include "sql/filesort.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/item_sum.h"
#include "sql/iterators/basic_row_iterators.h"
#include "sql/iterators/bka_iterator.h"
#include "sql/iterators/composite_iterators.h"
#include "sql/iterators/delete_rows_iterator.h"
#include "sql/iterators/hash_join_iterator.h"
#include "sql/iterators/ref_row_iterators.h"
#include "sql/iterators/sorting_iterator.h"
#include "sql/iterators/timing_iterator.h"
#include "sql/iterators/window_iterators.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/cost_model.h"
#include "sql/join_optimizer/estimate_selectivity.h"
#include "sql/join_optimizer/overflow_bitset.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/join_optimizer/walk_access_paths.h"
#include "sql/mem_root_array.h"
#include "sql/range_optimizer/geometry_index_range_scan.h"
#include "sql/range_optimizer/group_index_skip_scan.h"
#include "sql/range_optimizer/group_index_skip_scan_plan.h"
#include "sql/range_optimizer/index_merge.h"
#include "sql/range_optimizer/index_range_scan.h"
#include "sql/range_optimizer/index_skip_scan.h"
#include "sql/range_optimizer/index_skip_scan_plan.h"
#include "sql/range_optimizer/range_optimizer.h"
#include "sql/range_optimizer/reverse_index_range_scan.h"
#include "sql/range_optimizer/rowid_ordered_retrieval.h"
#include "sql/sql_optimizer.h"
#include "sql/sql_update.h"
#include "sql/table.h"
#include <vector>

Classes
struct	anonymous_namespace{access_path.cc}::IteratorToBeCreated

Namespaces
namespace	anonymous_namespace{access_path.cc}

Functions
AccessPath *	NewSortAccessPath (THD *thd, AccessPath *child, Filesort *filesort, ORDER *order, bool count_examined_rows)
AccessPath *	NewDeleteRowsAccessPath (THD *thd, AccessPath *child, table_map delete_tables, table_map immediate_tables)
AccessPath *	NewUpdateRowsAccessPath (THD *thd, AccessPath *child, table_map update_tables, table_map immediate_tables)
static AccessPath *	FindSingleAccessPathOfType (AccessPath *path, AccessPath::Type type)
static RowIterator *	FindSingleIteratorOfType (AccessPath *path, AccessPath::Type type)
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...
static Prealloced_array< TABLE *, 4 >	GetUsedTables (AccessPath *child, bool include_pruned_tables)
Mem_root_array< TABLE * >	CollectTables (THD *thd, AccessPath *root_path)
	Find the list of all tables used by this root, stopping at materializations. More...
static table_map	GetNullableEqRefTables (const AccessPath *root_path)
	Get the tables that are accessed by EQ_REF and can be on the inner side of an outer join. More...
bool	ShouldEnableBatchMode (AccessPath *path)
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...
void	anonymous_namespace{access_path.cc}::SetupJobsForChildren (MEM_ROOT *mem_root, AccessPath *child, JOIN *join, bool eligible_for_batch_mode, IteratorToBeCreated *job, Mem_root_array< IteratorToBeCreated > *todo)
void	anonymous_namespace{access_path.cc}::SetupJobsForChildren (MEM_ROOT *mem_root, AccessPath *outer, AccessPath *inner, JOIN *join, bool inner_eligible_for_batch_mode, IteratorToBeCreated *job, Mem_root_array< IteratorToBeCreated > *todo)
unique_ptr_destroy_only< RowIterator >	CreateIteratorFromAccessPath (THD *thd, MEM_ROOT *mem_root, AccessPath *top_path, JOIN *top_join, bool top_eligible_for_batch_mode)
void	FindTablesToGetRowidFor (AccessPath *path)
	Modifies "path" and the paths below it so that they provide row IDs for all tables. More...
static void	MoveFilterPredicatesIntoHashJoinCondition (THD *thd, AccessPath *path, const Mem_root_array< Predicate > &predicates, int num_where_predicates)
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...
void	ExpandFilterAccessPaths (THD *thd, AccessPath *path_arg, 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...
table_map	GetHashJoinTables (AccessPath *path)
	Returns the tables that are part of a hash join. 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”.

CreateIteratorFromAccessPath()

unique_ptr_destroy_only< RowIterator > CreateIteratorFromAccessPath	(	THD *	thd,
		MEM_ROOT *	mem_root,
		AccessPath *	top_path,
		JOIN *	top_join,
		bool	top_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.

FindSingleAccessPathOfType()

static AccessPath * FindSingleAccessPathOfType ( AccessPath *  path, AccessPath::Type  type  )

static

FindSingleIteratorOfType()

static RowIterator * FindSingleIteratorOfType ( AccessPath *  path, AccessPath::Type  type  )

static

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.

GetNullableEqRefTables()

static table_map GetNullableEqRefTables ( const AccessPath *  root_path )

static

Get the tables that are accessed by EQ_REF and can be on the inner side of an outer join.

These need some extra care in AggregateIterator when handling NULL-complemented rows, so that the cache in EQRefIterator is not disturbed by AggregateIterator's switching between groups.

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.

GetUsedTables()

static Prealloced_array< TABLE *, 4 > GetUsedTables ( AccessPath *  child, bool  include_pruned_tables  )

static

MoveFilterPredicatesIntoHashJoinCondition()

static void MoveFilterPredicatesIntoHashJoinCondition ( THD *  thd, AccessPath *  path, const Mem_root_array< Predicate > &  predicates, int  num_where_predicates  )

static

NewDeleteRowsAccessPath()

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

NewSortAccessPath()

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

NewUpdateRowsAccessPath()

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

ShouldEnableBatchMode()

bool ShouldEnableBatchMode

(

AccessPath *

path

)