Branch data Line data Source code
1 : : #include <mutable/IR/PlanEnumerator.hpp>
2 : :
3 : : #include <algorithm>
4 : : #include <cstring>
5 : : #include <execution>
6 : : #include <functional>
7 : : #include <iostream>
8 : : #include <iterator>
9 : : #include <memory>
10 : : #include <mutable/catalog/Catalog.hpp>
11 : : #include <mutable/catalog/CostFunction.hpp>
12 : : #include <mutable/util/ADT.hpp>
13 : : #include <mutable/util/fn.hpp>
14 : : #include <mutable/util/list_allocator.hpp>
15 : : #include <mutable/util/malloc_allocator.hpp>
16 : : #include <queue>
17 : : #include <set>
18 : : #include <type_traits>
19 : : #ifdef __BMI2__
20 : : #include <x86intrin.h>
21 : : #endif
22 : :
23 : :
24 : : using namespace m;
25 : : using namespace m::pe;
26 : :
27 : :
28 : : /*======================================================================================================================
29 : : * PEall
30 : : *====================================================================================================================*/
31 : :
32 : : /** Computes the join order by enumerating *all* join orders, including Cartesian products. */
33 : : struct PEall final : PlanEnumeratorCRTP<PEall>
34 : : {
35 : : using base_type = PlanEnumeratorCRTP<PEall>;
36 : : using base_type::operator();
37 : :
38 : : template<typename PlanTable>
39 : 0 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
40 : 0 : auto &sources = G.sources();
41 : 0 : const std::size_t n = sources.size();
42 : 0 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
43 : :
44 [ # # # # : 0 : for (std::size_t i = 1, end = 1UL << n; i < end; ++i) {
# # # # ]
45 : 0 : Subproblem S(i);
46 [ # # # # : 0 : if (S.size() == 1) continue; // skip
# # # # ]
47 : : /* Compute break condition to avoid enumerating symmetric subproblems. */
48 : 0 : uint64_t offset = S.capacity() - __builtin_clzl(uint64_t(S));
49 : 0 : M_insist(offset != 0, "invalid subproblem offset");
50 : 0 : Subproblem limit = Subproblem::Singleton(offset - 1);
51 [ # # # # : 0 : for (Subproblem S1(least_subset(S)); S1 != limit; S1 = Subproblem(next_subset(S1, S))) {
# # # # ]
52 : 0 : Subproblem S2 = S - S1; // = S \ S1;
53 : 0 : M_insist(PT.has_plan(S1), "must have found the optimal plan for S1");
54 : 0 : M_insist(PT.has_plan(S2), "must have found the optimal plan for S2");
55 : : /* Exploit commutativity of join. */
56 : 0 : cnf::CNF condition; // TODO use join condition
57 [ # # # # : 0 : PT.update(G, CE, CF, S1, S2, condition);
# # # # ]
58 : 0 : }
59 : 0 : }
60 : 0 : }
61 : : };
62 : :
63 : :
64 : : /*======================================================================================================================
65 : : * DPsize
66 : : *====================================================================================================================*/
67 : 0 :
68 : : /** Computes the join order using size-based dynamic programming. */
69 : : struct DPsize final : PlanEnumeratorCRTP<DPsize>
70 : : {
71 : : using base_type = PlanEnumeratorCRTP<DPsize>;
72 : : using base_type::operator();
73 : :
74 : 1 : template<typename PlanTable>
75 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
76 : 1 : auto &sources = G.sources();
77 : 1 : std::size_t n = sources.size();
78 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
79 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
80 : :
81 : : /* Process all subplans of size greater than one. */
82 [ # # # # : 4 : for (std::size_t s = 2; s <= n; ++s) {
+ + # # ]
83 [ # # # # : 9 : for (std::size_t s1 = 1; s1 < s; ++s1) {
+ + # # ]
84 : 6 : std::size_t s2 = s - s1;
85 : : /* Check for all combinations of subsets if they are valid joins and if so, forward the combination to the
86 : : * plan table. */
87 [ # # # # : 34 : for (auto S1 = GospersHack::enumerate_all(s1, n); S1; ++S1) { // enumerate all subsets of size `s1`
+ + # # ]
88 [ # # # # : 28 : if (not PT.has_plan(*S1)) continue; // subproblem S1 not connected -> skip
+ + # # ]
89 [ # # # # : 131 : for (auto S2 = GospersHack::enumerate_all(s2, n); S2; ++S2) { // enumerate all subsets of size `s - s1`
+ + # # ]
90 [ # # # # : 108 : if (not PT.has_plan(*S2)) continue; // subproblem S2 not connected -> skip
+ + # # ]
91 [ # # # # : 88 : if (*S1 & *S2) continue; // subproblems not disjoint -> skip
+ + # # ]
92 [ # # # # : 36 : if (not M.is_connected(*S1, *S2)) continue; // subproblems not connected -> skip
+ + # # ]
93 : 30 : cnf::CNF condition; // TODO use join condition
94 [ # # # # : 30 : PT.update(G, CE, CF, *S1, *S2, condition);
# # # # #
# # # - +
# # ]
95 : 30 : }
96 : 23 : }
97 : 6 : }
98 : 3 : }
99 : 1 : }
100 : : };
101 : :
102 : :
103 : : /*======================================================================================================================
104 : : * DPsizeOpt
105 : : *====================================================================================================================*/
106 : :
107 : : /** Computes the join order using size-based dynamic programming. In addition to `DPsize`, applies the following
108 : : * optimizations. First, do not enumerate symmetric subproblems. Second, in case both subproblems are of equal size,
109 : : * consider only subproblems succeeding the first subproblem. */
110 : : struct DPsizeOpt final : PlanEnumeratorCRTP<DPsizeOpt>
111 : : {
112 : : using base_type = PlanEnumeratorCRTP<DPsizeOpt>;
113 : : using base_type::operator();
114 : :
115 : : template<typename PlanTable>
116 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
117 : 1 : auto &sources = G.sources();
118 : 1 : std::size_t n = sources.size();
119 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
120 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
121 : :
122 : : /* Process all subplans of size greater than one. */
123 [ # # # # : 4 : for (std::size_t s = 2; s <= n; ++s) {
+ + # # ]
124 : 3 : std::size_t m = s / 2; // division with rounding down
125 [ # # # # : 7 : for (std::size_t s1 = 1; s1 <= m; ++s1) {
+ + # # ]
126 : 4 : std::size_t s2 = s - s1;
127 : : /* Check for all combinations of subsets if they are valid joins and if so, forward the combination to the
128 : : * plan table. */
129 [ # # # # : 4 : if (s1 == s2) { // exploit commutativity of join: if A⋈ B is possible, so is B⋈ A
+ + # # ]
130 [ # # # # : 12 : for (auto S1 = GospersHack::enumerate_all(s1, n); S1; ++S1) { // enumerate all subsets of size `s1`
+ + # # ]
131 [ # # # # : 10 : if (not PT.has_plan(*S1)) continue; // subproblem not connected -> skip
+ + # # ]
132 : 8 : GospersHack S2 = GospersHack::enumerate_from(*S1, n);
133 [ # # # # : 21 : for (++S2; S2; ++S2) { // enumerate only the subsets following S1
+ + # # ]
134 [ # # # # : 13 : if (not PT.has_plan(*S2)) continue; // subproblem not connected -> skip
+ + # # ]
135 [ # # # # : 12 : if (*S1 & *S2) continue; // subproblems not disjoint -> skip
+ + # # ]
136 [ # # # # : 7 : if (not M.is_connected(*S1, *S2)) continue; // subproblems not connected -> skip
+ + # # ]
137 : : /* Exploit commutativity of join. */
138 : 5 : cnf::CNF condition; // TODO use join condition
139 [ # # # # : 5 : PT.update(G, CE, CF, *S1, *S2, condition);
# # # # #
# # # - +
# # ]
140 : 5 : }
141 : 8 : }
142 : 2 : } else {
143 [ # # # # : 10 : for (auto S1 = GospersHack::enumerate_all(s1, n); S1; ++S1) { // enumerate all subsets of size `s1`
+ + # # ]
144 [ # # # # : 8 : if (not PT.has_plan(*S1)) continue; // subproblem not connected -> skip
+ - # # ]
145 [ # # # # : 48 : for (auto S2 = GospersHack::enumerate_all(s2, n); S2; ++S2) { // enumerate all subsets of size `s2`
+ + # # ]
146 [ # # # # : 40 : if (not PT.has_plan(*S2)) continue; // subproblem not connected -> skip
+ + # # ]
147 [ # # # # : 28 : if (*S1 & *S2) continue; // subproblems not disjoint -> skip
+ + # # ]
148 [ # # # # : 11 : if (not M.is_connected(*S1, *S2)) continue; // subproblems not connected -> skip
+ + # # ]
149 : : /* Exploit commutativity of join. */
150 : 10 : cnf::CNF condition; // TODO use join condition
151 [ # # # # : 10 : PT.update(G, CE, CF, *S1, *S2, condition);
# # # # #
# # # - +
# # ]
152 : 10 : }
153 : 8 : }
154 : : }
155 : 4 : }
156 : 3 : }
157 : 1 : }
158 : : };
159 : :
160 : :
161 : : /*======================================================================================================================
162 : : * DPsizeSub
163 : : *====================================================================================================================*/
164 : :
165 : : /** Computes the join order using size-based dynamic programming. */
166 : : struct DPsizeSub final : PlanEnumeratorCRTP<DPsizeSub>
167 : : {
168 : : using base_type = PlanEnumeratorCRTP<DPsizeSub>;
169 : : using base_type::operator();
170 : :
171 : : template<typename PlanTable>
172 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
173 : 1 : auto &sources = G.sources();
174 : 1 : std::size_t n = sources.size();
175 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
176 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
177 : :
178 : : /* Process all subplans of size greater than one. */
179 [ # # # # : 4 : for (std::size_t s = 2; s <= n; ++s) {
+ + # # ]
180 [ # # # # : 14 : for (auto S = GospersHack::enumerate_all(s, n); S; ++S) { // enumerate all subsets of size `s`
+ + # # ]
181 [ # # # # : 11 : if (not M.is_connected(*S)) continue; // not connected -> skip
+ + # # ]
182 [ # # # # : 48 : for (Subproblem O(least_subset(*S)); O != *S; O = Subproblem(next_subset(O, *S))) {
+ + # # ]
183 : 40 : Subproblem Comp = *S - O;
184 : 40 : M_insist(M.is_connected(O, Comp), "implied by S inducing a connected subgraph");
185 [ # # # # : 40 : if (not PT.has_plan(O)) continue; // not connected -> skip
+ + # # ]
186 [ # # # # : 35 : if (not PT.has_plan(Comp)) continue; // not connected -> skip
+ + # # ]
187 : 30 : cnf::CNF condition; // TODO use join condition
188 [ # # # # : 30 : PT.update(G, CE, CF, O, Comp, condition);
+ - # # ]
189 : 30 : }
190 : 8 : }
191 : 3 : }
192 : 1 : }
193 : : };
194 : :
195 : :
196 : : /*======================================================================================================================
197 : : * DPsub
198 : : *====================================================================================================================*/
199 : :
200 : : /** Computes the join order using subset-based dynamic programming. */
201 : : struct DPsub final : PlanEnumeratorCRTP<DPsub>
202 : : {
203 : : using base_type = PlanEnumeratorCRTP<DPsub>;
204 : : using base_type::operator();
205 : :
206 : : template<typename PlanTable>
207 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
208 : 1 : auto &sources = G.sources();
209 : 1 : const std::size_t n = sources.size();
210 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
211 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
212 : :
213 [ # # # # : 16 : for (std::size_t i = 1, end = 1UL << n; i < end; ++i) {
+ + # # ]
214 : 15 : Subproblem S(i);
215 [ # # # # : 15 : if (S.size() == 1) continue; // no non-empty and strict subset of S -> skip
+ + # # ]
216 [ # # # # : 11 : if (not M.is_connected(S)) continue; // not connected -> skip
+ + # # ]
217 [ # # # # : 48 : for (Subproblem S1(least_subset(S)); S1 != S; S1 = Subproblem(next_subset(S1, S))) {
+ + # # ]
218 : 40 : Subproblem S2 = S - S1;
219 : 40 : M_insist(M.is_connected(S1, S2), "implied by S inducing a connected subgraph");
220 [ # # # # : 40 : if (not PT.has_plan(S1)) continue; // not connected -> skip
+ + # # ]
221 [ # # # # : 35 : if (not PT.has_plan(S2)) continue; // not connected -> skip
+ + # # ]
222 : 30 : cnf::CNF condition; // TODO use join condition
223 [ # # # # : 30 : PT.update(G, CE, CF, S1, S2, condition);
- + # # ]
224 : 30 : }
225 : 8 : }
226 : 1 : }
227 : : };
228 : :
229 : :
230 : : /*======================================================================================================================
231 : : * DPsubOpt
232 : : *====================================================================================================================*/
233 : :
234 : : /** Computes the join order using subset-based dynamic programming. In comparison to `DPsub`, do not enumerate
235 : : * symmetric subproblems. */
236 : : struct DPsubOpt final : PlanEnumeratorCRTP<DPsubOpt>
237 : : {
238 : : using base_type = PlanEnumeratorCRTP<DPsubOpt>;
239 : : using base_type::operator();
240 : :
241 : : template<typename PlanTable>
242 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
243 : 1 : auto &sources = G.sources();
244 : 1 : const std::size_t n = sources.size();
245 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
246 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
247 : :
248 [ # # # # : 16 : for (std::size_t i = 1, end = 1UL << n; i < end; ++i) {
+ + # # ]
249 : 15 : Subproblem S(i);
250 [ # # # # : 15 : if (S.size() == 1) continue; // no non-empty and strict subset of S -> skip
+ + # # ]
251 [ # # # # : 11 : if (not M.is_connected(S)) continue;
+ + # # ]
252 : : /* Compute break condition to avoid enumerating symmetric subproblems. */
253 : 8 : uint64_t offset = S.capacity() - __builtin_clzl(uint64_t(S));
254 : 8 : M_insist(offset != 0, "invalid subproblem offset");
255 : 8 : Subproblem limit = Subproblem::Singleton(offset - 1);
256 [ # # # # : 28 : for (Subproblem S1(least_subset(S)); S1 != limit; S1 = Subproblem(next_subset(S1, S))) {
+ + # # ]
257 : 20 : Subproblem S2 = S - S1; // = S \ S1;
258 : 20 : M_insist(M.is_connected(S1, S2), "implied by S inducing a connected subgraph");
259 [ # # # # : 20 : if (not PT.has_plan(S1)) continue; // not connected -> skip
+ + # # ]
260 [ # # # # : 15 : if (not PT.has_plan(S2)) continue; // not connected -> skip
+ - # # ]
261 : : /* Exploit commutativity of join. */
262 : 15 : cnf::CNF condition; // TODO use join condition
263 [ # # # # : 15 : PT.update(G, CE, CF, S1, S2, condition);
- + # # ]
264 : 15 : }
265 : 8 : }
266 : 1 : }
267 : : };
268 : :
269 : :
270 : : /*======================================================================================================================
271 : : * DPccp
272 : : *====================================================================================================================*/
273 : :
274 : : template<typename PlanTable>
275 : 1 : void DPccp::operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const
276 : : {
277 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
278 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
279 : 1 : const Subproblem All = SmallBitset::All(G.num_sources());
280 : 1 : cnf::CNF condition; // TODO use join condition
281 : :
282 : 16 : auto handle_CSG_pair = [&](const Subproblem left, const Subproblem right) {
283 : 15 : PT.update(G, CE, CF, left, right, condition);
284 : 15 : };
285 : :
286 [ # # # # : 1 : M.for_each_CSG_pair_undirected(All, handle_CSG_pair);
# # # # +
- - + # #
# # ]
287 : 1 : }
288 : :
289 : :
290 : : /*======================================================================================================================
291 : : * IK/KBZ
292 : : *====================================================================================================================*/
293 : :
294 : : /** Implements join ordering using the IK/KBZ algorithm.
295 : : *
296 : : * See Toshihide (I)baraki and Tiko (K)ameda. "On the optimal nesting order for computing n-relational joins." and Ravi
297 : : * (K)rishnamurthy, Haran (B)oral, and Carlo (Z)aniolo. "Optimization of Nonrecursive Queries." */
298 : : struct IKKBZ final : PlanEnumeratorCRTP<IKKBZ>
299 : : {
300 : : using base_type = PlanEnumeratorCRTP<IKKBZ>;
301 : : using base_type::operator();
302 : :
303 : : template<typename PlanTable>
304 : : std::vector<std::size_t>
305 : 0 : linearize(PlanTable &PT, const QueryGraph &G, const AdjacencyMatrix &M, const CostFunction &CF,
306 : : const CardinalityEstimator &CE) const
307 : : {
308 : : /* Computes the selectivity between two relations, identified by indices `u` and `v`, respectively. */
309 : 0 : auto selectivity = [&](std::size_t u, std::size_t v) {
310 : 0 : const SmallBitset U = SmallBitset::Singleton(u);
311 : 0 : const SmallBitset V = SmallBitset::Singleton(v);
312 : 0 : auto &model_u = *PT[U].model;
313 : 0 : auto &model_v = *PT[V].model;
314 : 0 : auto &joined = PT[U|V];
315 [ # # # # ]: 0 : if (not joined.model) {
316 : 0 : cnf::CNF condition; // TODO use join condition
317 [ # # # # ]: 0 : joined.model = CE.estimate_join(G, model_u, model_v, condition);
318 : 0 : }
319 : 0 : const double cardinality_joined = double(CE.predict_cardinality(*joined.model));
320 : 0 : return cardinality_joined / double(CE.predict_cardinality(model_u)) / double(CE.predict_cardinality(model_v));
321 : 0 : };
322 : :
323 : : /* Compute MST w.r.t. selectivity of join edges. See Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo.
324 : : * "Optimization of Nonrecursive Queries." */
325 [ # # # # ]: 0 : const AdjacencyMatrix MST = M.minimum_spanning_forest(selectivity);
326 : :
327 : 0 : std::vector<std::size_t> linearization;
328 [ # # # # ]: 0 : linearization.reserve(G.num_sources());
329 : 0 : std::vector<std::size_t> best_linearization;
330 [ # # # # ]: 0 : best_linearization.reserve(G.num_sources());
331 : 0 : double least_cost = std::numeric_limits<decltype(least_cost)>::infinity();
332 : :
333 : : /* The *rank* of a relation is defined as the factor by which the result set grows when joining with this
334 : : * relation. The rank is defined for a *child* relation and its *parent* relation w.r.t. the MST.
335 : : * "Intuitively, the rank measures the increase in the intermediate result per unit differential cost of doing
336 : : * the join." */
337 : 0 : auto rank = [&](std::size_t parent_id, std::size_t child_id) -> double {
338 : 0 : const SmallBitset parent = SmallBitset::Singleton(parent_id);
339 : 0 : const SmallBitset child = SmallBitset::Singleton(child_id);
340 : 0 : M_insist(MST.is_connected(parent, child), "relations must be joinable");
341 : 0 : M_insist(MST.neighbors(parent)[child_id]);
342 : :
343 : 0 : const auto &model_parent = *PT[parent].model;
344 : 0 : const auto &model_child = *PT[child].model;
345 [ # # # # ]: 0 : if (not PT[parent|child].model) {
346 : 0 : cnf::CNF condition; // TODO use join condition
347 [ # # # # : 0 : PT[parent|child].model = CE.estimate_join(G, model_parent, model_child, condition);
# # # # #
# # # ]
348 : 0 : }
349 : 0 : const double cardinality_joined = CE.predict_cardinality(*PT[parent|child].model);
350 : 0 : const double cardinality_parent = CE.predict_cardinality(model_parent);
351 : 0 : const double cardinality_child = CE.predict_cardinality(model_child);
352 : 0 : auto g = [](double cardinality) -> double { return 1 * cardinality; }; // TODO adapt to cost function
353 : 0 : return (cardinality_joined - cardinality_parent) / g(cardinality_child);
354 : 0 : };
355 : :
356 : : struct ranked_relation
357 : : {
358 : : private:
359 : : std::size_t id_;
360 : : double rank_;
361 : :
362 : : public:
363 : 0 : ranked_relation(std::size_t id, double rank) : id_(id), rank_(rank) { }
364 : :
365 : 0 : std::size_t id() const { return id_; }
366 : 0 : double rank() const { return rank_; }
367 : :
368 : : bool operator<(const ranked_relation &other) const { return this->rank() < other.rank(); }
369 : 0 : bool operator>(const ranked_relation &other) const { return this->rank() > other.rank(); }
370 : : };
371 : :
372 : : /*---- Consider each relation as root and linearize the query tree. -----*/
373 [ # # # # ]: 0 : for (std::size_t root_id = 0; root_id != G.num_sources(); ++root_id) {
374 [ # # # # ]: 0 : Subproblem root = Subproblem::Singleton(root_id);
375 : :
376 : 0 : linearization.clear();
377 [ # # # # ]: 0 : linearization.emplace_back(root_id);
378 : :
379 : : /* Initialize MIN heap with successors of root of query tree. */
380 [ # # # # ]: 0 : std::priority_queue<ranked_relation, std::vector<ranked_relation>, std::greater<ranked_relation>> Q;
381 [ # # # # : 0 : for (std::size_t n : MST.neighbors(root))
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
382 [ # # # # : 0 : Q.emplace(n, rank(root_id, n));
# # # # ]
383 : :
384 : 0 : Subproblem joined = root;
385 [ # # # # : 0 : while (not Q.empty()) {
# # # # ]
386 [ # # # # ]: 0 : ranked_relation ranked_relation = Q.top();
387 [ # # # # ]: 0 : Q.pop();
388 : :
389 [ # # # # : 0 : const Subproblem R = Subproblem::Singleton(ranked_relation.id());
# # # # ]
390 [ # # # # : 0 : M_insist((joined & R).empty());
# # # # ]
391 [ # # # # : 0 : M_insist(MST.is_connected(joined, R));
# # # # ]
392 [ # # # # : 0 : linearization.emplace_back(ranked_relation.id());
# # # # ]
393 : :
394 : : /*----- Join next relation with already joined relations. -----*/
395 : 0 : cnf::CNF condition; // TODO use join condition
396 [ # # # # ]: 0 : PT.update(G, CE, CF, joined, R, condition);
397 [ # # # # ]: 0 : joined |= R; // add R to the joined relations
398 : :
399 : : /*----- Add all children of `R` to the priority queue. -----*/
400 [ # # # # : 0 : const Subproblem N = MST.neighbors(R) - joined;
# # # # ]
401 [ # # # # : 0 : for (std::size_t n : N)
# # # # #
# # # # #
# # # # #
# # # #
# ]
402 [ # # # # : 0 : Q.emplace(n, rank(ranked_relation.id(), n));
# # # # #
# # # ]
403 : 0 : }
404 : :
405 : : /* Get the cost of the final plan. */
406 [ # # # # ]: 0 : const double cost = PT[joined].cost;
407 : :
408 : : /*----- Clear plan table. -----*/
409 : 0 : Subproblem runner = root;
410 [ # # # # ]: 0 : M_insist(linearization[0] == root_id);
411 [ # # # # ]: 0 : for (std::size_t i = 1; i != linearization.size(); ++i) {
412 : 0 : const std::size_t R = linearization[i];
413 [ # # # # : 0 : M_insist(not runner[R]);
# # # # #
# ]
414 [ # # # # : 0 : runner[R] = true;
# # # # ]
415 [ # # # # : 0 : M_insist(not runner.is_singleton());
# # # # ]
416 [ # # # # : 0 : M_insist(bool(PT[runner].model), "must have computed a model during linearization");
# # # # ]
417 [ # # # # : 0 : M_insist(bool(PT[runner].left), "must have a left subplan");
# # # # ]
418 [ # # # # : 0 : M_insist(bool(PT[runner].right), "must have a right subplan");
# # # # ]
419 [ # # # # : 0 : PT[runner] = PlanTableEntry();
# # # # ]
420 : 0 : }
421 : :
422 [ # # # # ]: 0 : if (cost < least_cost) {
423 : : using std::swap;
424 : 0 : swap(best_linearization, linearization);
425 : 0 : least_cost = cost;
426 : 0 : }
427 : 0 : }
428 : :
429 : 0 : return best_linearization;
430 [ # # # # ]: 0 : }
431 : :
432 : : template<typename PlanTable>
433 : 0 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
434 : 0 : const AdjacencyMatrix &M = G.adjacency_matrix();
435 : 0 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
436 : :
437 : : /* Linearize the vertices. */
438 : 0 : const std::vector<std::size_t> linearization = linearize(PT, G, M, CF, CE);
439 [ # # # # : 0 : M_insist(linearization.size() == G.num_sources());
# # # # #
# # # ]
440 : :
441 : : /*----- Reconstruct the right-deep plan from the linearization. -----*/
442 [ # # # # : 0 : Subproblem right = Subproblem::Singleton(linearization[0]);
# # # # ]
443 [ # # # # : 0 : for (std::size_t i = 1; i < G.num_sources(); ++i) {
# # # # #
# # # ]
444 [ # # # # : 0 : const Subproblem left = Subproblem::Singleton(linearization[i]);
# # # # ]
445 : 0 : cnf::CNF condition; // TODO use join condition
446 [ # # # # : 0 : PT.update(G, CE, CF, left, right, condition);
# # # # ]
447 [ # # # # : 0 : right = left | right;
# # # # ]
448 : 0 : }
449 : 0 : }
450 : : };
451 : :
452 : :
453 : : /*======================================================================================================================
454 : : * LinearizedDP
455 : : *====================================================================================================================*/
456 : :
457 : : struct LinearizedDP final : PlanEnumeratorCRTP<LinearizedDP>
458 : : {
459 : : using base_type = PlanEnumeratorCRTP<LinearizedDP>;
460 : : using base_type::operator();
461 : :
462 : : struct Sequence
463 : : {
464 : : private:
465 : : const std::vector<std::size_t> &linearization_;
466 : : ///> the index in the linearization of the first element of this sequence
467 : : std::size_t begin_;
468 : : ///> the index in the linearization one past the last element of this sequence
469 : : std::size_t end_;
470 : : ///> the subproblem formed by this sequence
471 : : Subproblem S_;
472 : :
473 : : public:
474 : 0 : Sequence(const std::vector<std::size_t> &linearization, std::size_t begin, std::size_t end)
475 : 0 : : linearization_(linearization), begin_(begin), end_(end)
476 : : {
477 : 0 : S_ = compute_subproblem_from_sequence(begin_, end_);
478 : 0 : }
479 : :
480 : 0 : std::size_t length() const { return end_ - begin_; }
481 : 0 : Subproblem subproblem() const { return S_; }
482 : : /** Returns the index in linearization of the first element of this sequence. */
483 : 0 : std::size_t first_index() const { return begin_; }
484 : : /** Returns the index in linearization of the last element of this sequence. */
485 : 0 : std::size_t last_index() const { return end_ - 1; }
486 : : std::size_t end() const { return end_; }
487 : :
488 : 0 : std::size_t first() const { return linearization_[first_index()]; }
489 : 0 : std::size_t last() const { return linearization_[last_index()]; }
490 : :
491 : 0 : bool is_at_front() const { return begin_ == 0; }
492 : 0 : bool is_at_back() const { return end_ == linearization_.size(); }
493 : :
494 : 0 : Subproblem compute_subproblem_from_sequence(std::size_t begin, std::size_t end) {
495 : 0 : M_insist(begin < end);
496 : 0 : M_insist(end <= linearization_.size());
497 : 0 : Subproblem S;
498 [ # # ]: 0 : while (begin != end)
499 : 0 : S[linearization_[begin++]] = true;
500 : 0 : return S;
501 : : }
502 : :
503 : 0 : void extend_at_front() {
504 : 0 : M_insist(begin_ > 0);
505 : 0 : --begin_;
506 : 0 : S_[first()] = true;
507 : 0 : }
508 : :
509 : 0 : void extend_at_back() {
510 : 0 : M_insist(end_ < linearization_.size());
511 : 0 : ++end_;
512 : 0 : S_[last()] = true;
513 : 0 : }
514 : :
515 : 0 : void shrink_at_front() {
516 : 0 : M_insist(begin_ < end_);
517 : 0 : S_[first()] = false;
518 : 0 : ++begin_;
519 : 0 : }
520 : :
521 : 0 : void shrink_at_back() {
522 : 0 : M_insist(begin_ < end_);
523 : 0 : S_[last()] = false;
524 : 0 : --end_;
525 : 0 : }
526 : :
527 : : friend std::ostream & operator<<(std::ostream &out, const Sequence &seq) {
528 : : out << seq.first_index() << '-' << seq.last_index() << ": [";
529 : : for (std::size_t i = seq.first_index(); i <= seq.last_index(); ++i) {
530 : : if (i != seq.first_index()) out << ", ";
531 : : out << seq.linearization_[i];
532 : : }
533 : : return out << ']';
534 : : }
535 : :
536 : : void dump(std::ostream &out) const { out << *this << std::endl; }
537 : : void dump() const { dump(std::cerr); }
538 : : };
539 : :
540 : : template<typename PlanTable>
541 : 0 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
542 [ # # # # : 0 : if (G.num_sources() <= 1) return;
# # # # ]
543 : :
544 : 0 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
545 : 0 : const AdjacencyMatrix &M = G.adjacency_matrix();
546 [ # # # # : 0 : const std::vector<std::size_t> linearization = IKKBZ{}.linearize(PT, G, M, CF, CE);
# # # # ]
547 [ # # # # ]: 0 : const std::size_t num_relations = G.num_sources();
548 : :
549 [ # # # # : 0 : Sequence seq(linearization, 0, 2);
# # # # ]
550 : 0 : bool moves_right = true;
551 : 0 : for (;;) {
552 [ # # # # : 0 : if (M.is_connected(seq.subproblem())){
# # # # #
# # # # #
# # # # #
# ]
553 : : /*----- Consider all dissections of `seq` into two sequences. -----*/
554 [ # # # # : 0 : for (std::size_t mid = seq.first_index() + 1; mid <= seq.last_index(); ++mid) {
# # # # #
# # # # #
# # ]
555 [ # # # # : 0 : const Subproblem left = seq.compute_subproblem_from_sequence(seq.first_index(), mid);
# # # # #
# # # ]
556 [ # # # # : 0 : const Subproblem right = seq.subproblem() - left;
# # # # #
# # # ]
557 : :
558 [ # # # # : 0 : const bool is_left_connected = PT.has_plan(left);
# # # # ]
559 [ # # # # : 0 : const bool is_right_connected = PT.has_plan(right);
# # # # ]
560 [ # # # # : 0 : if (is_left_connected and is_right_connected) {
# # # # #
# # # # #
# # ]
561 : 0 : cnf::CNF condition; // TODO use join condition
562 [ # # # # : 0 : PT.update(G, CE, CF, left, right, condition);
# # # # ]
563 : 0 : }
564 : 0 : }
565 : 0 : }
566 : :
567 [ # # # # : 0 : if (seq.length() == num_relations)
# # # # #
# # # ]
568 : 0 : break;
569 : :
570 : : /*----- Move and grow the sequence. -----*/
571 [ # # # # : 0 : if (moves_right) {
# # # # ]
572 [ # # # # : 0 : if (seq.is_at_back()) [[unlikely]] {
# # # # #
# # # ]
573 : 0 : moves_right = false;
574 [ # # # # : 0 : seq.extend_at_front();
# # # # ]
575 : 0 : } else {
576 [ # # # # : 0 : seq.extend_at_back();
# # # # ]
577 [ # # # # : 0 : seq.shrink_at_front();
# # # # ]
578 : : }
579 : 0 : } else {
580 [ # # # # : 0 : if (seq.is_at_front()) [[unlikely]] {
# # # # #
# # # ]
581 : 0 : moves_right = true;
582 [ # # # # : 0 : seq.extend_at_back();
# # # # ]
583 : 0 : } else {
584 [ # # # # : 0 : seq.extend_at_front();
# # # # ]
585 [ # # # # : 0 : seq.shrink_at_back();
# # # # ]
586 : : }
587 : : }
588 : : }
589 : 0 : }
590 : : };
591 : :
592 : :
593 : : /*======================================================================================================================
594 : : * TDbasic
595 : : *====================================================================================================================*/
596 : :
597 : : struct TDbasic final : PlanEnumeratorCRTP<TDbasic>
598 : : {
599 : : using base_type = PlanEnumeratorCRTP<TDbasic>;
600 : : using base_type::operator();
601 : :
602 : : template<typename PlanTable>
603 : 31 : void PlanGen(const QueryGraph &G, const AdjacencyMatrix &M, const CostFunction &CF, const CardinalityEstimator &CE,
604 : : PlanTable &PT, Subproblem S) const
605 : : {
606 [ + + # # ]: 31 : if (not PT.has_plan(S)) {
607 : : /* Naive Partitioning */
608 : : /* Iterate over all non-empty and strict subsets in `S`. */
609 [ + + # # ]: 48 : for (Subproblem sub(least_subset(S)); sub != S; sub = Subproblem(next_subset(sub, S))) {
610 : 40 : Subproblem complement = S - sub;
611 : : /* Check for valid connected subgraph complement pair. */
612 [ + + + + : 60 : if (uint64_t(least_subset(sub)) < uint64_t(least_subset(complement)) and
# # # # ]
613 [ + + # # ]: 20 : M.is_connected(sub) and M.is_connected(complement))
614 : : {
615 : : /* Process `sub` and `complement` recursively. */
616 : 15 : PlanGen(G, M, CF, CE, PT, sub);
617 : 15 : PlanGen(G, M, CF, CE, PT, complement);
618 : :
619 : : /* Update `PlanTable`. */
620 : 15 : cnf::CNF condition; // TODO use join condition
621 [ - + # # ]: 15 : PT.update(G, CE, CF, sub, complement, condition);
622 : 15 : }
623 : 40 : }
624 : 8 : }
625 : 31 : }
626 : :
627 : : template<typename PlanTable>
628 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
629 : 1 : auto &sources = G.sources();
630 : 1 : std::size_t n = sources.size();
631 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
632 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
633 : :
634 : 1 : PlanGen(G, M, CF, CE, PT, Subproblem::All(n));
635 : 1 : }
636 : : };
637 : :
638 : :
639 : : /*======================================================================================================================
640 : : * TDMinCutAGaT
641 : : *====================================================================================================================*/
642 : :
643 : : struct TDMinCutAGaT final : PlanEnumeratorCRTP<TDMinCutAGaT>
644 : : {
645 : : using base_type = PlanEnumeratorCRTP<TDMinCutAGaT>;
646 : : using base_type::operator();
647 : :
648 : : template<typename PlanTable>
649 : 1 : void operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const {
650 : 1 : const AdjacencyMatrix &M = G.adjacency_matrix();
651 : 1 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
652 : :
653 : 5 : auto handle_ccp = [&](const Subproblem first, const Subproblem second) -> void {
654 : 19 : auto recurse = [&](const Subproblem first, const Subproblem second, auto recurse) -> void {
655 : 15 : auto handle_ccp = std::bind(recurse, std::placeholders::_1, std::placeholders::_2, recurse);
656 : : /*----- Solve recursively. -----*/
657 [ # # # # : 15 : if (not PT.has_plan(first))
+ + # # ]
658 : 5 : MinCutAGaT{}.partition(M, handle_ccp, first);
659 : 15 : M_insist(PT.has_plan(first));
660 [ # # # # : 15 : if (not PT.has_plan(second))
+ + # # ]
661 : 2 : MinCutAGaT{}.partition(M, handle_ccp, second);
662 : 15 : M_insist(PT.has_plan(second));
663 : :
664 : : /*----- Update `PlanTable`. -----*/
665 : 15 : cnf::CNF condition; // TODO use join condition
666 [ # # # # : 15 : PT.update(G, CE, CF, first, second, condition);
+ - # # ]
667 : 15 : };
668 : 4 : recurse(first, second, recurse);
669 : 4 : };
670 : :
671 [ # # # # : 1 : if (G.num_sources() > 1) {
- + # # ]
672 : 1 : const Subproblem All = Subproblem::All(G.num_sources());
673 : 1 : MinCutAGaT{}.partition(M, handle_ccp, All);
674 : 1 : }
675 : 1 : }
676 : : };
677 : :
678 : :
679 : : /*======================================================================================================================
680 : : * GOO
681 : : *====================================================================================================================*/
682 : :
683 : : template<typename PlanTable>
684 : 2 : void GOO::operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const
685 : : {
686 : 2 : const AdjacencyMatrix &M = G.adjacency_matrix();
687 : 2 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
688 : :
689 : : /*----- Initialize subproblems and their neighbors. -----*/
690 [ # # # # : 2 : node nodes[G.num_sources()];
+ - # # ]
691 [ # # # # : 10 : for (std::size_t i = 0; i != G.num_sources(); ++i) {
+ + # # ]
692 : 8 : Subproblem S = Subproblem::Singleton(i);
693 : 8 : Subproblem N = M.neighbors(S);
694 : 8 : nodes[i] = node(S, N);
695 : 8 : }
696 : :
697 : : /*----- Greedyly enumerate joins, thereby computing a plan. -----*/
698 : 2 : compute_plan(PT, G, M, CF, CE, nodes, nodes + G.num_sources());
699 : 2 : }
700 : :
701 : :
702 : : /*======================================================================================================================
703 : : * TDGOO
704 : : *====================================================================================================================*/
705 : :
706 : : template<typename PlanTable>
707 : 2 : void TDGOO::operator()(enumerate_tag, PlanTable &PT, const QueryGraph &G, const CostFunction &CF) const
708 : : {
709 : 2 : const AdjacencyMatrix &M = G.adjacency_matrix();
710 : 2 : auto &CE = Catalog::Get().get_database_in_use().cardinality_estimator();
711 : :
712 : 2 : const Subproblem All = Subproblem::All(G.num_sources());
713 : 2 : std::vector<Subproblem> worklist;
714 [ # # # # : 2 : worklist.reserve(G.num_sources());
# # # # +
- # # ]
715 [ # # # # : 2 : worklist.emplace_back(All);
+ - # # ]
716 : :
717 : : /*----- Compute a plan with top-down GOO. -----*/
718 : 8 : auto update_PT = [&](Subproblem left, Subproblem right) {
719 [ # # # # : 6 : PT.update(G, CE, CF, left, right, cnf::CNF{}); // TODO: use actual condition
+ - # # ]
720 : 6 : };
721 [ # # # # : 2 : for_each_join(update_PT, PT, G, M, CF, CE, std::move(worklist));
- + # # ]
722 : 2 : }
723 : :
724 : :
725 : : #define LIST_PE(X) \
726 : : X(DPccp, "enumerates connected subgraph complement pairs") \
727 : : X(DPsize, "size-based subproblem enumeration") \
728 : : X(DPsizeOpt, "optimized DPsize: does not enumerate symmetric subproblems") \
729 : : X(DPsizeSub, "DPsize with enumeration of subset complement pairs") \
730 : : X(DPsub, "subset-based subproblem enumeration") \
731 : : X(DPsubOpt, "optimized DPsub: does not enumerate symmetric subproblems") \
732 : : X(GOO, "Greedy Operator Ordering") \
733 : : X(TDGOO, "Top-down variant of Greedy Operator Ordering") \
734 : : X(IKKBZ, "greedy algorithm by IK/KBZ, ordering joins by rank") \
735 : : X(LinearizedDP, "DP with search space linearization based on IK/KBZ") \
736 : : X(TDbasic, "basic top-down join enumeration using generate-and-test partitioning") \
737 : : X(TDMinCutAGaT, "top-down join enumeration using minimal graph cuts and advanced generate-and-test partitioning") \
738 : : X(PEall, "enumerates ALL join orders, inclding Cartesian products")
739 : :
740 : : #define INSTANTIATE(NAME, _) \
741 : : template void NAME::operator()(enumerate_tag, PlanTableSmallOrDense &PT, const QueryGraph &G, const CostFunction &CF) const; \
742 : : template void NAME::operator()(enumerate_tag, PlanTableLargeAndSparse &PT, const QueryGraph &G, const CostFunction &CF) const;
743 : : LIST_PE(INSTANTIATE)
744 : : #undef INSTANTIATE
745 : :
746 : : __attribute__((constructor(202)))
747 : 1 : static void register_plan_enumerators()
748 : : {
749 : 1 : Catalog &C = Catalog::Get();
750 : : #define REGISTER(NAME, DESCRIPTION) \
751 : : C.register_plan_enumerator(C.pool(#NAME), std::make_unique<NAME>(), DESCRIPTION);
752 [ + - + - : 1 : LIST_PE(REGISTER)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
753 : : #undef REGISTER
754 : 1 : }
|
