Optimize_table_order Class Reference

This class determines the optimal join order for tables within a basic query block, ie a query specification clause, possibly extended with semi-joined tables from embedded subqueries. More...

#include <sql_planner.h>

Public Member Functions
	Optimize_table_order (THD *thd_arg, JOIN *join_arg, Table_ref *sjm_nest_arg)
	~Optimize_table_order ()=default
bool	choose_table_order ()
	Entry point to table join order optimization. More...
void	recalculate_lateral_deps (uint first_tab_no)
	Set join->deps_of_remaining_lateral_derived_tables to the set of lateral dependencies of the tables in the suffix of the join plan from 'tab_no' and on. More...
void	recalculate_lateral_deps_incrementally (uint first_tab_no)
	Update join->deps_of_remaining_lateral_derived_tables after adding JOIN_TAB first_tab_no-1 to the plan. More...

Private Member Functions
Key_use *	find_best_ref (const JOIN_TAB *tab, const table_map remaining_tables, const uint idx, const double prefix_rowcount, bool *found_condition, table_map *ref_depends_map, uint *used_key_parts)
	Find the best index to do 'ref' access on for a table. More...
double	calculate_scan_cost (const JOIN_TAB *tab, const uint idx, const Key_use *best_ref, const double prefix_rowcount, const bool found_condition, const bool disable_jbuf, double *rows_after_filtering, Opt_trace_object *trace_access_scan)
	Calculate the cost of range/table/index scanning table 'tab'. More...
void	best_access_path (JOIN_TAB *tab, const table_map remaining_tables, const uint idx, bool disable_jbuf, const double prefix_rowcount, POSITION *pos)
	Find the best access path for an extension of a partial execution plan and add this path to the plan. More...
bool	semijoin_loosescan_fill_driving_table_position (const JOIN_TAB *s, table_map remaining_tables, uint idx, double prefix_rowcount, POSITION *loose_scan_pos)
	Fills a POSITION object of the driving table of a semi-join LooseScan range, with the cheapest access path. More...
bool	check_interleaving_with_nj (JOIN_TAB *next_tab)
	Check interleaving with an inner tables of an outer join for extension table. More...
void	advance_sj_state (table_map remaining_tables, const JOIN_TAB *tab, uint idx)
	Do semi-join optimization step after we've added a new tab to join prefix. More...
void	backout_nj_state (const table_map remaining_tables, const JOIN_TAB *tab)
	Nested joins perspective: Remove the last table from the join order. More...
void	optimize_straight_join (table_map join_tables)
	Select the best ways to access the tables in a query without reordering them. More...
bool	greedy_search (table_map remaining_tables)
	Find a good, possibly optimal, query execution plan (QEP) by a greedy search. More...
bool	best_extension_by_limited_search (table_map remaining_tables, uint idx, uint current_search_depth)
	Find a good, possibly optimal, query execution plan (QEP) by a possibly exhaustive search. More...
table_map	eq_ref_extension_by_limited_search (table_map remaining_tables, uint idx, uint current_search_depth)
	Heuristic utility used by best_extension_by_limited_search(). More...
bool	consider_plan (uint idx, Opt_trace_object *trace_obj)
	Cost calculation of another (partial-)QEP has been completed. More...
bool	fix_semijoin_strategies ()
	Fix semi-join strategies for the picked join order. More...
bool	semijoin_firstmatch_loosescan_access_paths (uint first_tab, uint last_tab, table_map remaining_tables, bool loosescan, double *newcount, double *newcost)
	Find best access paths for semi-join FirstMatch or LooseScan strategy and calculate rowcount and cost based on these. More...
void	semijoin_mat_scan_access_paths (uint last_inner_tab, uint last_outer_tab, table_map remaining_tables, Table_ref *sjm_nest, double *newcount, double *newcost)
	Find best access paths for semi-join MaterializeScan strategy and calculate rowcount and cost based on these. More...
void	semijoin_mat_lookup_access_paths (uint last_inner, Table_ref *sjm_nest, double *newcount, double *newcost)
	Find best access paths for semi-join MaterializeLookup strategy. More...
void	semijoin_dupsweedout_access_paths (uint first_tab, uint last_tab, double *newcount, double *newcost)
	Find best access paths for semi-join DuplicateWeedout strategy and calculate rowcount and cost based on these. More...
