1#include "duckdb/execution/expression_executor.hpp"
2#include "duckdb/optimizer/filter_pushdown.hpp"
3#include "duckdb/optimizer/optimizer.hpp"
4#include "duckdb/planner/expression/bound_columnref_expression.hpp"
5#include "duckdb/planner/expression/bound_comparison_expression.hpp"
6#include "duckdb/planner/expression/bound_constant_expression.hpp"
7#include "duckdb/planner/expression_iterator.hpp"
8#include "duckdb/planner/operator/logical_comparison_join.hpp"
9#include "duckdb/planner/operator/logical_filter.hpp"
10
11namespace duckdb {
12
13using Filter = FilterPushdown::Filter;
14
15static unique_ptr<Expression> ReplaceColRefWithNull(unique_ptr<Expression> expr, unordered_set<idx_t> &right_bindings) {
16 if (expr->type == ExpressionType::BOUND_COLUMN_REF) {
17 auto &bound_colref = expr->Cast<BoundColumnRefExpression>();
18 if (right_bindings.find(x: bound_colref.binding.table_index) != right_bindings.end()) {
19 // bound colref belongs to RHS
20 // replace it with a constant NULL
21 return make_uniq<BoundConstantExpression>(args: Value(expr->return_type));
22 }
23 return expr;
24 }
25 ExpressionIterator::EnumerateChildren(
26 expression&: *expr, callback: [&](unique_ptr<Expression> &child) { child = ReplaceColRefWithNull(expr: std::move(child), right_bindings); });
27 return expr;
28}
29
30static bool FilterRemovesNull(ClientContext &context, ExpressionRewriter &rewriter, Expression *expr,
31 unordered_set<idx_t> &right_bindings) {
32 // make a copy of the expression
33 auto copy = expr->Copy();
34 // replace all BoundColumnRef expressions frmo the RHS with NULL constants in the copied expression
35 copy = ReplaceColRefWithNull(expr: std::move(copy), right_bindings);
36
37 // attempt to flatten the expression by running the expression rewriter on it
38 auto filter = make_uniq<LogicalFilter>();
39 filter->expressions.push_back(x: std::move(copy));
40 rewriter.VisitOperator(op&: *filter);
41
42 // check if all expressions are foldable
43 for (idx_t i = 0; i < filter->expressions.size(); i++) {
44 if (!filter->expressions[i]->IsFoldable()) {
45 return false;
46 }
47 // we flattened the result into a scalar, check if it is FALSE or NULL
48 auto val =
49 ExpressionExecutor::EvaluateScalar(context, expr: *filter->expressions[i]).DefaultCastAs(target_type: LogicalType::BOOLEAN);
50 // if the result of the expression with all expressions replaced with NULL is "NULL" or "false"
51 // then any extra entries generated by the LEFT OUTER JOIN will be filtered out!
52 // hence the LEFT OUTER JOIN is equivalent to an inner join
53 if (val.IsNull() || !BooleanValue::Get(value: val)) {
54 return true;
55 }
56 }
57 return false;
58}
59
60unique_ptr<LogicalOperator> FilterPushdown::PushdownLeftJoin(unique_ptr<LogicalOperator> op,
61 unordered_set<idx_t> &left_bindings,
62 unordered_set<idx_t> &right_bindings) {
63 auto &join = op->Cast<LogicalJoin>();
64 if (op->type == LogicalOperatorType::LOGICAL_DELIM_JOIN) {
65 return FinishPushdown(op: std::move(op));
66 }
67 FilterPushdown left_pushdown(optimizer), right_pushdown(optimizer);
68 // for a comparison join we create a FilterCombiner that checks if we can push conditions on LHS join conditions
69 // into the RHS of the join
70 FilterCombiner filter_combiner(optimizer);
71 const auto isComparison = (op->type == LogicalOperatorType::LOGICAL_COMPARISON_JOIN ||
72 op->type == LogicalOperatorType::LOGICAL_ASOF_JOIN);
73 if (isComparison) {
74 // add all comparison conditions
75 auto &comparison_join = op->Cast<LogicalComparisonJoin>();
76 for (auto &cond : comparison_join.conditions) {
77 filter_combiner.AddFilter(
78 expr: make_uniq<BoundComparisonExpression>(args&: cond.comparison, args: cond.left->Copy(), args: cond.right->Copy()));
79 }
80 }
81 // now check the set of filters
82 for (idx_t i = 0; i < filters.size(); i++) {
83 auto side = JoinSide::GetJoinSide(bindings: filters[i]->bindings, left_bindings, right_bindings);
84 if (side == JoinSide::LEFT) {
85 // bindings match left side
86 // we can push the filter into the left side
87 if (isComparison) {
88 // we MIGHT be able to push it down the RHS as well, but only if it is a comparison that matches the
89 // join predicates we use the FilterCombiner to figure this out add the expression to the FilterCombiner
90 filter_combiner.AddFilter(expr: filters[i]->filter->Copy());
91 }
92 left_pushdown.filters.push_back(x: std::move(filters[i]));
93 // erase the filter from the list of filters
94 filters.erase(position: filters.begin() + i);
95 i--;
96 } else {
97 // bindings match right side or both sides: we cannot directly push it into the right
98 // however, if the filter removes rows with null values from the RHS we can turn the left outer join
99 // in an inner join, and then push down as we would push down an inner join
100 if (FilterRemovesNull(context&: optimizer.context, rewriter&: optimizer.rewriter, expr: filters[i]->filter.get(), right_bindings)) {
101 // the filter removes NULL values, turn it into an inner join
102 join.join_type = JoinType::INNER;
103 // now we can do more pushdown
104 // move all filters we added to the left_pushdown back into the filter list
105 for (auto &left_filter : left_pushdown.filters) {
106 filters.push_back(x: std::move(left_filter));
107 }
108 // now push down the inner join
109 return PushdownInnerJoin(op: std::move(op), left_bindings, right_bindings);
110 }
111 }
112 }
113 // finally we check the FilterCombiner to see if there are any predicates we can push into the RHS
114 // we only added (1) predicates that have JoinSide::BOTH from the conditions, and
115 // (2) predicates that have JoinSide::LEFT from the filters
116 // we check now if this combination generated any new filters that are only on JoinSide::RIGHT
117 // this happens if, e.g. a join condition is (i=a) and there is a filter (i=500), we can then push the filter
118 // (a=500) into the RHS
119 filter_combiner.GenerateFilters(callback: [&](unique_ptr<Expression> filter) {
120 if (JoinSide::GetJoinSide(expression&: *filter, left_bindings, right_bindings) == JoinSide::RIGHT) {
121 right_pushdown.AddFilter(expr: std::move(filter));
122 }
123 });
124 right_pushdown.GenerateFilters();
125 op->children[0] = left_pushdown.Rewrite(op: std::move(op->children[0]));
126 op->children[1] = right_pushdown.Rewrite(op: std::move(op->children[1]));
127 return PushFinalFilters(op: std::move(op));
128}
129
130} // namespace duckdb
131