MySQL 8.4.3
Source Code Documentation
build_interesting_orders.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
25#define SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
26
29
30class Item_func_match;
31template <class T>
32class Mem_root_array;
33class Query_block;
34class THD;
35struct JoinHypergraph;
36struct ORDER;
37struct TABLE;
38
39// An ordering that we could be doing sort-ahead by; typically either an
40// interesting ordering or an ordering homogenized from one. It also includes
41// orderings that are used for sort-for-grouping, i.e. for GROUP BY,
42// PARTITION BY or DISTINCT.
43//
44// "Sort-ahead" means explicitly sorting rows (by adding a SORT access path) in
45// a way that could become beneficial to an operation later in the query
46// processing. The sort-ahead could come immediately before the operation that
47// can benefit from it (like a SORT on the GROUP BY columns just before the
48// AGGREGATE access path), or it can be further down in the access path tree if
49// all the intermediate access paths preserve the ordering (like sorting the
50// outer table of a nested loop join in order to satisfy the ordering
51// requirements of GROUP BY or ORDER BY after the join).
53 // Pointer to an ordering in LogicalOrderings.
55
56 // Which tables must be present in the join before one can apply
57 // this sort (usually because the elements we sort by are contained
58 // in these tables).
59 //
60 // The presence of RAND_TABLE_BIT means that the ordering contains
61 // at least one nondeterminstic item; we never allow pushing such
62 // orderings into the join (implicitly: sortahead during joins check
63 // required_nodes, and never include RAND_TABLE_BIT). This makes sure that we
64 // cannot push e.g. ORDER BY rand() into the left side of a join, which would
65 // make rows shuffled on that table only, which isn't what the user would
66 // expect. We also have special logic to disallow satisfying nondeterministic
67 // groupings/orderings others (both in the logic for group covers, and in NFSM
68 // construction), so that
69 //
70 // GROUP BY a ORDER BY a, func()
71 //
72 // cannot be done by evaluating func() too early, but we do allow exact
73 // matches, so that e.g. GROUP BY func() ORDER BY func() can be done as only
74 // one sort (which isn't too unreasonable). This may be a bit conservative
75 // or it may be a bit aggressive, depending on who you ask.
77
78 // Whether aggregates must be computed before one can apply this sort
79 // (because it includes at least one aggregate).
81
82 /// True if this ordering can be used for sort-ahead only, and not for sorting
83 /// after the joining and aggregation are done (that is, sorting for DISTINCT,
84 /// WINDOW or ORDER BY). This flag is set for orderings on expressions that
85 /// have not been added to join->fields, and their availability cannot be
86 /// relied on at the end of the query execution, as they are not included in
87 /// the temporary table if there is a materialization step. If an ordering
88 /// marked as sort-ahead-only is actually useful after aggregation, there is
89 /// usually an equivalent ordering using expressions that do exist in
90 /// join->fields, and that can be used instead.
92
93 // The ordering expressed in a form that filesort can use.
95};
96
97// An index that we can use in the query, either for index lookup (ref access)
98// or for scanning along to get an interesting ordering.
104};
105
106// A spatial index that we can use in a knn query to get an interesting
107// ordering.
112 // MBR coordinates to be passed to QUICK_RANGE.
113 // QUICK_RANGE needs at least one extra byte at the end (TODO:fix that).
114 double coordinates[5];
115};
116
117// A full-text index that we can use in the query, either for index lookup or
118// for scanning along to get an interesting order.
122};
123
124/**
125 Build all structures we need for keeping track of interesting orders.
126 We collect the actual relevant orderings (e.g. from ORDER BY) and any
127 functional dependencies we can find, then ask LogicalOrderings to create
128 its state machine (as defined in interesting_orders.h). The result is
129 said state machine, a list of potential sort-ahead orderings,
130 and a list of what indexes we can use to scan each table (including
131 what orderings they yield, if they are interesting).
132 */
134 THD *thd, JoinHypergraph *graph, Query_block *query_block,
135 LogicalOrderings *orderings,
136 Mem_root_array<SortAheadOrdering> *sort_ahead_orderings,
137 int *order_by_ordering_idx, int *group_by_ordering_idx,
138 int *distinct_ordering_idx, Mem_root_array<ActiveIndexInfo> *active_indexes,
140 Mem_root_array<FullTextIndexInfo> *fulltext_searches);
141
142// Build an ORDER * that we can give to Filesort. It is only suitable for
143// sort-ahead, since it assumes no temporary tables have been inserted.
144// It can however be used after temporary tables if
145// ReplaceOrderItemsWithTempTableFields() is called on it, and
146// FinalizePlanForQueryBlock() takes care of this for us.
147ORDER *BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings,
148 Ordering ordering);
149
150/**
151 Creates a reduced ordering for the ordering or grouping specified by
152 "ordering_idx". It is assumed that the ordering happens after all joins and
153 filters, so that all functional dependencies are active. All parts of the
154 ordering that are made redundant by functional dependencies, are removed.
155
156 The returned ordering may be empty if all elements are redundant. This happens
157 if all elements are constants, or have predicates that ensure they are
158 constant.
159 */
160Ordering ReduceFinalOrdering(THD *thd, const LogicalOrderings &orderings,
161 int ordering_idx);
162
163#endif // SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
ORDER * BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings, Ordering ordering)
Definition: build_interesting_orders.cc:288
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.
Definition: build_interesting_orders.cc:453
Ordering ReduceFinalOrdering(THD *thd, const LogicalOrderings &orderings, int ordering_idx)
Creates a reduced ordering for the ordering or grouping specified by "ordering_idx".
Definition: build_interesting_orders.cc:386
Definition: item_func.h:3465
Definition: interesting_orders.h:315
int StateIndex
Definition: interesting_orders.h:426
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:426
Represents a (potentially interesting) ordering, rollup or (non-rollup) grouping.
Definition: interesting_orders.h:160
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1163
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
Tracks which tuple streams follow which orders, and in particular whether they follow interesting ord...
uint64_t NodeMap
Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 6...
Definition: node_map.h:40
Definition: build_interesting_orders.h:99
LogicalOrderings::StateIndex reverse_order
Definition: build_interesting_orders.h:102
int key_idx
Definition: build_interesting_orders.h:101
LogicalOrderings::StateIndex reverse_order_without_extended_key_parts
Definition: build_interesting_orders.h:103
LogicalOrderings::StateIndex forward_order
Definition: build_interesting_orders.h:102
TABLE * table
Definition: build_interesting_orders.h:100
Definition: build_interesting_orders.h:119
LogicalOrderings::StateIndex order
Definition: build_interesting_orders.h:121
Item_func_match * match
Definition: build_interesting_orders.h:120
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:88
Definition: table.h:286
Definition: build_interesting_orders.h:52
ORDER * order
Definition: build_interesting_orders.h:94
bool aggregates_required
Definition: build_interesting_orders.h:80
bool sort_ahead_only
True if this ordering can be used for sort-ahead only, and not for sorting after the joining and aggr...
Definition: build_interesting_orders.h:91
hypergraph::NodeMap required_nodes
Definition: build_interesting_orders.h:76
int ordering_idx
Definition: build_interesting_orders.h:54
Definition: build_interesting_orders.h:108
LogicalOrderings::StateIndex forward_order
Definition: build_interesting_orders.h:111
int key_idx
Definition: build_interesting_orders.h:110
TABLE * table
Definition: build_interesting_orders.h:109
double coordinates[5]
Definition: build_interesting_orders.h:114
Definition: table.h:1406