/src/duckdb/src/optimizer/outer_join_simplification.cpp

Source
#include "duckdb/optimizer/outer_join_simplification.hpp"

#include "duckdb/planner/operator/list.hpp"
#include "duckdb/planner/expression/bound_cast_expression.hpp"
#include "duckdb/planner/expression/bound_columnref_expression.hpp"
#include "duckdb/planner/expression/bound_comparison_expression.hpp"
#include "duckdb/planner/expression/bound_constant_expression.hpp"
#include "duckdb/planner/expression/bound_operator_expression.hpp"
#include "duckdb/planner/expression/bound_function_expression.hpp"
#include "duckdb/planner/expression_iterator.hpp"

namespace duckdb {

//===--------------------------------------------------------------------===//
// Setup
//===--------------------------------------------------------------------===//

OuterJoinSimplification::OuterJoinSimplification() {
}

OuterJoinSimplification::OuterJoinSimplification(column_binding_set_t required_columns_p)
    : required_columns(std::move(required_columns_p)), initialized_required_columns(true) {
}

//===--------------------------------------------------------------------===//
// Column Binding Helpers
//===--------------------------------------------------------------------===//

void OuterJoinSimplification::AddColumnReferences(const Expression &expr, column_binding_set_t &bindings) {
  ExpressionIterator::VisitExpression<BoundColumnRefExpression>(expr, [&](const BoundColumnRefExpression &colref) {
    if (colref.Depth() == 0) {
      bindings.insert(colref.Binding());
    }
  });
}

void OuterJoinSimplification::AddRequiredColumns(const Expression &expr) {
  AddColumnReferences(expr, required_columns);
}

void OuterJoinSimplification::AddRequiredColumns(const JoinCondition &condition) {
  if (condition.IsComparison()) {
    AddRequiredColumns(condition.GetLHS());
    AddRequiredColumns(condition.GetRHS());
  } else {
    AddRequiredColumns(condition.GetJoinExpression());
  }
}

void OuterJoinSimplification::AddRequiredColumns(const vector<JoinCondition> &conditions) {
  for (const auto &condition : conditions) {
    AddRequiredColumns(condition);
  }
}

bool OuterJoinSimplification::GetColumnBinding(const Expression &expr, ColumnBinding &binding) {
  if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
    if (!BoundCastExpression::IsCast(expr)) {
      return false;
    }
    auto &cast = expr.Cast<BoundFunctionExpression>();
    return GetColumnBinding(BoundCastExpression::Child(cast), binding);
  }
  auto &colref = expr.Cast<BoundColumnRefExpression>();
  binding = colref.Binding();
  return true;
}

bool OuterJoinSimplification::GetNullPreservingColumnBinding(const Expression &expr, ColumnBinding &binding) {
  if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
    if (!BoundCastExpression::IsCast(expr)) {
      return false;
    }
    auto &cast = expr.Cast<BoundFunctionExpression>();
    if (BoundCastExpression::IsTryCast(cast) ||
        !BoundCastExpression::CastIsInvertible(BoundCastExpression::SourceType(cast), cast.GetReturnType())) {
      return false;
    }
    return GetNullPreservingColumnBinding(BoundCastExpression::Child(cast), binding);
  }
  auto &colref = expr.Cast<BoundColumnRefExpression>();
  binding = colref.Binding();
  return true;
}

//===--------------------------------------------------------------------===//
// NULL Constraint Tracking
//===--------------------------------------------------------------------===//

void OuterJoinSimplification::HandleExpression(const Expression &expr) {
  ColumnBinding binding;
  if (GetColumnBinding(expr, binding)) {
    null_filtered_columns.insert(binding);
  }
}

void OuterJoinSimplification::HandleFilterExpression(const Expression &expr) {
  if (expr.GetExpressionClass() == ExpressionClass::BOUND_OPERATOR &&
      expr.GetExpressionType() == ExpressionType::OPERATOR_IS_NOT_NULL) {
    const auto &is_not_null = expr.Cast<BoundOperatorExpression>();
    HandleExpression(*is_not_null.GetChildren()[0]);
    AddRequiredColumns(expr);
    return;
  }

  if (expr.GetExpressionClass() == ExpressionClass::BOUND_OPERATOR &&
      expr.GetExpressionType() == ExpressionType::OPERATOR_IS_NULL) {
    const auto &is_null = expr.Cast<BoundOperatorExpression>();
    if (!HandleIsNullExpression(*is_null.GetChildren()[0])) {
      AddRequiredColumns(expr);
    }
    return;
  }

  if (!BoundComparisonExpression::IsComparison(expr)) {
    AddRequiredColumns(expr);
    return;
  }

  AddRequiredColumns(expr);
  if (!FiltersNulls(expr.GetExpressionType())) {
    return;
  }
  const auto &comparison = expr.Cast<BoundFunctionExpression>();
  HandleExpression(BoundComparisonExpression::Left(comparison));
  HandleExpression(BoundComparisonExpression::Right(comparison));
}

