#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, 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)

static size_t	CountOrderElements (const ORDER *order)

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)

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,
		LogicalOrderings *	orderings
	)

static

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

◆ AddOrdering()

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

static

◆ 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()

static size_t CountOrderElements ( const ORDER * order )

static

◆ 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()

◆ BuildInterestingOrders()

◆ BuildSortAheadOrdering()

◆ CanonicalizeGrouping()

◆ CollectFunctionalDependenciesFromJoins()

◆ CollectFunctionalDependenciesFromPredicates()

◆ CollectFunctionalDependenciesFromUniqueIndexes()

◆ CollectInterestingOrder()

◆ CollectOrderingsFromSpatialIndex()

◆ CountOrderElements()

◆ FindOrderElementInORDER()

◆ ReduceFinalOrdering()

◆ RemoveRedundantOrderElements()