unlock unlimited code runs for $79, limited time →
NOSSLETTER.techLIVE
back to OSSpedia
duckdb/duckdb
mid8/10
query-optimizationdata-structuresalgorithmic-optimizationtesting-strategy

Prune row groups for column-constant OR

Project: duckdb/duckdb | Language: C++ | Concepts: query-optimization, data-structures, algorithmic-optimization, testing-strategy | Difficulty: mid
Link: https://github.com/duckdb/duckdb/pull/24963

The problem

DuckDB was unable to use row-group statistics to prune data when queries included OR predicates across columns, even if each branch of the OR could be independently ruled out by statistics. This meant that queries like WHERE x < 100 OR s > '00008000' would scan every row group, even if some groups could be excluded based on column statistics.

Why it's non-trivial

A naive fix would only handle single-column predicates or overlook the need for a general mechanism to represent and push down multi-column OR expressions in a way compatible with DuckDB's statistics-based pruning. Additionally, the solution must ensure that filter expressions are canonicalized for plan caching and subplan matching, without losing important bound-function state.

The approach

The PR introduces logic to recognize and handle multi-column OR expressions where each branch is a column-to-constant comparison, converting them into a form that allows row group pruning. Key changes include:

1. Recognize column-constant ORs

A new helper checks if an expression is an OR of column-to-constant comparisons:

+static bool IsColumnConstantOr(const Expression &expr) {
+	if (expr.GetExpressionClass() != ExpressionClass::BOUND_CONJUNCTION ||
+	    expr.GetExpressionType() != ExpressionType::CONJUNCTION_OR) {
+		return false;
+	}
+	const auto &conjunction = expr.Cast<BoundConjunctionExpression>();
+	if (conjunction.GetChildren().empty()) {
+		return false;
+	}
+	for (const auto &child : conjunction.GetChildren()) {
+		if (!BoundComparisonExpression::IsComparison(*child) ||
+		    !SupportedFilterComparison(child->GetExpressionType())) {
+			return false;
+		}
+		const auto &comparison = child->Cast<BoundFunctionExpression>();
+		const auto &left = BoundComparisonExpression::Left(comparison);
+		const auto &right = BoundComparisonExpression::Right(comparison);
+		optional_ptr<const BoundColumnRefExpression> column_ref;
+		optional_ptr<const BoundConstantExpression> constant;
+		if (left.GetExpressionClass() == ExpressionClass::BOUND_COLUMN_REF &&
+		    right.GetExpressionClass() == ExpressionClass::BOUND_CONSTANT) {
+			column_ref = left.Cast<BoundColumnRefExpression>();
+			constant = right.Cast<BoundConstantExpression>();
+		} else if (left.GetExpressionClass() == ExpressionClass::BOUND_CONSTANT &&
+		           right.GetExpressionClass() == ExpressionClass::BOUND_COLUMN_REF) {
+			column_ref = right.Cast<BoundColumnRefExpression>();
+			constant = left.Cast<BoundConstantExpression>();
+		} else {
+			return false;
+		}
+		if (constant->GetValue().IsNull() || !TypeSupportsConstantFilter(column_ref->GetReturnType())) {
+			return false;
+		}
+	}
+	return true;
+}

This function ensures the expression is an OR, and that each child is a supported column-to-constant comparison.

2. Canonicalize and build a multi-column filter

When such an expression is found, it is converted into an ExpressionFilter with the right column indexes, and all query-specific metadata (like aliases and query locations) is cleared for plan canonicalization:

+	auto filter_expr = expr.Copy();
+	ExpressionIterator::VisitExpressionMutable<BoundColumnRefExpression>(
+	    filter_expr, [&](BoundColumnRefExpression &column_ref, unique_ptr<Expression> &child) {
+		    const auto entry = binding_indexes.find(column_ref.Binding());
+		    D_ASSERT(entry != binding_indexes.end());
+		    child =
+		        make_uniq<BoundReferenceExpression>(column_ref.GetAlias(), column_ref.GetReturnType(), entry->second);
+	    });
+	// Remove query-specific metadata so equivalent filters serialize identically for common-subplan matching.
+	ExpressionIterator::EnumerateExpression(filter_expr, [](Expression &expr) {
+		expr.ClearAlias();
+		expr.SetQueryLocation(optional_idx());
+	});
+	return make_uniq<ExpressionFilter>(std::move(filter_expr), std::move(column_indexes));

This ensures that the filter is both correct for execution and canonical for plan matching.

3. Integrate with the filter pushdown logic

The main filter pushdown function is updated to use the new logic, generalizing previous handling of two-column numeric comparisons to also handle column-constant ORs:

-	if (bindings.size() == 2 && bindings[0] != bindings[1] && table && table->IsDuckTable() &&
-	    BoundComparisonExpression::IsComparison(expr)) {
-		...
-		get.table_filters.PushMultiColumnFilter(
-		    make_uniq<ExpressionFilter>(std::move(filter_expr), std::move(column_indexes)));
-		return FilterPushdownResult::PUSHED_DOWN_PARTIALLY;
-	}
+	if (table && table->IsDuckTable() && CanPushdownMultiColumnExpression(expr, bindings)) {
+		auto filter = TryCreateMultiColumnExpressionFilter(get, expr, bindings);
+		if (!filter) {
+			return FilterPushdownResult::NO_PUSHDOWN;
+		}
+		get.table_filters.PushMultiColumnFilter(std::move(filter));
+		return FilterPushdownResult::PUSHED_DOWN_PARTIALLY;
+	}

This allows the optimizer to push down multi-column OR expressions for row-group pruning, not just two-column comparisons.

4. Add comprehensive tests

A new test file verifies that row group pruning works for various forms of cross-column OR predicates, including different column orders, more than two columns, repeated columns, and with/without nulls.

+query II
+EXPLAIN ANALYZE SELECT sum(x) FROM t WHERE x < 100 OR s > '00008000';
+----
+analyzed_plan	<REGEX>:.*Row Groups Scanned: 2 / 4.*

This and other tests confirm that only the relevant row groups are scanned.

From the review thread

kryonix:
The canonicalization required for common-subplan signatures only needs to clear aliases and query locations. Recreating every comparison also discards its bound-function state and couples this helper to the current comparison representation. This is harmless for today's built-in comparisons, but unnecessary and fragile as multi-column filters become more general. Please preserve the copied comparisons and only clear their query-specific metadata.

Maybe something like this:

ExpressionIterator::EnumerateExpression(filter_expr, [](Expression &expr) {
    expr.ClearAlias();
    expr.SetQueryLocation(optional_idx());
});

Takeaways

  • Design filter pushdown logic to recognize and handle multi-column predicates, not just single-column or two-column cases.
  • When canonicalizing expressions for plan caching or matching, clear only query-specific metadata (like aliases and locations) to avoid losing essential bound state.
  • Comprehensive tests should cover variations in predicate structure, column order, and nullability to ensure optimizer enhancements work as intended.
Prune row groups for column-constant OR — nossletter.tech