bool OuterJoinSimplification::HandleIsNullExpression(const Expression &expr) {
  ColumnBinding binding;
  if (GetNullPreservingColumnBinding(expr, binding)) {
    null_required_columns.insert(binding);
    return true;
  }
  return false;
}

bool OuterJoinSimplification::IsNullFilter(const Expression &expr, ColumnBinding &binding) {
  if (expr.GetExpressionClass() != ExpressionClass::BOUND_OPERATOR ||
      expr.GetExpressionType() != ExpressionType::OPERATOR_IS_NULL) {
    return false;
  }
  auto &is_null = expr.Cast<BoundOperatorExpression>();
  auto &child = *is_null.GetChildren()[0];
  return GetNullPreservingColumnBinding(child, binding);
}

void OuterJoinSimplification::InitializeRequiredColumns(LogicalOperator &op) {
  if (initialized_required_columns) {
    return;
  }
  for (const auto &binding : op.GetColumnBindings()) {
    required_columns.insert(binding);
  }
  initialized_required_columns = true;
}

bool OuterJoinSimplification::FiltersNulls(ExpressionType comparison_type) {
  return comparison_type != ExpressionType::COMPARE_DISTINCT_FROM &&
         comparison_type != ExpressionType::COMPARE_NOT_DISTINCT_FROM;
}

//===--------------------------------------------------------------------===//
// Join Rewrite Helpers
//===--------------------------------------------------------------------===//

vector<ColumnBinding> OuterJoinSimplification::GetRightBindings(LogicalJoin &join) {
  return LogicalOperator::MapBindings(join.children[1]->GetColumnBindings(), join.right_projection_map);
}

bool OuterJoinSimplification::HasNullRequiredColumns(const vector<ColumnBinding> &bindings) {
  for (const auto &binding : bindings) {
    if (null_required_columns.find(binding) != null_required_columns.end()) {
      return true;
    }
  }
  return false;
}

bool OuterJoinSimplification::HasRequiredColumns(const vector<ColumnBinding> &bindings) {
  for (const auto &binding : bindings) {
    if (required_columns.find(binding) != required_columns.end()) {
      return true;
    }
  }
  return false;
}

void OuterJoinSimplification::EraseNullRequiredColumns(LogicalOperator &child) {
  for (const auto &binding : child.GetColumnBindings()) {
    null_required_columns.erase(binding);
  }
}

void OuterJoinSimplification::MarkEliminatedNullColumns(const vector<ColumnBinding> &bindings) {
  for (const auto &binding : bindings) {
    eliminated_null_columns.insert(binding);
  }
}

bool OuterJoinSimplification::TryConvertLeftToAntiJoin(LogicalComparisonJoin &join) {
  if (join.join_type != JoinType::LEFT) {
    return false;
  }

  auto right_bindings = GetRightBindings(join);
  if (!HasNullRequiredColumns(right_bindings) || HasRequiredColumns(right_bindings)) {
    return false;
  }

  column_binding_set_t match_non_null_rhs;
  for (const auto &condition : join.conditions) {
    if (!condition.IsComparison() || !FiltersNulls(condition.GetComparisonType())) {
      continue;
    }
    ColumnBinding rhs_binding;
    if (!GetColumnBinding(condition.GetRHS(), rhs_binding)) {
      continue;
    }
    match_non_null_rhs.insert(rhs_binding);
  }

  for (const auto &binding : right_bindings) {
    if (null_required_columns.find(binding) == null_required_columns.end()) {
      continue;
    }
    if (match_non_null_rhs.find(binding) == match_non_null_rhs.end()) {
      continue;
    }
    join.join_type = JoinType::ANTI;
    return true;
  }
  return false;
}

void OuterJoinSimplification::SimplifyOuterJoinType(LogicalComparisonJoin &join) {
  bool preserves_null_extended_rows[2] = {join.join_type == JoinType::LEFT || join.join_type == JoinType::OUTER,
                                          join.join_type == JoinType::RIGHT || join.join_type == JoinType::OUTER};
  for (idx_t child_idx = 0; child_idx < 2; child_idx++) {
    for (const auto &binding : join.children[child_idx]->GetColumnBindings()) {
      if (null_filtered_columns.find(binding) != null_filtered_columns.end()) {
        // Rejecting NULLs in one child removes preservation of NULL extended rows for the other child.
        preserves_null_extended_rows[1 - child_idx] = false;
        break;
      }
    }
  }

  if (!preserves_null_extended_rows[0] && !preserves_null_extended_rows[1]) {
    join.join_type = JoinType::INNER;
    return;
  }

  if (preserves_null_extended_rows[0] && !preserves_null_extended_rows[1]) {
    D_ASSERT(join.join_type == JoinType::LEFT || join.join_type == JoinType::OUTER);
    join.join_type = JoinType::LEFT;
  } else if (!preserves_null_extended_rows[0] && preserves_null_extended_rows[1]) {
    D_ASSERT(join.join_type == JoinType::RIGHT || join.join_type == JoinType::OUTER);
    join.join_type = JoinType::RIGHT;
  } else {
    D_ASSERT(join.join_type == JoinType::OUTER);
    join.join_type = JoinType::OUTER;
  }
}

