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