anonymous_namespace{make_join_hypergraph.cc} Namespace Reference

Enumerations
enum class	AssociativeRewritesAllowed { ANY , RIGHT_ONLY , LEFT_ONLY }

Functions
RelationalExpression *	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	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	IsMultipleEquals (const Item *cond)
Item_func_eq *	MakeEqItem (Item *a, Item *b, Item_multi_eq *source_multiple_equality)
int	CountTablesInEquiJoinCondition (const Item *cond)
	Helper function for ReorderConditions(), which counts how many tables are referenced by an equijoin condition. More...
void	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	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...
Item *	EarlyExpandMultipleEquals (Item *condition, table_map tables_in_subtree)
	Expand multiple equalities that can (and should) be expanded before join pushdown. More...
RelationalExpression *	MakeRelationalExpression (THD *thd, const Query_block *query_block, const Table_ref *tl)
void	CreateInnerJoinFromChildList (Mem_root_array< RelationalExpression * > children, RelationalExpression *expr)
	Convert a multi-join into a simple inner join. More...
void	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	UnflattenInnerJoins (RelationalExpression *expr)
	The opposite of FlattenInnerJoins(); converts all flattened joins to a series of (right-deep) binary joins. More...
RelationalExpression *	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	PrintRelationalExpression (RelationalExpression *expr, int level)
bool	IsNullRejecting (const RelationalExpression &expr, table_map tables)
bool	IsInnerJoin (RelationalExpression::Type type)
bool	OperatorsAreAssociative (const RelationalExpression &a, const RelationalExpression &b)
bool	OperatorsAreLeftAsscom (const RelationalExpression &a, const RelationalExpression &b)
bool	OperatorsAreRightAsscom (const RelationalExpression &a, const RelationalExpression &b)
table_map	UsedTablesForCondition (const RelationalExpression &expr)
	Find a bitmap of used tables for all conditions on <expr>. More...
table_map	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	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	ComesFromMultipleEquality (Item *item, Item_multi_eq *equal)
int	FindSourceMultipleEquality (Item *item, const Mem_root_array< Item_multi_eq * > &equals)
bool	MultipleEqualityAlreadyExistsOnJoin (Item_multi_eq *equal, const RelationalExpression &expr)
bool	AlreadyExistsOnJoin (Item *cond, const RelationalExpression &expr)
bool	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	RotateRight (RelationalExpression *op)
	Applies the following rewrite on <op>: More...
void	RotateLeft (RelationalExpression *op)
	Opposite of RotateRight; that is: More...
Item_func_eq *	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	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...
Item *	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 * >	ResplitConditions (THD *thd, const Mem_root_array< Item * > &conditions)
bool	CanonicalizeConditions (THD *thd, table_map visible_tables, table_map all_tables, Mem_root_array< Item * > *conditions)
bool	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	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	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 * >	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	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	PushDownJoinConditionsForSargable (THD *thd, RelationalExpression *expr)
	Similar to PushDownJoinConditions(), but for push of sargable conditions (see PushDownJoinConditionsForSargable()). More...
void	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	FindNullGuaranteedTables (const RelationalExpression *expr)
void	ClearImpossibleJoinConditions (RelationalExpression *expr)
bool	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	ExtractCycleMultipleEqualities (const Mem_root_array< Item * > &conditions, const CompanionSetCollection &companion_collection, Mem_root_array< Item_multi_eq * > *multiple_equalities)
void	ExtractCycleMultipleEqualitiesFromJoinConditions (const RelationalExpression *expr, const CompanionSetCollection &companion_collection, Mem_root_array< Item_multi_eq * > *multiple_equalities)
bool	CanonicalizeJoinConditions (THD *thd, RelationalExpression *expr)
	Similar to work done in JOIN::finalize_table_conditions() in the old optimizer. More...
void	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	FindConditionsUsedTables (THD *thd, RelationalExpression *expr)
void	CSEConditions (THD *thd, Mem_root_array< Item * > *conditions)
	Run simple CSE on all conditions (see CommonSubexpressionElimination()). More...
Item *	GetSubstitutionConst (Item_field *item, Item_func *parent_func)
	Find (via a multiple equality) and return a constant that should replace "item". More...
Item *	PropagateConstants (Item *cond)
	Replace fields with constants in "cond". More...
