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