MySQL 8.0.32
Source Code Documentation
graph_simplification.h
Go to the documentation of this file.
1/* Copyright (c) 2021, 2022, 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_GRAPH_SIMPLIFICATION_H_
24#define SQL_JOIN_OPTIMIZER_GRAPH_SIMPLIFICATION_H_
25
26/**
27 @file
28
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.
34
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.
43
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).
52
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.
59
60
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 */
66
67#include <stddef.h>
68
69#include <string>
70#include <vector>
71
72#include "my_compiler.h"
73#include "priority_queue.h"
76#include "sql/mem_root_array.h"
77#include "sql/sql_array.h"
78
79class THD;
80struct JoinHypergraph;
81struct MEM_ROOT;
82template <class T>
84
85// Exposed for unit testing.
87 public:
89
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
92 // NO_SIMPLIFICATION_POSSIBLE or not.
94 // No (more) simplifications are possible on this hypergraph.
96
97 // We applied a simplification of the graph (forcing one join ahead of
98 // another).
100
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.
107
108 // We applied a step that was earlier undone using UndoSimplificationStep().
109 // (We do not know whether it was originally APPLIED_SIMPLIFICATION or
110 // APPLIED_NOOP.)
112 };
114
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.
131
132 // How many steps we've (successfully) done and not undone.
133 int num_steps_done() const { return m_done_steps.size(); }
134
135 private:
136 // Update the given join's cache in the priority queue (or take it in
137 // or out of the queue), presumably after best_step.benefit has changed
138 // for that join.
139 //
140 // After this operation, m_pq should be in a consistent state.
141 void UpdatePQ(size_t edge_idx);
142
143 // Recalculate the benefit of all orderings involving the given edge,
144 // i.e., the advantage of ordering any other neighboring join before
145 // or after it. (These are stored in m_cache; see NeighborCache for
146 // more information on the scheme.) You will typically need to call this
147 // after having modified the given join (hyperedge endpoint). Note that
148 // if a given ordering has become less advantageous, this may entail
149 // recalculating other nodes recursively as well, but this should be rare
150 // (again, see the comments on NeighborCache).
151 //
152 // “begin” and “end” are the range of other joins to compare against
153 // (edge1_idx itself is always excluded). It should normally be set to
154 // 0 and N (the number of edges) to compare against all, but during the
155 // initial population in the constructor, where every pair is considered,
156 // it is be used to avoid redundant computation.
157 //
158 // It would have been nice to somehow be able to use neighbor-of-neighbor
159 // information to avoid rescanning all candidates for neighbors
160 // (and the paper mentions “materializing all neighbors of a join”),
161 // but given how hyperedges work, there doesn't seem to be a trivial way
162 // of doing that (after A has absorbed B's into one of its hyperedges,
163 // it seems it could gain new neighbors that were neither neighbors of
164 // A nor B).
165 void RecalculateNeighbors(size_t edge1_idx, size_t begin, size_t end);
166
168 double benefit;
171 };
172
173 // Returns whether two joins are neighboring (share edges),
174 // and if so, estimates the benefit of joining one before the other
175 // (including which one should be first) and writes into “step”.
176 ALWAYS_INLINE bool EdgesAreNeighboring(size_t edge1_idx, size_t edge2_idx,
178
182
183 // Old and new versions of after_edge_idx.
186 };
187
188 // Convert a simplification step (join A before join B) to an actual
189 // idea of how to modify the given edge (new values for join B's
190 // hyperedge endpoints).
193
194 // Steps that we have applied so far, in chronological order.
195 // Used so that we can undo them easily on UndoSimplificationStep().
197
198 // Steps that we used to have applied, but have undone, in chronological
199 // order of the undo (ie., latest undone step last).
200 // DoSimplificationStep() will use these to quickly reapply an undone
201 // step if needed (and then move it to the end of done_steps again).
203
204 // Cache the cardinalities of (a join of) the nodes on each side of each
205 // hyperedge, corresponding 1:1 index-wise to m_graph->edges. So if
206 // e.g. m_graph->graph.edges[0].left contains {t1,t2,t4}, then
207 // m_edge_cardinalities[0].left will contain the cardinality of joining
208 // t1, t2 and t4 together.
209 //
210 // This cache is so that we don't need to make repeated calls to
211 // GetCardinality(), which is fairly expensive. It is updated when we
212 // apply simplification steps (which change the hyperedges).
214 double left;
215 double right;
216 };
218
219 // The graph we are simplifying.
221
222 // Stores must-happen-before relationships between the joins (edges),
223 // so that we don't end up with impossibilities. See OnlineCycleFinder
224 // for more information.
226
227 // Used for storing which neighbors are possible to simplify,
228 // and how attractive they are. This speeds up repeated application of
229 // DoSimplificationStep() significantly, as we don't have to recompute
230 // the same information over and over again. This is keyed on the numerically
231 // lowest join of the join pair, i.e., information about the benefit of
232 // ordering join A before or after join B is stored on m_cache[min(A,B)].
233 // These take part in a priority queue (see m_pq below), so that we always
234 // know cheaply which one is the most attractive.
235 //
236 // There is a maybe surprising twist here; for any given cache node (join),
237 // we only store the most beneficial ordering, and throw away all others.
238 // This is because our benefit values keep changing all the time; once we've
239 // chosen to put A before B, it means we've changed B, and that means every
240 // single join pair involving B now needs to be recalculated anyway
241 // (the costs, and thus ordering benefits, are highly dependent on the
242 // hyperedge of B). Thus, storing only the best one (and by extension,
243 // not having information about the other ones in the priority queue)
244 // allows us to very quickly and easily throw away half of the invalidated
245 // ones. We still need to check the other half (the ones that may be the best
246 // for other nodes) to see if we need to invalidate them, but actual
247 // invalidation is rare, as it only happens for the best simplification
248 // involving that node (i.e., 1/N).
249 //
250 // It's unclear if this is the same scheme that the paper alludes to;
251 // it mentions a priority queue and ordering by neighbor-involving joins,
252 // but very little detail.
254 // The best simplification involving this join and a higher-indexed join,
255 // and the index of that other node. (best_neighbor could be inferred
256 // from the indexes in best_step and this index, but we keep it around
257 // for simplicity.) best_neighbor == -1 indicates that there are no
258 // possible reorderings involving this join and a higher-indexed one
259 // (so it should not take part in the priority queue).
262
263 // Where we are in the priority queue (heap index);
264 // Priority_queue will update this for us (through MarkNeighborCache)
265 // whenever we are insert into or moved around in the queue.
266 // This is so that we can easily tell the PQ to recalculate our position
267 // whenever best_step.benefit changes. -1 means that we are
268 // currently not in the priority queue.
269 int index_in_pq = -1;
270 };
272
273 // A priority queue of which simplifications are the most attractive,
274 // containing pointers into m_cache. See the documentation on NeighborCache
275 // for more information.
277 bool operator()(const NeighborCache *a, const NeighborCache *b) const {
278 return a->best_step.benefit < b->best_step.benefit;
279 }
280 };
282 void operator()(size_t index, NeighborCache **cache) {
283 (*cache)->index_in_pq = index;
284 }
285 };
287 NeighborCache *,
288 std::vector<NeighborCache *, Mem_root_allocator<NeighborCache *>>,
289 CompareByBenefit, MarkNeighborCache>
291};
292
293// See comment in .cc file.
294void SimplifyQueryGraph(THD *thd, int subgraph_pair_limit,
295 JoinHypergraph *graph, std::string *trace);
296
297#endif // SQL_JOIN_OPTIMIZER_GRAPH_SIMPLIFICATION_H_
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)
Definition: graph_simplification.cc:646
Bounds_checked_array< NeighborCache > m_cache
Definition: graph_simplification.h:271
Bounds_checked_array< EdgeCardinalities > m_edge_cardinalities
Definition: graph_simplification.h:217
void RecalculateNeighbors(size_t edge1_idx, size_t begin, size_t end)
Definition: graph_simplification.cc:595
SimplificationStep ConcretizeSimplificationStep(GraphSimplifier::ProposedSimplificationStep step)
Definition: graph_simplification.cc:760
JoinHypergraph * m_graph
Definition: graph_simplification.h:220
SimplificationResult
Definition: graph_simplification.h:93
@ APPLIED_REDO_STEP
Definition: graph_simplification.h:111
@ NO_SIMPLIFICATION_POSSIBLE
Definition: graph_simplification.h:95
@ APPLIED_SIMPLIFICATION
Definition: graph_simplification.h:99
@ APPLIED_NOOP
Definition: graph_simplification.h:106
void UndoSimplificationStep()
Definition: graph_simplification.cc:886
SimplificationResult DoSimplificationStep()
Definition: graph_simplification.cc:815
Mem_root_array< SimplificationStep > m_undone_steps
Definition: graph_simplification.h:202
void UpdatePQ(size_t edge_idx)
Definition: graph_simplification.cc:576
int num_steps_done() const
Definition: graph_simplification.h:133
Priority_queue< NeighborCache *, std::vector< NeighborCache *, Mem_root_allocator< NeighborCache * > >, CompareByBenefit, MarkNeighborCache > m_pq
Definition: graph_simplification.h:290
OnlineCycleFinder m_cycles
Definition: graph_simplification.h:225
Mem_root_array< SimplificationStep > m_done_steps
Definition: graph_simplification.h:196
GraphSimplifier(JoinHypergraph *graph, MEM_ROOT *mem_root)
Definition: graph_simplification.cc:552
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:33
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
void SimplifyQueryGraph(THD *thd, int subgraph_pair_limit, JoinHypergraph *graph, std::string *trace)
Definition of an undirected (join) hypergraph.
Header for compiler-dependent features.
#define ALWAYS_INLINE
Definition: my_compiler.h:109
Cursor end()
A past-the-end Cursor.
Definition: rules_table_service.cc:191
Definition: graph_simplification.h:276
bool operator()(const NeighborCache *a, const NeighborCache *b) const
Definition: graph_simplification.h:277
Definition: graph_simplification.h:213
double left
Definition: graph_simplification.h:214
double right
Definition: graph_simplification.h:215
Definition: graph_simplification.h:281
void operator()(size_t index, NeighborCache **cache)
Definition: graph_simplification.h:282
Definition: graph_simplification.h:253
int best_neighbor
Definition: graph_simplification.h:260
ProposedSimplificationStep best_step
Definition: graph_simplification.h:261
int index_in_pq
Definition: graph_simplification.h:269
Definition: graph_simplification.h:167
int before_edge_idx
Definition: graph_simplification.h:169
int after_edge_idx
Definition: graph_simplification.h:170
double benefit
Definition: graph_simplification.h:168
Definition: graph_simplification.h:179
int after_edge_idx
Definition: graph_simplification.h:181
int before_edge_idx
Definition: graph_simplification.h:180
hypergraph::Hyperedge new_edge
Definition: graph_simplification.h:185
hypergraph::Hyperedge old_edge
Definition: graph_simplification.h:184
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:75
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Definition: hypergraph.h:79