MySQL  8.0.27
Source Code Documentation
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_LIST *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_usefind_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_LIST *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_LIST *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_LIST 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_LIST *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_LIST* 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: