1#include "duckdb/common/vector_operations/vector_operations.hpp"
2#include "duckdb/execution/expression_executor.hpp"
3#include "duckdb/planner/expression/bound_conjunction_expression.hpp"
4#include "duckdb/execution/adaptive_filter.hpp"
5
6#include <chrono>
7#include <random>
8#include <vector>
9
10using namespace duckdb;
11using namespace std;
12using namespace chrono;
13
14struct ConjunctionState : public ExpressionState {
15 ConjunctionState(Expression &expr, ExpressionExecutorState &root)
16 : ExpressionState(expr, root) {
17 adaptive_filter = make_unique<AdaptiveFilter>(expr);
18 }
19 unique_ptr<AdaptiveFilter> adaptive_filter;
20};
21
22unique_ptr<ExpressionState> ExpressionExecutor::InitializeState(BoundConjunctionExpression &expr,
23 ExpressionExecutorState &root) {
24 auto result = make_unique<ConjunctionState>(expr, root);
25 for (auto &child : expr.children) {
26 result->AddChild(child.get());
27 }
28 return move(result);
29}
30
31void ExpressionExecutor::Execute(BoundConjunctionExpression &expr, ExpressionState *state, const SelectionVector *sel,
32 idx_t count, Vector &result) {
33 // execute the children
34 for (idx_t i = 0; i < expr.children.size(); i++) {
35 Vector current_result(TypeId::BOOL);
36 Execute(*expr.children[i], state->child_states[i].get(), sel, count, current_result);
37 if (i == 0) {
38 // move the result
39 result.Reference(current_result);
40 } else {
41 Vector intermediate(TypeId::BOOL);
42 // AND/OR together
43 switch (expr.type) {
44 case ExpressionType::CONJUNCTION_AND:
45 VectorOperations::And(current_result, result, intermediate, count);
46 break;
47 case ExpressionType::CONJUNCTION_OR:
48 VectorOperations::Or(current_result, result, intermediate, count);
49 break;
50 default:
51 throw NotImplementedException("Unknown conjunction type!");
52 }
53 result.Reference(intermediate);
54 }
55 }
56}
57
58idx_t ExpressionExecutor::Select(BoundConjunctionExpression &expr, ExpressionState *state_, const SelectionVector *sel,
59 idx_t count, SelectionVector *true_sel, SelectionVector *false_sel) {
60 auto state = (ConjunctionState *)state_;
61
62 if (expr.type == ExpressionType::CONJUNCTION_AND) {
63 // get runtime statistics
64 auto start_time = high_resolution_clock::now();
65
66 const SelectionVector *current_sel = sel;
67 idx_t current_count = count;
68 idx_t false_count = 0;
69
70 unique_ptr<SelectionVector> temp_true, temp_false;
71 if (false_sel) {
72 temp_false = make_unique<SelectionVector>(STANDARD_VECTOR_SIZE);
73 }
74 if (!true_sel) {
75 temp_true = make_unique<SelectionVector>(STANDARD_VECTOR_SIZE);
76 true_sel = temp_true.get();
77 }
78 for (idx_t i = 0; i < expr.children.size(); i++) {
79 idx_t tcount =
80 Select(*expr.children[state->adaptive_filter->permutation[i]], state->child_states[state->adaptive_filter->permutation[i]].get(),
81 current_sel, current_count, true_sel, temp_false.get());
82 idx_t fcount = current_count - tcount;
83 if (fcount > 0 && false_sel) {
84 // move failing tuples into the false_sel
85 // tuples passed, move them into the actual result vector
86 for (idx_t i = 0; i < fcount; i++) {
87 false_sel->set_index(false_count++, temp_false->get_index(i));
88 }
89 }
90 current_count = tcount;
91 if (current_count == 0) {
92 break;
93 }
94 if (current_count < count) {
95 // tuples were filtered out: move on to using the true_sel to only evaluate passing tuples in subsequent
96 // iterations
97 current_sel = true_sel;
98 }
99 }
100
101 // adapt runtime statistics
102 auto end_time = high_resolution_clock::now();
103 state->adaptive_filter->AdaptRuntimeStatistics(
104 duration_cast<duration<double>>(end_time - start_time).count());
105 return current_count;
106 } else {
107 // get runtime statistics
108 auto start_time = high_resolution_clock::now();
109
110 const SelectionVector *current_sel = sel;
111 idx_t current_count = count;
112 idx_t result_count = 0;
113
114 unique_ptr<SelectionVector> temp_true, temp_false;
115 if (true_sel) {
116 temp_true = make_unique<SelectionVector>(STANDARD_VECTOR_SIZE);
117 }
118 if (!false_sel) {
119 temp_false = make_unique<SelectionVector>(STANDARD_VECTOR_SIZE);
120 false_sel = temp_false.get();
121 }
122 for (idx_t i = 0; i < expr.children.size(); i++) {
123 idx_t tcount =
124 Select(*expr.children[state->adaptive_filter->permutation[i]], state->child_states[state->adaptive_filter->permutation[i]].get(),
125 current_sel, current_count, temp_true.get(), false_sel);
126 if (tcount > 0) {
127 if (true_sel) {
128 // tuples passed, move them into the actual result vector
129 for (idx_t i = 0; i < tcount; i++) {
130 true_sel->set_index(result_count++, temp_true->get_index(i));
131 }
132 }
133 // now move on to check only the non-passing tuples
134 current_count -= tcount;
135 current_sel = false_sel;
136 }
137 }
138
139 // adapt runtime statistics
140 auto end_time = high_resolution_clock::now();
141 state->adaptive_filter->AdaptRuntimeStatistics(
142 duration_cast<duration<double>>(end_time - start_time).count());
143 return result_count;
144 }
145}
146