bug: NOT IN / <> ALL with a NULL in the subquery returns rows once the mark join spills

Search before asking

• I had searched in the issues and found no similar issues.

Version

8.0.90-v1.2.943-nightly-419338dde9 (SELECT version()), image datafuselabs/databend:nightly pulled 2026-09-15, single node, QUERY_STORAGE_TYPE=fs, Linux x86_64 (kernel 5.15.0-187).

Also reproduces on v1.2.940-nightly-a280ed1f26. The defect is visible in main @ 6b31170.

What's Wrong?

Under SQL's three-valued logic, if the subquery of x NOT IN (SELECT ...) produces any NULL, the predicate is NULL for every probe row that has no match, so the query must return no rows at all. Databend gets this right while the join stays in memory, but once the hash join spills, NOT IN and <> ALL return a nondeterministic subset of the rows that should have been filtered out. Nothing in the query fails or warns — it is a silent wrong answer, and it appears only under memory pressure.

The same defect is visible in the exposed marker value: k IN (SELECT ...) returns false (and k NOT IN (...) returns true) for rows whose correct value is NULL.

Minimal case (4-row and 2-row tables, force_join_data_spill = 1)

CREATE OR REPLACE TABLE na_a (k INT NULL, v INT);
CREATE OR REPLACE TABLE na_b (k INT NULL);
INSERT INTO na_a VALUES (1,10),(2,20),(3,30),(NULL,40);
INSERT INTO na_b VALUES (1),(NULL);

na_b is {1, NULL}, so k NOT IN (SELECT k FROM na_b) is FALSE for k = 1 and NULL for every other k (including k IS NULL). The correct result is empty.

The marker expression shows the corruption directly — note that k = 3 is still correct, i.e. only some rows lose their NULL marker:

SET force_join_data_spill = 1;
SELECT k, v, k IN (SELECT k FROM na_b) AS in_expr,
              k NOT IN (SELECT k FROM na_b) AS notin_expr
FROM na_a ORDER BY k;

and consequently CASE WHEN k IN (...) THEN 'in' WHEN k NOT IN (...) THEN 'out' ELSE 'unknown' END reports 'out' for k = 2 where it must report 'unknown'.

MySQL 9.7.2 on the same data returns no rows for the filter and NULL/NULL for the marker columns of k = 2 and k = 3, matching the non-spilled Databend result.

It is specifically the null-aware (mark) path, and specifically the spill rounds

Same data, same query, one setting changed at a time:

join_spilling_partition_bits = 0 means a single spill partition, i.e. a single restore round — and that is exactly the case that stays correct. enable_experimental_new_join makes no difference because mark joins are not handled by the new join and always execute in the legacy hash join.

NOT EXISTS, <> ANY, > ALL, scalar subqueries, LEFT/RIGHT/FULL joins and plain IN with a NULL-free subquery are all correct under the same forced spilling. Only the null-aware mark semantics are lost.

Reproduces with no test-only setting, at a documented memory limit

force_join_data_spill is only a convenience for the minimal case. The same wrong answer appears with stock settings plus a max_query_memory_usage / max_memory_usage value — documented knobs that multi-tenant deployments are sized with. Probe = 3 000 000 rows, subquery = 8 000 000 rows containing exactly one NULL key, max_threads = 4:

The control column is the point: at the very same 96 MB limit, the same query over a subquery without a NULL returns the correct 2 571 427 rows. The memory limit is not truncating anything — only the null-aware marker is being lost.

The wrong count is nondeterministic while the wrongness is not. Seven consecutive runs at 96 MB: 1 767 967 / 1 928 703 / 1 607 245 / 321 481 / 642 827 / 2 410 762 / 642 891 — never 0. Two discriminators at that same 96 MB limit:

So it is not a data race between probe threads — a single thread reproduces it — and it disappears the moment the spill is reduced to one restore round.

Both mark orientations are affected

The planner picks the orientation by size, and both are wrong:

• minimal case above: join type: RIGHT MARK (build = subquery, probe = outer)
• 3M × 8M case above: join type: LEFT MARK (build = outer, probe = subquery)

Severity

Silent wrong results for a standard SQL idiom (NOT IN / <> ALL over a nullable column), triggered by memory pressure rather than by anything in the query. The failure direction is the dangerous one: rows that should have been excluded are returned, so an anti-join used for filtering (exclusion lists, delta computation, "records not present in X") silently over-reports, and a query that is correct in staging becomes wrong in production purely because the data grew or the memory budget shrank.

How to Reproduce?

Single-node server, any MySQL client on port 3307:

docker run -d --name databend -p 3307:3307 \
  -e QUERY_DEFAULT_USER=root -e QUERY_DEFAULT_PASSWORD=root -e QUERY_STORAGE_TYPE=fs \
  datafuselabs/databend:nightly
mysql -h127.0.0.1 -P3307 -uroot -proot

1. Minimal, deterministic (uses force_join_data_spill to make the spill cheap):

CREATE OR REPLACE TABLE na_a (k INT NULL, v INT);
CREATE OR REPLACE TABLE na_b (k INT NULL);
INSERT INTO na_a VALUES (1,10),(2,20),(3,30),(NULL,40);
INSERT INTO na_b VALUES (1),(NULL);

-- baseline, no spilling: correct (no rows)
SELECT k, v FROM na_a WHERE k NOT IN (SELECT k FROM na_b) ORDER BY k;

SET force_join_data_spill = 1;

-- WRONG: returns (2, 20)
SELECT k, v FROM na_a WHERE k NOT IN (SELECT k FROM na_b) ORDER BY k;

-- WRONG: returns (2, 20)
SELECT k, v FROM na_a WHERE k <> ALL (SELECT k FROM na_b) ORDER BY k;

