#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"

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
RelationalExpression *	anonymous_namespace{make_join_hypergraph.cc}::MakeRelationalExpressionFromJoinList (THD thd, const mem_root_deque< Table_ref > &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, 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{make_join_hypergraph.cc}::IsMultipleEquals (const Item *cond)

Item_func_eq *	anonymous_namespace{make_join_hypergraph.cc}::MakeEqItem (Item a, Item b, Item_equal *source_multiple_equality)

int	anonymous_namespace{make_join_hypergraph.cc}::CountTablesInEquiJoinCondition (const Item *cond)
	Helper function for ReorderConditions(), which counts how many tables are referenced by an equijoin condition. More...

void	anonymous_namespace{make_join_hypergraph.cc}::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{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_ref tl)

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...

bool	anonymous_namespace{make_join_hypergraph.cc}::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{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 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{make_join_hypergraph.cc}::ResplitConditions (THD thd, const Mem_root_array< Item > &conditions)

bool	anonymous_namespace{make_join_hypergraph.cc}::CanonicalizeConditions (THD thd, table_map visible_tables, table_map all_tables, Mem_root_array< Item > *conditions)

bool	anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::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{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 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{make_join_hypergraph.cc}::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{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 CompanionSetCollection &companion_collection)
	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 CompanionSetCollection &companion_collection, Mem_root_array< Item_equal * > *multiple_equalities)

void	anonymous_namespace{make_join_hypergraph.cc}::ExtractCycleMultipleEqualitiesFromJoinConditions (const RelationalExpression expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item_equal > *multiple_equalities)

bool	anonymous_namespace{make_join_hypergraph.cc}::CanonicalizeJoinConditions (THD thd, RelationalExpression expr)
	Similar to work done in JOIN::finalize_table_conditions() in the old optimizer. 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...

Item *	anonymous_namespace{make_join_hypergraph.cc}::GetSubstitutionConst (Item_field item, Item_func parent_func)
	Find (via a multiple equality) and return a constant that should replace "item". More...

Item *	anonymous_namespace{make_join_hypergraph.cc}::PropagateConstants (Item *cond)
	Replace fields with constants in "cond". More...

Item_field *	anonymous_namespace{make_join_hypergraph.cc}::GetSubstitutionField (Item_field item, Item_func parent, table_map allowed_tables)
	Find (via a multiple equality) a field that should replace "item". More...

Item *	anonymous_namespace{make_join_hypergraph.cc}::PropagateEqualities (Item cond, const RelationalExpression join)

string	anonymous_namespace{make_join_hypergraph.cc}::PrintJoinList (const mem_root_deque< Table_ref * > &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...

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{make_join_hypergraph.cc}::IntersectIfNotDegenerate (table_map used_tables, table_map available_tables)

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, 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{make_join_hypergraph.cc}::EstimateRowWidthForJoin (const JoinHypergraph &graph, const RelationalExpression *expr)

void	anonymous_namespace{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::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{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, CompanionSetCollection &companion_collection, JoinHypergraph *graph)
	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, 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{make_join_hypergraph.cc}::AddMultipleEqualityPredicate (THD thd, CompanionSetCollection &companion_collection, 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, 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{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::ExpandMultipleEqualsForSingleTable (Item_equal 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{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::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{make_join_hypergraph.cc}::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 graph.dot > graph.ps display graph.ps

Namespaces

Enumerations