Fixes (#24115) : Use single-column ART index scan for IS NOT DISTINCT FROM

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

The problem

Queries using IS NOT DISTINCT FROM with a non-NULL constant (e.g., x IS NOT DISTINCT FROM 42) did not use an existing single-column ART (Adaptive Radix Tree) index. Instead, DuckDB fell back to a sequential scan, even though such queries are semantically equivalent to equality (=) checks for non-NULL constants. This led to much slower query plans on large, indexed tables, especially for workloads that generate SQL with null-safe equality.

Why it's non-trivial

A naive fix might simply treat IS NOT DISTINCT FROM as = in all cases, but this would be incorrect for cases involving NULLs or when the predicate is not at the root of the filter. The subtle difference between IS NOT DISTINCT FROM and = (especially in how NULLs are handled) means the optimization is only valid in certain contexts, and only when the constant is not NULL. The planner and index scan code must be careful to only apply the optimization when it is logically sound.

The approach

1. Extend expression matcher to recognize IS NOT DISTINCT FROM

Previously, the matcher only recognized standard comparison types:

-		       type == ExpressionType::COMPARE_GREATERTHAN;
+		       type == ExpressionType::COMPARE_GREATERTHAN || type == ExpressionType::COMPARE_NOT_DISTINCT_FROM;

What this does:
This change allows the optimizer to recognize IS NOT DISTINCT FROM as a candidate for index scans, in addition to the usual comparison operators.

2. Handle IS NOT DISTINCT FROM in index scan initialization

In the ART index scan code, the logic for initializing a scan is extended:

-		if (comparison_type == ExpressionType::COMPARE_EQUAL) {
+		if (comparison_type == ExpressionType::COMPARE_NOT_DISTINCT_FROM) {
+			// Table filters discard NULL and false alike, so IS NOT DISTINCT FROM a
+			// non-NULL constant selects the same rows as equality. NULL is not indexed.
+			if (constant_value.IsNull()) {
+				return nullptr;
+			}
+			equal_value = constant_value;
+		} else if (comparison_type == ExpressionType::COMPARE_EQUAL) {
 			// An equality value overrides any other bounds.
 			equal_value = constant_value;

What this does:

• If the comparison is IS NOT DISTINCT FROM and the constant is not NULL, treat it as an equality for index scan purposes.
• If the constant is NULL, return nullptr (i.e., do not use the index), because the ART does not index NULLs.

3. Add comprehensive tests

A new test file verifies both the fast path (index scan) and the fallback (sequential scan):

+query II
+EXPLAIN ANALYZE SELECT count(*) FROM tbl WHERE i IS NOT DISTINCT FROM 499995;
+----
+analyzed_plan	<REGEX>:.*Type: Index Scan.*
+
+query II
+EXPLAIN ANALYZE SELECT count(*) FROM tbl WHERE i IS NOT DISTINCT FROM NULL;
+----
+analyzed_plan	<REGEX>:.*Sequential Scan.*

What this does:

• Confirms that a non-NULL constant triggers an index scan.
• Confirms that a NULL constant falls back to a sequential scan.
• Additional queries check behavior with NULLs in the data and verify that negated or wrapped predicates do not incorrectly use the index.

From the review thread

Mytherin:
IS NOT DISTINCT FROM is not equivalent to = also for non-NULL constants, e.g.:

create table integers(i int);
insert into integers values (1), (2), (3), (NULL);
select i, i is not distinct from 1 not_distinct_from, i = 1 equals from integers;
┌───────┬───────────────────┬─────────┐
│   i   │ not_distinct_from │ equals  │
│ int32 │      boolean      │ boolean │
├───────┼───────────────────┼─────────┤
│     1 │ true              │ true    │
│     2 │ false             │ false   │
│     3 │ false             │ false   │
│  NULL │ false             │ NULL    │
└───────┴───────────────────┴─────────┘

This is only the same when either the column does not have NULL values, or false and NULL are equivalent (like in the root of the WHERE clause). Can you verify this is correctly handled in your PR?

kid-ye:
@Mytherin Good catch, you're right, and my code comment overstated it. IS NOT DISTINCT FROM is only interchangeable with = where NULL and false coincide, which I've now said accurately in the comment.

The rewrite is sound because it can only ever fire in that context. ART::TryInitializeScan has exactly one caller TryScanIndex, driven by the scan's TableFilterSet and a table filter keeps a row only when the predicate is TRUE, discarding NULL and false alike. So it's structurally always the filter-root case you describe. And where the difference is observable, the pattern doesn't match: ComparisonExpressionMatcher matches only at the root of the pushed-down expression, so NOT (i IS NOT DISTINCT FROM 1) and (i IS NOT DISTINCT FROM 1) = false have a NOT/= at the root and fall back to a sequential scan. The NULL constant is guarded separately since NULLs aren't in the ART.

Verified on 500K rows with every 5th value NULL, indexed vs. an identical non-indexed table:

| Query | Plan | Indexed | Non-indexed | |---|---|---|---| | i IS NOT DISTINCT FROM 499997 | Index Scan | 1 | 1 | | i IS NOT DISTINCT FROM 499995 (row is NULL) | Index Scan | 0 | 0 | | NOT (i IS NOT DISTINCT FROM 499997) | Sequential | 199999 | 199999 | | (i IS NOT DISTINCT FROM 499997) = false | Sequential | 199999 | 199999 | | i IS NOT DISTINCT FROM NULL | Sequential | 40000 | 40000 |

NOT returning 199999 rather than 159999 confirms the NULL rows are retained. I've extended the test to cover a NULL-containing indexed column, both wrappers, and the false-vs-NULL contrast from your example.

Takeaways

• When optimizing for index usage, only treat logically-equivalent predicates as such in contexts where their semantics truly align (e.g., IS NOT DISTINCT FROM vs = with non-NULL constants at the root of a filter).
• Always guard special cases (like NULL handling) explicitly in index scan logic, since index structures often do not store NULLs.
• Comprehensive testing should cover both the fast path (index usage) and all fallback scenarios, especially for edge cases involving NULLs and predicate negation.