//===--------------------------------------------------------------------===//
// Operator Visitors
//===--------------------------------------------------------------------===//

void OuterJoinSimplification::VisitComparisonJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
  switch (join.join_type) {
  case JoinType::INNER:
  case JoinType::SEMI:
    VisitInnerOrSemiJoin(join, op);
    return;
  case JoinType::LEFT:
  case JoinType::RIGHT:
  case JoinType::OUTER:
    VisitOuterJoin(join, op);
    return;
  default:
    break;
  }
  VisitUnsupportedOperator(op);
}

void OuterJoinSimplification::VisitInnerOrSemiJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
  for (const auto &condition : join.conditions) {
    if (!condition.IsComparison()) {
      continue;
    }
    AddRequiredColumns(condition);
    if (!FiltersNulls(condition.GetComparisonType())) {
      continue;
    }
    HandleExpression(condition.GetLHS());
    HandleExpression(condition.GetRHS());
  }
  VisitOperatorChildren(op);
}

void OuterJoinSimplification::VisitOuterJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
  if (TryConvertLeftToAntiJoin(join)) {
    auto right_bindings = GetRightBindings(join);
    AddRequiredColumns(join.conditions);
    EraseNullRequiredColumns(*join.children[1]);
    VisitOperatorChildren(op);
    // only operators above the join see the right side as NULL, not the right child itself
    MarkEliminatedNullColumns(right_bindings);
    return;
  }

  SimplifyOuterJoinType(join);
  if (join.join_type == JoinType::INNER) {
    VisitOperator(op);
    return;
  }

  AddRequiredColumns(join.conditions);
  // NULL values in the NULL-extended side can be introduced by this join itself,
  // so columns of that side are not guaranteed to be NULL below the join
  if (join.join_type == JoinType::LEFT || join.join_type == JoinType::OUTER) {
    EraseNullRequiredColumns(*join.children[1]);
  }
  if (join.join_type == JoinType::RIGHT || join.join_type == JoinType::OUTER) {
    EraseNullRequiredColumns(*join.children[0]);
  }
  VisitOperatorChildren(op);
}

void OuterJoinSimplification::VisitProjection(LogicalProjection &projection, LogicalOperator &op) {
  vector<pair<idx_t, ColumnBinding>> direct_projection_map;
  for (idx_t col_idx = 0; col_idx < projection.expressions.size(); col_idx++) {
    auto &expr = *projection.expressions[col_idx];
    const ColumnBinding binding(projection.table_index, ProjectionIndex(col_idx));
    if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
      AddRequiredColumns(expr);
      continue;
    }

    auto input_binding = expr.Cast<BoundColumnRefExpression>().Binding();
    direct_projection_map.emplace_back(col_idx, input_binding);
    if (null_filtered_columns.find(binding) != null_filtered_columns.end()) {
      null_filtered_columns.insert(input_binding);
    }
    if (null_required_columns.find(binding) != null_required_columns.end()) {
      null_required_columns.insert(input_binding);
    }
  }
  VisitOperatorChildren(op);

  for (const auto &entry : direct_projection_map) {
    auto col_idx = entry.first;
    auto input_binding = entry.second;
    if (eliminated_null_columns.find(input_binding) == eliminated_null_columns.end()) {
      continue;
    }
    const ColumnBinding output_binding(projection.table_index, ProjectionIndex(col_idx));
    auto type = projection.expressions[col_idx]->GetReturnType();
    projection.expressions[col_idx] = make_uniq<BoundConstantExpression>(Value(type));
    eliminated_null_columns.insert(output_binding);
  }
}

void OuterJoinSimplification::VisitFilter(LogicalFilter &filter, LogicalOperator &op) {
  filter.SplitPredicates(filter.expressions);
  for (const auto &expr : filter.expressions) {
    HandleFilterExpression(*expr);
  }
  VisitOperatorChildren(op);

  for (idx_t i = 0; i < filter.expressions.size(); i++) {
    ColumnBinding binding;
    if (!IsNullFilter(*filter.expressions[i], binding)) {
      continue;
    }
    if (eliminated_null_columns.find(binding) == eliminated_null_columns.end()) {
      continue;
    }
    filter.expressions.erase_at(i);
    i--;
  }
}

void OuterJoinSimplification::VisitOrder(LogicalOrder &order, LogicalOperator &op) {
  for (const auto &order_node : order.orders) {
    AddRequiredColumns(*order_node.expression);
  }
  VisitOperatorChildren(op);
}

void OuterJoinSimplification::VisitTopN(LogicalTopN &top_n, LogicalOperator &op) {
  for (const auto &order_node : top_n.orders) {
    AddRequiredColumns(*order_node.expression);
  }
  OuterJoinSimplification child_simplification(required_columns);
  child_simplification.VisitOperator(*op.children[0]);
}

