NOT IN in a Hash Join: Why DataFusion Decides UNKNOWN Per Build Row

TL;DR: x NOT IN (1, 2, NULL) is not “false” — it is UNKNOWN, and UNKNOWN propagates through every predicate. A hash join cannot implement this with a flag on the probe side, because whether a NULL matters depends on which build row it came from and which probe row is being tested. DataFusion therefore records the decision in a bitmap indexed by build row, and keeps a separate hash table of just the NULL-valued build rows so the cost is proportional to the number of NULLs, not to the number of matches.

NOT IN is the most subtly-specified operator in SQL. It is not the negation of IN:

The NULL in the list poisons everything, because NULL = 3 is UNKNOWN and UNKNOWN propagates through NOT.

Implementing this in a hash join is genuinely hard, and the reason is subtle.

The problem with a flag

The naive approach: hash the build side’s keys, and set a single flag “the build side contains a NULL” when one is seen. Then, at probe time, if the flag is set, the answer is UNKNOWN for every probe row.

That is correct for the uncorrelated case, and it is wrong in general.

Consider a correlated NOT IN — the shape you get from a NOT EXISTS rewritten into an anti-join:

SELECT * FROM t1 WHERE x NOT IN (SELECT y FROM t2 WHERE t2.z = t1.z);

The subquery’s rows are only “in” the NOT IN list for a given t1 row if they match t1.z. A NULL y in t2 only matters for the t1 rows whose z matches that NULL row’s z. For every other t1 row, the NULL is irrelevant.

So the flag is wrong: it would make every probe row UNKNOWN when it should only make some of them UNKNOWN.

And the decision depends on the build row: two build rows with the same correlation scope but different filter outcomes give different answers.

The per-build-row bitmap

DataFusion’s answer is a bitmap indexed by build row:

/// The build rows with a NULL `NOT IN` value key (in any element of a
/// multi-column key), used by correlated null-aware joins (see
/// [`NullAwareMode`]).
///
/// Such rows are UNKNOWN whenever *any* probe row in their correlation scope
/// passes the join filter, so every probe row must be tested against them.
/// Restricting this lookup to the NULL-valued build rows keeps it
/// proportional to the number of NULLs instead of enumerating every scope
/// match of every probe row.
pub(super) struct NullValueBuildRows {
    /// Hash table keyed by the correlation scope values of the NULL-valued
    /// build rows. Stored positions index into `scope_values`/`build_indices`,
    /// not the full build batch. `None` when the join has no correlation
    /// scope keys, so every probe row is in scope.
    pub(super) scope_map: Option<Box<dyn JoinHashMapType>>,
    /// Correlation scope key values of the NULL-valued build rows.
    pub(super) scope_values: Vec<ArrayRef>,
    /// Maps positions in `map`/`scope_values` back to row indices in the full
    /// build batch.
    pub(super) build_indices: UInt64Array,
}

Three fields, and the design is in the comment on the third one: the hash table stores positions into a compact list, and the compact list maps back to the full build batch’s row indices. So the NULL-valued build rows are stored in a dense side structure, separate from the main build batch.

The key insight is in the sentence:

Restricting this lookup to the NULL-valued build rows keeps it proportional to the number of NULLs instead of enumerating every scope match of every probe row.

A NULL in the build side is rare. You do not want to test every probe row against every build row to find the NULLs. You want a lookup structure containing only the NULL rows, keyed by their correlation scope, so the probe asks “are there NULL-valued build rows in my scope?” and the answer is usually “no”, found in O(1).

The mode enum

The different flavours of NOT IN need different machinery, and the code makes the distinction explicit:

pub(super) enum NullAwareMode {
    /// `build.key NOT IN (probe.key)`: emits build rows. When uncorrelated,
    /// none of them are emitted once any probe key is NULL.
    LeftAnti { correlated: bool, value_keys: usize },
    /// Uncorrelated `probe.key NOT IN (build.key)`: emits probe rows, and
    /// none of them once any build key is NULL.
    RightAnti,
    /// `NOT IN` as a nullable mark column on the build rows; `value_keys` as
    /// for `LeftAnti`.
    LeftMark { correlated: bool, value_keys: usize },
}

Three modes, and the correlated flag is the one that matters:

/// Whether this join decides UNKNOWN per build row (see [`NullAwareMode`]).
pub(super) fn is_correlated(self) -> bool {
    matches!(
        self,
        Self::LeftAnti { correlated: true, .. } | Self::LeftMark { correlated: true, .. }
    )
}

RightAnti is never correlated — it is always the simple case where a single flag suffices. The other two can be.

And when is a join “correlated”? The answer is a subtle one:

// `num_keys > 1` also covers a multi-column value key without any
// correlation: a NULL in one tuple element leaves the comparison FALSE
// whenever another element is a definite mismatch, so it too must be
// decided per build row.
let correlated = num_keys > 1 || has_filter;

So a multi-column join key counts as correlated, even without any correlation scope. Why? Because with a composite key (a, b), a NULL in a makes the comparison UNKNOWN only if b might match; if b is definitely different, the comparison is FALSE regardless of a’s NULL.

That is exactly the kind of detail that is easy to get wrong and expensive to debug.

The legal combinations are enumerated

The constructor is a whitelist:

match mode {
    Self::RightAnti if num_keys != 1 => plan_err!(
        "null_aware {join_type} joins only support single column join key, got {num_keys} columns"
    ),
    // Correlated joins share the per-build-row null bitmap across all
    // probe partitions.
    Self::LeftMark { .. }
    | Self::LeftAnti { correlated: true, .. } if partition_mode == PartitionMode::Partitioned => {
        plan_err!(
            "null_aware joins require PartitionMode::CollectLeft, got PartitionMode::Partitioned"
        )
    }
    Self::RightAnti if has_filter => {
        plan_err!("null_aware RightAnti join does not support a join filter")
    }
    _ => Ok(mode),
}

The Partitioned restriction is a concurrency restriction, not a semantic one: a correlated null-aware join needs to share a per-build-row bitmap across all probe partitions, and the partitioned mode’s partitions each build their own table. So it is simply not supported there, and the constructor says so.

Finding the NULL-valued rows

The mask that identifies them:

/// Returns the rows where at least one of `value_keys` is NULL, or `None` when
/// there is no such row.
pub(super) fn null_value_key_mask(value_keys: &[ArrayRef]) -> Option<BooleanArray> {
    let logical_nulls: Vec<_> = value_keys.iter().map(|v| v.logical_nulls()).collect();
    let valid = NullBuffer::union_many(logical_nulls.iter().map(Option::as_ref))?;
    (valid.null_count() > 0).then(|| BooleanArray::new(!valid.inner(), None))
}

Note logical_nulls() rather than nulls(). A dictionary-encoded column can have a logical null (a key that points at a null value) without having a null in its validity bitmap. Using nulls() would miss those and produce wrong results.

And union_many combines the null masks of all the value key columns: a row is NULL-valued if any element of the composite key is NULL.

The (valid.null_count() > 0).then(...) is a nice micro-optimisation: if no build row has a NULL value key, the whole NULL-handling machinery is skipped, and the mask is None rather than an all-false bitmap.

The catch

• The per-build-row bitmap is shared state. In CollectLeft mode all probe partitions see the same build side, so they must agree on the bitmap. The Mutex-wrapped SharedBitmapBuilder handles that, at the cost of contention.
• The NULL rows are stored twice. Once in the main build batch, once in the compact scope_values / build_indices side structure.
• The mode matrix is small and the errors are loud. Only three combinations are legal, and the rest are plan_err!s at plan time rather than wrong answers at run time.
• The correlated case needs a filter or a composite key. An uncorrelated single-column NOT IN takes the simple path; anything else goes down the per-build-row path.
• This is not the same thing as a LEFT JOIN with a WHERE. The difference is precisely the UNKNOWN handling, and it is why NOT IN gets its own implementation rather than being rewritten into a join with a filter.

Why it matters

NOT IN is not a rare corner. It is the default spelling of “not present in this list of possible values”, and it shows up in every “make sure this value is not in the forbidden set” query.

And the reason it needs its own implementation is a good lesson in general: SQL’s three-valued logic is not a decoration on top of two-valued logic — it is a different algebra, and optimisations that treat NOT IN as NOT (IN) will produce wrong answers. DataFusion’s approach — decide per build row, and index the rare case — is the general shape of the solution: when the semantics are per-row, your data structures have to be per-row too.