1#include "duckdb/common/vector_operations/vector_operations.hpp"
2#include "duckdb/planner/expression/bound_conjunction_expression.hpp"
3#include "duckdb/execution/adaptive_filter.hpp"
4#include <vector>
5
6using namespace duckdb;
7using namespace std;
8
9AdaptiveFilter::AdaptiveFilter(Expression &expr)
10 : iteration_count(0), observe_interval(10), execute_interval(20), warmup(true) {
11 auto &conj_expr = (BoundConjunctionExpression &)expr;
12 assert(conj_expr.children.size() > 1);
13 for (idx_t idx = 0; idx < conj_expr.children.size(); idx++) {
14 permutation.push_back(idx);
15 if (idx != conj_expr.children.size() - 1) {
16 swap_likeliness.push_back(100);
17 }
18 }
19 right_random_border = 100 * (conj_expr.children.size() - 1);
20}
21
22AdaptiveFilter::AdaptiveFilter(unordered_map<idx_t, vector<TableFilter>> &table_filters)
23 : iteration_count(0), observe_interval(10), execute_interval(20), warmup(true) {
24 for (auto &table_filter : table_filters) {
25 permutation.push_back(table_filter.first);
26 swap_likeliness.push_back(100);
27 }
28 swap_likeliness.pop_back();
29 right_random_border = 100 * (table_filters.size() - 1);
30}
31void AdaptiveFilter::AdaptRuntimeStatistics(double duration) {
32 iteration_count++;
33 runtime_sum += duration;
34
35 if (!warmup) {
36 // the last swap was observed
37 if (observe && iteration_count == observe_interval) {
38 // keep swap if runtime decreased, else reverse swap
39 if (prev_mean - (runtime_sum / iteration_count) <= 0) {
40 // reverse swap because runtime didn't decrease
41 swap(permutation[swap_idx], permutation[swap_idx + 1]);
42
43 // decrease swap likeliness, but make sure there is always a small likeliness left
44 if (swap_likeliness[swap_idx] > 1) {
45 swap_likeliness[swap_idx] /= 2;
46 }
47 } else {
48 // keep swap because runtime decreased, reset likeliness
49 swap_likeliness[swap_idx] = 100;
50 }
51 observe = false;
52
53 // reset values
54 iteration_count = 0;
55 runtime_sum = 0.0;
56 } else if (!observe && iteration_count == execute_interval) {
57 // save old mean to evaluate swap
58 prev_mean = runtime_sum / iteration_count;
59
60 // get swap index and swap likeliness
61 uniform_int_distribution<int> distribution(1, right_random_border); // a <= i <= b
62 idx_t random_number = distribution(generator) - 1;
63
64 swap_idx = random_number / 100; // index to be swapped
65 idx_t likeliness = random_number - 100 * swap_idx; // random number between [0, 100)
66
67 // check if swap is going to happen
68 if (swap_likeliness[swap_idx] > likeliness) { // always true for the first swap of an index
69 // swap
70 swap(permutation[swap_idx], permutation[swap_idx + 1]);
71
72 // observe whether swap will be applied
73 observe = true;
74 }
75
76 // reset values
77 iteration_count = 0;
78 runtime_sum = 0.0;
79 }
80 } else {
81 if (iteration_count == 5) {
82 // initially set all values
83 iteration_count = 0;
84 runtime_sum = 0.0;
85 observe = false;
86 warmup = false;
87 }
88 }
89}
90