Item_field *	GetSubstitutionField (Item_field *item, Item_func *parent, table_map allowed_tables)
	Find (via a multiple equality) a field that should replace "item". More...
Item *	PropagateEqualities (Item *cond, const RelationalExpression *join)
string	PrintJoinList (const mem_root_deque< Table_ref * > &join_list, int level)
table_map	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...
table_map	IntersectIfNotDegenerate (table_map used_tables, table_map available_tables)
NodeMap	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	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	EstimateRowWidthForJoin (const JoinHypergraph &graph, const RelationalExpression *expr)
void	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	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	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	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	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	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	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	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	GetTablesInnerToOuterJoinOrAntiJoin (const RelationalExpression *expr)
	Returns a map of all tables that are on the inner side of some outer join or antijoin. More...
bool	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	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	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	FindLateralDependencies (JoinHypergraph *graph)

Enumeration Type Documentation

AssociativeRewritesAllowed

enum class anonymous_namespace{make_join_hypergraph.cc}::AssociativeRewritesAllowed

strong

Enumerator
ANY
RIGHT_ONLY
LEFT_ONLY

Function Documentation

AbsorbConflictRulesIntoTES()

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.

This works by growing the TES (Total Eligibility Set), the set of tables that needs to be present before we can do the join; the TES will eventually be split into two and made into a hyperedge.

The TES must obviously include the SES (Syntactic Eligibility Set), every table mentioned in the join condition. And if anything on the left side of a conflict rule overlaps with the TES, that conflict rule would always be active, and we can safely include the right side into the TES. Similarly, if the TES is a superset of what's on the right side of a conflict rule, that rule will never prevent anything (since we never see a subgraph unless we have everything touched by its hyperedge, ie., the TES), so it can be removed. We iterate over all the conflict rules until they are all gone or the TES has stopped growing; then we create our hyperedge by splitting the TES.

AddCycleEdges()

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.

AddJoinConditionPossiblyWithRewrite()

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.

(See IsBadJoinForCondition().)

a JOIN (b JOIN c ON TRUE) ON a.x=b.x WHERE a.y=c.y

In this case, we'd try rewriting the join tree into

(a JOIN b ON a.x=b.x) JOIN c ON TRUE WHERE a.y=c.y

which would then allow the push with no issues:

(a JOIN b ON a.x=b.x) JOIN c ON a.y=c.y

Note that with flattening, we don't need this for inner joins (flattening solves all inner-join cases without needing this machinery), so this is only ever called when outer joins are involved (inner joins are used in the example above for ease of exposition).

This function works recursively, and returns true if the condition was pushed.

AddMultipleEqualityPredicate()

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

AddPredicate()

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.

AlreadyExistsOnJoin()

bool anonymous_namespace{make_join_hypergraph.cc}::AlreadyExistsOnJoin	(	Item *	cond,
		const RelationalExpression &	expr
	)

AreNodesConnected()

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.

CanonicalizeCondition()

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.

Caches around constant arguments are not added here but during finalize, since we might plan two times, and the caches from the first time may confuse remove_eq_cond() in the second.

CanonicalizeConditions()

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

CanonicalizeJoinConditions()

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.

Non-join predicates are done near the start in MakeJoinHypergraph().

CertainlyUsedTablesForCondition()

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.

This is the case for tables that are the only ones on their side of the join. E.g.: For a multiple equality {A,C,D} on a join (A,B) JOIN (C,D), A is certain; either A=C or A=D has to be included no matter what.

ClearImpossibleJoinConditions()

void anonymous_namespace{make_join_hypergraph.cc}::ClearImpossibleJoinConditions

(

RelationalExpression *

expr

)

ComesFromMultipleEquality()

bool anonymous_namespace{make_join_hypergraph.cc}::ComesFromMultipleEquality	(	Item *	item,
		Item_multi_eq *	equal
	)

CompleteFullMeshForMultipleEqualities()

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

The tables must all be in the same companion set (ie., no outer joins in the way).

Must run after equijoin conditions are extracted. Should be run after trivial conditions have been removed.

ConcretizeMultipleEquals()

Item_func_eq * anonymous_namespace{make_join_hypergraph.cc}::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”.

E.g. for joining (A,B) and (C,D), and given the multi-equality (A.x,B.x,D.x), it may pick A.x = D.x or B.x = D.x (but never A.x = B.x).

