#include "sql/join_optimizer/build_interesting_orders.h"
#include <assert.h>
#include <stdio.h>
#include <algorithm>
#include <bit>
#include <string>
#include <utility>
#include "ft_global.h"
#include "my_alloc.h"
#include "my_base.h"
#include "my_table_map.h"
#include "mysql/udf_registration_types.h"
#include "sql/field.h"
#include "sql/gis/mbr_utils.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/item_row.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/interesting_orders.h"
#include "sql/join_optimizer/interesting_orders_defs.h"
#include "sql/join_optimizer/make_join_hypergraph.h"
#include "sql/join_optimizer/optimizer_trace.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/key.h"
#include "sql/key_spec.h"
#include "sql/mem_root_array.h"
#include "sql/sql_array.h"
#include "sql/sql_bitmap.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/sql_resolver.h"
#include "sql/sql_select.h"
#include "sql/table.h"
#include "sql/window.h"
#include "template_utils.h"

Functions
static int	AddFunctionalDependencyFromCondition (THD thd, Item condition, bool always_active, bool possibly_null_complemented_later, LogicalOrderings *orderings)
	Helper for CollectFunctionalDependenciesFromPredicates(); also used for non-equijoin predicates in CollectFunctionalDependenciesFromJoins(). More...

static void	CollectFunctionalDependenciesFromJoins (THD thd, JoinHypergraph graph, LogicalOrderings *orderings)
	Collect functional dependencies from joins. More...

static void	CollectFunctionalDependenciesFromPredicates (THD thd, JoinHypergraph graph, LogicalOrderings *orderings)
	Collect functional dependencies from non-join predicates. More...

static void	CollectFunctionalDependenciesFromUniqueIndexes (THD thd, JoinHypergraph graph, LogicalOrderings *orderings)

size_t	CountOrderElements (const ORDER *order)
	Simply counts the ORDER elements. More...

static Ordering::Elements	CollectInterestingOrder (THD thd, const ORDER order, bool unwrap_rollup, LogicalOrderings *orderings)

ORDER *	BuildSortAheadOrdering (THD thd, const LogicalOrderings orderings, Ordering ordering)

static int	AddOrdering (THD thd, Ordering ordering, bool used_at_end, table_map homogenize_tables, LogicalOrderings orderings)

static void	CanonicalizeGrouping (Ordering::Elements *elements)

static ORDER *	FindOrderElementInORDER (OrderElement element, ORDER *order, const LogicalOrderings &orderings)
	Find the ORDER objects pointing corresponding to a given OrderElement. More...

static ORDER *	RemoveRedundantOrderElements (ORDER *order, Ordering reduced_ordering, const LogicalOrderings &orderings)
	Remove all redundant elements from a chain of ORDERs by modifying the next pointers in the intrusive list. More...

Ordering	ReduceFinalOrdering (THD *thd, const LogicalOrderings &orderings, int ordering_idx)
	Creates a reduced ordering for the ordering or grouping specified by "ordering_idx". More...

static void	CollectOrderingsFromSpatialIndex (THD thd, TABLE table, int key_idx, LogicalOrderings orderings, Mem_root_array< SpatialDistanceScanInfo > spatial_indexes)

static IndexOrderingInfo	BuildIndexOrderings (THD thd, LogicalOrderings orderings, TABLE *table, int key_idx, int first_key_part, int num_key_parts, int num_user_defined_key_parts)
	Register the orderings that a scan along a window of an index's key parts delivers. More...

void	BuildInterestingOrders (THD thd, JoinHypergraph graph, Query_block query_block, LogicalOrderings orderings, Mem_root_array< SortAheadOrdering > sort_ahead_orderings, int order_by_ordering_idx, int group_by_ordering_idx, int distinct_ordering_idx, Mem_root_array< ActiveIndexInfo > active_indexes, Mem_root_array< SpatialDistanceScanInfo > spatial_indexes, Mem_root_array< FullTextIndexInfo > *fulltext_searches)
	Build all structures we need for keeping track of interesting orders. More...

Function Documentation

