Branch data Line data Source code
1 : : #include <mutable/catalog/CardinalityEstimator.hpp>
2 : :
3 : : #include "backend/Interpreter.hpp"
4 : : #include "catalog/SpnWrapper.hpp"
5 : : #include "util/Spn.hpp"
6 : : #include <algorithm>
7 : : #include <cstddef>
8 : : #include <cstdlib>
9 : : #include <cstring>
10 : : #include <filesystem>
11 : : #include <mutable/catalog/Catalog.hpp>
12 : : #include <mutable/IR/CNF.hpp>
13 : : #include <mutable/IR/Operator.hpp>
14 : : #include <mutable/IR/PlanTable.hpp>
15 : : #include <mutable/IR/QueryGraph.hpp>
16 : : #include <mutable/Options.hpp>
17 : : #include <mutable/util/Diagnostic.hpp>
18 : : #include <mutable/util/Pool.hpp>
19 : : #include <nlohmann/json.hpp>
20 : :
21 : :
22 : : using namespace m;
23 : :
24 : :
25 : : namespace {
26 : :
27 : : namespace options {
28 : :
29 : 1 : std::filesystem::path injected_cardinalities_file;
30 : :
31 : : }
32 : :
33 : : }
34 : :
35 : : /*======================================================================================================================
36 : : * CardinalityEstimator
37 : : *====================================================================================================================*/
38 : 1 :
39 : 1544 : DataModel::~DataModel() { }
40 : :
41 : 612 : CardinalityEstimator::~CardinalityEstimator() { }
42 : :
43 : 0 : double CardinalityEstimator::predict_number_distinct_values(const DataModel&) const
44 : : {
45 [ # # # # : 0 : throw data_model_exception("predicting the number of distinct values is not supported by this data model.");
# # # # ]
46 : 0 : };
47 : :
48 : : M_LCOV_EXCL_START
49 : : void CardinalityEstimator::dump(std::ostream &out) const
50 : : {
51 : : print(out);
52 : : out << std::endl;
53 : : }
54 : :
55 : : void CardinalityEstimator::dump() const { dump(std::cerr); }
56 : : M_LCOV_EXCL_STOP
57 : 1 :
58 : :
59 : : /*======================================================================================================================
60 : : * CartesianProductEstimator
61 : : *====================================================================================================================*/
62 : :
63 : 0 : std::unique_ptr<DataModel> CartesianProductEstimator::empty_model() const
64 : : {
65 : 0 : auto model = std::make_unique<CartesianProductDataModel>();
66 : 0 : model->size = 0;
67 : 0 : return model;
68 : 0 : }
69 : :
70 : 194 : std::unique_ptr<DataModel> CartesianProductEstimator::estimate_scan(const QueryGraph &G, Subproblem P) const
71 : : {
72 : 194 : M_insist(P.size() == 1, "Subproblem must identify exactly one DataSource");
73 : 194 : auto idx = *P.begin();
74 : 195 : auto &BT = as<const BaseTable>(*G.sources()[idx]);
75 : 194 : auto model = std::make_unique<CartesianProductDataModel>();
76 [ + - + - : 194 : model->size = BT.table().store().num_rows();
+ - ]
77 : 194 : return model;
78 : 194 : }
79 : :
80 : : std::unique_ptr<DataModel>
81 : 1 : CartesianProductEstimator::estimate_filter(const QueryGraph&, const DataModel &_data, const cnf::CNF&) const
82 : : {
83 : : /* This model cannot estimate the effects of applying a filter. */
84 : 1 : auto &data = as<const CartesianProductDataModel>(_data);
85 : 1 : return std::make_unique<CartesianProductDataModel>(data); // copy
86 : : }
87 : :
88 : : std::unique_ptr<DataModel>
89 : 4 : CartesianProductEstimator::estimate_limit(const QueryGraph&, const DataModel &_data, std::size_t limit,
90 : : std::size_t offset) const
91 : : {
92 : 4 : auto data = as<const CartesianProductDataModel>(_data);
93 [ - + ]: 4 : const std::size_t remaining = offset > data.size ? 0UL : data.size - offset;
94 [ + - ]: 4 : auto model = std::make_unique<CartesianProductDataModel>();
95 [ - + ]: 4 : model->size = std::min(remaining, limit);
96 : 4 : return model;
97 : 4 : }
98 : :
99 : : std::unique_ptr<DataModel>
100 : 1 : CartesianProductEstimator::estimate_grouping(const QueryGraph&, const DataModel &_data,
101 : : const std::vector<group_type>&) const
102 : : {
103 : 1 : auto &data = as<const CartesianProductDataModel>(_data);
104 : 1 : auto model = std::make_unique<CartesianProductDataModel>();
105 : 1 : model->size = data.size; // this model cannot estimate the effects of grouping
106 : 1 : return model;
107 : 1 : }
108 : :
109 : : std::unique_ptr<DataModel>
110 : 158 : CartesianProductEstimator::estimate_join(const QueryGraph&, const DataModel &_left, const DataModel &_right,
111 : : const cnf::CNF&) const
112 : : {
113 : 158 : auto left = as<const CartesianProductDataModel>(_left);
114 [ + - ]: 158 : auto right = as<const CartesianProductDataModel>(_right);
115 [ - + ]: 158 : auto model = std::make_unique<CartesianProductDataModel>();
116 : 158 : model->size = left.size * right.size; // this model cannot estimate the effects of a join condition
117 : 158 : return model;
118 : 158 : }
119 : :
120 : : template<typename PlanTable>
121 : : std::unique_ptr<DataModel>
122 : 13 : CartesianProductEstimator::operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph&, Subproblem to_join,
123 : : const cnf::CNF&) const
124 : : {
125 : 13 : M_insist(not to_join.empty());
126 : 13 : auto model = std::make_unique<CartesianProductDataModel>();
127 : 13 : model->size = 1UL;
128 [ + - + - : 46 : for (auto it = to_join.begin(); it != to_join.end(); ++it)
+ - + + +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
129 [ + - + - : 33 : model->size *= as<const CartesianProductDataModel>(*PT[it.as_set()].model).size;
+ - # # #
# # # # #
# # # # #
# # # #
# ]
130 : 13 : return model;
131 : 13 : }
132 : :
133 : : template
134 : : std::unique_ptr<DataModel>
135 : : CartesianProductEstimator::operator()(estimate_join_all_tag, const PlanTableSmallOrDense&, const QueryGraph&,
136 : : Subproblem, const cnf::CNF&) const;
137 : : template
138 : : std::unique_ptr<DataModel>
139 : : CartesianProductEstimator::operator()(estimate_join_all_tag, const PlanTableLargeAndSparse&, const QueryGraph&,
140 : : Subproblem, const cnf::CNF&) const;
141 : :
142 : 574 : std::size_t CartesianProductEstimator::predict_cardinality(const DataModel &data) const
143 : : {
144 : 574 : return as<const CartesianProductDataModel>(data).size;
145 : : }
146 : :
147 : : M_LCOV_EXCL_START
148 : : void CartesianProductEstimator::print(std::ostream &out) const
149 : : {
150 : : out << "CartesianProductEstimator - returns size of the Cartesian product of the given subproblems";
151 : : }
152 : : M_LCOV_EXCL_STOP
153 : :
154 : :
155 : : /*======================================================================================================================
156 : : * InjectionCardinalityEstimator
157 : : *====================================================================================================================*/
158 : :
159 : : /*----- Constructors -------------------------------------------------------------------------------------------------*/
160 : :
161 [ # # # # : 0 : InjectionCardinalityEstimator::InjectionCardinalityEstimator(ThreadSafePooledString name_of_database)
# # # # #
# ]
162 [ # # # # : 0 : : fallback_(name_of_database)
# # # # ]
163 : 0 : {
164 [ # # # # : 0 : Diagnostic diag(Options::Get().has_color, std::cout, std::cerr);
# # # # ]
165 [ # # # # ]: 0 : Position pos("InjectionCardinalityEstimator");
166 : :
167 [ # # # # ]: 0 : if (options::injected_cardinalities_file.empty()) {
168 [ # # # # ]: 0 : std::cout << "No injection file was passed.\n";
169 : 0 : } else {
170 [ # # # # ]: 0 : std::ifstream in(options::injected_cardinalities_file);
171 [ # # # # : 1 : if (in) {
# # # # ]
172 [ # # # # ]: 0 : read_json(diag, in, name_of_database);
173 : 0 : } else {
174 [ # # # # : 0 : diag.w(pos) << "Could not open file " << options::injected_cardinalities_file << ".\n"
# # # # #
# # # # #
# # ]
175 [ # # # # ]: 0 : << "A dummy estimator will be used to do estimations.\n";
176 : : }
177 : 0 : }
178 : 0 : }
179 : :
180 [ # # # # : 156 : InjectionCardinalityEstimator::InjectionCardinalityEstimator(Diagnostic &diag, ThreadSafePooledString name_of_database,
+ - + - +
- ]
181 : : std::istream &in)
182 [ # # # # : 52 : : fallback_(name_of_database)
+ - + - ]
183 : 104 : {
184 [ # # - + ]: 52 : read_json(diag, in, name_of_database);
185 : 52 : }
186 : :
187 : 52 : void InjectionCardinalityEstimator::read_json(Diagnostic &diag, std::istream &in,
188 : : const ThreadSafePooledString &name_of_database)
189 : 1 : {
190 : 52 : Catalog &C = Catalog::Get();
191 : 52 : Position pos("InjectionCardinalityEstimator");
192 : 52 : std::string prev_relation;
193 : :
194 : : using json = nlohmann::json;
195 : 52 : json cardinalities;
196 : : try {
197 [ + - ]: 52 : in >> cardinalities;
198 [ # # ]: 52 : } catch (json::parse_error parse_error) {
199 [ # # # # ]: 0 : diag.w(pos) << "The file could not be parsed as json. Parser error output:\n"
200 [ # # # # ]: 0 : << parse_error.what() << "\n"
201 [ # # ]: 0 : << "A dummy estimator will be used to do estimations.\n";
202 : : return;
203 [ # # # # ]: 0 : }
204 : : json *database_entry;
205 : : try {
206 [ + - + - : 52 : database_entry = &cardinalities.at(*name_of_database); //throws if key does not exist
+ + ]
207 [ + - ]: 52 : } catch (json::out_of_range &out_of_range) {
208 [ + - + - : 1 : diag.w(pos) << "No entry for the db " << name_of_database << " in the file.\n"
+ - + - ]
209 [ + - ]: 1 : << "A dummy estimator will be used to do estimations.\n";
210 : : return;
211 [ + - # # ]: 1 : }
212 [ + - ]: 51 : cardinality_table_.reserve(database_entry->size());
213 : 51 : std::vector<std::string> names;
214 [ + - + + : 645 : for (auto &subproblem_entry : *database_entry) {
+ - + - ]
215 : : json* relations_array;
216 : : json* size;
217 : : try {
218 [ + - + - ]: 594 : relations_array = &subproblem_entry.at("relations");
219 [ + - + - ]: 594 : size = &subproblem_entry.at("size");
220 [ # # ]: 594 : } catch (json::exception &exception) {
221 [ # # # # : 0 : diag.w(pos) << "The entry " << subproblem_entry << " for the db \"" << name_of_database << "\""
# # # # #
# # # ]
222 [ # # ]: 0 : << " does not have the required form of {\"relations\": ..., \"size\": ... } "
223 [ # # ]: 0 : << "and will thus be ignored.\n";
224 : : continue;
225 [ # # # # ]: 0 : }
226 : :
227 : 594 : names.clear();
228 [ + - + + : 1863 : for (auto it = relations_array->begin(); it != relations_array->end(); ++it)
+ - ]
229 [ + - + - : 1269 : names.emplace_back(it->get<std::string>());
+ - ]
230 [ + - ]: 594 : std::sort(names.begin(), names.end());
231 : :
232 : 594 : buf_.clear();
233 [ + + ]: 1863 : for (auto it = names.begin(); it != names.end(); ++it) {
234 [ + + ]: 1269 : if (it != names.begin())
235 [ + - ]: 675 : buf_.emplace_back('$');
236 [ + - ]: 1269 : buf_append(*it);
237 : 1269 : }
238 [ + - ]: 594 : buf_.emplace_back(0);
239 [ + - + - ]: 594 : ThreadSafePooledString str = C.pool(buf_view());
240 [ + - ]: 594 : auto res = cardinality_table_.emplace(std::move(str), *size);
241 [ + - ]: 594 : M_insist(res.second, "insertion must not fail as we do not allow for duplicates in the input file");
242 : 594 : }
243 [ - + ]: 53 : }
244 : :
245 : : /*----- Model calculation --------------------------------------------------------------------------------------------*/
246 : :
247 : 0 : std::unique_ptr<DataModel> InjectionCardinalityEstimator::empty_model() const
248 : : {
249 : 0 : return std::make_unique<InjectionCardinalityDataModel>(Subproblem(), 0);
250 : : }
251 : :
252 : 357 : std::unique_ptr<DataModel> InjectionCardinalityEstimator::estimate_scan(const QueryGraph &G, Subproblem P) const
253 : : {
254 : 357 : M_insist(P.size() == 1);
255 : 357 : const auto idx = *P.begin();
256 : 357 : auto &DS = *G.sources()[idx];
257 : :
258 [ + - + - : 357 : if (auto it = cardinality_table_.find(DS.name().assert_not_none()); it != cardinality_table_.end()) {
+ + ]
259 : 349 : return std::make_unique<InjectionCardinalityDataModel>(P, it->second);
260 : : } else {
261 : : /* no match, fall back */
262 : 8 : auto fallback_model = fallback_.estimate_scan(G, P);
263 [ + - + - ]: 8 : return std::make_unique<InjectionCardinalityDataModel>(P, fallback_.predict_cardinality(*fallback_model));
264 : 8 : }
265 : 357 : }
266 : :
267 : : std::unique_ptr<DataModel>
268 : 2 : InjectionCardinalityEstimator::estimate_filter(const QueryGraph&, const DataModel &_data, const cnf::CNF&) const
269 : : {
270 : : /* This model cannot estimate the effects of applying a filter. */
271 : 2 : auto &data = as<const InjectionCardinalityDataModel>(_data);
272 : 2 : return std::make_unique<InjectionCardinalityDataModel>(data); // copy
273 : : }
274 : :
275 : : std::unique_ptr<DataModel>
276 : 4 : InjectionCardinalityEstimator::estimate_limit(const QueryGraph&, const DataModel &_data, std::size_t limit,
277 : : std::size_t offset) const
278 : : {
279 : 4 : auto &data = as<const InjectionCardinalityDataModel>(_data);
280 [ - + ]: 4 : const std::size_t remaining = offset > data.size_ ? 0UL : data.size_ - offset;
281 : 4 : return std::make_unique<InjectionCardinalityDataModel>(data.subproblem_, std::min(remaining, limit));
282 : : }
283 : :
284 : : std::unique_ptr<DataModel>
285 : 2 : InjectionCardinalityEstimator::estimate_grouping(const QueryGraph&, const DataModel &_data,
286 : : const std::vector<group_type> &exprs) const
287 : : {
288 : 2 : auto &data = as<const InjectionCardinalityDataModel>(_data);
289 : :
290 [ + - ]: 2 : if (exprs.empty())
291 : 2 : return std::make_unique<InjectionCardinalityDataModel>(data.subproblem_, 1); // single group
292 : :
293 : : /* Combine grouping keys into an identifier. */
294 [ # # # # ]: 0 : oss_.str("");
295 : 0 : oss_ << "g";
296 [ # # ]: 0 : for (auto [grp, alias] : exprs) {
297 [ # # ]: 0 : oss_ << '#';
298 [ # # # # ]: 0 : if (alias.has_value())
299 [ # # # # ]: 0 : oss_ << alias;
300 : : else
301 [ # # # # ]: 0 : oss_ << grp.get();
302 : 0 : }
303 [ # # ]: 0 : ThreadSafePooledString id = Catalog::Get().pool(oss_.str().c_str());
304 : :
305 [ # # # # ]: 0 : if (auto it = cardinality_table_.find(id); it != cardinality_table_.end()) {
306 : : /* Clamp injected cardinality to at most the cardinality of the grouping's child since it cannot produce more
307 : : * tuples than it receives. */
308 [ # # # # ]: 0 : return std::make_unique<InjectionCardinalityDataModel>(data.subproblem_, std::min(it->second, data.size_));
309 : : } else {
310 : : /* This model cannot estimate the effects of grouping. */
311 [ # # ]: 0 : return std::make_unique<InjectionCardinalityDataModel>(data); // copy
312 : : }
313 : 2 : }
314 : :
315 : : std::unique_ptr<DataModel>
316 : 364 : InjectionCardinalityEstimator::estimate_join(const QueryGraph &G, const DataModel &_left, const DataModel &_right,
317 : : const cnf::CNF &condition) const
318 : : {
319 : 364 : auto &left = as<const InjectionCardinalityDataModel>(_left);
320 : 364 : auto &right = as<const InjectionCardinalityDataModel>(_right);
321 : :
322 : 364 : const Subproblem subproblem = left.subproblem_ | right.subproblem_;
323 : 364 : ThreadSafePooledString id = make_identifier(G, subproblem);
324 : :
325 : : /* Lookup cardinality in table. */
326 [ + - + + ]: 364 : if (auto it = cardinality_table_.find(id); it != cardinality_table_.end()) {
327 : : /* Clamp injected cardinality to at most the cardinality of the cartesian product of the join's children
328 : : * since it cannot produce more tuples than that. */
329 : 362 : const std::size_t max_cardinality = left.size_ * right.size_;
330 [ + - + - ]: 362 : return std::make_unique<InjectionCardinalityDataModel>(subproblem, std::min(it->second, max_cardinality));
331 : : } else {
332 : : /* Fallback to CartesianProductEstimator. */
333 [ + - - + ]: 2 : if (not Options::Get().quiet)
334 [ # # # # : 0 : std::cerr << "warning: failed to estimate the join of " << left.subproblem_ << " and " << right.subproblem_
# # # # ]
335 [ # # ]: 0 : << '\n';
336 [ + - ]: 2 : auto left_fallback = std::make_unique<CartesianProductEstimator::CartesianProductDataModel>();
337 : 2 : left_fallback->size = left.size_;
338 [ + - ]: 2 : auto right_fallback = std::make_unique<CartesianProductEstimator::CartesianProductDataModel>();
339 : 2 : right_fallback->size = right.size_;
340 [ - + ]: 2 : auto fallback_model = fallback_.estimate_join(G, *left_fallback, *right_fallback, condition);
341 [ + - ]: 2 : return std::make_unique<InjectionCardinalityDataModel>(subproblem,
342 [ + - ]: 2 : fallback_.predict_cardinality(*fallback_model));
343 : 2 : }
344 : 364 : }
345 : :
346 : : template<typename PlanTable>
347 : : std::unique_ptr<DataModel>
348 : 120 : InjectionCardinalityEstimator::operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph &G,
349 : : Subproblem to_join, const cnf::CNF&) const
350 : : {
351 : 120 : ThreadSafePooledString id = make_identifier(G, to_join);
352 [ + - + - : 120 : if (auto it = cardinality_table_.find(id); it != cardinality_table_.end()) {
# # # # #
# # # # #
# # ]
353 : : /* Clamp injected cardinality to at most the cardinality of the cartesian product of the join's children
354 : : * since it cannot produce more tuples than that. */
355 : 120 : std::size_t max_cardinality = 1;
356 [ + - + - : 408 : for (auto it = to_join.begin(); it != to_join.end(); ++it)
+ - + + +
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
357 [ + - + - : 288 : max_cardinality *= as<const InjectionCardinalityDataModel>(*PT[it.as_set()].model).size_;
+ - # # #
# # # # #
# # # # #
# # # #
# ]
358 [ + - + - : 120 : return std::make_unique<InjectionCardinalityDataModel>(to_join, std::min(it->second, max_cardinality));
# # # # #
# # # # #
# # ]
359 : : } else {
360 : : /* Fallback to cartesian product. */
361 [ # # # # : 0 : if (not Options::Get().quiet)
# # # # #
# # # # #
# # ]
362 [ # # # # : 0 : std::cerr << "warning: failed to estimate the join of all data sources in " << to_join << '\n';
# # # # #
# # # # #
# # # # #
# # # #
# ]
363 [ # # # # : 0 : auto ds_it = to_join.begin();
# # # # ]
364 [ # # # # : 0 : std::size_t size = as<const InjectionCardinalityDataModel>(*PT[ds_it.as_set()].model).size_;
# # # # #
# # # # #
# # # # #
# # # #
# ]
365 [ # # # # : 0 : for (; ds_it != to_join.end(); ++ds_it)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
366 [ # # # # : 0 : size *= as<const InjectionCardinalityDataModel>(*PT[ds_it.as_set()].model).size_;
# # # # #
# # # # #
# # # # #
# # # #
# ]
367 [ # # # # : 0 : return std::make_unique<InjectionCardinalityDataModel>(to_join, size);
# # # # ]
368 : : }
369 : 120 : }
370 : :
371 : : template
372 : : std::unique_ptr<DataModel>
373 : : InjectionCardinalityEstimator::operator()(estimate_join_all_tag, const PlanTableSmallOrDense&, const QueryGraph&,
374 : : Subproblem, const cnf::CNF&) const;
375 : :
376 : : template
377 : : std::unique_ptr<DataModel>
378 : : InjectionCardinalityEstimator::operator()(estimate_join_all_tag, const PlanTableLargeAndSparse&, const QueryGraph&,
379 : : Subproblem, const cnf::CNF&) const;
380 : :
381 : 2054 : std::size_t InjectionCardinalityEstimator::predict_cardinality(const DataModel &data) const
382 : : {
383 : 2054 : return as<const InjectionCardinalityDataModel>(data).size_;
384 : : }
385 : :
386 : : M_LCOV_EXCL_START
387 : : void InjectionCardinalityEstimator::print(std::ostream &out) const
388 : : {
389 : : constexpr uint32_t max_rows_printed = 100; /// Number of rows of the cardinality_table printed
390 : : std::size_t sub_len = 13; /// Length of Subproblem column
391 : : for (auto &entry : cardinality_table_)
392 : : sub_len = std::max(sub_len, strlen(*entry.first));
393 : :
394 : : out << std::left << "InjectionCardinalityEstimator\n"
395 : : << std::setw(sub_len) << "Subproblem" << "Size" << "\n" << std::right;
396 : :
397 : : /* ------- Print maximum max_rows_printed rows of the cardinality_table_ */
398 : : uint32_t counter = 0;
399 : : for (auto &entry : cardinality_table_) {
400 : : if (counter >= max_rows_printed) break;
401 : : out << std::left << std::setw(sub_len) << entry.first << entry.second << "\n";
402 : : counter++;
403 : : }
404 : : }
405 : : M_LCOV_EXCL_STOP
406 : :
407 : 484 : ThreadSafePooledString InjectionCardinalityEstimator::make_identifier(const QueryGraph &G, const Subproblem S) const
408 : : {
409 : 484 : auto &C = Catalog::Get();
410 [ + + ]: 484 : static thread_local std::vector<ThreadSafePooledString> names;
411 : 484 : names.clear();
412 [ + + ]: 1786 : for (auto id : S)
413 [ + - ]: 1302 : names.emplace_back(G.sources()[id]->name());
414 : 2120 : std::sort(names.begin(), names.end(), [](auto lhs, auto rhs){ return strcmp(*lhs, *rhs) < 0; });
415 : :
416 : 484 : buf_.clear();
417 [ + + ]: 1786 : for (auto it = names.begin(); it != names.end(); ++it) {
418 [ + + ]: 1302 : if (it != names.begin())
419 : 818 : buf_.emplace_back('$');
420 : 1302 : buf_append(**it);
421 : 1302 : }
422 : :
423 : 484 : buf_.emplace_back(0);
424 : 484 : return C.pool(buf_view());
425 : 0 : }
426 : :
427 : :
428 : : /*======================================================================================================================
429 : : * SpnEstimator
430 : : *====================================================================================================================*/
431 : :
432 : : namespace {
433 : :
434 : : /** Visitor to translate a CNF to an Spn filter. Only consider sargable expressions. */
435 : : struct FilterTranslator : ast::ConstASTExprVisitor {
436 [ # # ]: 0 : Catalog &C = Catalog::Get();
437 : : ThreadSafePooledString attribute;
438 : : float value;
439 : : Spn::SpnOperator op;
440 : :
441 [ # # ]: 0 : FilterTranslator() : attribute(C.pool("")), value(0), op(Spn::EQUAL) { }
442 : :
443 : : using ConstASTExprVisitor::operator();
444 : :
445 : 0 : void operator()(const ast::Designator &designator) { attribute = designator.attr_name.text.assert_not_none(); }
446 : :
447 : 0 : void operator()(const ast::Constant &constant) {
448 : 0 : auto val = Interpreter::eval(constant);
449 : :
450 : 0 : visit(overloaded {
451 : 0 : [&val, this](const Numeric &numeric) {
452 [ # # # # ]: 0 : switch (numeric.kind) {
453 : : case Numeric::N_Int:
454 : 0 : value = float(val.as_i());
455 : 0 : break;
456 : : case Numeric::N_Float:
457 : 0 : value = val.as_f();
458 : 0 : break;
459 : : case Numeric::N_Decimal:
460 : 0 : value = float(val.as_d());
461 : 0 : break;
462 : : }
463 : 0 : },
464 : 0 : [this](const NoneType&) { op = Spn::IS_NULL; },
465 : 0 : [](auto&&) { M_unreachable("Unsupported type."); },
466 : 0 : }, *constant.type());
467 : 0 : }
468 : :
469 : 0 : void operator()(const ast::BinaryExpr &binary_expr) {
470 [ # # # # : 0 : switch (binary_expr.op().type) {
# # ]
471 : : case TK_EQUAL:
472 : 0 : op = Spn::EQUAL;
473 : 0 : break;
474 : : case TK_LESS:
475 : 0 : op = Spn::LESS;
476 : 0 : break;
477 : : case TK_LESS_EQUAL:
478 : 0 : op = Spn::LESS_EQUAL;
479 : 0 : break;
480 : : case TK_GREATER:
481 : 0 : op = Spn::GREATER;
482 : 0 : break;
483 : : case TK_GREATER_EQUAL:
484 : 0 : op = Spn::GREATER_EQUAL;
485 : 0 : break;
486 : : default:
487 : 0 : M_unreachable("Operator can't be handled");
488 : : }
489 : :
490 : 0 : (*this)(*binary_expr.lhs);
491 : 0 : (*this)(*binary_expr.rhs);
492 : 0 : }
493 : :
494 : 0 : void operator()(const ast::ErrorExpr&) { /* nothing to be done */ }
495 : 0 : void operator()(const ast::FnApplicationExpr &) { /* nothing to be done */ }
496 : 0 : void operator()(const ast::UnaryExpr &) { /* nothing to be done */ }
497 : 0 : void operator()(const ast::QueryExpr &) { /* nothing to be done */ }
498 : : };
499 : :
500 : : /** Visitor to translate a CNF join condition (get the two identifiers of an equi Join). */
501 : : struct JoinTranslator : ast::ConstASTExprVisitor {
502 : :
503 : : std::vector<std::pair<ThreadSafePooledString, ThreadSafePooledString>> join_designator;
504 : :
505 : : using ConstASTExprVisitor::operator();
506 : :
507 : 0 : void operator()(const ast::Designator &designator) {
508 : 0 : join_designator.emplace_back(designator.table_name.text, designator.attr_name.text);
509 : 0 : }
510 : :
511 : 0 : void operator()(const ast::BinaryExpr &binary_expr) {
512 : :
513 [ # # ]: 0 : if (binary_expr.op().type != m::TK_EQUAL) { M_unreachable("Operator can't be handled"); }
514 : :
515 : 0 : (*this)(*binary_expr.lhs);
516 : 0 : (*this)(*binary_expr.rhs);
517 : 0 : }
518 : :
519 : 0 : void operator()(const ast::Constant &) { /* nothing to be done */ }
520 : 0 : void operator()(const ast::ErrorExpr&) { /* nothing to be done */ }
521 : 0 : void operator()(const ast::FnApplicationExpr &) { /* nothing to be done */ }
522 : 0 : void operator()(const ast::UnaryExpr &) { /* nothing to be done */ }
523 : 0 : void operator()(const ast::QueryExpr &) { /* nothing to be done */ }
524 : : };
525 : :
526 : : }
527 : :
528 : 0 : SpnEstimator::~SpnEstimator()
529 : 0 : {
530 [ # # ]: 0 : for (auto &e : table_to_spn_)
531 [ # # ]: 0 : delete e.second;
532 : 0 : }
533 : :
534 [ # # ]: 0 : void SpnEstimator::learn_spns() { table_to_spn_ = SpnWrapper::learn_spn_database(name_of_database_); }
535 : :
536 : 0 : void SpnEstimator::learn_new_spn(const ThreadSafePooledString &name_of_table)
537 : : {
538 [ # # # # ]: 0 : table_to_spn_.emplace(
539 : 0 : name_of_table,
540 [ # # ]: 0 : new SpnWrapper(SpnWrapper::learn_spn_table(name_of_database_, name_of_table))
541 : : );
542 : 0 : }
543 : :
544 : 0 : std::pair<unsigned, bool> SpnEstimator::find_spn_id(const SpnDataModel &data, SpnJoin &join)
545 : : {
546 : : /* we only have a single spn */
547 : 0 : ThreadSafePooledString table_name = data.spns_.begin()->first;
548 [ # # ]: 0 : auto &attr_to_id = data.spns_.begin()->second.get().get_attribute_to_id();
549 : :
550 : 0 : unsigned spn_id = 0;
551 : 0 : bool is_primary_key = false;
552 : :
553 : : /* check which identifier of the join corresponds to the table of the spn, get the corresponding attribute id */
554 [ # # # # : 0 : auto find_iter = table_name == join.first.first ?
# # ]
555 [ # # # # ]: 0 : attr_to_id.find(join.first.second) : attr_to_id.find(join.second.second);
556 : :
557 [ # # ]: 0 : if (find_iter != attr_to_id.end()) { spn_id = find_iter->second; }
558 : 0 : else { is_primary_key = true; }
559 : :
560 : 0 : return {spn_id, is_primary_key};
561 : 0 : }
562 : :
563 : 0 : std::size_t SpnEstimator::max_frequency(const SpnDataModel &data, SpnJoin &join)
564 : : {
565 : 0 : auto [spn_id, is_primary_key] = find_spn_id(data, join);
566 : :
567 : : /* maximum frequency is only computed on data models which only have one Spn */
568 : 0 : const SpnWrapper &spn = data.spns_.begin()->second.get();
569 : :
570 [ # # ]: 0 : return is_primary_key ? 1 : data.num_rows_ / spn.estimate_number_distinct_values(spn_id);
571 : : }
572 : :
573 : 0 : std::size_t SpnEstimator::max_frequency(const SpnDataModel &data, const ThreadSafePooledString &attribute)
574 : : {
575 : : /* maximum frequency is only computed on data models which only have one Spn */
576 : 0 : const SpnWrapper &spn = data.spns_.begin()->second.get();
577 : 0 : auto &attr_to_id = spn.get_attribute_to_id();
578 : 0 : auto find_iter = attr_to_id.find(attribute);
579 : :
580 [ # # ]: 0 : return find_iter == attr_to_id.end() ? 1 : data.num_rows_ / spn.estimate_number_distinct_values(find_iter->second);
581 : : }
582 : :
583 : : /*----- Model calculation --------------------------------------------------------------------------------------------*/
584 : :
585 : 0 : std::unique_ptr<DataModel> SpnEstimator::empty_model() const
586 : : {
587 [ # # ]: 0 : return std::make_unique<SpnDataModel>(table_spn_map(), 0);
588 : 0 : }
589 : :
590 : 0 : std::unique_ptr<DataModel> SpnEstimator::estimate_scan(const QueryGraph &G, Subproblem P) const
591 : : {
592 : 0 : M_insist(P.size() == 1);
593 : 0 : const auto idx = *P.begin();
594 : 0 : auto &BT = as<const BaseTable>(*G.sources()[idx]);
595 : : /* get the Spn corresponding for the table to scan */
596 [ # # # # : 0 : if (auto it = table_to_spn_.find(BT.name().assert_not_none()); it != table_to_spn_.end()) {
# # ]
597 : 0 : table_spn_map spns;
598 : 0 : const SpnWrapper &spn = *it->second;
599 [ # # # # ]: 0 : spns.emplace(BT.name(), spn);
600 [ # # # # ]: 0 : return std::make_unique<SpnDataModel>(std::move(spns), spn.num_rows());
601 : 0 : } else {
602 [ # # # # : 0 : throw data_model_exception("Table does not exist.");
# # # # ]
603 : : }
604 : 0 : }
605 : :
606 : : std::unique_ptr<DataModel>
607 : 0 : SpnEstimator::estimate_filter(const QueryGraph&, const DataModel &_data, const cnf::CNF &filter) const
608 : : {
609 : 0 : auto &data = as<const SpnDataModel>(_data);
610 : 0 : M_insist(data.spns_.size() == 1);
611 : 0 : auto new_data = std::make_unique<SpnDataModel>(data);
612 : 0 : auto &spn = new_data->spns_.begin()->second.get();
613 [ # # ]: 0 : auto &attribute_to_id = spn.get_attribute_to_id();
614 : :
615 : 0 : Spn::Filter translated_filter;
616 [ # # ]: 0 : FilterTranslator ft;
617 : :
618 : : /* only consider clauses with one element, since Spns cannot estimate disjunctions */
619 [ # # ]: 0 : for (auto &clause : filter) {
620 [ # # ]: 0 : M_insist(clause.size() == 1);
621 [ # # # # ]: 0 : ft(*clause[0]);
622 : : unsigned spn_id;
623 : :
624 [ # # # # ]: 0 : if (auto it = attribute_to_id.find(ft.attribute); it != attribute_to_id.end()) {
625 : 0 : spn_id = it->second;
626 : 0 : } else {
627 [ # # # # : 0 : throw data_model_exception("Attribute does not exist.");
# # # # ]
628 : : }
629 : :
630 [ # # # # ]: 0 : translated_filter.emplace(spn_id, std::make_pair(ft.op, ft.value));
631 : : }
632 : :
633 : : /* Save number of rows in the newly constructed data model with the filter applied */
634 [ # # ]: 0 : new_data->num_rows_ = float(new_data->num_rows_) * spn.likelihood(translated_filter);
635 : 0 : return new_data;
636 : 0 : }
637 : :
638 : : std::unique_ptr<DataModel>
639 : 0 : SpnEstimator::estimate_limit(const QueryGraph&, const DataModel &data, std::size_t limit, std::size_t) const
640 : : {
641 : 0 : auto model = std::make_unique<SpnDataModel>(as<const SpnDataModel>(data));
642 [ # # ]: 0 : model->num_rows_ = std::min(model->num_rows_, limit);
643 : 0 : return model;
644 : 0 : }
645 : :
646 : 0 : std::unique_ptr<DataModel> SpnEstimator::estimate_grouping(const QueryGraph&, const DataModel &data,
647 : : const std::vector<group_type> &groups) const
648 : : {
649 : 0 : auto model = std::make_unique<SpnDataModel>(as<const SpnDataModel>(data));
650 : 0 : std::size_t num_rows = 1;
651 [ # # # # ]: 0 : for (auto [grp, alias] : groups) {
652 [ # # ]: 0 : auto designator = cast<const ast::Designator>(&grp.get());
653 [ # # ]: 0 : if (not designator)
654 [ # # # # : 0 : throw data_model_exception("SpnEstimator only supports Designators and no composed expressions");
# # ]
655 [ # # # # ]: 0 : auto spn_it = model->spns_.find(designator->table_name.text.assert_not_none());
656 [ # # ]: 0 : if (spn_it == model->spns_.end())
657 [ # # # # : 0 : throw data_model_exception("Could not find table for grouping.");
# # ]
658 : :
659 : 0 : auto &spn = spn_it->second.get();
660 [ # # ]: 0 : auto &attr_to_id = spn.get_attribute_to_id();
661 [ # # # # : 0 : if (auto attr_it = attr_to_id.find(designator->attr_name.text.assert_not_none()); attr_it != attr_to_id.end()) {
# # ]
662 [ # # ]: 0 : num_rows *= spn.estimate_number_distinct_values(attr_it->second);
663 : 0 : } else {
664 [ # # ]: 0 : num_rows *= spn.num_rows(); // if attribute is primary key, distinct values = num rows
665 : : }
666 : 0 : }
667 : 0 : model->num_rows_ = num_rows;
668 : 0 : return model;
669 : 0 : }
670 : :
671 : : std::unique_ptr<DataModel>
672 : 0 : SpnEstimator::estimate_join(const QueryGraph&, const DataModel &_left, const DataModel &_right,
673 : : const cnf::CNF &condition) const
674 : : {
675 : 0 : auto &left = as<const SpnDataModel>(_left);
676 : 0 : auto &right = as<const SpnDataModel>(_right);
677 : :
678 : 0 : auto new_left = std::make_unique<SpnDataModel>(left);
679 [ # # ]: 0 : auto new_right = std::make_unique<SpnDataModel>(right);
680 : :
681 [ # # ]: 0 : JoinTranslator jt;
682 : :
683 [ # # ]: 0 : if (not condition.empty()) {
684 : : /* only consider single equi join */
685 [ # # # # ]: 0 : jt(*condition[0][0]);
686 [ # # ]: 0 : auto first_identifier = std::make_pair(jt.join_designator[0].first, jt.join_designator[0].second);
687 [ # # ]: 0 : auto second_identifier = std::make_pair(jt.join_designator[1].first, jt.join_designator[1].second);
688 [ # # ]: 0 : SpnJoin join = std::make_pair(first_identifier, second_identifier);
689 : :
690 : : /* if a data model is only responsible for one table (one spn) add the maximum frequency of the value
691 : : * of the joined attribute */
692 [ # # # # : 0 : if (left.spns_.size() == 1) { new_left->max_frequencies_.emplace_back(max_frequency(left, join)); }
# # ]
693 [ # # # # : 0 : if (right.spns_.size() == 1) { new_right->max_frequencies_.emplace_back(max_frequency(right, join)); }
# # ]
694 : :
695 : : /* compute the estimated cardinality of the join via distinct count estimates.
696 : : * See http://www.cidrdb.org/cidr2021/papers/cidr2021_paper01.pdf */
697 [ # # ]: 0 : std::size_t mf_left = std::accumulate(
698 : 0 : new_left->max_frequencies_.begin(), new_left->max_frequencies_.end(), 1, std::multiplies<>());
699 : :
700 [ # # ]: 0 : std::size_t mf_right = std::accumulate(
701 : 0 : new_right->max_frequencies_.begin(), new_right->max_frequencies_.end(), 1, std::multiplies<>());
702 : :
703 : 0 : std::size_t left_clause = new_left->num_rows_ / mf_left;
704 : 0 : std::size_t right_clause = new_right->num_rows_ / mf_right;
705 : :
706 [ # # ]: 0 : std::size_t num_rows_join = std::min<std::size_t>(left_clause, right_clause) * mf_left * mf_right;
707 : :
708 : 0 : new_left->num_rows_ = num_rows_join;
709 : 0 : } else {
710 : : /* compute cartesian product since there is no join condition */
711 [ # # # # ]: 0 : if (left.spns_.size() == 1) { new_left->max_frequencies_.emplace_back(left.num_rows_); }
712 [ # # # # ]: 0 : if (right.spns_.size() == 1) { new_right->max_frequencies_.emplace_back(right.num_rows_); }
713 : :
714 : 0 : new_left->num_rows_ = left.num_rows_ * right.num_rows_;
715 : : }
716 : :
717 : : /* copy data from new_right to new_left to collect all information in one DataModel */
718 [ # # ]: 0 : new_left->spns_.insert(new_right->spns_.begin(), new_right->spns_.end());
719 [ # # # # ]: 0 : new_left->max_frequencies_.insert(
720 : 0 : new_left->max_frequencies_.end(), new_right->max_frequencies_.begin(), new_right->max_frequencies_.end());
721 : :
722 : 0 : return new_left;
723 : 0 : }
724 : :
725 : : template<typename PlanTable>
726 : : std::unique_ptr<DataModel>
727 : 0 : SpnEstimator::operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph&, Subproblem to_join,
728 : : const cnf::CNF &condition) const
729 : : {
730 : 0 : M_insist(not to_join.empty());
731 : : /* compute cartesian product */
732 [ # # # # : 0 : if (condition.empty()) {
# # # # ]
733 : 0 : auto model = std::make_unique<SpnDataModel>();
734 : 0 : model->num_rows_ = 1UL;
735 [ # # # # : 0 : for (auto it = to_join.begin(); it != to_join.end(); ++it)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
736 [ # # # # : 0 : model->num_rows_ *= as<const SpnDataModel>(*PT[it.as_set()].model).num_rows_;
# # # # #
# # # # #
# # # # #
# # # #
# ]
737 : 0 : return model;
738 : 0 : }
739 : :
740 : : /* get all attributes to join on */
741 : 0 : JoinTranslator jt;
742 : 0 : std::unordered_map<ThreadSafePooledString, ThreadSafePooledString> table_to_attribute;
743 [ # # # # : 0 : for (auto clause : condition) {
# # # # #
# # # # #
# # ]
744 [ # # # # : 0 : jt(*clause[0]);
# # # # #
# # # # #
# # ]
745 [ # # # # : 0 : table_to_attribute.emplace(jt.join_designator[0].first, jt.join_designator[0].second);
# # # # ]
746 [ # # # # : 0 : table_to_attribute.emplace(jt.join_designator[1].first, jt.join_designator[1].second);
# # # # ]
747 : 0 : }
748 : :
749 : : /* get first model to join */
750 [ # # # # : 0 : SpnDataModel final_model = as<const SpnDataModel>(*PT[to_join.begin().as_set()].model);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
751 [ # # # # : 0 : ThreadSafePooledString first_table_name = final_model.spns_.begin()->first;
# # # # ]
752 : :
753 : : /* if there is a join condition on this model, get the maximum frequency of the attribute */
754 [ # # # # : 0 : if (auto find_iter = table_to_attribute.find(first_table_name); find_iter != table_to_attribute.end()) {
# # # # #
# # # # #
# # ]
755 [ # # # # : 0 : final_model.max_frequencies_.emplace_back(max_frequency(final_model, find_iter->second));
# # # # #
# # # # #
# # ]
756 : 0 : }
757 : : /* else, maximum frequency is set as the number of rows (to compute the cartesian product) */
758 : : else {
759 [ # # # # : 0 : final_model.max_frequencies_.emplace_back(final_model.spns_.begin()->second.get().num_rows());
# # # # #
# # # # #
# # ]
760 : : }
761 : :
762 : : /* iteratively add the next model to join via distinct count estimates */
763 [ # # # # : 0 : for (auto it = ++to_join.begin(); it != to_join.end(); it++) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
764 [ # # # # : 0 : SpnDataModel model = as<const SpnDataModel>(*PT[it.as_set()].model);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
765 [ # # # # : 0 : ThreadSafePooledString table_name = model.spns_.begin()->first;
# # # # ]
766 : :
767 [ # # # # : 0 : if (auto find_iter = table_to_attribute.find(table_name); find_iter != table_to_attribute.end()) {
# # # # #
# # # # #
# # ]
768 [ # # # # : 0 : model.max_frequencies_.emplace_back(max_frequency(model, find_iter->second));
# # # # #
# # # # #
# # ]
769 : 0 : } else {
770 [ # # # # : 0 : model.max_frequencies_.emplace_back(model.spns_.begin()->second.get().num_rows());
# # # # #
# # # # #
# # ]
771 : : }
772 : :
773 [ # # # # ]: 0 : std::size_t mf_left = std::accumulate(
774 : 0 : final_model.max_frequencies_.begin(), final_model.max_frequencies_.end(), 1, std::multiplies<>());
775 : 0 : std::size_t mf_right = model.max_frequencies_[0];
776 : :
777 : 0 : std::size_t left_clause = final_model.num_rows_ / mf_left;
778 : 0 : std::size_t right_clause = model.num_rows_ / mf_right;
779 : :
780 [ # # # # ]: 0 : std::size_t num_rows_join = std::min<std::size_t>(left_clause, right_clause) * mf_left * mf_right;
781 : :
782 : 0 : final_model.num_rows_ = num_rows_join;
783 : :
784 : : /* copy data from model to final_model to collect all information in one DataModel */
785 [ # # # # : 0 : final_model.spns_.emplace(*model.spns_.begin());
# # # # ]
786 [ # # # # : 0 : final_model.max_frequencies_.emplace_back(model.max_frequencies_[0]);
# # # # ]
787 : 0 : }
788 : :
789 [ # # # # : 0 : return std::make_unique<SpnDataModel>(final_model);
# # # # ]
790 : 0 : }
791 : :
792 : 0 : std::size_t SpnEstimator::predict_cardinality(const DataModel &_data) const
793 : : {
794 : 0 : auto &data = as<const SpnDataModel>(_data);
795 : 0 : return data.num_rows_;
796 : : }
797 : :
798 : 0 : void SpnEstimator::print(std::ostream&) const { }
799 : :
800 : :
801 : : #define LIST_CE(X) \
802 : : X(CartesianProductEstimator, "CartesianProduct", "estimates cardinalities as Cartesian product") \
803 : : X(InjectionCardinalityEstimator, "Injected", "estimates cardinalities based on a JSON file") \
804 : : X(SpnEstimator, "Spn", "estimates cardinalities based on Sum-Product Networks")
805 : :
806 : : #define INSTANTIATE(TYPE, _1, _2) \
807 : : template std::unique_ptr<DataModel> TYPE::operator()(estimate_join_all_tag, PlanTableSmallOrDense &&PT, \
808 : : const QueryGraph &G, Subproblem to_join, \
809 : : const cnf::CNF &condition) const; \
810 : : template std::unique_ptr<DataModel> TYPE::operator()(estimate_join_all_tag, PlanTableLargeAndSparse &&PT, \
811 : : const QueryGraph &G, Subproblem to_join, \
812 : : const cnf::CNF &condition) const;
813 : : LIST_CE(INSTANTIATE)
814 : : #undef INSTANTIATE
815 : :
816 : : __attribute__((constructor(202)))
817 : 1 : static void register_cardinality_estimators()
818 : : {
819 : 1 : Catalog &C = Catalog::Get();
820 : :
821 : : #define REGISTER(TYPE, NAME, DESCRIPTION) \
822 : : C.register_cardinality_estimator<TYPE>(C.pool(NAME), DESCRIPTION);
823 [ + - + - : 1 : LIST_CE(REGISTER)
- + ]
824 : : #undef REGISTER
825 : :
826 : 1 : C.arg_parser().add<bool>(
827 : : /* group= */ "Cardinality estimation",
828 : : /* short= */ nullptr,
829 : : /* long= */ "--show-cardinality-file-example",
830 : : /* description= */ "show an example of an input JSON file for cardinality injection",
831 : 0 : [] (bool) {
832 : 0 : std::cout << "\
833 : : Example for injected cardinalities file:\n\
834 : : {\n\
835 : : database1: [\n\
836 : : {\n\
837 : : \"relations\": [\"A\", \"B\", ...],\n\
838 : : \"size\": 150\n\
839 : : },\n\
840 : : {\n\
841 : : \"relations\": [\"C\", \"A\", ...],\n\
842 : : \"size\": 100\n\
843 : : },\n\
844 : : },\n\
845 : : database2: [\n\
846 : : {\n\
847 : : \"relations\": [\"customers\"],\n\
848 : : \"size\": 1000\n\
849 : : },\n\
850 : : {\n\
851 : : \"relations\": [\"customers\", \"orders\", ...],\n\
852 : : \"size\": 50\n\
853 : : },\n\
854 : : },\n\
855 : : }\n";
856 : 0 : exit(EXIT_SUCCESS);
857 : : }
858 : : );
859 : 1 : C.arg_parser().add<const char*>(
860 : : /* group= */ "Cardinality estimation",
861 : : /* short= */ nullptr,
862 : : /* long= */ "--use-cardinality-file",
863 : : /* description= */ "inject cardinalities from the given JSON file",
864 : 0 : [] (const char *path) {
865 : 0 : options::injected_cardinalities_file = path;
866 : 0 : }
867 : : );
868 : 1 : }
|