CountTablesInEquiJoinCondition()

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.

This enables ReorderConditions() to sort the conditions on their complexity (referencing more tables == more complex). Multiple equalities are considered simple, referencing two tables, regardless of how many tables are actually referenced by them. This is because multiple equalities will be split into one or more single equalities later, referencing no more than two tables each.

CreateInnerJoinFromChildList()

void anonymous_namespace{make_join_hypergraph.cc}::CreateInnerJoinFromChildList	(	Mem_root_array< RelationalExpression * >	children,
		RelationalExpression *	expr
	)

Convert a multi-join into a simple inner join.

expr must already have the correct companion set filled out.

Only the top level will be converted, so there may still be a multi-join below the modified node, e.g.:

MULTIJOIN(a, b) -> a JOIN b MULTIJOIN(a, b, c, ...) -> a JOIN MULTIJOIN(b, c, ...)

If you want full unflattening, call UnflattenInnerJoins(), which calls this function recursively.

CSEConditions()

void anonymous_namespace{make_join_hypergraph.cc}::CSEConditions	(	THD *	thd,
		Mem_root_array< Item * > *	conditions
	)

Run simple CSE on all conditions (see CommonSubexpressionElimination()).

EarlyExpandMultipleEquals()

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.

These are the ones that touch at most two tables, or that are against a constant. They can be expanded unambiguously; no matter the join order, they will be the same. Fields on tables not in “tables_in_subtree” are assumed to be irrelevant to the equality and ignored (see the comment on PushDownCondition() for more details).

For multi-equalities that are kept, split out any conditions that refer to the same table. See ExpandSameTableFromMultipleEquals().

The return value is an AND conjunction, so most likely, it needs to be split.

EarlyNormalizeConditions()

bool anonymous_namespace make_join_hypergraph anonymous_namespace{make_join_hypergraph.cc}::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.

For simple filters, propagate constants if there are any established through multiple equalities. Note that most of the propagation is already done in optimize_cond(). This is to handle only the corner cases where equality propagation in optimize_cond() would have been rejected (which is done in old optimizer at a later point). For join conditions which are not part of multiple equalities, try to substitute fields with the fields from available tables in the join. It's possible only if there are multiple equalities for the fields in the join condition. E.g.

1. t1.a = t2.a and t1.a <> t2.a would be multi-equal(t1.a, t2.a) and t1.a <> t2.a post optimize_cond(). We could transform this condition into multi-equal(t1.a, t2.a) and t1.a <> t1.a.
2. t1.a = t2.a + t3.a could be converted to t1.a = t2.a + t2.a if there is multiple equality (t2.a, t3.a). This makes it an equi-join condition rather than an extra predicate for the join.

For simple filters, propagate constants if there are any established through multiple equalities. Note that most of the propagation is already done in optimize_cond(). This is to handle only the corner cases where equality propagation in optimize_cond() would have been rejected (which is done in old optimizer at a later point). For join conditions which are not part of multiple equalities, try to substitute fields with the fields from available tables in the join. It's possible only if there are multiple equalities for the fields in the join condition. E.g.

1. t1.a = t2.a and t1.a <> t2.a would be multi-equal(t1.a, t2.a) and t1.a <> t2.a post optimize_cond(). We could transform this condition into multi-equal(t1.a, t2.a) and t1.a <> t1.a.
2. t1.a = t2.a + t3.a could be converted to t1.a = t2.a + t2.a if there is multiple equality (t2.a, t3.a). This makes it an equi-join condition rather than an extra predicate for the join.

EstimateRowWidthForJoin()

size_t anonymous_namespace{make_join_hypergraph.cc}::EstimateRowWidthForJoin	(	const JoinHypergraph &	graph,
		const RelationalExpression *	expr
	)

ExpandMultipleEqualsForSingleTable()

bool anonymous_namespace{make_join_hypergraph.cc}::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.

Only expected to be called on multiple equalities that do not have an already known value, as such equalities should be eliminated by constant folding instead of being expanded.

ExpandSameTableFromMultipleEquals()

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

for equal(t1.a, t2.a, t2.b, t3.a), will return t2.a=t2.b AND (original item). This means that later stages can ignore such duplicates, and also that we can push these parts independently of the multiple equality as a whole.