◆ AddFunctionalDependencyFromCondition()

static int AddFunctionalDependencyFromCondition	(	THD *	thd,
		Item *	condition,
		bool	always_active,
		bool	possibly_null_complemented_later,
		LogicalOrderings *	orderings
	)

static

Helper for CollectFunctionalDependenciesFromPredicates(); also used for non-equijoin predicates in CollectFunctionalDependenciesFromJoins().

Parameters

thd	Current thread.
condition	The condition to analyze.
always_active	Whether the functional dependencies are active in the entire join tree. Functional dependencies from table filters are considered always active, whereas join predicates are only active after the join has been performed.
possibly_null_complemented_later	If this is true, the condition is applied in some part of the join tree that is inner to an outer join, and the referenced tables might get NULL-complemented by that outer join. In these cases, don't collect functional dependencies from the condition if they don't hold in NULL-complemented rows.
orderings	The logical orderings.

Returns: The index of the collected functional dependency, or -1 if no functional dependency was collected.

◆ AddOrdering()

static int AddOrdering	(	THD *	thd,
		Ordering	ordering,
		bool	used_at_end,
		table_map	homogenize_tables,
		LogicalOrderings *	orderings
	)

static

◆ BuildIndexOrderings()

static IndexOrderingInfo BuildIndexOrderings	(	THD *	thd,
		LogicalOrderings *	orderings,
		TABLE *	table,
		int	key_idx,
		int	first_key_part,
		int	num_key_parts,
		int	num_user_defined_key_parts
	)

static

Register the orderings that a scan along a window of an index's key parts delivers.

Parameters

thd	Thread handle.
orderings	The orderings to register in.
table	The table the index belongs to.
key_idx	The index, as an offset into table->key_info.
first_key_part	The first key part of the window.
num_key_parts	The number of key parts in the window; must be > 0.
num_user_defined_key_parts	How many of the key parts in the window are user-defined, that is, not appended from the primary key; at most num_key_parts. May be zero, in which case no ordering without the extended key parts is registered.

Returns: The registered orderings. The reverse ones are left at zero if the index cannot be scanned backwards.

◆ BuildInterestingOrders()

void BuildInterestingOrders	(	THD *	thd,
		JoinHypergraph *	graph,
		Query_block *	query_block,
		LogicalOrderings *	orderings,
		Mem_root_array< SortAheadOrdering > *	sort_ahead_orderings,
		int *	order_by_ordering_idx,
		int *	group_by_ordering_idx,
		int *	distinct_ordering_idx,
		Mem_root_array< ActiveIndexInfo > *	active_indexes,
		Mem_root_array< SpatialDistanceScanInfo > *	spatial_indexes,
		Mem_root_array< FullTextIndexInfo > *	fulltext_searches
	)

Build all structures we need for keeping track of interesting orders.

We collect the actual relevant orderings (e.g. from ORDER BY) and any functional dependencies we can find, then ask LogicalOrderings to create its state machine (as defined in interesting_orders.h). The result is said state machine, a list of potential sort-ahead orderings, and a list of what indexes we can use to scan each table (including what orderings they yield, if they are interesting).

◆ BuildSortAheadOrdering()

ORDER * BuildSortAheadOrdering	(	THD *	thd,
		const LogicalOrderings *	orderings,
		Ordering	ordering
	)

◆ CanonicalizeGrouping()

static void CanonicalizeGrouping ( Ordering::Elements * elements )

static

◆ CollectFunctionalDependenciesFromJoins()

static void CollectFunctionalDependenciesFromJoins	(	THD *	thd,
		JoinHypergraph *	graph,
		LogicalOrderings *	orderings
	)

static

Collect functional dependencies from joins.

Currently, we apply item = item only, and only on inner joins and semijoins. Outer joins do not enforce their equivalences unconditionally (e.g. with an outer join on t1.a = t2.b, t1.a = t2.b does not hold afterwards; t2.b could be NULL). Semijoins do, and even though the attributes from the inner side are inaccessible afterwards, there could still be interesting constant FDs that are applicable to the outer side after equivalences.

