build_interesting_orders.cc File Reference

#include "sql/join_optimizer/build_interesting_orders.h"
#include <assert.h>
#include <stdio.h>
#include <algorithm>
#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/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/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 Ordering::Elements	CollectInterestingOrder (THD *thd, ORDER *order, int order_len, bool unwrap_rollup, LogicalOrderings *orderings)
static Ordering::Elements	CollectInterestingOrder (THD *thd, const SQL_I_List< ORDER > &order_list, 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...
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< FullTextIndexInfo > *fulltext_searches, string *trace)

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< FullTextIndexInfo > *	fulltext_searches,
		string *	trace
	)

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() [1/2]

static Ordering::Elements CollectInterestingOrder ( THD *  thd, const SQL_I_List< ORDER > &  order_list, bool  unwrap_rollup, LogicalOrderings *  orderings  )

static

CollectInterestingOrder() [2/2]

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

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.