ExtractCycleMultipleEqualities()

void anonymous_namespace{make_join_hypergraph.cc}::ExtractCycleMultipleEqualities	(	const Mem_root_array< Item * > &	conditions,
		const CompanionSetCollection &	companion_collection,
		Mem_root_array< Item_multi_eq * > *	multiple_equalities
	)

ExtractCycleMultipleEqualitiesFromJoinConditions()

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

ExtractWhereConditionsForSingleTable()

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.

Multiple equalities are fully expanded unconditionally, since there is only one way to expand them when there is only a single table (no need to consider that they should be pushable to joins). Normalization will also be performed if necessary.

FindConditionsUsedTables()

void anonymous_namespace{make_join_hypergraph.cc}::FindConditionsUsedTables	(	THD *	thd,
		RelationalExpression *	expr
	)

FindHyperedgeAndJoinConflicts()

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.

The conditions given by the hyperedge are necessary and usually sufficient; for the cases where they are not sufficient, we leave conflict rules on “expr” (see below).

This function is almost verbatim the CD-C algorithm from “On the correct and complete enumeration of the core search space” by Moerkotte et al [Moe13]. It works by the concept of conflict rules (CRs); if a CR A → B, for relation sets A and B, is attached on a given join, then if any table from A is present in the join, then all tables from B are required. As a trivial example, one can imagine t1 <opA> (t2 <opB> t3); if <opA> has a CR {t2} → {t3}, then the rewrite (t1 <opA> t2) <opB> t3 would not be allowed, since t2 is present but t3 is not. However, in the absence of other CRs, and given appropriate connectivity in the graph, the rewrite (t1 <opA> t3) <opB> t2 would be allowed.

Conflict rules are both expressive enough to precisely limit invalid rewrites, and in the majority of cases, can be folded into hyperedges, relegating the task of producing only valid plans to the subgraph enumeration (DPhyp), which is highly efficient at it. In the few cases that remain, they will need to be checked manually in CostingReceiver, but this is fast (only a few bitmap operations per remaining CR).

The gist of the algorithm is to compare every operator with every operator below it in the join tree, looking for illegal rewrites between them, and adding precise CRs to stop only those rewrites. For instance, assume a query like

t1 LEFT JOIN (t2 JOIN t3 USING (y)) ON t1.x=t2.x

Looking at the root predicate (the LEFT JOIN), the question is what CRs and hyperedge to produce. The join predicate only mentions t1 and t2, so it only gives rise to the simple edge {t1}→{t2}. So without any conflict rules, nothing would stop us from joining t1/t2 without including t3, and we would allow a generated plan essentially equal to

(t1 LEFT JOIN t2 ON t1.x=t2.x) JOIN t3 USING (y)

which is illegal; we have attempted to use associativity illegally. So when we compare the LEFT JOIN (in the original query tree) with the JOIN, we look up those two operator types using OperatorsAreAssociative() (which essentially does a lookup into a small table), see that the combination LEFT JOIN and JOIN is not associative, and thus create a conflict rule that prevents this:

{t2} → {t3}

t2 here is everything on the left side of the inner join, and t3 is every table on the right side of the inner join that is mentioned in the join condition (which happens to also be everything on the right side). This rule, posted on the LEFT JOIN, prevents it from including t2 until it has been combined with t3, which is exactly what we want. There are some tweaks for degenerate conditions, but that's really all for associativity conflict rules.

The other source of conflict rules comes from a parallel property called l-asscom and r-asscom; see OperatorsAreLeftAsscom() and OperatorsAreRightAsscom(). They work in exactly the same way; look at every pair between and operator and its children, look it up in a table, and add a conflict rule that prevents the rewrite if it is illegal.

When we have the CRs, we want to fold them into the hyperedge we are about to create. See AbsorbConflictRulesIntoTES() for details.

Note that in the presence of degenerate predicates or Cartesian products, we may make overly broad hyperedges, ie., we will disallow otherwise valid plans (but never allow invalid plans). This is the only case where the algorithm misses a valid join ordering, and also the only place where we diverge somewhat from the paper, which doesn't discuss hyperedges in the presence of such cases.

FindLateralDependencies()

void anonymous_namespace{make_join_hypergraph.cc}::FindLateralDependencies

(

JoinHypergraph *

graph

)

FindNullGuaranteedTables()

