MySQL 8.0.29
Source Code Documentation
make_join_hypergraph.cc File Reference
#include "sql/join_optimizer/make_join_hypergraph.h"
#include <assert.h>
#include <stddef.h>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <utility>
#include <vector>
#include "limits.h"
#include "mem_root_deque.h"
#include "my_alloc.h"
#include "my_bit.h"
#include "my_inttypes.h"
#include "my_sys.h"
#include "my_table_map.h"
#include "mysqld_error.h"
#include "sql/current_thd.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/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_executor.h"
#include "sql/sql_lex.h"
#include "sql/sql_optimizer.h"
#include "sql/table.h"
#include "template_utils.h"

Namespaces

namespace  anonymous_namespace{make_join_hypergraph.cc}
 

Enumerations

enum class  anonymous_namespace{make_join_hypergraph.cc}::AssociativeRewritesAllowed { anonymous_namespace{make_join_hypergraph.cc}::ANY , anonymous_namespace{make_join_hypergraph.cc}::RIGHT_ONLY , anonymous_namespace{make_join_hypergraph.cc}::LEFT_ONLY }
 

Functions

RelationalExpressionanonymous_namespace{make_join_hypergraph.cc}::MakeRelationalExpressionFromJoinList (THD *thd, const mem_root_deque< TABLE_LIST * > &join_list)
 Convert the Query_block's join lists into a RelationalExpression, ie., a join tree with tables at the leaves. More...
 
bool anonymous_namespace{make_join_hypergraph.cc}::EarlyNormalizeConditions (THD *thd, Mem_root_array< Item * > *conditions)
 Do some constant conversion/folding work needed for correctness. More...
 
bool anonymous_namespace{make_join_hypergraph.cc}::IsMultipleEquals (Item *cond)
 
Item_func_eqanonymous_namespace{make_join_hypergraph.cc}::MakeEqItem (Item *a, Item *b, Item_equal *source_multiple_equality)
 
