![]() |
MySQL 8.0.29
Source Code Documentation
|
#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} |
Functions | |
RelationalExpression * | anonymous_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_eq * | anonymous_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... | |
Item * | anonymous_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... | |
RelationalExpression * | anonymous_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... | |
RelationalExpression * | anonymous_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_eq * | anonymous_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... | |
Item * | anonymous_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) |
NodeMap GetNodeMapFromTableMap | ( | table_map | map, |
const array< int, MAX_TABLES > & | table_num_to_node_num | ||
) |
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().
bool MakeJoinHypergraph | ( | THD * | thd, |
string * | trace, | ||
JoinHypergraph * | graph | ||
) |
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.