table_map anonymous_namespace{make_join_hypergraph.cc}::FindNullGuaranteedTables

(

const RelationalExpression *

expr

)

FindSourceMultipleEquality()

int anonymous_namespace{make_join_hypergraph.cc}::FindSourceMultipleEquality	(	Item *	item,
		const Mem_root_array< Item_multi_eq * > &	equals
	)

FindTESForCondition()

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

The SES contains all relations that are directly referenced by the predicate; the TES contains all relations that are needed to be available before the predicate can be evaluated.

The TES always contains at least SES, but may be bigger. For instance, given the join tree (a LEFT JOIN b), a condition such as b.x IS NULL would have a SES of {b}, but a TES of {a,b}, since joining in a could synthesize NULLs from b. However, given (a JOIN b) (ie., an inner join instead of an outer join), the TES would be {b}, identical to the SES.

NOTE: The terms SES and TES are often used about join conditions; the use here is for general conditions beyond just those.

NOTE: This returns a table_map, which is later converted to a NodeMap.

FlattenInnerJoins()

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

We do this even for the joins that have only two children, as it makes it easier to absorb them into higher multi-joins.

The primary motivation for flattening is more flexible pushdown; when there is a large multi-way join, we can push pretty much any equality condition down to it, no matter how the join tree was written by the user. See PartiallyUnflattenJoinForCondition() for details.

Note that this (currently) does not do any rewrites to flatten even more. E.g., for the tree (a JOIN (b LEFT JOIN c)), it would be beneficial to use associativity to rewrite into (a JOIN b) LEFT JOIN c (assuming a and b could be combined further with other joins). This also means that there may be items in the companion set that are not part of the same multi-join.

FullyConcretizeMultipleEquals()

template<class T >

static void anonymous_namespace{make_join_hypergraph.cc}::FullyConcretizeMultipleEquals ( Item_multi_eq *  cond, table_map  allowed_tables, T *  result  )

static

From “cond”, create exactly as many simple equalities that are needed to connect all tables in “allowed_tables”.

E.g. for joining (A,B) and (C,D) (ie., allowed_tables={A,B,C,D}), and given the multi-equality (A.x, B.x, D.x, E.x), it will generate A.x = B.x and B.x = D.x (E.x is ignored).

The given container must support push_back(Item_func_eq *).

GetSubstitutionConst()

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

If no such constant is found, return "item".

GetSubstitutionField()

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

If no such field is found, return "item".

Parameters

item	The item to find a replacement for.
parent	The immediately enclosing function in which "item" is found.
allowed_tables	The set of tables the replacement can come from.

Returns

The field to replace "item" with, or "item".

GetTablesInnerToOuterJoinOrAntiJoin()

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.

IntersectIfNotDegenerate()

table_map anonymous_namespace{make_join_hypergraph.cc}::IntersectIfNotDegenerate	(	table_map	used_tables,
		table_map	available_tables
	)

IsBadJoinForCondition()

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.

The former is suboptimal since it would create a wider hyperedge than is usually needed, ie., it restricts join ordering. Consider for instance a join such as

a JOIN (b JOIN c ON TRUE) ON a.x=b.x WHERE a.y=c.y

If pushing the WHERE condition down on the a/bc join, that join would get a dependency on both b and c, hindering (ab) and (ac) as subplans. This function allows us to detect this and look for other opportunities (see AddJoinCondition()).

IsCandidateForCycle()

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

IsInnerJoin()

bool anonymous_namespace{make_join_hypergraph.cc}::IsInnerJoin

(

RelationalExpression::Type

type

)

IsMultipleEquals()

bool anonymous_namespace{make_join_hypergraph.cc}::IsMultipleEquals ( const Item *  cond )

inline

IsNullRejecting()

bool anonymous_namespace{make_join_hypergraph.cc}::IsNullRejecting	(	const RelationalExpression &	expr,
		table_map	tables
	)

IsPartOfCycle()

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

Edges that are not part of a cycle are called “bridges” in graph theory. There are efficient algorithms for finding all bridges in a graph (see e.g. Schmidt: “A Simple Test on 2-Vertex- and 2-Edge-Connectivity”), but our graph is small, so we opt for simplicity by simply doing a depth-first search for all edges. We only need to consider the part of the subgraph given by inner joins (the companion set) – but we cannot ignore hyperedges, since we determine companion sets before we know all the join predicates.