void OuterJoinSimplification::VisitAggregate(LogicalAggregate &aggregate, LogicalOperator &op) {
  column_binding_set_t child_required_columns;
  for (const auto &expr : aggregate.groups) {
    AddColumnReferences(*expr, child_required_columns);
  }
  for (const auto &expr : aggregate.expressions) {
    AddColumnReferences(*expr, child_required_columns);
  }
  OuterJoinSimplification child_simplification(std::move(child_required_columns));
  child_simplification.VisitOperator(*op.children[0]);
}

void OuterJoinSimplification::VisitUnsupportedOperator(LogicalOperator &op) {
  for (auto &child : op.children) {
    column_binding_set_t child_required_columns;
    for (const auto &binding : child->GetColumnBindings()) {
      child_required_columns.insert(binding);
    }
    OuterJoinSimplification outer_join_simplification(std::move(child_required_columns));
    outer_join_simplification.VisitOperator(*child);
  }
}

void OuterJoinSimplification::VisitOperator(LogicalOperator &op) {
  InitializeRequiredColumns(op);

  switch (op.type) {
  case LogicalOperatorType::LOGICAL_COMPARISON_JOIN: {
    auto &join = op.Cast<LogicalComparisonJoin>();
    VisitComparisonJoin(join, op);
    return;
  }
  case LogicalOperatorType::LOGICAL_PROJECTION: {
    auto &projection = op.Cast<LogicalProjection>();
    VisitProjection(projection, op);
    return;
  }
  case LogicalOperatorType::LOGICAL_FILTER: {
    auto &filter = op.Cast<LogicalFilter>();
    VisitFilter(filter, op);
    return;
  }
  case LogicalOperatorType::LOGICAL_ORDER_BY: {
    auto &order = op.Cast<LogicalOrder>();
    VisitOrder(order, op);
    return;
  }
  case LogicalOperatorType::LOGICAL_TOP_N: {
    auto &top_n = op.Cast<LogicalTopN>();
    VisitTopN(top_n, op);
    return;
  }
  case LogicalOperatorType::LOGICAL_LIMIT: {
    OuterJoinSimplification child_simplification(required_columns);
    child_simplification.VisitOperator(*op.children[0]);
    return;
  }
  case LogicalOperatorType::LOGICAL_AGGREGATE_AND_GROUP_BY: {
    auto &aggregate = op.Cast<LogicalAggregate>();
    VisitAggregate(aggregate, op);
    return;
  }
  default:
    // Passthrough not supported. TODO: could pass through more operators like LOGICAL_UNION
    break;
  }

  VisitUnsupportedOperator(op);
}

} // namespace duckdb

Coverage Report

Created: 2026-11-11 06:47

