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