LateConcretizeMultipleEqualities()

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.

The reason for doing it after all other pushing is that we want to make sure not to expand the hyperedges any more than necessary, and we don't know what “necessary” is before everything else is pushed.

This is only relevant for antijoins and semijoins; inner joins (and partially left joins) get concretized as we push, since they can resolve such conflicts by associative rewrites and/or creating cycles in the graph. Normally, we probably wouldn't worry about such a narrow case, but there are specific benchmark queries that happen to exhibit this problem.

There may still be remaining ones afterwards, such as those that are degenerate or within more complex expressions; CanonicalizeJoinConditions() will deal with them.

MakeEqItem()

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

MakeHashJoinConditions()

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.

An equijoin condition for us is one that is an equality comparison (=) and pulls in relations from both sides of the tree (so is not degenerate, and pushed as far down as possible). We also demand that it does not use row comparison, as our hash join implementation currently does not support that. Any condition that is found to be an equijoin condition is moved from expr->join_conditions to expr->equijoin_conditions.

The function recurses down the join tree.

MakeRelationalExpression()

RelationalExpression * anonymous_namespace{make_join_hypergraph.cc}::MakeRelationalExpression	(	THD *	thd,
		const Query_block *	query_block,
		const Table_ref *	tl
	)

MakeRelationalExpressionFromJoinList()

RelationalExpression *anonymous_namespace make_join_hypergraph anonymous_namespace{make_join_hypergraph.cc}::cc::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.

If join order hints are specified, use the join order specified in the join order hints.

Parameters

thd	Current thread
query_block	Current query block
join_list_arg	List of tables in this join
toplevel	False for subqueries, true otherwise

Returns

RelationalExpression for all tables in join

MakeSingleTableHypergraph()

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.

MultipleEqualityAlreadyExistsOnJoin()

bool anonymous_namespace{make_join_hypergraph.cc}::MultipleEqualityAlreadyExistsOnJoin	(	Item_multi_eq *	equal,
		const RelationalExpression &	expr
	)

OperatorsAreAssociative()

bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreAssociative	(	const RelationalExpression &	a,
		const RelationalExpression &	b
	)

OperatorsAreLeftAsscom()

bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreLeftAsscom	(	const RelationalExpression &	a,
		const RelationalExpression &	b
	)

OperatorsAreRightAsscom()

bool anonymous_namespace{make_join_hypergraph.cc}::OperatorsAreRightAsscom	(	const RelationalExpression &	a,
		const RelationalExpression &	b
	)

PartiallyUnflattenJoinForCondition()

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.

For instance, if we have

MULTIJOIN(t1, t2, t3, t4 LJ t5)

and we have a condition t2.x = t5.x, we need to pull out the parts referring to t2 and t5, partially exploding the multi-join:

MULTIJOIN(t1, t3, t2 JOIN (t4 LJ t5))

The newly created child will be returned, and the condition can be pushed onto it. Note that there may be flattened joins under it; it is only the returned node itself that is guaranteed to be a binary join.

If the condition touches all tables in the flattened join, the newly created binary node will completely replace the former. (The simplest case of this is a multi-join with only two nodes, and a condition referring to both of them.) For instance, given

MULTIJOIN(t1, t2, t3)

and a condition t1.x = t2.x + t3.x, the entire node will be replaced by

t1 JOIN MULTIJOIN(t2, t3)

on which it is possible to push the condition. Which node is pulled out to the left side is undefined.

See also CreateInnerJoinFromChildList().

PrintJoinList()

string anonymous_namespace{make_join_hypergraph.cc}::PrintJoinList	(	const mem_root_deque< Table_ref * > &	join_list,
		int	level
	)

PrintRelationalExpression()

string anonymous_namespace{make_join_hypergraph.cc}::PrintRelationalExpression	(	RelationalExpression *	expr,
		int	level
	)

PromoteCycleJoinPredicates()

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

The reason for this is that when we have cycles in the graph, we can no longer guarantee that all join predicates will be seen; e.g. if we have a cycle A - B - C - A, and choose to complete the join by using the A-B and C-A edges, we would miss the B-C join predicate. Thus, we promote all join edges involved in cycles to WHERE predicates; however, we mark them as coming from a join condition, and we also note in the join edge what the indexes of the added predicate are. Thus, for A-B and C-A in the given example, we would ignore the corresponding WHERE predicates so they do not get double-applied.

