Branch data Line data Source code
1 : : #include "IR/PartialPlanGenerator.hpp"
2 : :
3 : : #include <mutable/IR/PlanTable.hpp>
4 : :
5 : :
6 : : using namespace m;
7 : :
8 : :
9 : : template<typename PlanTable>
10 : 0 : void PartialPlanGenerator::for_each_complete_partial_plan(const PlanTable &PT, callback_type callback)
11 : : {
12 [ # # # # ]: 0 : if (PT.num_sources() == 0)
13 : 0 : return;
14 : :
15 [ # # # # ]: 0 : if (PT.num_sources() == 1) {
16 : 0 : const Subproblem root(1UL);
17 [ # # # # ]: 0 : partial_plan_type partial_plans{{ root }};
18 [ # # # # ]: 0 : callback(partial_plans);
19 : : return;
20 : 0 : }
21 : :
22 : 0 : const auto &final_plan_entry = PT.get_final();
23 : 0 : const Subproblem root_of_final_plan = final_plan_entry.left | final_plan_entry.right;
24 : :
25 : : ///> The set of partial plans used.
26 : 0 : partial_plan_type partial_plans;
27 : : ///> The set of remaining partial plan candidates. If empty, `partial_plans` is complete.
28 : 0 : partial_plan_type candidates;
29 : : ///> Stores the decision whether a partial plan was used in the current trace.
30 : 0 : std::vector<bool> decision_stack;
31 [ # # # # : 0 : partial_plans.reserve(PT.num_sources());
# # # # ]
32 [ # # # # : 0 : candidates.reserve(PT.num_sources());
# # # # ]
33 : : /* Every plan that is *not* a relation, can be rejected. With *n* relations, there are *n-1* such plans. Hence,
34 : : * the decision stack can have at most *n-1* times NO and *n* times YES. */
35 [ # # # # : 0 : decision_stack.reserve(2 * PT.num_sources());
# # # # ]
36 : :
37 : : /*----- Initialize -----*/
38 [ # # # # ]: 0 : partial_plans.emplace_back(root_of_final_plan);
39 [ # # # # ]: 0 : decision_stack.emplace_back(true);
40 : :
41 : 0 : for (;;) {
42 [ # # # # ]: 0 : if (candidates.empty()) {
43 [ # # # # ]: 0 : callback(partial_plans);
44 : :
45 : : /*----- Unwind the decision stack. -----*/
46 : 0 : for (;;) {
47 [ # # # # ]: 0 : if (decision_stack.empty())
48 : 0 : goto finished;
49 : :
50 [ # # # # ]: 0 : const bool was_partial_plan_taken = decision_stack.back();
51 [ # # # # ]: 0 : if (not was_partial_plan_taken) {
52 [ # # # # ]: 0 : M_insist(candidates.size() >= 2);
53 : 0 : const Subproblem right = candidates.back();
54 : 0 : candidates.pop_back();
55 : 0 : const Subproblem left = candidates.back();
56 : 0 : candidates.pop_back();
57 [ # # # # ]: 0 : decision_stack.pop_back();
58 [ # # # # : 0 : candidates.emplace_back(left|right); // reconstruct unaccepted partial plan from its children
# # # # ]
59 : 0 : continue;
60 : : }
61 : :
62 [ # # # # ]: 0 : M_insist(not partial_plans.empty());
63 : 0 : const auto partial_plan = partial_plans.back();
64 : 0 : partial_plans.pop_back();
65 [ # # # # : 0 : if (partial_plan.is_singleton()) {
# # # # ]
66 [ # # # # ]: 0 : decision_stack.pop_back();
67 [ # # # # ]: 0 : candidates.push_back(partial_plan); // leaves become candidates again
68 : 0 : continue;
69 : : }
70 : :
71 [ # # # # ]: 0 : M_insist(was_partial_plan_taken);
72 [ # # # # ]: 0 : decision_stack.back() = false; // no more an accepted partial plan in the new trace
73 [ # # # # : 0 : candidates.push_back(PT[partial_plan].left); // left child
# # # # ]
74 [ # # # # : 1 : candidates.push_back(PT[partial_plan].right); // right child
# # # # ]
75 : 0 : break;
76 : : }
77 : 0 : } else {
78 : : /*----- Take next partial plan candidate. -----*/
79 : 0 : auto partial_plan = candidates.back();
80 : 0 : candidates.pop_back();
81 [ # # # # ]: 0 : partial_plans.emplace_back(partial_plan);
82 [ # # # # ]: 0 : decision_stack.emplace_back(true);
83 : : }
84 : : }
85 : : finished:;
86 : 0 : }
87 : :
88 : : template<typename PlanTable>
89 : 0 : void PartialPlanGenerator::write_partial_plans_JSON(std::ostream &out, const QueryGraph &G, const PlanTable &PT,
90 : : std::function<void(callback_type)> for_each_partial_plan)
91 : : {
92 : : /*----- Lambda writes a partial plan tree to `out`, given the root if the tree. -----*/
93 : 0 : auto write_tree = [&](Subproblem root) -> void {
94 : 0 : auto write_tree_rec = [&](Subproblem root, auto &write_tree_rec) -> void {
95 [ # # # # ]: 0 : if (root.is_singleton()) {
96 [ # # # # ]: 0 : out << G.sources()[*root.begin()]->name();
97 : 0 : } else {
98 : 0 : out << "@ ";
99 : 0 : write_tree_rec(PT[root].left, write_tree_rec);
100 : 0 : out << ' ';
101 : 0 : write_tree_rec(PT[root].right, write_tree_rec);
102 : : }
103 : 0 : };
104 : 0 : write_tree_rec(root, write_tree_rec);
105 : 0 : };
106 : :
107 : : /* Given a forest of trees, representing a partial plan of a query, where each tree is uniquely represented by its
108 : : * root, write a JSON representation of this partial plan to `out`.
109 : : *
110 : : * Example:
111 : : * Graph:
112 : : * A - B - C
113 : : *
114 : : * Input --> Output:
115 : : * { A, B, C } --> [ "A", "B", "C" ]
116 : : * { AB, C } --> [ "@ A B", "C" ]
117 : : * { A, BC } --> [ "A", "@ B C" ]
118 : : * { A(BC) } --> [ "@ A @ B C" ]
119 : : * { (AB)C } --> [ "@ @ A B C" ]
120 : : */
121 : 0 : auto write_partial_plan = [&](const partial_plan_type &partial_plans) {
122 : 0 : M_insist(not partial_plans.empty());
123 : :
124 : : static bool is_first = true;
125 [ # # # # ]: 0 : if (is_first)
126 : 0 : is_first = false;
127 : : else
128 : 0 : out << ',';
129 : 0 : out << "\n ";
130 : :
131 : 0 : out << "[ ";
132 [ # # # # ]: 0 : for (auto it = partial_plans.cbegin(); it != partial_plans.cend(); ++it) {
133 [ # # # # ]: 0 : if (it != partial_plans.cbegin()) out << ", ";
134 : 0 : out << '"';
135 : 0 : write_tree(*it);
136 : 0 : out << '"';
137 : 0 : }
138 : 0 : out << " ]";
139 : 0 : };
140 : :
141 : :
142 : : /*----- Write beginning of JSON. -----*/
143 : 0 : out << '[';
144 : :
145 : : /*----- Write partial plans. -----*/
146 [ # # # # ]: 0 : for_each_partial_plan(write_partial_plan);
147 : :
148 : : /*----- Write end of JSON. -----*/
149 : 0 : out << "\n]\n";
150 : 0 : }
151 : :
152 : : /*----- Explicit tempalte instantiations. ----------------------------------------------------------------------------*/
153 : : template void PartialPlanGenerator::for_each_complete_partial_plan(const PlanTableSmallOrDense&, callback_type);
154 : : template void PartialPlanGenerator::for_each_complete_partial_plan(const PlanTableLargeAndSparse&, callback_type);
155 : : template void PartialPlanGenerator::write_partial_plans_JSON(std::ostream&, const QueryGraph&, const PlanTableSmallOrDense&, std::function<void(callback_type)>);
156 : : template void PartialPlanGenerator::write_partial_plans_JSON(std::ostream&, const QueryGraph&, const PlanTableLargeAndSparse&, std::function<void(callback_type)>);
|
