Prune row groups when an IN-list covers the whole zonemap range

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

The problem

When a NOT IN predicate is used in a query, and the IN-list covers every possible value in a row group's zonemap (i.e., the minimum and maximum value in the group), DuckDB still scans that row group, even though it is guaranteed to return no results. This is inefficient: the scan could be skipped entirely.

Why it's non-trivial

A naive fix might just check if all values in the zonemap are present in the IN-list, but this is only valid for integral types and when the range is contiguous. It also needs to handle edge cases like type mismatches, NULLs, and non-integral types (e.g., floating point), where the logic does not apply. The fix must be careful not to prune too aggressively and skip rows that could match.

The approach

1. Add a function to check if the IN-list covers the entire zonemap range

+	//! Whether the constants cover every value in [min, max] - only meaningful for integral types
+	static bool ConstantsCoverRange(const BaseStatistics &stats, array_ptr<const Value> constants);

This new function, added to NumericStats, checks if the list of constants covers every value in the [min, max] range of the statistics. It is only meaningful for integral types.

2. Implement the logic for checking coverage

+bool NumericStats::ConstantsCoverRange(const BaseStatistics &stats, array_ptr<const Value> constants) {
+	auto &type = stats.GetType();
+	// values are compared as hugeint_t, which cannot hold large UINT128 values
+	if (!type.IsIntegral() || type.InternalType() == PhysicalType::UINT128 || !NumericStats::HasMinMax(stats)) {
+		return false;
+	}
+	auto min_value = NumericStats::Min(stats).GetValue<hugeint_t>();
+	auto max_value = NumericStats::Max(stats).GetValue<hugeint_t>();
+	// covering [min, max] requires at least max - min + 1 constants
+	hugeint_t range;
+	if (!TrySubtractOperator::Operation(max_value, min_value, range) ||
+	    range >= NumericCast<int64_t>(constants.size())) {
+		return false;
+	}
+	vector<hugeint_t> values;
+	for (auto &constant_value : constants) {
+		if (constant_value.type() != type) {
+			return false;
+		}
+		auto constant = constant_value.GetValue<hugeint_t>();
+		if (constant >= min_value && constant <= max_value) {
+			values.push_back(constant);
+		}
+	}
+	std::sort(values.begin(), values.end());
+	if (values.empty() || values.front() != min_value || values.back() != max_value) {
+		return false;
+	}
+	for (idx_t i = 1; i < values.size(); i++) {
+		if (values[i - 1] != values[i] && values[i - 1] + 1 != values[i]) {
+			return false;
+		}
+	}
+	return true;
+}

• Early-outs for non-integral types, UINT128, or missing min/max.
• Checks that the number of constants is at least the size of the range.
• Collects all constants within the range, sorts them, and checks for contiguous coverage.
• Returns true only if the constants exactly cover the range.

3. Integrate the coverage check into filter propagation

-	auto result = CheckZonemapAgainstConstants(*filter_stats, ExpressionType::COMPARE_EQUAL,
-	                                           array_ptr<const Value>(values.data(), values.size()));
+	array_ptr<const Value> constants(values.data(), values.size());
+	auto result = CheckZonemapAgainstConstants(*filter_stats, ExpressionType::COMPARE_EQUAL, constants);
+	if (result == FilterPropagateResult::NO_PRUNING_POSSIBLE &&
+	    NumericStats::ConstantsCoverRange(*filter_stats, constants)) {
+		// an integral column whose whole [min, max] range is listed always matches
+		result = FilterPropagateResult::FILTER_ALWAYS_TRUE;
+	}

• After checking for standard zonemap pruning, the code checks if the constants cover the range.
• If so, the filter is always true for that row group.

4. Update NOT IN logic to use this new information

-	if (ExpressionFilter::CheckExpressionStatistics(context_p, child, stats) ==
-	    FilterPropagateResult::FILTER_ALWAYS_TRUE) {
-		return FilterPropagateResult::FILTER_ALWAYS_FALSE;
-	}

• If the child (IN-list) matches every row, then NOT IN can never match any row in this group, so the filter is always false.

5. Add targeted tests

A new test file ensures:

• Full coverage prunes all groups (Empty Result).
• Partial coverage prunes only some groups.
• Non-integral types are not incorrectly pruned.

+query II
+EXPLAIN ANALYZE SELECT count(*) FROM covered WHERE i NOT IN (1, 2, 3);
+----
+analyzed_plan	<REGEX>:.*Empty Result.*

and

+query II
+EXPLAIN ANALYZE SELECT count(*) FROM mixed WHERE i NOT IN (1, 2, 3);
+----
+analyzed_plan	<REGEX>:.*Row Groups Scanned: 2 / 3.*

From the review thread

Mytherin: Maybe add an early-out if we know the amount of values in the IN list cannot possibly cover the entire range, e.g.:

if (constants.size() < max_value - min_value + 1) {
      return false;  // not enough constants to cover the range
  }

vvvdwbvvv: Binding guarantees the constants share a type, but stats here is derived by TryGetExpressionStats, not the column's own statistics — its type isn't binder-controlled. On a mismatch GetValue<hugeint_t>() can throw during planning, so I'd rather bail than assert. Can hoist it out of the loop and check constants[0].type() once if you prefer.

Takeaways

• When optimizing with range metadata (zonemaps), ensure that pruning logic is only applied when the data type and value coverage semantics are correct—especially for integral vs. non-integral types.
• Always check that the filter's value list is sufficient to cover the entire range before pruning; insufficient or non-contiguous lists must not trigger pruning.
• Test edge cases: both full and partial coverage, as well as type mismatches, to ensure the optimizer does not incorrectly skip rows.