We need to mark which predicates came from which multiple equalities, so that they are not added when they are redundant; see the comment on top of CostingReceiver::ApplyDelayedPredicatesAfterJoin().

Note that join predicates may actually get added as predicates a second time, if they are found to be sargable. However, in that case they are not counted as WHERE predicates (they are never automatically applied), so this is a separate use.

PropagateConstants()

Item * anonymous_namespace{make_join_hypergraph.cc}::PropagateConstants

(

Item *

cond

)

Replace fields with constants in "cond".

PropagateEqualities()

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

PushDownAsMuchAsPossible()

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

The parts that could not be pushed are returned.

The conditions are nominally taken to be from higher up the tree than “expr” (e.g., WHERE conditions, or join conditions from a higher join), unless is_join_condition_for_expr is true, in which case they are taken to be posted as join conditions posted on “expr” itself. This causes them to be returned as remaining if “expr” is indeed their final lowest place in the tree (otherwise, they might get lost).

PushDownCondition()

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.

cond is either a join condition on expr (is_join_condition_for_expr=true), or a filter which is applied at some point after expr (...=false).

If the condition was not pushable, ie., it couldn't be stored as a join condition on some lower place than it started, it will push it onto “remaining_parts”. remaining_parts can be nullptr, in which case the condition is simply dropped.

Since PushDownAsMuchAsPossible() only calls us for join conditions, there is only one way we can push down something onto a single table (which naturally has no concept of “join condition”), and it does not affect the return condition. That is partial pushdown:

In addition to regular pushdown, PushDownCondition() will do partial pushdown if appropriate. Some expressions cannot be fully pushed down, but we can push down necessary-but-not-sufficient conditions to get earlier filtering. (This is a performance win for e.g. hash join and the left side of a nested loop join, but not for the right side of a nested loop join. Note that we currently do not compensate for the errors in selectivity estimation this may incur.) An example would be

(t1.x = 1 AND t2.y=2) OR (t1.x = 3 AND t2.y=4);

we could push down the conditions (t1.x = 1 OR t1.x = 3) to t1 and similarly for t2, but we could not delete the original condition. If we get all the way down to a table, we store the condition in “table_filters”. These are conditions that can be evaluated directly on the given table, without any concern for what is joined in before (ie., TES = SES).

Multiple equalities

Pushing down multiple equalities is somewhat tricky. To recap, a multiple equality (Item_multi_eq) is a set of N fields (a,b,c,...) that are all assumed to be equal to each other. As part of pushdown, we concretize these into (N-1) regular equalities (where every field is referred to at least once); this is enough for query correctness, and the remaining options will be added to the query graph later. E.g., if we have multiple equals (a,b,c), we could add a=b AND b=c, or equivalently a=c AND b=c. But for (a,b,c,d), we couldn't do with a=b AND a=c AND b=c; even though it would be (N-1) equalities, d still needs to be in the mix.

We solve this by pushing down multiple equalities as usual down the tree until it becomes a join condition at the current node (ie., it refers to tables from both sides). At that point, we can pick an arbitrary table from each sides to create an equality. E.g. for (a,b,c,d) pushed onto (a,b) JOIN (c,d), we can choose an equality a=c, or a=d, or similar. However, this only resolves one equality; we need to keep pushing it down on both sides. This will create the (N-1) ones we want in the end. But at this point, the multiple equality will refer to tables not part of the join; e.g. trying to push down equals(a,b,c,d) onto a JOIN b. If so, we simply ignore the fields belonging to tables not part of the join, so we create a=b (the only possibility).

If we at some point end up with a multiple equality we cannot push (e.g., because it hit an outer join), we will resolve it at the latest in CanonicalizeCondition().

PushDownJoinConditions()

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.

This is needed because the initial optimization steps (before the join optimizer) try to hoist join conditions as far up the tree as possible, normally all the way up to the WHERE, but could be stopped by outer joins and antijoins. E.g. assume what the user wrote was

a LEFT JOIN (B JOIN C on b.x=c.x)

This would be pulled up to

a LEFT JOIN (B JOIN C) ON b.x=c.x

