MySQL 9.0.0
Source Code Documentation File Reference
#include "sql/join_optimizer/make_join_hypergraph.h"
#include <assert.h>
#include <sys/types.h>
#include <algorithm>
#include <array>
#include <bit>
#include <iterator>
#include <numeric>
#include <ostream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#include "mem_root_deque.h"
#include "my_alloc.h"
#include "my_bitmap.h"
#include "my_inttypes.h"
#include "my_table_map.h"
#include "mysql/components/services/bits/psi_bits.h"
#include "prealloced_array.h"
#include "sql/current_thd.h"
#include "sql/field.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/common_subexpression_elimination.h"
#include "sql/join_optimizer/cost_model.h"
#include "sql/join_optimizer/estimate_selectivity.h"
#include "sql/join_optimizer/find_contained_subqueries.h"
#include "sql/join_optimizer/hypergraph.h"
#include "sql/join_optimizer/optimizer_trace.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/join_optimizer/subgraph_enumeration.h"
#include "sql/nested_join.h"
#include "sql/sql_class.h"
#include "sql/sql_const.h"
#include "sql/sql_executor.h"
#include "sql/sql_lex.h"
#include "sql/sql_list.h"
#include "sql/sql_optimizer.h"
#include "sql/table.h"
#include "sql/table_function.h"
#include "template_utils.h"


namespace  anonymous_namespace{}


enum class  anonymous_namespace{}::AssociativeRewritesAllowed { anonymous_namespace{}::ANY , anonymous_namespace{}::RIGHT_ONLY , anonymous_namespace{}::LEFT_ONLY }


RelationalExpressionanonymous_namespace{}::MakeRelationalExpressionFromJoinList (THD *thd, const Query_block *query_block, const mem_root_deque< Table_ref * > &join_list_arg, bool toplevel)
 Convert the Query_block's join lists into a RelationalExpression, ie., a join tree with tables at the leaves. More...
bool anonymous_namespace{}::EarlyNormalizeConditions (THD *thd, const RelationalExpression *join, Mem_root_array< Item * > *conditions, bool *always_false)
 Do some equality and constant propagation, conversion/folding work needed for correctness and performance. More...
bool anonymous_namespace{}::IsMultipleEquals (const Item *cond)
Item_func_eqanonymous_namespace{}::MakeEqItem (Item *a, Item *b, Item_multi_eq *source_multiple_equality)
int anonymous_namespace{}::CountTablesInEquiJoinCondition (const Item *cond)
 Helper function for ReorderConditions(), which counts how many tables are referenced by an equijoin condition. More...
void anonymous_namespace{}::ReorderConditions (Mem_root_array< Item * > *condition_parts)
 Reorders the predicates in such a way that equalities are placed ahead of other types of predicates. More...
void anonymous_namespace{}::ExpandSameTableFromMultipleEquals (Item_multi_eq *equal, table_map tables_in_subtree, List< Item > *eq_items)
 For a multiple equality, split out any conditions that refer to the same table, without touching the multi-equality; e.g. More...
Itemanonymous_namespace{}::EarlyExpandMultipleEquals (Item *condition, table_map tables_in_subtree)
 Expand multiple equalities that can (and should) be expanded before join pushdown. More...
RelationalExpressionanonymous_namespace{}::MakeRelationalExpression (THD *thd, const Query_block *query_block, const Table_ref *tl)
void anonymous_namespace{}::CreateInnerJoinFromChildList (Mem_root_array< RelationalExpression * > children, RelationalExpression *expr)
 Convert a multi-join into a simple inner join. More...
void anonymous_namespace{}::FlattenInnerJoins (RelationalExpression *expr)
 Find all inner joins under “expr” without a join condition, and convert them to a flattened join (MULTI_INNER_JOIN). More...
void anonymous_namespace{}::UnflattenInnerJoins (RelationalExpression *expr)
 The opposite of FlattenInnerJoins(); converts all flattened joins to a series of (right-deep) binary joins. More...
RelationalExpressionanonymous_namespace{}::PartiallyUnflattenJoinForCondition (table_map used_tables, RelationalExpression *expr)
 For the given flattened join (multi-join), pull out (only) the parts we need to push the given condition, and make a binary join for it. More...
string anonymous_namespace{}::PrintRelationalExpression (RelationalExpression *expr, int level)
bool anonymous_namespace{}::IsNullRejecting (const RelationalExpression &expr, table_map tables)
bool anonymous_namespace{}::IsInnerJoin (RelationalExpression::Type type)
bool anonymous_namespace{}::OperatorsAreAssociative (const RelationalExpression &a, const RelationalExpression &b)
bool anonymous_namespace{}::OperatorsAreLeftAsscom (const RelationalExpression &a, const RelationalExpression &b)
bool anonymous_namespace{}::OperatorsAreRightAsscom (const RelationalExpression &a, const RelationalExpression &b)
table_map anonymous_namespace{}::UsedTablesForCondition (const RelationalExpression &expr)
 Find a bitmap of used tables for all conditions on <expr>. More...