double	lateral_derived_cost (const JOIN_TAB *tab, const uint idx, const double prefix_rowcount, const Cost_model_server *cost_model)
	If table is a lateral derived table, calculates the "cost of materialization", which is the cost of a single materialization (available in the DT's underlying JOIN final plan) multiplied by the number of rows output by the last-in-plan table which DT references (available in a POSITION structure). More...
table_map	calculate_lateral_deps_of_final_plan (uint tab_no) const
	Calculate the lateral dependencies of the suffix of JOIN_TABs from tab_no to join->tables-1 in the final join plan, i.e. More...
bool	plan_has_duplicate_tabs () const
	Check if any Table_ref appears twice in the plan (which is an error). More...

Static Private Member Functions
static uint	determine_search_depth (uint search_depth, uint table_count)
	Heuristic procedure to automatically guess a reasonable degree of exhaustiveness for the greedy search procedure. More...

Private Attributes
THD *const	thd
JOIN *const	join
const uint	search_depth
const uint	prune_level
nested_join_map	cur_embedding_map
	Bitmap of all join nests embedding the last table appended to the current partial join. More...
const Table_ref *const	emb_sjm_nest
	If non-NULL, we are optimizing a materialized semi-join nest. More...
const table_map	excluded_tables
	When calculating a plan for a materialized semi-join nest, best_access_path() needs to know not only the remaining tables within the semi-join nest, but also all tables outside of this nest, because there may be key references between the semi-join nest and the outside tables that should not be considered when materializing the semi-join nest. More...
const bool	has_sj
bool	test_all_ref_keys
	If true, find_best_ref() must go through all keys, no shortcutting allowed. More...
bool	found_plan_with_allowed_sj
	True if we found a complete plan using only allowed semijoin strategies. More...
bool	got_final_plan
	False/true at start/end of choose_table_order(). More...
bool	use_best_so_far {false}
	Set true when we have decided to return with a "good enough" plan. More...

Detailed Description

This class determines the optimal join order for tables within a basic query block, ie a query specification clause, possibly extended with semi-joined tables from embedded subqueries.

This class takes as prerequisite a join class where all dependencies among tables have been sorted out, all possible access paths have been sorted out, and all statistics information has been filled in.

The class has a sole public function that will calculate the most optimal plan based on the inputs and the environment, such as prune level and greedy optimizer search depth. For more information, see the function headers for the private functions greedy_search(), best_extension_by_limited_search() and eq_ref_extension_by_limited_search().

Constructor & Destructor Documentation

~Optimize_table_order()

Optimize_table_order::~Optimize_table_order ( )

default

Member Data Documentation

cur_embedding_map

nested_join_map Optimize_table_order::cur_embedding_map

private

Bitmap of all join nests embedding the last table appended to the current partial join.

emb_sjm_nest

const Table_ref* const Optimize_table_order::emb_sjm_nest

private

If non-NULL, we are optimizing a materialized semi-join nest.

If NULL, we are optimizing a complete join plan.

excluded_tables

const table_map Optimize_table_order::excluded_tables

private

When calculating a plan for a materialized semi-join nest, best_access_path() needs to know not only the remaining tables within the semi-join nest, but also all tables outside of this nest, because there may be key references between the semi-join nest and the outside tables that should not be considered when materializing the semi-join nest.

excluded_tables tracks these tables.

found_plan_with_allowed_sj

bool Optimize_table_order::found_plan_with_allowed_sj

private

True if we found a complete plan using only allowed semijoin strategies.

got_final_plan

bool Optimize_table_order::got_final_plan

private

False/true at start/end of choose_table_order().

Helps member functions know if current plan is in join->positions or join->best_positions.

has_sj

const bool Optimize_table_order::has_sj

private

join

JOIN* const Optimize_table_order::join

private

prune_level

const uint Optimize_table_order::prune_level

private

search_depth

const uint Optimize_table_order::search_depth

private

test_all_ref_keys

bool Optimize_table_order::test_all_ref_keys

private

If true, find_best_ref() must go through all keys, no shortcutting allowed.

thd

THD* const Optimize_table_order::thd

private

use_best_so_far

bool Optimize_table_order::use_best_so_far {false}

private

Set true when we have decided to return with a "good enough" plan.

---

The documentation for this class was generated from the following files:

• sql/sql_planner.h
• sql/sql_planner.cc