MySQL 8.2.0
Source Code Documentation
Go to the documentation of this file.
1/* Copyright (c) 2021, 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 */
27 @file
29 Heuristic simplification of query graphs to make them execute faster,
30 largely a direct implementation of [Neu09] (any references to just
31 “the paper” will generally be to that). This is needed for when
32 query hypergraphs have too many possible (connected) subgraphs to
33 evaluate all of them, and we need to resort to heuristics.
35 The algorithm works by evaluating pairs of neighboring joins
36 (largely, those that touch some of the same tables), finding obviously _bad_
37 pairwise orderings and then disallowing them. I.e., if join A must
38 very likely happen before join B (as measured by cost heuristics),
39 we disallow the B-before-A join by extending the hyperedge of
40 B to include A's nodes. This makes the graph more visually complicated
41 (thus making “simplification” a bit of a misnomer), but reduces the search
42 space, so that the query generally is faster to plan.
44 Obviously, as the algorithm is greedy, it will sometimes make mistakes
45 and make for a more expensive (or at least higher-cost) query.
46 This isn't necessarily an optimal or even particularly good algorithm;
47 e.g. LinDP++ [Rad19] claims significantly better results, especially
48 on joins that are 40 tables or more. However, using graph simplification
49 allows us to handle large queries reasonably well, while still reusing nearly
50 all of our query planning machinery (i.e., we don't have to implement a
51 separate query planner and cost model for large queries).
53 Also note that graph simplification only addresses the problem of subgraph
54 pair explosion. If each subgraph pair generates large amounts of candidate
55 access paths (e.g. through parameterized paths), each subgraph pair will in
56 itself be expensive, and graph simplification does not concern itself with
57 this at all. Thus, to get a complete solution, we must _also_ have heuristic
58 pruning of access paths within a subgraph, which we're currently missing.
61 [Neu09] Neumann: “Query Simplification: Graceful Degradation for Join-Order
62 Optimization”.
63 [Rad19] Radke and Neumann: “LinDP++: Generalizing Linearized DP to
64 Crossproducts and Non-Inner Joins”.
65 */
67#include <stddef.h>
69#include <string>
70#include <vector>
72#include "my_compiler.h"
73#include "priority_queue.h"
76#include "sql/mem_root_array.h"
77#include "sql/sql_array.h"
79class THD;
80struct JoinHypergraph;
81struct MEM_ROOT;
82template <class T>
85// Exposed for unit testing.
87 public:
90 // Do a single simplification step. The return enum is mostly for unit tests;
91 // general code only needs to care about whether it returned
94 // No (more) simplifications are possible on this hypergraph.
97 // We applied a simplification of the graph (forcing one join ahead of
98 // another).
101 // We applied a simplification, but it was one that was forced upon us;
102 // we intended to apply the opposite, but discovered it would leave the
103 // graph
104 // in an impossible state. Thus, the graph has been changed, but the actual
105 // available join orderings are exactly as they were.
108 // We applied a step that was earlier undone using UndoSimplificationStep().
109 // (We do not know whether it was originally APPLIED_SIMPLIFICATION or
112 };
115 // Undo the last applied simplification step (by DoSimplificationStep()).
116 // Note that this does not reset the internal state, i.e., it only puts
117 // the graph back into the state before the last DoSimplificationStep()
118 // call. This means that the internal happens-before graph and cardinalities
119 // remain as if the step was still done. This is because if calling
120 // DoSimplificationStep() after an UndoSimplificationStep() call,
121 // no new work is done; the change is simply replayed again, with no
122 // new computation done. We only need to search for more simplifications
123 // once we've replayed all undone steps. This also means that we make
124 // the assumption that nobody else is changing the graph during the
125 // lifetime of GraphSimplifier.
126 //
127 // You can call UndoSimplificationStep() several times, as long as there
128 // is at least one simplification step to undo; undo/redo works essentially
129 // as a stack.
132 // How many steps we've (successfully) done and not undone.
133 int num_steps_done() const {
134 assert(m_done_steps.size() < size_t{std::numeric_limits<int>::max()});
135 return static_cast<int>(m_done_steps.size());
136 }
138 // How many steps we've undone.
139 int num_steps_undone() const {
140 assert(m_undone_steps.size() < size_t{std::numeric_limits<int>::max()});
141 return static_cast<int>(m_undone_steps.size());
142 }
144 private:
145 // Update the given join's cache in the priority queue (or take it in
146 // or out of the queue), presumably after best_step.benefit has changed
147 // for that join.
148 //
149 // After this operation, m_pq should be in a consistent state.
150 void UpdatePQ(size_t edge_idx);
152 // Recalculate the benefit of all orderings involving the given edge,
153 // i.e., the advantage of ordering any other neighboring join before
154 // or after it. (These are stored in m_cache; see NeighborCache for
155 // more information on the scheme.) You will typically need to call this
156 // after having modified the given join (hyperedge endpoint). Note that
157 // if a given ordering has become less advantageous, this may entail
158 // recalculating other nodes recursively as well, but this should be rare
159 // (again, see the comments on NeighborCache).
160 //
161 // “begin” and “end” are the range of other joins to compare against
162 // (edge1_idx itself is always excluded). It should normally be set to
163 // 0 and N (the number of edges) to compare against all, but during the
164 // initial population in the constructor, where every pair is considered,
165 // it is be used to avoid redundant computation.
166 //
167 // It would have been nice to somehow be able to use neighbor-of-neighbor
168 // information to avoid rescanning all candidates for neighbors
169 // (and the paper mentions “materializing all neighbors of a join”),
170 // but given how hyperedges work, there doesn't seem to be a trivial way
171 // of doing that (after A has absorbed B's into one of its hyperedges,
172 // it seems it could gain new neighbors that were neither neighbors of
173 // A nor B).
174 void RecalculateNeighbors(size_t edge1_idx, size_t begin, size_t end);
177 double benefit;
180 };
182 // Returns whether two joins are neighboring (share edges),
183 // and if so, estimates the benefit of joining one before the other
184 // (including which one should be first) and writes into “step”.
185 ALWAYS_INLINE bool EdgesAreNeighboring(size_t edge1_idx, size_t edge2_idx,
192 // Old and new versions of after_edge_idx.
195 };
197 // Convert a simplification step (join A before join B) to an actual
198 // idea of how to modify the given edge (new values for join B's
199 // hyperedge endpoints).
203 // Steps that we have applied so far, in chronological order.
204 // Used so that we can undo them easily on UndoSimplificationStep().
207 // Steps that we used to have applied, but have undone, in chronological
208 // order of the undo (ie., latest undone step last).
209 // DoSimplificationStep() will use these to quickly reapply an undone
210 // step if needed (and then move it to the end of done_steps again).
213 // Cache the cardinalities of (a join of) the nodes on each side of each
214 // hyperedge, corresponding 1:1 index-wise to m_graph->edges. So if
215 // e.g. m_graph->graph.edges[0].left contains {t1,t2,t4}, then
216 // m_edge_cardinalities[0].left will contain the cardinality of joining
217 // t1, t2 and t4 together.
218 //
219 // This cache is so that we don't need to make repeated calls to
220 // GetCardinality(), which is fairly expensive. It is updated when we
221 // apply simplification steps (which change the hyperedges).
223 double left;
224 double right;
225 };
228 // The graph we are simplifying.
231 // Stores must-happen-before relationships between the joins (edges),
232 // so that we don't end up with impossibilities. See OnlineCycleFinder
233 // for more information.
236 // Used for storing which neighbors are possible to simplify,
237 // and how attractive they are. This speeds up repeated application of
238 // DoSimplificationStep() significantly, as we don't have to recompute
239 // the same information over and over again. This is keyed on the numerically
240 // lowest join of the join pair, i.e., information about the benefit of
241 // ordering join A before or after join B is stored on m_cache[min(A,B)].
242 // These take part in a priority queue (see m_pq below), so that we always
243 // know cheaply which one is the most attractive.
244 //
245 // There is a maybe surprising twist here; for any given cache node (join),
246 // we only store the most beneficial ordering, and throw away all others.
247 // This is because our benefit values keep changing all the time; once we've
248 // chosen to put A before B, it means we've changed B, and that means every
249 // single join pair involving B now needs to be recalculated anyway
250 // (the costs, and thus ordering benefits, are highly dependent on the
251 // hyperedge of B). Thus, storing only the best one (and by extension,
252 // not having information about the other ones in the priority queue)
253 // allows us to very quickly and easily throw away half of the invalidated
254 // ones. We still need to check the other half (the ones that may be the best
255 // for other nodes) to see if we need to invalidate them, but actual
256 // invalidation is rare, as it only happens for the best simplification
257 // involving that node (i.e., 1/N).
258 //
259 // It's unclear if this is the same scheme that the paper alludes to;
260 // it mentions a priority queue and ordering by neighbor-involving joins,
261 // but very little detail.
263 // The best simplification involving this join and a higher-indexed join,
264 // and the index of that other node. (best_neighbor could be inferred
265 // from the indexes in best_step and this index, but we keep it around
266 // for simplicity.) best_neighbor == -1 indicates that there are no
267 // possible reorderings involving this join and a higher-indexed one
268 // (so it should not take part in the priority queue).
272 // Where we are in the priority queue (heap index);
273 // Priority_queue will update this for us (through MarkNeighborCache)
274 // whenever we are insert into or moved around in the queue.
275 // This is so that we can easily tell the PQ to recalculate our position
276 // whenever best_step.benefit changes. -1 means that we are
277 // currently not in the priority queue.
278 int index_in_pq = -1;
279 };
282 // A priority queue of which simplifications are the most attractive,
283 // containing pointers into m_cache. See the documentation on NeighborCache
284 // for more information.
286 bool operator()(const NeighborCache *a, const NeighborCache *b) const {
287 return a->best_step.benefit < b->best_step.benefit;
288 }
289 };
291 void operator()(size_t index, NeighborCache **cache) {
292 (*cache)->index_in_pq = index;
293 }
294 };
296 NeighborCache *,
297 std::vector<NeighborCache *, Mem_root_allocator<NeighborCache *>>,
298 CompareByBenefit, MarkNeighborCache>
302void SetNumberOfSimplifications(int num_simplifications,
303 GraphSimplifier *simplifier);
305// See comment in .cc file.
306void SimplifyQueryGraph(THD *thd, int subgraph_pair_limit,
307 JoinHypergraph *graph, GraphSimplifier *simplifier,
308 std::string *trace);
A wrapper class which provides array bounds checking.
Definition: sql_array.h:46
Definition: graph_simplification.h:86
ALWAYS_INLINE bool EdgesAreNeighboring(size_t edge1_idx, size_t edge2_idx, ProposedSimplificationStep *step)
Bounds_checked_array< NeighborCache > m_cache
Definition: graph_simplification.h:280
Bounds_checked_array< EdgeCardinalities > m_edge_cardinalities
Definition: graph_simplification.h:226
void RecalculateNeighbors(size_t edge1_idx, size_t begin, size_t end)
SimplificationStep ConcretizeSimplificationStep(GraphSimplifier::ProposedSimplificationStep step)
JoinHypergraph * m_graph
Definition: graph_simplification.h:229
Definition: graph_simplification.h:93
Definition: graph_simplification.h:111
Definition: graph_simplification.h:95
Definition: graph_simplification.h:99
Definition: graph_simplification.h:106
void UndoSimplificationStep()
SimplificationResult DoSimplificationStep()
Mem_root_array< SimplificationStep > m_undone_steps
Definition: graph_simplification.h:211
void UpdatePQ(size_t edge_idx)
int num_steps_done() const
Definition: graph_simplification.h:133
int num_steps_undone() const
Definition: graph_simplification.h:139
Priority_queue< NeighborCache *, std::vector< NeighborCache *, Mem_root_allocator< NeighborCache * > >, CompareByBenefit, MarkNeighborCache > m_pq
Definition: graph_simplification.h:299
OnlineCycleFinder m_cycles
Definition: graph_simplification.h:234
Mem_root_array< SimplificationStep > m_done_steps
Definition: graph_simplification.h:205
GraphSimplifier(JoinHypergraph *graph, MEM_ROOT *mem_root)
Mem_root_allocator is a C++ STL memory allocator based on MEM_ROOT.
Definition: mem_root_allocator.h:67
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
A fast online cycle finder, based on [Pea03].
Definition: online_cycle_finder.h:53
Implements a priority queue using a vector-based max-heap.
Definition: priority_queue.h:103
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:35
static MEM_ROOT mem_root
void SimplifyQueryGraph(THD *thd, int subgraph_pair_limit, JoinHypergraph *graph, GraphSimplifier *simplifier, std::string *trace)
void SetNumberOfSimplifications(int num_simplifications, GraphSimplifier *simplifier)
Definition of an undirected (join) hypergraph.
Header for compiler-dependent features.
Definition: my_compiler.h:98
void * begin(THD *thd, const TABLE *table, size_t data_size, size_t memory, size_t num_threads) noexcept
Cursor end()
A past-the-end Cursor.
Definition: graph_simplification.h:285
bool operator()(const NeighborCache *a, const NeighborCache *b) const
Definition: graph_simplification.h:286
Definition: graph_simplification.h:222
double left
Definition: graph_simplification.h:223
double right
Definition: graph_simplification.h:224
Definition: graph_simplification.h:290
void operator()(size_t index, NeighborCache **cache)
Definition: graph_simplification.h:291
Definition: graph_simplification.h:262
int best_neighbor
Definition: graph_simplification.h:269
ProposedSimplificationStep best_step
Definition: graph_simplification.h:270
int index_in_pq
Definition: graph_simplification.h:278
Definition: graph_simplification.h:176
int before_edge_idx
Definition: graph_simplification.h:178
int after_edge_idx
Definition: graph_simplification.h:179
double benefit
Definition: graph_simplification.h:177
Definition: graph_simplification.h:188
int after_edge_idx
Definition: graph_simplification.h:190
int before_edge_idx
Definition: graph_simplification.h:189
hypergraph::Hyperedge new_edge
Definition: graph_simplification.h:194
hypergraph::Hyperedge old_edge
Definition: graph_simplification.h:193
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:77
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Definition: hypergraph.h:79