1#include "duckdb/optimizer/filter_pushdown.hpp"
2#include "duckdb/optimizer/optimizer.hpp"
3#include "duckdb/planner/binder.hpp"
4#include "duckdb/planner/expression/bound_columnref_expression.hpp"
5#include "duckdb/planner/expression_iterator.hpp"
6#include "duckdb/planner/operator/logical_empty_result.hpp"
7#include "duckdb/planner/operator/logical_projection.hpp"
8#include "duckdb/planner/operator/logical_set_operation.hpp"
9
10namespace duckdb {
11
12using Filter = FilterPushdown::Filter;
13
14static void ReplaceSetOpBindings(vector<ColumnBinding> &bindings, Filter &filter, Expression &expr,
15 LogicalSetOperation &setop) {
16 if (expr.type == ExpressionType::BOUND_COLUMN_REF) {
17 auto &colref = expr.Cast<BoundColumnRefExpression>();
18 D_ASSERT(colref.binding.table_index == setop.table_index);
19 D_ASSERT(colref.depth == 0);
20
21 // rewrite the binding by looking into the bound_tables list of the subquery
22 colref.binding = bindings[colref.binding.column_index];
23 filter.bindings.insert(x: colref.binding.table_index);
24 return;
25 }
26 ExpressionIterator::EnumerateChildren(
27 expression&: expr, callback: [&](Expression &child) { ReplaceSetOpBindings(bindings, filter, expr&: child, setop); });
28}
29
30unique_ptr<LogicalOperator> FilterPushdown::PushdownSetOperation(unique_ptr<LogicalOperator> op) {
31 D_ASSERT(op->type == LogicalOperatorType::LOGICAL_UNION || op->type == LogicalOperatorType::LOGICAL_EXCEPT ||
32 op->type == LogicalOperatorType::LOGICAL_INTERSECT);
33 auto &setop = op->Cast<LogicalSetOperation>();
34
35 D_ASSERT(op->children.size() == 2);
36 auto left_bindings = op->children[0]->GetColumnBindings();
37 auto right_bindings = op->children[1]->GetColumnBindings();
38 if (left_bindings.size() != right_bindings.size()) {
39 throw InternalException("Filter pushdown - set operation LHS and RHS have incompatible counts");
40 }
41
42 // pushdown into set operation, we can duplicate the condition and pushdown the expressions into both sides
43 FilterPushdown left_pushdown(optimizer), right_pushdown(optimizer);
44 for (idx_t i = 0; i < filters.size(); i++) {
45 // first create a copy of the filter
46 auto right_filter = make_uniq<Filter>();
47 right_filter->filter = filters[i]->filter->Copy();
48
49 // in the original filter, rewrite references to the result of the union into references to the left_index
50 ReplaceSetOpBindings(bindings&: left_bindings, filter&: *filters[i], expr&: *filters[i]->filter, setop);
51 // in the copied filter, rewrite references to the result of the union into references to the right_index
52 ReplaceSetOpBindings(bindings&: right_bindings, filter&: *right_filter, expr&: *right_filter->filter, setop);
53
54 // extract bindings again
55 filters[i]->ExtractBindings();
56 right_filter->ExtractBindings();
57
58 // move the filters into the child pushdown nodes
59 left_pushdown.filters.push_back(x: std::move(filters[i]));
60 right_pushdown.filters.push_back(x: std::move(right_filter));
61 }
62
63 op->children[0] = left_pushdown.Rewrite(op: std::move(op->children[0]));
64 op->children[1] = right_pushdown.Rewrite(op: std::move(op->children[1]));
65
66 bool left_empty = op->children[0]->type == LogicalOperatorType::LOGICAL_EMPTY_RESULT;
67 bool right_empty = op->children[1]->type == LogicalOperatorType::LOGICAL_EMPTY_RESULT;
68 if (left_empty && right_empty) {
69 // both empty: return empty result
70 return make_uniq<LogicalEmptyResult>(args: std::move(op));
71 }
72 if (left_empty) {
73 // left child is empty result
74 switch (op->type) {
75 case LogicalOperatorType::LOGICAL_UNION:
76 if (op->children[1]->type == LogicalOperatorType::LOGICAL_PROJECTION) {
77 // union with empty left side: return right child
78 auto &projection = op->children[1]->Cast<LogicalProjection>();
79 projection.table_index = setop.table_index;
80 return std::move(op->children[1]);
81 }
82 break;
83 case LogicalOperatorType::LOGICAL_EXCEPT:
84 // except: if left child is empty, return empty result
85 case LogicalOperatorType::LOGICAL_INTERSECT:
86 // intersect: if any child is empty, return empty result itself
87 return make_uniq<LogicalEmptyResult>(args: std::move(op));
88 default:
89 throw InternalException("Unsupported set operation");
90 }
91 } else if (right_empty) {
92 // right child is empty result
93 switch (op->type) {
94 case LogicalOperatorType::LOGICAL_UNION:
95 case LogicalOperatorType::LOGICAL_EXCEPT:
96 if (op->children[0]->type == LogicalOperatorType::LOGICAL_PROJECTION) {
97 // union or except with empty right child: return left child
98 auto &projection = op->children[0]->Cast<LogicalProjection>();
99 projection.table_index = setop.table_index;
100 return std::move(op->children[0]);
101 }
102 break;
103 case LogicalOperatorType::LOGICAL_INTERSECT:
104 // intersect: if any child is empty, return empty result itself
105 return make_uniq<LogicalEmptyResult>(args: std::move(op));
106 default:
107 throw InternalException("Unsupported set operation");
108 }
109 }
110 return op;
111}
112
113} // namespace duckdb
114