MySQL 9.0.0
Source Code Documentation
build_interesting_orders.cc File Reference
#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)
 
ORDERBuildSortAheadOrdering (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 ORDERFindOrderElementInORDER (OrderElement element, ORDER *order, const LogicalOrderings &orderings)
 Find the ORDER objects pointing corresponding to a given OrderElement. More...
 
static ORDERRemoveRedundantOrderElements (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
orderPointer to the first element of the original ORDER BY clause.
reduced_orderingAn Ordering object that contains only the non-redundant elements of "order".
orderingsThe logical orderings.
Returns
Pointer to the first element of the reduced ordering.