Line	Count	Source
1		#include "duckdb/optimizer/outer_join_simplification.hpp"
2
3		#include "duckdb/planner/operator/list.hpp"
4		#include "duckdb/planner/expression/bound_cast_expression.hpp"
5		#include "duckdb/planner/expression/bound_columnref_expression.hpp"
6		#include "duckdb/planner/expression/bound_comparison_expression.hpp"
7		#include "duckdb/planner/expression/bound_constant_expression.hpp"
8		#include "duckdb/planner/expression/bound_operator_expression.hpp"
9		#include "duckdb/planner/expression/bound_function_expression.hpp"
10		#include "duckdb/planner/expression_iterator.hpp"
11
12		namespace duckdb {
13
14		//===--------------------------------------------------------------------===//
15		// Setup
16		//===--------------------------------------------------------------------===//
17
18	63.9k	OuterJoinSimplification::OuterJoinSimplification() {
19	63.9k	}
20
21		OuterJoinSimplification::OuterJoinSimplification(column_binding_set_t required_columns_p)
22	143k	: required_columns(std::move(required_columns_p)), initialized_required_columns(true) {
23	143k	}
24
25		//===--------------------------------------------------------------------===//
26		// Column Binding Helpers
27		//===--------------------------------------------------------------------===//
28
29	417k	void OuterJoinSimplification::AddColumnReferences(const Expression &expr, column_binding_set_t &bindings) {
30	417k	ExpressionIterator::VisitExpression<BoundColumnRefExpression>(expr, [&](const BoundColumnRefExpression &colref) {
31	106k	if (colref.Depth() == 0) {
32	106k	bindings.insert(colref.Binding());
33	106k	}
34	106k	});
35	417k	}
36
37	345k	void OuterJoinSimplification::AddRequiredColumns(const Expression &expr) {
38	345k	AddColumnReferences(expr, required_columns);
39	345k	}
40
41	0	void OuterJoinSimplification::AddRequiredColumns(const JoinCondition &condition) {
42	0	if (condition.IsComparison()) {
43	0	AddRequiredColumns(condition.GetLHS());
44	0	AddRequiredColumns(condition.GetRHS());
45	0	} else {
46	0	AddRequiredColumns(condition.GetJoinExpression());
47	0	}
48	0	}
49
50	0	void OuterJoinSimplification::AddRequiredColumns(const vector<JoinCondition> &conditions) {
51	0	for (const auto &condition : conditions) {
52	0	AddRequiredColumns(condition);
53	0	}
54	0	}
55
56	0	bool OuterJoinSimplification::GetColumnBinding(const Expression &expr, ColumnBinding &binding) {
57	0	if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
58	0	if (!BoundCastExpression::IsCast(expr)) {
59	0	return false;
60	0	}
61	0	auto &cast = expr.Cast<BoundFunctionExpression>();
62	0	return GetColumnBinding(BoundCastExpression::Child(cast), binding);
63	0	}
64	0	auto &colref = expr.Cast<BoundColumnRefExpression>();
65	0	binding = colref.Binding();
66	0	return true;
67	0	}
68
69	0	bool OuterJoinSimplification::GetNullPreservingColumnBinding(const Expression &expr, ColumnBinding &binding) {
70	0	if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
71	0	if (!BoundCastExpression::IsCast(expr)) {
72	0	return false;
73	0	}
74	0	auto &cast = expr.Cast<BoundFunctionExpression>();
75	0	if (BoundCastExpression::IsTryCast(cast) \|\|
76	0	!BoundCastExpression::CastIsInvertible(BoundCastExpression::SourceType(cast), cast.GetReturnType())) {
77	0	return false;
78	0	}
79	0	return GetNullPreservingColumnBinding(BoundCastExpression::Child(cast), binding);
80	0	}
81	0	auto &colref = expr.Cast<BoundColumnRefExpression>();
82	0	binding = colref.Binding();
83	0	return true;
84	0	}
85
86		//===--------------------------------------------------------------------===//
87		// NULL Constraint Tracking
88		//===--------------------------------------------------------------------===//
89
90	0	void OuterJoinSimplification::HandleExpression(const Expression &expr) {
91	0	ColumnBinding binding;
92	0	if (GetColumnBinding(expr, binding)) {
93	0	null_filtered_columns.insert(binding);
94	0	}
95	0	}
96
97	15.4k	void OuterJoinSimplification::HandleFilterExpression(const Expression &expr) {
98	15.4k	if (expr.GetExpressionClass() == ExpressionClass::BOUND_OPERATOR &&
99	15.4k	expr.GetExpressionType() == ExpressionType::OPERATOR_IS_NOT_NULL) {
100	0	const auto &is_not_null = expr.Cast<BoundOperatorExpression>();
101	0	HandleExpression(*is_not_null.GetChildren()[0]);
102	0	AddRequiredColumns(expr);
103	0	return;
104	0	}
105
106	15.4k	if (expr.GetExpressionClass() == ExpressionClass::BOUND_OPERATOR &&
107	15.4k	expr.GetExpressionType() == ExpressionType::OPERATOR_IS_NULL) {
108	0	const auto &is_null = expr.Cast<BoundOperatorExpression>();
109	0	if (!HandleIsNullExpression(*is_null.GetChildren()[0])) {
110	0	AddRequiredColumns(expr);
111	0	}
112	0	return;
113	0	}
114
115	15.4k	if (!BoundComparisonExpression::IsComparison(expr)) {
116	15.4k	AddRequiredColumns(expr);
117	15.4k	return;
118	15.4k	}
119
120	0	AddRequiredColumns(expr);
121	0	if (!FiltersNulls(expr.GetExpressionType())) {
122	0	return;
123	0	}
124	0	const auto &comparison = expr.Cast<BoundFunctionExpression>();
125	0	HandleExpression(BoundComparisonExpression::Left(comparison));
126	0	HandleExpression(BoundComparisonExpression::Right(comparison));
127	0	}
128
129	0	bool OuterJoinSimplification::HandleIsNullExpression(const Expression &expr) {
130	0	ColumnBinding binding;
131	0	if (GetNullPreservingColumnBinding(expr, binding)) {
132	0	null_required_columns.insert(binding);
133	0	return true;
134	0	}
135	0	return false;
136	0	}
137
138	15.4k	bool OuterJoinSimplification::IsNullFilter(const Expression &expr, ColumnBinding &binding) {
139	15.4k	if (expr.GetExpressionClass() != ExpressionClass::BOUND_OPERATOR \|\|
140	15.4k	expr.GetExpressionType() != ExpressionType::OPERATOR_IS_NULL) {
141	15.4k	return false;
142	15.4k	}
143	0	auto &is_null = expr.Cast<BoundOperatorExpression>();
144	0	auto &child = *is_null.GetChildren()[0];
145	0	return GetNullPreservingColumnBinding(child, binding);
146	15.4k	}
147
148	388k	void OuterJoinSimplification::InitializeRequiredColumns(LogicalOperator &op) {
149	388k	if (initialized_required_columns) {
150	324k	return;
151	324k	}
152	1.84M	for (const auto &binding : op.GetColumnBindings()) {
153	1.84M	required_columns.insert(binding);
154	1.84M	}
155	63.9k	initialized_required_columns = true;
156	63.9k	}
157
158	0	bool OuterJoinSimplification::FiltersNulls(ExpressionType comparison_type) {
159	0	return comparison_type != ExpressionType::COMPARE_DISTINCT_FROM &&
160	0	comparison_type != ExpressionType::COMPARE_NOT_DISTINCT_FROM;
161	0	}
162
163		//===--------------------------------------------------------------------===//
164		// Join Rewrite Helpers
165		//===--------------------------------------------------------------------===//
166
167	0	vector<ColumnBinding> OuterJoinSimplification::GetRightBindings(LogicalJoin &join) {
168	0	return LogicalOperator::MapBindings(join.children[1]->GetColumnBindings(), join.right_projection_map);
169	0	}
170
171	0	bool OuterJoinSimplification::HasNullRequiredColumns(const vector<ColumnBinding> &bindings) {
172	0	for (const auto &binding : bindings) {
173	0	if (null_required_columns.find(binding) != null_required_columns.end()) {
174	0	return true;
175	0	}
176	0	}
177	0	return false;
178	0	}
179
180	0	bool OuterJoinSimplification::HasRequiredColumns(const vector<ColumnBinding> &bindings) {
181	0	for (const auto &binding : bindings) {
182	0	if (required_columns.find(binding) != required_columns.end()) {
183	0	return true;
184	0	}
185	0	}
186	0	return false;
187	0	}
188
189	0	void OuterJoinSimplification::EraseNullRequiredColumns(LogicalOperator &child) {
190	0	for (const auto &binding : child.GetColumnBindings()) {
191	0	null_required_columns.erase(binding);
192	0	}
193	0	}
194
195	0	void OuterJoinSimplification::MarkEliminatedNullColumns(const vector<ColumnBinding> &bindings) {
196	0	for (const auto &binding : bindings) {
197	0	eliminated_null_columns.insert(binding);
198	0	}
199	0	}
200
201	0	bool OuterJoinSimplification::TryConvertLeftToAntiJoin(LogicalComparisonJoin &join) {
202	0	if (join.join_type != JoinType::LEFT) {
203	0	return false;
204	0	}
205
206	0	auto right_bindings = GetRightBindings(join);
207	0	if (!HasNullRequiredColumns(right_bindings) \|\| HasRequiredColumns(right_bindings)) {
208	0	return false;
209	0	}
210
211	0	column_binding_set_t match_non_null_rhs;
212	0	for (const auto &condition : join.conditions) {
213	0	if (!condition.IsComparison() \|\| !FiltersNulls(condition.GetComparisonType())) {
214	0	continue;
215	0	}
216	0	ColumnBinding rhs_binding;
217	0	if (!GetColumnBinding(condition.GetRHS(), rhs_binding)) {
218	0	continue;
219	0	}
220	0	match_non_null_rhs.insert(rhs_binding);
221	0	}
222
223	0	for (const auto &binding : right_bindings) {
224	0	if (null_required_columns.find(binding) == null_required_columns.end()) {
225	0	continue;
226	0	}
227	0	if (match_non_null_rhs.find(binding) == match_non_null_rhs.end()) {
228	0	continue;
229	0	}
230	0	join.join_type = JoinType::ANTI;
231	0	return true;
232	0	}
233	0	return false;
234	0	}
235
236	0	void OuterJoinSimplification::SimplifyOuterJoinType(LogicalComparisonJoin &join) {
237	0	bool preserves_null_extended_rows[2] = {join.join_type == JoinType::LEFT \|\| join.join_type == JoinType::OUTER,
238	0	join.join_type == JoinType::RIGHT \|\| join.join_type == JoinType::OUTER};
239	0	for (idx_t child_idx = 0; child_idx < 2; child_idx++) {
240	0	for (const auto &binding : join.children[child_idx]->GetColumnBindings()) {
241	0	if (null_filtered_columns.find(binding) != null_filtered_columns.end()) {
242		// Rejecting NULLs in one child removes preservation of NULL extended rows for the other child.
243	0	preserves_null_extended_rows[1 - child_idx] = false;
244	0	break;
245	0	}
246	0	}
247	0	}
248
249	0	if (!preserves_null_extended_rows[0] && !preserves_null_extended_rows[1]) {
250	0	join.join_type = JoinType::INNER;
251	0	return;
252	0	}
253
254	0	if (preserves_null_extended_rows[0] && !preserves_null_extended_rows[1]) {
255	0	D_ASSERT(join.join_type == JoinType::LEFT \|\| join.join_type == JoinType::OUTER);
256	0	join.join_type = JoinType::LEFT;
257	0	} else if (!preserves_null_extended_rows[0] && preserves_null_extended_rows[1]) {
258	0	D_ASSERT(join.join_type == JoinType::RIGHT \|\| join.join_type == JoinType::OUTER);
259	0	join.join_type = JoinType::RIGHT;
260	0	} else {
261	0	D_ASSERT(join.join_type == JoinType::OUTER);
262	0	join.join_type = JoinType::OUTER;
263	0	}
264	0	}
265
266		//===--------------------------------------------------------------------===//
267		// Operator Visitors
268		//===--------------------------------------------------------------------===//
269
270	32.8k	void OuterJoinSimplification::VisitComparisonJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
271	32.8k	switch (join.join_type) {
272	0	case JoinType::INNER:
273	0	case JoinType::SEMI:
274	0	VisitInnerOrSemiJoin(join, op);
275	0	return;
276	0	case JoinType::LEFT:
277	0	case JoinType::RIGHT:
278	0	case JoinType::OUTER:
279	0	VisitOuterJoin(join, op);
280	0	return;
281	32.8k	default:
282	32.8k	break;
283	32.8k	}
284	32.8k	VisitUnsupportedOperator(op);
285	32.8k	}
286
287	0	void OuterJoinSimplification::VisitInnerOrSemiJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
288	0	for (const auto &condition : join.conditions) {
289	0	if (!condition.IsComparison()) {
290	0	continue;
291	0	}
292	0	AddRequiredColumns(condition);
293	0	if (!FiltersNulls(condition.GetComparisonType())) {
294	0	continue;
295	0	}
296	0	HandleExpression(condition.GetLHS());
297	0	HandleExpression(condition.GetRHS());
298	0	}
299	0	VisitOperatorChildren(op);
300	0	}
301
302	0	void OuterJoinSimplification::VisitOuterJoin(LogicalComparisonJoin &join, LogicalOperator &op) {
303	0	if (TryConvertLeftToAntiJoin(join)) {
304	0	auto right_bindings = GetRightBindings(join);
305	0	AddRequiredColumns(join.conditions);
306	0	EraseNullRequiredColumns(*join.children[1]);
307	0	VisitOperatorChildren(op);
308		// only operators above the join see the right side as NULL, not the right child itself
309	0	MarkEliminatedNullColumns(right_bindings);
310	0	return;
311	0	}
312
313	0	SimplifyOuterJoinType(join);
314	0	if (join.join_type == JoinType::INNER) {
315	0	VisitOperator(op);
316	0	return;
317	0	}
318
319	0	AddRequiredColumns(join.conditions);
320		// NULL values in the NULL-extended side can be introduced by this join itself,
321		// so columns of that side are not guaranteed to be NULL below the join
322	0	if (join.join_type == JoinType::LEFT \|\| join.join_type == JoinType::OUTER) {
323	0	EraseNullRequiredColumns(*join.children[1]);
324	0	}
325	0	if (join.join_type == JoinType::RIGHT \|\| join.join_type == JoinType::OUTER) {
326	0	EraseNullRequiredColumns(*join.children[0]);
327	0	}
328	0	VisitOperatorChildren(op);
329	0	}
330
331	165k	void OuterJoinSimplification::VisitProjection(LogicalProjection &projection, LogicalOperator &op) {
332	165k	vector<pair<idx_t, ColumnBinding>> direct_projection_map;
333	2.31M	for (idx_t col_idx = 0; col_idx < projection.expressions.size(); col_idx++) {
334	2.15M	auto &expr = *projection.expressions[col_idx];
335	2.15M	const ColumnBinding binding(projection.table_index, ProjectionIndex(col_idx));
336	2.15M	if (expr.GetExpressionClass() != ExpressionClass::BOUND_COLUMN_REF) {
337	329k	AddRequiredColumns(expr);
338	329k	continue;
339	329k	}
340
341	1.82M	auto input_binding = expr.Cast<BoundColumnRefExpression>().Binding();
342	1.82M	direct_projection_map.emplace_back(col_idx, input_binding);
343	1.82M	if (null_filtered_columns.find(binding) != null_filtered_columns.end()) {
344	0	null_filtered_columns.insert(input_binding);
345	0	}
346	1.82M	if (null_required_columns.find(binding) != null_required_columns.end()) {
347	0	null_required_columns.insert(input_binding);
348	0	}
349	1.82M	}
350	165k	VisitOperatorChildren(op);
351
352	1.82M	for (const auto &entry : direct_projection_map) {
353	1.82M	auto col_idx = entry.first;
354	1.82M	auto input_binding = entry.second;
355	1.82M	if (eliminated_null_columns.find(input_binding) == eliminated_null_columns.end()) {
356	1.82M	continue;
357	1.82M	}
358	0	const ColumnBinding output_binding(projection.table_index, ProjectionIndex(col_idx));
359	0	auto type = projection.expressions[col_idx]->GetReturnType();
360	0	projection.expressions[col_idx] = make_uniq<BoundConstantExpression>(Value(type));
361	0	eliminated_null_columns.insert(output_binding);
362	0	}
363	165k	}
364
365	15.4k	void OuterJoinSimplification::VisitFilter(LogicalFilter &filter, LogicalOperator &op) {
366	15.4k	filter.SplitPredicates(filter.expressions);
367	15.4k	for (const auto &expr : filter.expressions) {
368	15.4k	HandleFilterExpression(*expr);
369	15.4k	}
370	15.4k	VisitOperatorChildren(op);
371
372	30.8k	for (idx_t i = 0; i < filter.expressions.size(); i++) {
373	15.4k	ColumnBinding binding;
374	15.4k	if (!IsNullFilter(*filter.expressions[i], binding)) {
375	15.4k	continue;
376	15.4k	}
377	0	if (eliminated_null_columns.find(binding) == eliminated_null_columns.end()) {
378	0	continue;
379	0	}
380	0	filter.expressions.erase_at(i);
381	0	i--;
382	0	}
383	15.4k	}
384
385	230	void OuterJoinSimplification::VisitOrder(LogicalOrder &order, LogicalOperator &op) {
386	230	for (const auto &order_node : order.orders) {
387	230	AddRequiredColumns(*order_node.expression);
388	230	}
389	230	VisitOperatorChildren(op);
390	230	}
391
392	0	void OuterJoinSimplification::VisitTopN(LogicalTopN &top_n, LogicalOperator &op) {
393	0	for (const auto &order_node : top_n.orders) {
394	0	AddRequiredColumns(*order_node.expression);
395	0	}
396	0	OuterJoinSimplification child_simplification(required_columns);
397	0	child_simplification.VisitOperator(*op.children[0]);
398	0	}
399
400	34.5k	void OuterJoinSimplification::VisitAggregate(LogicalAggregate &aggregate, LogicalOperator &op) {
401	34.5k	column_binding_set_t child_required_columns;
402	71.3k	for (const auto &expr : aggregate.groups) {
403	71.3k	AddColumnReferences(*expr, child_required_columns);
404	71.3k	}
405	34.5k	for (const auto &expr : aggregate.expressions) {
406	167	AddColumnReferences(*expr, child_required_columns);
407	167	}
408	34.5k	OuterJoinSimplification child_simplification(std::move(child_required_columns));
409	34.5k	child_simplification.VisitOperator(*op.children[0]);
410	34.5k	}
411
412	164k	void OuterJoinSimplification::VisitUnsupportedOperator(LogicalOperator &op) {
413	164k	for (auto &child : op.children) {
414	100k	column_binding_set_t child_required_columns;
415	270k	for (const auto &binding : child->GetColumnBindings()) {
416	270k	child_required_columns.insert(binding);
417	270k	}
418	100k	OuterJoinSimplification outer_join_simplification(std::move(child_required_columns));
419	100k	outer_join_simplification.VisitOperator(*child);
420	100k	}
421	164k	}
422
423	388k	void OuterJoinSimplification::VisitOperator(LogicalOperator &op) {
424	388k	InitializeRequiredColumns(op);
425
426	388k	switch (op.type) {
427	32.8k	case LogicalOperatorType::LOGICAL_COMPARISON_JOIN: {
428	32.8k	auto &join = op.Cast<LogicalComparisonJoin>();
429	32.8k	VisitComparisonJoin(join, op);
430	32.8k	return;
431	0	}
432	165k	case LogicalOperatorType::LOGICAL_PROJECTION: {
433	165k	auto &projection = op.Cast<LogicalProjection>();
434	165k	VisitProjection(projection, op);
435	165k	return;
436	0	}
437	15.4k	case LogicalOperatorType::LOGICAL_FILTER: {
438	15.4k	auto &filter = op.Cast<LogicalFilter>();
439	15.4k	VisitFilter(filter, op);
440	15.4k	return;
441	0	}
442	230	case LogicalOperatorType::LOGICAL_ORDER_BY: {
443	230	auto &order = op.Cast<LogicalOrder>();
444	230	VisitOrder(order, op);
445	230	return;
446	0	}
447	0	case LogicalOperatorType::LOGICAL_TOP_N: {
448	0	auto &top_n = op.Cast<LogicalTopN>();
449	0	VisitTopN(top_n, op);
450	0	return;
451	0	}
452	7.74k	case LogicalOperatorType::LOGICAL_LIMIT: {
453	7.74k	OuterJoinSimplification child_simplification(required_columns);
454	7.74k	child_simplification.VisitOperator(*op.children[0]);
455	7.74k	return;
456	0	}
457	34.5k	case LogicalOperatorType::LOGICAL_AGGREGATE_AND_GROUP_BY: {
458	34.5k	auto &aggregate = op.Cast<LogicalAggregate>();
459	34.5k	VisitAggregate(aggregate, op);
460	34.5k	return;
461	0	}
462	132k	default:
463		// Passthrough not supported. TODO: could pass through more operators like LOGICAL_UNION
464	132k	break;
465	388k	}
466
467	132k	VisitUnsupportedOperator(op);
468	132k	}
469
470		} // namespace duckdb