It is possible to generate a weaker form of FDs for outer joins, as described in sql/aggregate_check.h (and done for GROUP BY); e.g. from the join condition t1.x=t2.x AND t1.y=t2.y, one can infer a functional dependency {t1.x,t1.y} → t2.x and similar for t2.y. However, do note the comment about FD propagation in the calling function.

◆ CollectFunctionalDependenciesFromPredicates()

static void CollectFunctionalDependenciesFromPredicates	(	THD *	thd,
		JoinHypergraph *	graph,
		LogicalOrderings *	orderings
	)

static

Collect functional dependencies from non-join predicates.

Again, we only do item = item, and more interesting; we only take the raw items, where we could have been much more sophisticated. Imagine a predicate like a = b + c; we will add a FD saying exactly that (which may or may not be useful, if b + c shows up in ORDER BY), but we should probably also have added {b,c} → a, if b and c could be generated somehow.

However, we do special-case item = const, since they are so useful; they become {} → item instead.

◆ CollectFunctionalDependenciesFromUniqueIndexes()

static void CollectFunctionalDependenciesFromUniqueIndexes	(	THD *	thd,
		JoinHypergraph *	graph,
		LogicalOrderings *	orderings
	)

static

◆ CollectInterestingOrder()

static Ordering::Elements CollectInterestingOrder	(	THD *	thd,
		const ORDER *	order,
		bool	unwrap_rollup,
		LogicalOrderings *	orderings
	)

static

◆ CollectOrderingsFromSpatialIndex()

static void CollectOrderingsFromSpatialIndex	(	THD *	thd,
		TABLE *	table,
		int	key_idx,
		LogicalOrderings *	orderings,
		Mem_root_array< SpatialDistanceScanInfo > *	spatial_indexes
	)

static

◆ CountOrderElements()

size_t CountOrderElements ( const ORDER * order )

Simply counts the ORDER elements.

◆ FindOrderElementInORDER()

static ORDER * FindOrderElementInORDER	(	OrderElement	element,
		ORDER *	order,
		const LogicalOrderings &	orderings
	)

static

Find the ORDER objects pointing corresponding to a given OrderElement.

That is, return the first ORDER that has the same item and direction as the given OrderElement. It is assumed that there is a corresponding one.

◆ ReduceFinalOrdering()

Ordering ReduceFinalOrdering	(	THD *	thd,
		const LogicalOrderings &	orderings,
		int	ordering_idx
	)

Creates a reduced ordering for the ordering or grouping specified by "ordering_idx".

It is assumed that the ordering happens after all joins and filters, so that all functional dependencies are active. All parts of the ordering that are made redundant by functional dependencies, are removed.

The returned ordering may be empty if all elements are redundant. This happens if all elements are constants, or have predicates that ensure they are constant.

◆ RemoveRedundantOrderElements()

static ORDER * RemoveRedundantOrderElements	(	ORDER *	order,
		Ordering	reduced_ordering,
		const LogicalOrderings &	orderings
	)

static

Remove all redundant elements from a chain of ORDERs by modifying the next pointers in the intrusive list.

Parameters

order	Pointer to the first element of the original ORDER BY clause.
reduced_ordering	An Ordering object that contains only the non-redundant elements of "order".
orderings	The logical orderings.

Returns: Pointer to the first element of the reduced ordering.

Functions

Function Documentation

◆ AddFunctionalDependencyFromCondition()

◆ AddOrdering()

◆ BuildIndexOrderings()

◆ BuildInterestingOrders()

◆ BuildSortAheadOrdering()

◆ CanonicalizeGrouping()

◆ CollectFunctionalDependenciesFromJoins()

◆ CollectFunctionalDependenciesFromPredicates()

◆ CollectFunctionalDependenciesFromUniqueIndexes()

◆ CollectInterestingOrder()

◆ CollectOrderingsFromSpatialIndex()

◆ CountOrderElements()

◆ FindOrderElementInORDER()

◆ ReduceFinalOrdering()

◆ RemoveRedundantOrderElements()