void anonymous_namespace{make_join_hypergraph.cc}::ExpandSameTableFromMultipleEquals (Item_equal *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{make_join_hypergraph.cc}::EarlyExpandMultipleEquals (Item *condition, table_map tables_in_subtree)
 Expand multiple equalities that can (and should) be expanded before join pushdown. More...
 
RelationalExpressionanonymous_namespace{make_join_hypergraph.cc}::MakeRelationalExpression (THD *thd, const TABLE_LIST *tl)
 
void anonymous_namespace{make_join_hypergraph.cc}::ComputeCompanionSets (RelationalExpression *expr, int current_set, int *num_companion_sets, int table_num_to_companion_set[MAX_TABLES])
 
void anonymous_namespace{make_join_hypergraph.cc}::CreateInnerJoinFromChildList (Mem_root_array< RelationalExpression * > children, RelationalExpression *expr)
 Convert a multi-join into a simple inner join. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::UnflattenInnerJoins (RelationalExpression *expr)
 The opposite of FlattenInnerJoins(); converts all flattened joins to a series of (right-deep) binary joins. More...
 
RelationalExpressionanonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::PrintRelationalExpression (RelationalExpression *expr, int level)
 
bool anonymous_namespace{make_join_hypergraph.cc}::IsNullRejecting (const RelationalExpression &expr, table_map tables)
 
bool anonymous_namespace{make_join_hypergraph.cc}::IsInnerJoin (RelationalExpression::Type type)
 
bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreAssociative (const RelationalExpression &a, const RelationalExpression &b)
 
bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreLeftAsscom (const RelationalExpression &a, const RelationalExpression &b)
 
bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreRightAsscom (const RelationalExpression &a, const RelationalExpression &b)
 
table_map anonymous_namespace{make_join_hypergraph.cc}::UsedTablesForCondition (const RelationalExpression &expr)
 Find a bitmap of used tables for all conditions on <expr>. More...
 
table_map anonymous_namespace{make_join_hypergraph.cc}::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...
 
int anonymous_namespace{make_join_hypergraph.cc}::CompanionSetUsedByCondition (table_map tables, const int table_num_to_companion_set[MAX_TABLES])
 For a given set of tables, find the companion set they are part of (see RelationalExpression::companion_set for an explanation of companion sets). More...
 
bool anonymous_namespace{make_join_hypergraph.cc}::IsCandidateForCycle (RelationalExpression *expr, Item *cond, const int table_num_to_companion_set[MAX_TABLES])
 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{make_join_hypergraph.cc}::ComesFromMultipleEquality (Item *item, Item_equal *equal)
 
int anonymous_namespace{make_join_hypergraph.cc}::FindSourceMultipleEquality (Item *item, const Mem_root_array< Item_equal * > &equals)
 
bool anonymous_namespace{make_join_hypergraph.cc}::MultipleEqualityAlreadyExistsOnJoin (Item_equal *equal, const RelationalExpression &expr)
 
bool anonymous_namespace{make_join_hypergraph.cc}::AlreadyExistsOnJoin (Item *cond, const RelationalExpression &expr)
 
bool anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::RotateRight (RelationalExpression *op)
 Applies the following rewrite on <op>: More...
 
void anonymous_namespace{make_join_hypergraph.cc}::RotateLeft (RelationalExpression *op)
 Opposite of RotateRight; that is: More...
 
Item_func_eqanonymous_namespace{make_join_hypergraph.cc}::ConcretizeMultipleEquals (Item_equal *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{make_join_hypergraph.cc}::FullyConcretizeMultipleEquals (Item_equal *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{make_join_hypergraph.cc}::CanonicalizeCondition (Item *condition, table_map allowed_tables)
 Finalize a condition (join condition or WHERE predicate); resolve any remaining multiple equalities, and add casts to comparisons where needed. More...
 
bool anonymous_namespace{make_join_hypergraph.cc}::CanonicalizeConditions (THD *thd, table_map tables_in_subtree, Mem_root_array< Item * > *conditions)
 
bool anonymous_namespace{make_join_hypergraph.cc}::AddJoinConditionPossiblyWithRewrite (RelationalExpression *expr, Item *cond, AssociativeRewritesAllowed allowed, bool used_commutativity, bool *need_flatten, string *trace)
 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{make_join_hypergraph.cc}::PushDownCondition (Item *cond, RelationalExpression *expr, bool is_join_condition_for_expr, const int table_num_to_companion_set[MAX_TABLES], Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges, Mem_root_array< Item * > *remaining_parts, string *trace)
 Try to push down the condition “cond” down in the join tree given by “expr”, as far as possible. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::PushDownAsMuchAsPossible (THD *thd, Mem_root_array< Item * > conditions, RelationalExpression *expr, bool is_join_condition_for_expr, const int table_num_to_companion_set[MAX_TABLES], Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges, string *trace)
 Push down as many of the conditions in “conditions” as we can, into the join tree under “expr”. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::PushDownJoinConditions (THD *thd, RelationalExpression *expr, const int table_num_to_companion_set[MAX_TABLES], Mem_root_array< Item * > *table_filters, Mem_root_array< Item * > *cycle_inducing_edges, string *trace)
 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{make_join_hypergraph.cc}::PushDownJoinConditionsForSargable (THD *thd, RelationalExpression *expr)
 Similar to PushDownJoinConditions(), but for push of sargable conditions (see PushDownJoinConditionsForSargable()). More...
 
void anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::FindNullGuaranteedTables (const RelationalExpression *expr)
 
void anonymous_namespace{make_join_hypergraph.cc}::ClearImpossibleJoinConditions (RelationalExpression *expr)
 
bool anonymous_namespace{make_join_hypergraph.cc}::ShouldCompleteMeshForCondition (Item_equal *item_equal, const int table_num_to_companion_set[MAX_TABLES])
 Find out whether we should create mesh edges (all-to-all) for this multiple equality. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::ExtractCycleMultipleEqualities (const Mem_root_array< Item * > &conditions, const int table_num_to_companion_set[MAX_TABLES], Mem_root_array< Item_equal * > *multiple_equalities)
 
void anonymous_namespace{make_join_hypergraph.cc}::ExtractCycleMultipleEqualitiesFromJoinConditions (const RelationalExpression *expr, const int table_num_to_companion_set[MAX_TABLES], Mem_root_array< Item_equal * > *multiple_equalities)
 
bool anonymous_namespace{make_join_hypergraph.cc}::CanonicalizeJoinConditions (THD *thd, RelationalExpression *expr)
 Find constant expressions in join conditions, and add caches around them. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::FindConditionsUsedTables (THD *thd, RelationalExpression *expr)
 
void anonymous_namespace{make_join_hypergraph.cc}::CSEConditions (THD *thd, Mem_root_array< Item * > *conditions)
 Run simple CSE on all conditions (see CommonSubexpressionElimination()). More...
 
string anonymous_namespace{make_join_hypergraph.cc}::PrintJoinList (const mem_root_deque< TABLE_LIST * > &join_list, int level)
 
table_map anonymous_namespace{make_join_hypergraph.cc}::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...
 
NodeMap anonymous_namespace{make_join_hypergraph.cc}::IntersectIfNotDegenerate (NodeMap used_nodes, NodeMap available_nodes)
 
NodeMap anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::FindHyperedgeAndJoinConflicts (THD *thd, NodeMap used_nodes, RelationalExpression *expr)
 For the join operator in “expr”, build a hyperedge that encapsulates its reordering conditions as completely as possible. More...
 
size_t anonymous_namespace{make_join_hypergraph.cc}::EstimateRowWidthForJoin (const JoinHypergraph &graph, const RelationalExpression *expr)
 
int anonymous_namespace{make_join_hypergraph.cc}::AddPredicate (THD *thd, Item *condition, bool was_join_condition, int source_multiple_equality_idx, const RelationalExpression *root, JoinHypergraph *graph, string *trace)
 Add the given predicate to the list of WHERE predicates, doing some bookkeeping that such predicates need. More...
 
bool anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::AddCycleEdges (THD *thd, const Mem_root_array< Item * > &cycle_inducing_edges, JoinHypergraph *graph, string *trace)
 For each of the given join conditions, add a cycle-inducing edge to the hypergraph. More...
 
void anonymous_namespace{make_join_hypergraph.cc}::PromoteCycleJoinPredicates (THD *thd, const RelationalExpression *root, const Mem_root_array< Item_equal * > &multiple_equalities, JoinHypergraph *graph, string *trace)
 Promote join predicates that became part of (newly-formed) cycles to WHERE predicates. More...
 
void MakeJoinGraphFromRelationalExpression (THD *thd, RelationalExpression *expr, string *trace, 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)
 
bool anonymous_namespace{make_join_hypergraph.cc}::ExistsEdgeBetween (const JoinHypergraph *graph, int left_node_idx, int right_node_idx, int *out_edge_idx)
 
void anonymous_namespace{make_join_hypergraph.cc}::AddMultipleEqualityPredicate (THD *thd, Item_equal *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{make_join_hypergraph.cc}::CompleteFullMeshForMultipleEqualities (THD *thd, const Mem_root_array< Item_equal * > &multiple_equalities, JoinHypergraph *graph, string *trace)
 For each relevant multiple equality, add edges so that there are direct connections between all the involved tables (full mesh). More...
 
bool MakeJoinHypergraph (THD *thd, string *trace, JoinHypergraph *graph)
 

Function Documentation

◆ GetNodeMapFromTableMap()

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

◆ MakeJoinGraphFromRelationalExpression()

void MakeJoinGraphFromRelationalExpression ( THD thd,
RelationalExpression expr,
string *  trace,
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,
string *  trace,
JoinHypergraph graph 
)

◆ 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 graph.dot > graph.ps display graph.ps

See also Dbug_table_list_dumper.