table_map anonymous_namespace{}::CertainlyUsedTablesForCondition (const RelationalExpression &expr)
 Like UsedTablesForCondition(), but multiple equalities set no bits unless they're certain, i.e., cannot be avoided no matter how we break up the multiple equality. More...
bool anonymous_namespace{}::IsCandidateForCycle (RelationalExpression *expr, Item *cond, const CompanionSetCollection &companion_collection)
 Check whether we are allowed to make an extra join edge with the given condition, instead of pushing the condition onto the given point in the join tree (which we have presumably found out that we don't want). More...
bool anonymous_namespace{}::ComesFromMultipleEquality (Item *item, Item_multi_eq *equal)
int anonymous_namespace{}::FindSourceMultipleEquality (Item *item, const Mem_root_array< Item_multi_eq * > &equals)
bool anonymous_namespace{}::MultipleEqualityAlreadyExistsOnJoin (Item_multi_eq *equal, const RelationalExpression &expr)
bool anonymous_namespace{}::AlreadyExistsOnJoin (Item *cond, const RelationalExpression &expr)
bool anonymous_namespace{}::IsBadJoinForCondition (const RelationalExpression &expr, Item *cond)
 Returns whether adding “cond” to the given join would unduly enlarge the number of tables it references, or create a degenerate join. More...
void anonymous_namespace{}::RotateRight (RelationalExpression *op)
 Applies the following rewrite on <op>: More...
void anonymous_namespace{}::RotateLeft (RelationalExpression *op)
 Opposite of RotateRight; that is: More...
Item_func_eqanonymous_namespace{}::ConcretizeMultipleEquals (Item_multi_eq *cond, const RelationalExpression &expr)
 From “cond”, create exactly one simple equality that will connect the left and right sides of “expr”. More...
template<class T >
static void anonymous_namespace{}::FullyConcretizeMultipleEquals (Item_multi_eq *cond, table_map allowed_tables, T *result)
 From “cond”, create exactly as many simple equalities that are needed to connect all tables in “allowed_tables”. More...
Itemanonymous_namespace{}::CanonicalizeCondition (Item *condition, table_map visible_tables, table_map all_tables)
 Finalize a condition (join condition or WHERE predicate); resolve any remaining multiple equalities. More...
Mem_root_array< Item * > anonymous_namespace{}::ResplitConditions (THD *thd, const Mem_root_array< Item * > &conditions)
bool anonymous_namespace{}::CanonicalizeConditions (THD *thd, table_map visible_tables, table_map all_tables, Mem_root_array< Item * > *conditions)
bool anonymous_namespace{}::AddJoinConditionPossiblyWithRewrite (THD *thd, RelationalExpression *expr, Item *cond, AssociativeRewritesAllowed allowed, bool used_commutativity, bool *need_flatten)
 Add “cond” as a join condition to “expr”, but if it would enlarge the set of referenced tables, try to rewrite the join tree using associativity (either left or right) to be able to put the condition on a more favorable node. More...
void anonymous_namespace{}::PushDownCondition (THD *thd, Item *cond, RelationalExpression *expr, bool is_join_condition_for_expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges, Mem_root_array< Item * > *remaining_parts)
 Try to push down the condition “cond” down in the join tree given by “expr”, as far as possible. More...
void anonymous_namespace{}::PushDownToSargableCondition (Item *cond, RelationalExpression *expr, bool is_join_condition_for_expr)
 Try to push down conditions (like PushDownCondition()), but with the intent of pushing join conditions down to sargable conditions on tables. More...
Mem_root_array< Item * > anonymous_namespace{}::PushDownAsMuchAsPossible (THD *thd, Mem_root_array< Item * > conditions, RelationalExpression *expr, bool is_join_condition_for_expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges)
 Push down as many of the conditions in “conditions” as we can, into the join tree under “expr”. More...
void anonymous_namespace{}::PushDownJoinConditions (THD *thd, RelationalExpression *expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges)
 For each condition posted as a join condition on “expr”, try to push all of them further down the tree, as far as we can; then recurse to the child nodes, if any. More...
void anonymous_namespace{}::PushDownJoinConditionsForSargable (THD *thd, RelationalExpression *expr)
 Similar to PushDownJoinConditions(), but for push of sargable conditions (see PushDownJoinConditionsForSargable()). More...
void anonymous_namespace{}::LateConcretizeMultipleEqualities (THD *thd, RelationalExpression *expr)
 Do a final pass of unexpanded (and non-degenerate) multiple equalities on join conditions, deciding on what equalities to concretize them into right before pushing join conditions to sargable predicates. More...
table_map anonymous_namespace{}::FindNullGuaranteedTables (const RelationalExpression *expr)
void anonymous_namespace{}::ClearImpossibleJoinConditions (RelationalExpression *expr)
bool anonymous_namespace{}::ShouldCompleteMeshForCondition (Item_multi_eq *item_equal, const CompanionSetCollection &companion_collection)
 Find out whether we should create mesh edges (all-to-all) for this multiple equality. More...
void anonymous_namespace{}::ExtractCycleMultipleEqualities (const Mem_root_array< Item * > &conditions, const CompanionSetCollection &companion_collection, Mem_root_array< Item_multi_eq * > *multiple_equalities)
void anonymous_namespace{}::ExtractCycleMultipleEqualitiesFromJoinConditions (const RelationalExpression *expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item_multi_eq * > *multiple_equalities)
bool anonymous_namespace{}::CanonicalizeJoinConditions (THD *thd, RelationalExpression *expr)
 Similar to work done in JOIN::finalize_table_conditions() in the old optimizer. More...
void anonymous_namespace{}::MakeHashJoinConditions (THD *thd, RelationalExpression *expr)
 For all join conditions on “expr”, go through and figure out which ones are equijoin conditions, ie., suitable for hash join. More...
void anonymous_namespace{}::FindConditionsUsedTables (THD *thd, RelationalExpression *expr)
void anonymous_namespace{}::CSEConditions (THD *thd, Mem_root_array< Item * > *conditions)
 Run simple CSE on all conditions (see CommonSubexpressionElimination()). More...
Itemanonymous_namespace{}::GetSubstitutionConst (Item_field *item, Item_func *parent_func)
 Find (via a multiple equality) and return a constant that should replace "item". More...
Itemanonymous_namespace{}::PropagateConstants (Item *cond)
 Replace fields with constants in "cond". More...
Item_fieldanonymous_namespace{}::GetSubstitutionField (Item_field *item, Item_func *parent, table_map allowed_tables)
 Find (via a multiple equality) a field that should replace "item". More...
Itemanonymous_namespace{}::PropagateEqualities (Item *cond, const RelationalExpression *join)
string anonymous_namespace{}::PrintJoinList (const mem_root_deque< Table_ref * > &join_list, int level)
table_map anonymous_namespace{}::FindTESForCondition (table_map used_tables, const RelationalExpression *expr)
 For a condition with the SES (Syntactic Eligibility Set) “used_tables”, find all relations in or under “expr” that are part of the condition's TES (Total Eligibility Set). More...
string PrintDottyHypergraph (const JoinHypergraph &graph)
 For the given hypergraph, make a textual representation in the form of a dotty graph. More...
size_t EstimateHashJoinKeyWidth (const RelationalExpression *expr)
 Estimates the size of the hash join keys generated from the equi-join predicates in "expr". More...
table_map anonymous_namespace{}::IntersectIfNotDegenerate (table_map used_tables, table_map available_tables)
NodeMap anonymous_namespace{}::AbsorbConflictRulesIntoTES (NodeMap total_eligibility_set, Mem_root_array< ConflictRule > *conflict_rules)
 When we have the conflict rules, we want to fold them into the hyperedge we are about to create. More...
Hyperedge anonymous_namespace{}::FindHyperedgeAndJoinConflicts (THD *thd, NodeMap used_nodes, RelationalExpression *expr, const JoinHypergraph *graph)
 For the join operator in “expr”, build a hyperedge that encapsulates its reordering conditions as completely as possible. More...
size_t anonymous_namespace{}::EstimateRowWidthForJoin (const JoinHypergraph &graph, const RelationalExpression *expr)
void anonymous_namespace{}::SortPredicates (Predicate *begin, Predicate *end)
 Sorts the given range of predicates so that the most selective and least expensive predicates come first, and the less selective and more expensive ones come last. More...
int anonymous_namespace{}::AddPredicate (THD *thd, Item *condition, bool was_join_condition, int source_multiple_equality_idx, const RelationalExpression *root, const CompanionSetCollection *companion_collection, JoinHypergraph *graph)
 Add the given predicate to the list of WHERE predicates, doing some bookkeeping that such predicates need. More...
bool anonymous_namespace{}::AreNodesConnected (const Hypergraph &graph, int source, int destination, int forbidden_edge_idx, NodeMap *seen_nodes)
 Return whether we can find a path from “source” to “destination”, without using forbidden_edge_idx. More...
bool anonymous_namespace{}::IsPartOfCycle (const JoinHypergraph *graph, int edge_idx)
 Returns whether the given edge is part of a graph cycle; if so, its join condition might not actually get evaluated as part of the regular structure, and we need to take special precautions (make backup WHERE conditions for them). More...
void anonymous_namespace{}::AddCycleEdges (THD *thd, const Mem_root_array< Item * > &cycle_inducing_edges, CompanionSetCollection &companion_collection, JoinHypergraph *graph)
 For each of the given join conditions, add a cycle-inducing edge to the hypergraph. More...
void anonymous_namespace{}::PromoteCycleJoinPredicates (THD *thd, const RelationalExpression *root, const Mem_root_array< Item_multi_eq * > &multiple_equalities, const CompanionSetCollection &companion_collection, JoinHypergraph *graph)
 Promote join predicates that became part of (newly-formed) cycles to WHERE predicates. More...
void MakeJoinGraphFromRelationalExpression (THD *thd, RelationalExpression *expr, JoinHypergraph *graph)
 Convert a join rooted at “expr” into a join hypergraph that encapsulates the constraints given by the relational expressions (e.g. More...
NodeMap GetNodeMapFromTableMap (table_map map, const array< int, MAX_TABLES > &table_num_to_node_num)
void anonymous_namespace{}::AddMultipleEqualityPredicate (THD *thd, CompanionSetCollection &companion_collection, Item_multi_eq *item_equal, Item_field *left_field, int left_table_idx, Item_field *right_field, int right_table_idx, double selectivity, JoinHypergraph *graph)
void anonymous_namespace{}::CompleteFullMeshForMultipleEqualities (THD *thd, const Mem_root_array< Item_multi_eq * > &multiple_equalities, CompanionSetCollection &companion_collection, JoinHypergraph *graph)
 For each relevant multiple equality, add edges so that there are direct connections between all the involved tables (full mesh). More...
table_map anonymous_namespace{}::GetTablesInnerToOuterJoinOrAntiJoin (const RelationalExpression *expr)
 Returns a map of all tables that are on the inner side of some outer join or antijoin. More...
bool anonymous_namespace{}::ExpandMultipleEqualsForSingleTable (Item_multi_eq *equal, Mem_root_array< Item * > *conditions)
 Fully expand a multiple equality for a single table as simple equalities and append each equality to the array of conditions. More...
bool anonymous_namespace{}::ExtractWhereConditionsForSingleTable (THD *thd, Item *condition, Mem_root_array< Item * > *conditions, bool *where_is_always_false)
 Extract all WHERE conditions in a single-table query. More...
bool anonymous_namespace{}::MakeSingleTableHypergraph (THD *thd, const Query_block *query_block, JoinHypergraph *graph, bool *where_is_always_false)
 Fast path for MakeJoinHypergraph() when the query accesses a single table or no table. More...
void anonymous_namespace{}::FindLateralDependencies (JoinHypergraph *graph)
bool MakeJoinHypergraph (THD *thd, JoinHypergraph *graph, bool *where_is_always_false)
 Make a join hypergraph from the query block given by “graph->query_block”, converting from MySQL's join list structures to the ones expected by the hypergraph join optimizer. More...
table_map GetVisibleTables (const RelationalExpression *expr)

Function Documentation

◆ EstimateHashJoinKeyWidth()

size_t EstimateHashJoinKeyWidth ( const RelationalExpression expr)

Estimates the size of the hash join keys generated from the equi-join predicates in "expr".

◆ GetNodeMapFromTableMap()

NodeMap GetNodeMapFromTableMap ( table_map  map,
const array< int, MAX_TABLES > &  table_num_to_node_num 

◆ GetVisibleTables()

table_map GetVisibleTables ( const RelationalExpression expr)

◆ MakeJoinGraphFromRelationalExpression()

void MakeJoinGraphFromRelationalExpression ( THD thd,
RelationalExpression expr,
JoinHypergraph graph 

Convert a join rooted at “expr” into a join hypergraph that encapsulates the constraints given by the relational expressions (e.g.

inner joins are more freely reorderable than outer joins).

The function in itself only does some bookkeeping around node bitmaps, and then defers the actual conflict detection logic to FindHyperedgeAndJoinConflicts().

◆ MakeJoinHypergraph()

bool MakeJoinHypergraph ( THD thd,
JoinHypergraph graph,
bool *  where_is_always_false 

Make a join hypergraph from the query block given by “graph->query_block”, converting from MySQL's join list structures to the ones expected by the hypergraph join optimizer.

This includes pushdown of WHERE predicates, and detection of conditions suitable for hash join. However, it does not include simplification of outer to inner joins; that is presumed to have happened earlier.

The result is suitable for running DPhyp (subgraph_enumeration.h) to find optimal join planning.

◆ PrintDottyHypergraph()

string PrintDottyHypergraph ( const JoinHypergraph graph)

For the given hypergraph, make a textual representation in the form of a dotty graph.

You can save this to a file and then use Graphviz to render this it a graphical representation of the hypergraph for easier debugging, e.g. like this:

dot -Tps > display

See also Dbug_table_list_dumper.