MySQL 8.0.33
Source Code Documentation
build_interesting_orders.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, 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 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.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
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 */
22
23#ifndef SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
24#define SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
25
28
29#include <string>
30
31class Item_func_match;
32template <class T>
33class Mem_root_array;
34class Query_block;
35class THD;
36struct JoinHypergraph;
37struct ORDER;
38struct TABLE;
39
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,
43// PARTITION BY or DISTINCT.
45 // Pointer to an ordering in LogicalOrderings.
47
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.
69
70 // Whether aggregates must be computed before one can apply this sort
71 // (because it includes at least one aggregate).
73
74 // The ordering expressed in a form that filesort can use.
76};
77
78// An index that we can use in the query, either for index lookup (ref access)
79// or for scanning along to get an interesting ordering.
85};
86
87// A full-text index that we can use in the query, either for index lookup or
88// for scanning along to get an interesting order.
92};
93
94/**
95 Build all structures we need for keeping track of interesting orders.
96 We collect the actual relevant orderings (e.g. from ORDER BY) and any
97 functional dependencies we can find, then ask LogicalOrderings to create
98 its state machine (as defined in interesting_orders.h). The result is
99 said state machine, a list of potential sort-ahead orderings,
100 and a list of what indexes we can use to scan each table (including
101 what orderings they yield, if they are interesting).
102 */
104 THD *thd, JoinHypergraph *graph, Query_block *query_block,
105 LogicalOrderings *orderings,
106 Mem_root_array<SortAheadOrdering> *sort_ahead_orderings,
107 int *order_by_ordering_idx, int *group_by_ordering_idx,
108 int *distinct_ordering_idx, Mem_root_array<ActiveIndexInfo> *active_indexes,
109 Mem_root_array<FullTextIndexInfo> *fulltext_searches, std::string *trace);
110
111// Build an ORDER * that we can give to Filesort. It is only suitable for
112// sort-ahead, since it assumes no temporary tables have been inserted.
113// It can however be used after temporary tables if
114// ReplaceOrderItemsWithTempTableFields() is called on it, and
115// FinalizePlanForQueryBlock() takes care of this for us.
116ORDER *BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings,
117 Ordering ordering);
118
119/**
120 Creates a reduced ordering for the ordering or grouping specified by
121 "ordering_idx". It is assumed that the ordering happens after all joins and
122 filters, so that all functional dependencies are active. All parts of the
123 ordering that are made redundant by functional dependencies, are removed.
124
125 The returned ordering may be empty if all elements are redundant. This happens
126 if all elements are constants, or have predicates that ensure they are
127 constant.
128 */
129Ordering ReduceFinalOrdering(THD *thd, const LogicalOrderings &orderings,
130 int ordering_idx);
131
132#endif // SQL_JOIN_OPTIMIZER_BUILD_INTERESTING_ORDERS_H_
ORDER * BuildSortAheadOrdering(THD *thd, const LogicalOrderings *orderings, Ordering ordering)
Definition: build_interesting_orders.cc:285
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: build_interesting_orders.cc:383
Definition: item_func.h:3387
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:1155
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:33
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:80
LogicalOrderings::StateIndex reverse_order
Definition: build_interesting_orders.h:83
int key_idx
Definition: build_interesting_orders.h:82
LogicalOrderings::StateIndex reverse_order_without_extended_key_parts
Definition: build_interesting_orders.h:84
LogicalOrderings::StateIndex forward_order
Definition: build_interesting_orders.h:83
TABLE * table
Definition: build_interesting_orders.h:81
Definition: build_interesting_orders.h:89
LogicalOrderings::StateIndex order
Definition: build_interesting_orders.h:91
Item_func_match * match
Definition: build_interesting_orders.h:90
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:76
Definition: table.h:280
Definition: build_interesting_orders.h:44
ORDER * order
Definition: build_interesting_orders.h:75
bool aggregates_required
Definition: build_interesting_orders.h:72
hypergraph::NodeMap required_nodes
Definition: build_interesting_orders.h:68
int ordering_idx
Definition: build_interesting_orders.h:46
Definition: table.h:1395