ie., a pushable join condition posted on the LEFT JOIN, that could not go into the WHERE. When this function is called on the said join, it will push the join condition down again.

PushDownJoinConditionsForSargable()

void anonymous_namespace{make_join_hypergraph.cc}::PushDownJoinConditionsForSargable	(	THD *	thd,
		RelationalExpression *	expr
	)

Similar to PushDownJoinConditions(), but for push of sargable conditions (see PushDownJoinConditionsForSargable()).

The reason this is a separate function, is that we want to run sargable push after all join conditions have been finalized; in particular, that multiple equalities have been concretized into single equalities. (We don't recognize multi-equalities as sargable predicates in their multi-form, since they could be matching multiple targets and generally are more complicated. It is much simpler to wait until they are concretized.)

PushDownToSargableCondition()

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.

Equijoin conditions can often be pushed down into indexes; e.g. t1.x = t2.x could be pushed down into an index on t1.x. When we have pushed such a condition all the way down onto the t1/t2 join, we are ostensibly done with regular push (in PushDownCondition()), but here, we would push down the condition onto both sides if possible. (E.g.: If the join was a left join, we could push it down to t2, but not to t1.) When we hit a table in such a push, we store the conditions in “m_pushable_conditions“ for the table to signal that it should be investigated when we consider the table during join optimization.

ReorderConditions()

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.

These will be followed by predicates having subqueries and the expensive predicates at the end. This is used in the early stage of optimization. Predicates are not ordered based on their selectivity yet. The call to optimize_cond() would have put all the equalities at the end (because it tries to create multiple equalities out of them). It is always better to see the equalties ahead of other types of conditions when pushing join conditions down. E.g: (t1.f1 != t2.f1) and (t1.f2 = t3.f2 OR t4.f1 = t5.f3) and (3 = select #2) and (t1.f3 = t3.f3) and multi_equal(t1.f2,t2.f3,t3.f4) will be split in this order (t1.f3 = t3.f3) and multi_equal(t1.f2,t2.f3,t3.f4) and (t1.f1 != t2.f1) and (t1.f2 = t3.f2 OR t4.f1 = t5.f3) and (3 = select #2)

Simple equijoin conditions (like t1.x=t2.x) are placed ahead of more complex ones (like t1.x=t2.x+t3.x), so that we prefer making simple edges and avoid hyperedges when we can.

ResplitConditions()

Mem_root_array< Item * > anonymous_namespace{make_join_hypergraph.cc}::ResplitConditions	(	THD *	thd,
		const Mem_root_array< Item * > &	conditions
	)

RotateLeft()

void anonymous_namespace{make_join_hypergraph.cc}::RotateLeft

(

RelationalExpression *

op

)

Opposite of RotateRight; that is:

(A <op2> B) <op> C => A <op2> (B <op> C)

See RotateRight for details.

RotateRight()

void anonymous_namespace{make_join_hypergraph.cc}::RotateRight

(

RelationalExpression *

op

)

Applies the following rewrite on <op>:

A <op> (B <op2> C) => (A <op> B) <op2> C

Importantly, the pointer <op> still points to the new top node (that is, <op2>), so you don't need to rewrite any nodes higher up in the tree. Join conditions and types are left as-is, ie., if <op2> is a LEFT JOIN, it will remain one.

Does not check that the transformation is actually legal.

ShouldCompleteMeshForCondition()

bool anonymous_namespace{make_join_hypergraph.cc}::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.

Currently, we only support full mesh, ie., those where all tables involved in the multi-equality are part of the same companion set. One could imagine a multi-equality where not all tables are possible to mesh, e.g. {t1,t2,t3,t4} where {t1,t2,t3} are on the left side of an outer join and t4 is on the right side (and thus not part of the same companion set); if so, we could have created a mesh of the three first ones, but we don't currently.

SortPredicates()

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.

UnflattenInnerJoins()

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.

UsedTablesForCondition()

table_map anonymous_namespace{make_join_hypergraph.cc}::UsedTablesForCondition

(

const RelationalExpression &

expr

)

Find a bitmap of used tables for all conditions on <expr>.

Note that after all conditions have been pushed, you can check expr.conditions_used_tables instead (see FindConditionsUsedTables()).

NOTE: The map might be wider than expr.tables_in_subtree due to multiple equalities; you should normally just ignore those bits.