MySQL 8.2.0
Source Code Documentation
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, Oracle and/or its affiliates.
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.
7 This program is also distributed 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 included with MySQL.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 GNU General Public License, version 2.0, for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
29#include <string>
31class Item_func_match;
32template <class T>
33class Mem_root_array;
34class Query_block;
35class THD;
36struct JoinHypergraph;
37struct ORDER;
38struct TABLE;
40// An ordering that we could be doing sort-ahead by; typically either an
41// interesting ordering or an ordering homogenized from one. It also includes
42// orderings that are used for sort-for-grouping, i.e. for GROUP BY,
45 // Pointer to an ordering in LogicalOrderings.
48 // Which tables must be present in the join before one can apply
49 // this sort (usually because the elements we sort by are contained
50 // in these tables).
51 //
52 // The presence of RAND_TABLE_BIT means that the ordering contains
53 // at least one nondeterminstic item; we never allow pushing such
54 // orderings into the join (implicitly: sortahead during joins check
55 // required_nodes, and never include RAND_TABLE_BIT). This makes sure that we
56 // cannot push e.g. ORDER BY rand() into the left side of a join, which would
57 // make rows shuffled on that table only, which isn't what the user would
58 // expect. We also have special logic to disallow satisfying nondeterministic
59 // groupings/orderings others (both in the logic for group covers, and in NFSM
60 // construction), so that
61 //
62 // GROUP BY a ORDER BY a, func()
63 //
64 // cannot be done by evaluating func() too early, but we do allow exact
65 // matches, so that e.g. GROUP BY func() ORDER BY func() can be done as only
66 // one sort (which isn't too unreasonable). This may be a bit conservative
67 // or it may be a bit aggressive, depending on who you ask.
70 // Whether aggregates must be computed before one can apply this sort
71 // (because it includes at least one aggregate).
74 /// True if this ordering can be used for sort-ahead only, and not for sorting
75 /// after the joining and aggregation are done (that is, sorting for DISTINCT,
76 /// WINDOW or ORDER BY). This flag is set for orderings on expressions that
77 /// have not been added to join->fields, and their availability cannot be
78 /// relied on at the end of the query execution, as they are not included in
79 /// the temporary table if there is a materialization step. If an ordering
80 /// marked as sort-ahead-only is actually useful after aggregation, there is
81 /// usually an equivalent ordering using expressions that do exist in
82 /// join->fields, and that can be used instead.
85 // The ordering expressed in a form that filesort can use.
89// An index that we can use in the query, either for index lookup (ref access)
90// or for scanning along to get an interesting ordering.
98// A full-text index that we can use in the query, either for index lookup or
99// for scanning along to get an interesting order.
106 Build all structures we need for keeping track of interesting orders.
107 We collect the actual relevant orderings (e.g. from ORDER BY) and any
108 functional dependencies we can find, then ask LogicalOrderings to create
109 its state machine (as defined in interesting_orders.h). The result is
110 said state machine, a list of potential sort-ahead orderings,
111 and a list of what indexes we can use to scan each table (including
112 what orderings they yield, if they are interesting).
113 */
115 THD *thd, JoinHypergraph *graph, Query_block *query_block,
116 LogicalOrderings *orderings,
117 Mem_root_array<SortAheadOrdering> *sort_ahead_orderings,
118 int *order_by_ordering_idx, int *group_by_ordering_idx,
119 int *distinct_ordering_idx, Mem_root_array<ActiveIndexInfo> *active_indexes,
120 Mem_root_array<FullTextIndexInfo> *fulltext_searches, std::string *trace);
122// Build an ORDER * that we can give to Filesort. It is only suitable for
123// sort-ahead, since it assumes no temporary tables have been inserted.
124// It can however be used after temporary tables if
125// ReplaceOrderItemsWithTempTableFields() is called on it, and
126// FinalizePlanForQueryBlock() takes care of this for us.
127ORDER *BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings,
128 Ordering ordering);
131 Creates a reduced ordering for the ordering or grouping specified by
132 "ordering_idx". It is assumed that the ordering happens after all joins and
133 filters, so that all functional dependencies are active. All parts of the
134 ordering that are made redundant by functional dependencies, are removed.
136 The returned ordering may be empty if all elements are redundant. This happens
137 if all elements are constants, or have predicates that ensure they are
138 constant.
139 */
140Ordering ReduceFinalOrdering(THD *thd, const LogicalOrderings &orderings,
141 int ordering_idx);
ORDER * BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings, Ordering ordering)
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, std::string *trace)
Build all structures we need for keeping track of interesting orders.
Ordering ReduceFinalOrdering(THD *thd, const LogicalOrderings &orderings, int ordering_idx)
Creates a reduced ordering for the ordering or grouping specified by "ordering_idx".
Definition: item_func.h:3420
Definition: interesting_orders.h:313
int StateIndex
Definition: interesting_orders.h:426
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Represents a (potentially interesting) ordering, rollup or (non-rollup) grouping.
Definition: interesting_orders.h:158
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1161
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:35
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:39
Definition: build_interesting_orders.h:91
LogicalOrderings::StateIndex reverse_order
Definition: build_interesting_orders.h:94
int key_idx
Definition: build_interesting_orders.h:93
LogicalOrderings::StateIndex reverse_order_without_extended_key_parts
Definition: build_interesting_orders.h:95
LogicalOrderings::StateIndex forward_order
Definition: build_interesting_orders.h:94
TABLE * table
Definition: build_interesting_orders.h:92
Definition: build_interesting_orders.h:100
LogicalOrderings::StateIndex order
Definition: build_interesting_orders.h:102
Item_func_match * match
Definition: build_interesting_orders.h:101
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:77
Definition: table.h:283
Definition: build_interesting_orders.h:44
ORDER * order
Definition: build_interesting_orders.h:86
bool aggregates_required
Definition: build_interesting_orders.h:72
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:83
hypergraph::NodeMap required_nodes
Definition: build_interesting_orders.h:68
int ordering_idx
Definition: build_interesting_orders.h:46
Definition: table.h:1396