Fix Top-N window elimination for nullable ordering expressions

Project: duckdb/duckdb | Language: C++ | Concepts: query-optimization, algorithmic-optimization, error-handling | Difficulty: senior
Link: https://github.com/duckdb/duckdb/pull/24551

The problem

The Top-N window elimination optimization in DuckDB incorrectly assumed that if the input columns to a window function's ordering expression were non-nullable, then the ordering expression itself could never be NULL. This is not always true: expressions like NULLIF, TRY_CAST, or similar can introduce NULLs even when their input columns are non-nullable. As a result, the optimizer could incorrectly use an aggregate path that ignores NULL keys, causing rows with NULL ordering expressions to be silently dropped and returning too few rows.

Why it's non-trivial

A naive fix would just check the nullability of the columns referenced in the ordering expression, but this misses cases where the expression itself can produce NULLs (e.g., via NULLIF, TRY_CAST). Correctly determining if an arbitrary expression is guaranteed non-null requires analyzing the entire expression tree, not just its leaf columns. Additionally, the optimizer must be conservative: if it cannot prove non-nullability, it must fall back to the safe, null-preserving path to avoid incorrect query results.

The approach

The PR introduces a new analysis class and rewrites the optimizer logic to use it. Key changes:

1. Introduce NotNullExpressionAnalyzer
A new class is added to conservatively check if an expression can be NULL at a given logical operator's output.

+//! Conservatively proves that an expression cannot be NULL at a logical operator's output.
+class NotNullExpressionAnalyzer {
+public:
+	explicit NotNullExpressionAnalyzer(ClientContext &context, optional_ptr<LogicalOperator> plan_root = nullptr);
+
+	bool IsNotNull(LogicalOperator &op, const Expression &expr);
+...
+};

This class traverses the logical plan and expression tree to determine if an expression is provably non-null.

2. Use the analyzer in TopNWindowElimination
The optimizer now uses NotNullExpressionAnalyzer to check the full ordering and payload expressions, not just their referenced columns.

-	VisitExpression(&window_expr.orders[0].expression);
-	if (params.payload_type == TopNPayloadType::SINGLE_COLUMN && !aggregate_payload.empty()) {
-		VisitExpression(&aggregate_payload[0]);
+	NotNullExpressionAnalyzer nullability(context);
+	params.can_be_null = !nullability.IsNotNull(*window.children[0], *window_expr.orders[0].expression);
+	if (!params.can_be_null && params.payload_type == TopNPayloadType::SINGLE_COLUMN && !aggregate_payload.empty()) {
+		params.can_be_null = !nullability.IsNotNull(*window.children[0], *aggregate_payload[0]);
 	}

This ensures the optimizer only uses the non-null-ignoring path when it can prove the expression is never NULL.

3. Remove old column-based nullability logic
The previous logic that checked only column statistics is removed:

-	if (column_references.empty()) {
-		params.can_be_null = true;
-	} else {
-		for (const auto &column_ref : column_references) {
-			const auto &column_stats = stats->find(column_ref.first);
-			if (column_stats == stats->end() || column_stats->second->CanHaveNull()) {
-				params.can_be_null = true;
-				break;
-			}
-		}
-	}
-	column_references.clear();

This code is now replaced by the more robust expression-level analysis.

4. Add comprehensive tests
New test cases are added to cover scenarios where ordering expressions can produce NULLs, including use of NULLIF, TRY_CAST, always-NULL expressions, partitioned windows, and multi-payload cases.

+# Ordering expressions can introduce NULLs even when their input columns cannot
+statement ok
+CREATE TABLE expression_nulls(id INTEGER PRIMARY KEY)
+...
+SELECT id, row_number() OVER (ORDER BY NULLIF(id % 3, 0) DESC NULLS LAST) AS rn
+FROM expression_nulls
+QUALIFY rn <= 3
+ORDER BY rn
+----
+2	1
+1	2
+3	3

These tests ensure the fix covers all relevant edge cases and does not regress.

From the review thread

matthiasgoergens: Done — the branch is now based directly on v1.5-variegata with only the fix and test commits. The port needed NotNullExpressionAnalyzer backported from main (it doesn't exist on this branch), adapted to v1.5's statistics API; unknown and empty statistics conservatively take the null-preserving aggregate path. The full topn_window_elimination.test_slow passes locally (289 assertions), including the new NULLIF/TRY_CAST cases.

lnkuiper: Thanks!

Takeaways

• Always analyze the full expression tree for nullability, not just its input columns, when correctness depends on the presence of NULLs.
• Optimizations should be conservative: if you cannot prove an assumption (e.g., non-nullability), fall back to the safe path to avoid silent data loss.
• Comprehensive tests with edge-case expressions (like those introducing NULLs) are essential to catch subtle bugs in query optimizers.