-- WRONG: in_expr/notin_expr are false/true for k = 2, must be NULL/NULL
SELECT k, v, k IN     (SELECT k FROM na_b) AS in_expr,
              k NOT IN (SELECT k FROM na_b) AS notin_expr
FROM na_a ORDER BY k;

-- legacy join explicitly: still WRONG
SET enable_experimental_new_join = 0;
SELECT k, v FROM na_a WHERE k NOT IN (SELECT k FROM na_b) ORDER BY k;
UNSET enable_experimental_new_join;

-- single spill partition => single round: CORRECT (no rows)
SET join_spilling_partition_bits = 0;
SELECT k, v FROM na_a WHERE k NOT IN (SELECT k FROM na_b) ORDER BY k;
UNSET join_spilling_partition_bits;

-- the same code is reached from a literal IN-list via inlist_to_join_threshold: WRONG
SET inlist_to_join_threshold = 1;
SELECT k, v FROM na_a WHERE k NOT IN (1, NULL) ORDER BY k;
UNSET inlist_to_join_threshold;
UNSET force_join_data_spill;

2. No test-only setting — natural spill under a memory limit:

SET max_threads = 4;

CREATE OR REPLACE TABLE nb_probe AS
  SELECT number AS id, (number % 1000003) AS k FROM numbers(3000000);

-- 8M rows, exactly one NULL key
CREATE OR REPLACE TABLE nb_build AS
  SELECT number AS id, if(number = 777777, NULL, (number * 7) % 100000007) AS k,
         to_string(number) AS pad
  FROM numbers(8000000);

-- control: identical, but no NULL key
CREATE OR REPLACE TABLE nb_build_nonull AS
  SELECT number AS id, ((number * 7) % 100000007) AS k, to_string(number) AS pad
  FROM numbers(8000000);

SELECT count(*) FROM nb_build WHERE k IS NULL;          -- 1

-- default memory limits: correct
SELECT count(*) FROM nb_probe WHERE k NOT IN (SELECT k FROM nb_build);          -- 0

SET max_memory_usage       = 100663296;   -- 96 MiB
SET max_query_memory_usage = 100663296;

-- WRONG: expected 0, observed 321481 .. 2410762 (varies per run, never 0)
SELECT count(*) FROM nb_probe WHERE k NOT IN (SELECT k FROM nb_build);

-- control at the SAME limit: correct
SELECT count(*) FROM nb_probe WHERE k NOT IN (SELECT k FROM nb_build_nonull);   -- 2571427

-- one restore round at the SAME limit: correct
SET join_spilling_partition_bits = 0;
SELECT count(*) FROM nb_probe WHERE k NOT IN (SELECT k FROM nb_build);          -- 0
UNSET join_spilling_partition_bits;

UNSET max_memory_usage;
UNSET max_query_memory_usage;

On this host the spill boundary for that data sits between 96 MiB and 128 MiB; at 128 MiB and above the query stays in memory and is correct. The 96 MiB figure is not meaningful in itself — the trigger is "the mark join spilled into more than one restore round", and which rows/limit combination reaches that depends on the data size and on which side the planner chooses to build. Note when scaling this up that the build side is whichever side the planner picks (check EXPLAIN for LEFT MARK vs RIGHT MARK), so growing the subquery alone may not move the spill point.

Root cause (reading main @ 6b31170)

Null-awareness of a mark join is carried by one global flag, MarkJoinDesc::has_null: RwLock<bool> (hash_join/desc.rs:50, initialised false at desc.rs:141). It is filled in incrementally as data flows through, but it is read whenever a block of markers is emitted — and with spilling, markers are emitted round by round, long before the whole input has been seen.

RIGHT MARK (build side = subquery):

• set: hash_join_build_state.rs:719-733 — while building each build chunk, if that chunk's key column has any NULL, *has_null = true.
• read: probe_join/right_mark_join.rs:45-49 (and :100 for the _with_conjunct variant) — read once per probe block and handed straight to create_marker_block(has_null, ...), which turns MARKER_KIND_FALSE into MARKER_KIND_NULL. The block is then emitted.

LEFT MARK (probe side = subquery):

• set: probe_join/left_mark_join.rs:49-56 — when a probe block's key column contains a NULL.
• read: hash_join_probe_state.rs:666-670 in left_mark_scan, the per-round final scan, which does if markers[i] == MARKER_KIND_FALSE && has_null { MARKER_KIND_NULL }.

With spilling, both sides are hash-partitioned and processed in rounds (transform_hash_join_probe.rs: final_scan() → next_round(); HashJoinState::reset() at hash_join_state.rs:272 clears chunks and mark_scan_map between rounds, and correctly leaves has_null sticky). But a NULL key is a property of the whole side, while it lands in exactly one partition. Every round that completes before that partition is processed reads has_null == false, emits MARKER_KIND_FALSE for its unmatched rows, and those rows leave the operator with NOT IN = TRUE. Later rounds see the flag and are correct — which is precisely the observed "partial, varying subset of rows".

This explains every observation above: one round (join_spilling_partition_bits = 0) is always correct; the count varies run to run with restore order; a single thread still reproduces it; and a subquery with no NULL is never affected.

Suggested fix

Determine NULL presence over the entire relevant key column before any marker block is emitted, rather than accumulating it as chunks/blocks arrive. Concretely, compute it while the side is being partitioned/spilled (hash_join_spiller.rs) and store it once per join, so that the first restore round already sees the final value. Alternatively, mark joins could withhold marker output until the whole null-aware side has been consumed, but computing the flag during partitioning is far cheaper.

A regression test would need more than one spill partition: the current join_spilling_partition_bits = 0 path happens to be correct and would hide the bug.

Are you willing to submit PR?

• Yes I am willing to submit a PR!