The Validity Mask Is Optional: A Null Pointer Means No NULLs

TL;DR: Every DuckDB vector carries a NULL bitmap — but the bitmap is lazily allocated. A null validity_mask pointer is the encoding of “this column has no NULLs”. RowIsValid short-circuits to true without touching memory, SetValid is a no-op, and only SetInvalid pays for an allocation.
The payoff is not just memory. The aggregate hash table asks CannotHaveNull() once, at construction, and if the group columns can never be NULL it swaps the row-match predicate from COMPARE_NOT_DISTINCT_FROM to plain COMPARE_EQUAL — changing the inner loop of every probe in the table.

The cheapest possible representation of “no NULLs”

Consider two tables with identical data:

sql
CREATE TABLE a (id INTEGER NOT NULL, val INTEGER);
CREATE TABLE b (id INTEGER, val INTEGER);

Column a.id can never be NULL. Column b.id might be. As far as the values are concerned, the two are identical when b.id happens to have no NULLs in it.

The obvious design is to always carry a bitmap: one bit per row, 1 meaning “not null”. For a 2048-row vector of int64_t that is 16 KiB of data plus 256 bytes of bitmap — a 1.5% overhead, paid whether or not anyone needs it.

DuckDB’s design is better: the absence of the bitmap is the information. A ValidityMask is a uint64_t* plus a shared_ptr to the allocation. If the pointer is null, the mask says “all rows are valid” and there is nothing to store.

The type

cpp
// src/include/duckdb/common/types/validity_mask.hpp:64
	static constexpr const idx_t BITS_PER_VALUE = ValidityBuffer::BITS_PER_VALUE;
	static constexpr const idx_t STANDARD_ENTRY_COUNT = (STANDARD_VECTOR_SIZE + (BITS_PER_VALUE - 1)) / BITS_PER_VALUE;
	static constexpr const idx_t STANDARD_MASK_SIZE = STANDARD_ENTRY_COUNT * sizeof(V);

validity_t is uint64_t, so BITS_PER_VALUE is 64. A standard vector of 2048 rows needs exactly 32 words — 256 bytes, four cache lines. The (BITS_PER_VALUE - 1) in the ceiling division is there for the ragged tail: a vector of, say, 100 rows needs two words, not one.

And the two predicates that the rest of the engine branches on:

cpp
// src/include/duckdb/common/types/validity_mask.hpp:82
	inline bool CannotHaveNull() const {
		return !validity_mask;
	}
	inline bool CanHaveNull() const {
		return validity_mask;
	}

CannotHaveNull() is the interesting one. It is a null-pointer check, not a scan. It is O(1), branch-predictable, and it is the answer to “does this column need a NULL check at all?”.

Reading: the short circuit

cpp
// src/include/duckdb/common/types/validity_mask.hpp:197
	//! Returns true if a row is valid (i.e. not null), false otherwise
	inline bool RowIsValid(idx_t row_idx) const {
#ifdef DEBUG
		if (row_idx >= capacity) {
			throw InternalException("ValidityMask::RowIsValid - row_idx %d is out-of-range for mask with capacity %llu",
			                        row_idx, capacity);
		}
#endif
		if (!validity_mask) {
			return true;
		}
		return RowIsValidUnsafe(row_idx);
	}

Two branches. In a release build the first is gone entirely, and the second is if (!validity_mask) return true;.

This is the pattern to internalise: the check for “is there a mask?” is hoisted out of the per-row loop, but it is written once, in one place, and every caller gets it for free. A kernel that calls RowIsValid per row does not know whether it is paying for a mask read or not — but the branch predictor will, after the first few rows, nail the !validity_mask case completely, because it is the same answer every time.

Compare that with the alternative: allocate the mask, fill it with all-ones, and read a bit per row. Same answer, but 256 bytes of memory traffic per vector and one extra load in the dependency chain.

Writing: only one direction costs anything

Writing is asymmetric, and deliberately so.

Marking a row valid is free, because the default state is already “valid”:

cpp
// src/include/duckdb/common/types/validity_mask.hpp:219
	//! Marks the entry at the specified row index as valid (i.e. not-null)
	inline void SetValid(idx_t row_idx) {
#ifdef DEBUG
		if (row_idx >= capacity) {
			throw InternalException("ValidityMask::SetValid - row_idx %d is out-of-range for mask with capacity %llu",
			                        row_idx, capacity);
		}
#endif
		if (!validity_mask) {
			// if CannotHaveNull() we don't need to do anything
			// the row is already valid
			return;
		}
		SetValidUnsafe(row_idx);
	}

The comment says it plainly: “if CannotHaveNull() we don’t need to do anything / the row is already valid”.

Marking a row invalid is the only operation that allocates:

cpp
// src/include/duckdb/common/types/validity_mask.hpp:248
	//! Marks the entry at the specified row index as invalid (i.e. null)
	inline void SetInvalid(idx_t row_idx) {
#ifdef DEBUG
		if (row_idx >= capacity) {
			throw InternalException("ValidityMask::SetInvalid - row_idx %d is out-of-range for mask with capacity %llu",
			                        row_idx, capacity);
		}
#endif
		if (!validity_mask) {
			Initialize(capacity);
		}
		SetInvalidUnsafe(row_idx);
	}

Initialize(capacity) allocates the mask and — crucially — fills it with all-ones first, so that the other 2047 rows are correctly marked valid. One allocation, and only when a NULL actually shows up.

So the lifecycle is: start with no mask, stay with no mask until someone writes a NULL, allocate once at that moment, and keep the mask thereafter. A column that is NOT NULL never allocates a mask at all.

And you can always go back:

cpp
// src/include/duckdb/common/types/validity_mask.hpp:144
	inline void Reset(idx_t target_count_p = STANDARD_VECTOR_SIZE) {
		validity_mask = nullptr;
		validity_data.reset();
		capacity = target_count_p;
	}

Reset frees the mask and sets the pointer back to null. “This column has no NULLs” is a state you can return to.

Where it pays off: the aggregate hash table

Here is where the trick stops being a memory optimisation and becomes a query optimisation.

DuckDB’s hash aggregate stores groups in a TupleDataLayout — a columnar layout with its own validity bytes per row. When it builds the table, it has to decide how to compare a probe row against a stored row. There are two candidate semantics:

COMPARE_EQUAL — plain equality. NULL = NULL is false, and a NULL never equals anything.
COMPARE_NOT_DISTINCT_FROM — SQL’s IS NOT DISTINCT FROM. NULL = NULL is true.

If the group columns can contain NULLs, you must use the second: GROUP BY x puts all the NULLs into one group, and a probe row with x = NULL has to find that group.

But if the group columns can never contain NULLs, the two semantics coincide, and you can use the much cheaper plain equality. DuckDB decides this once, at table construction time:

cpp
// src/execution/aggregate_hashtable.cpp:86
	// Predicates
	const auto expr_type = (layout_ptr->CannotHaveNull() && !layout_ptr->HasNestedTypes())
	                           ? ExpressionType::COMPARE_EQUAL
	                           : ExpressionType::COMPARE_NOT_DISTINCT_FROM;
	predicates.resize(layout_ptr->ColumnCount() - 1, expr_type);
	row_matcher.Initialize(true, *layout_ptr, predicates);

One ternary, evaluated once, that changes the comparison function used by every probe of the table, forever.

What does that buy? Look at the comparison operators:

cpp
// src/include/duckdb/common/operator/comparison_operators.hpp:105
struct DistinctFrom {
	template <class T>
	static inline bool Operation(const T &left, const T &right, bool left_null, bool right_null) {
		if (left_null || right_null) {
			return left_null != right_null;
		}
		return NotEquals::Operation(left, right);
	}
};

struct NotDistinctFrom {
	template <class T>
	static inline bool Operation(const T &left, const T &right, bool left_null, bool right_null) {
		return !DistinctFrom::Operation(left, right, left_null, right_null);
	}
};

NotDistinctFrom is !DistinctFrom, and DistinctFrom has an extra branch on the two null flags plus a negation on top. Equals has neither. So the cheap predicate is one fewer branch and one fewer boolean inversion, on every column of every group key, for every probe row.

And DuckDB pushes the decision even further down, into the template. The row matcher specialises on four combinations of “left side all valid” and “right side all valid”:

cpp
// src/common/row_operations/row_matcher.cpp:64
template <bool NO_MATCH_SEL, class T, class OP>
static idx_t TemplatedMatch(Vector &, const TupleDataVectorFormat &lhs_format, SelectionVector &sel, const idx_t count,
                            const TupleDataLayout &rhs_layout, Vector &rhs_row_locations, const idx_t col_idx,
                            const vector<MatchFunction> &, SelectionVector *no_match_sel, idx_t &no_match_count) {
#if DUCKDB_SMALLER_BINARY(row_matcher_validity)
	return TemplatedMatchLoop<NO_MATCH_SEL, T, OP>(lhs_format, sel, count, rhs_layout, rhs_row_locations, col_idx,
	                                               no_match_sel, no_match_count);
#else
	if (lhs_format.unified.validity.CannotHaveNull()) {
		if (rhs_layout.CannotHaveNull()) {
			return TemplatedMatchLoop<NO_MATCH_SEL, T, OP, true, true>(
			    lhs_format, sel, count, rhs_layout, rhs_row_locations, col_idx, no_match_sel, no_match_count);
		} else {
			return TemplatedMatchLoop<NO_MATCH_SEL, T, OP, true, false>(
			    lhs_format, sel, count, rhs_layout, rhs_row_locations, col_idx, no_match_sel, no_match_count);
		}
	} else {
		if (rhs_layout.CannotHaveNull()) {
			return TemplatedMatchLoop<NO_MATCH_SEL, T, OP, false, true>(
			    lhs_format, sel, count, rhs_layout, rhs_row_locations, col_idx, no_match_sel, no_match_count);
		} else {
			return TemplatedMatchLoop<NO_MATCH_SEL, T, OP, false, false>(
			    lhs_format, sel, count, rhs_layout, rhs_row_locations, col_idx, no_match_sel, no_match_count);
		}
	}
#endif
}

This is the payoff in its full glory. The runtime fact “this column has no NULLs” is turned into a compile-time template parameter, and the inner loop then contains literally zero NULL checks:

cpp
// src/common/row_operations/row_matcher.cpp:49
		if (COMPARISON_OP::template Operation<T>(
		        lhs_data[lhs_idx], Load<T>(rhs_location + rhs_offset_in_row),
		        LHS_ALL_VALID ? false : !lhs_validity.RowIsValidUnsafe(lhs_idx),
		        RHS_ALL_VALID ? false
		                      : !ValidityBytes::RowIsValid(
		                            ValidityBytes(rhs_location, rhs_column_count).GetValidityEntryUnsafe(entry_idx),
		                            idx_in_entry))) {

LHS_ALL_VALID ? false : ... — when LHS_ALL_VALID is true as a template parameter, the compiler folds the whole expression away. RHS_ALL_VALID ? false : ... likewise. The ?: here is not a runtime branch; it is a compile-time one, because the left operand is a template parameter.

So the chain is:

CannotHaveNull() is a null-pointer test — O(1), no memory access.
It selects the comparison semantics once, at hash-table construction.
That semantics, plus the per-side validity flags, selects a template instantiation of the match loop.
The template instantiation has the NULL checks compiled out entirely.

A runtime fact became a compile-time fact, and the whole cost of it vanished.

The write side propagates the fact

For the above to work, “this column has no NULLs” has to survive being copied around. And it does, because copying a mask that does not exist is a no-op rather than a materialisation:

cpp
// src/common/vector/flat_vector.cpp:527
void FlatVector::CopyValidity(Vector &target, const Vector &source, idx_t count) {
	if (source.GetVectorType() == VectorType::FLAT_VECTOR) {
		SetValidity(target, Validity(source));
		return;
	}
	auto &result_validity = ValidityMutable(target);
	if (source.GetVectorType() == VectorType::CONSTANT_VECTOR) {
		if (ConstantVector::IsNull(source)) {
			result_validity.SetAllInvalid(count);
		} else {
			result_validity.Reset(count);
		}
		return;
	}
	auto validity = source.Validity();
	if (!validity.CanHaveNull()) {
		result_validity.Reset(count);
		return;
	}
	for (idx_t r = 0; r < count; r++) {
		if (!validity.IsValid(r)) {
			result_validity.SetInvalid(r);
		}
	}
}

result_validity.Reset(count) — not “allocate a mask and set every bit”. Reset sets the pointer to null. So a NULL-free column propagates its NULL-freeness downstream instead of turning into a 256-byte all-ones bitmap that every downstream kernel would then have to read.

The same thing happens in the validity mask’s own Copy:

cpp
// src/include/duckdb/common/types/validity_mask.hpp:351
	inline void Copy(const TemplatedValidityMask &other, idx_t count) {
		capacity = count;
		if (other.CannotHaveNull()) {
			validity_data = nullptr;
			validity_mask = nullptr;
		} else {
			validity_data = make_buffer<ValidityBuffer>(other.validity_mask, count);
			validity_mask = validity_data->owned_data.get();
		}
	}

The same idea, one layer down: MVCC deletes

This “absence encodes meaning” pattern shows up again in DuckDB’s transaction layer, and it is worth looking at because it is the same trick applied to a harder problem.

DuckDB’s MVCC stores, per row, the transaction id that inserted it and the transaction id that deleted it. Storing two uint64_ts per row for a billion rows is 16 GB of metadata, so the representation has to degrade gracefully. It does so with three states:

cpp
// src/include/duckdb/storage/table/chunk_info.hpp:47
//! The storage state of the delete side of a ChunkVectorInfo. Exhaustive and mutually exclusive:
//! CONSTANT - all rows share constant_delete_id (NOT_DELETED_ID for none-deleted, or a single delete id)
//! MASKED   - partially deleted, all deleted rows share one committed id (mask_delete_id): which rows are
//!            deleted is stored in deleted_mask, deleted_data freed
//! ARRAY    - per-row delete ids materialized in deleted_data
enum class DeleteIdState : uint8_t { CONSTANT, MASKED, ARRAY };

Read the CONSTANT case again: “all rows share constant_delete_id (NOT_DELETED_ID for none-deleted)”. A single sentinel value means “not deleted” — the absence of a per-row array is the information, exactly like a null validity pointer.

And the MASKED state is the same idea as the validity mask: a bitmap of deleted rows plus one shared transaction id, valid because every deleted row in the vector was deleted by the same committed transaction.

The scan over that mask is word-at-a-time:

cpp
// src/storage/table/chunk_info.cpp:104
	case DeleteIdState::MASKED: {
		// every deleted row shares mask_delete_id and alive rows are NOT_DELETED_ID (never deleted), so the
		// delete decision is a single constant for the whole vector
		const bool masked_deleted = DELETE_OP::IsDeleted(view, mask_delete_id);
		if (HasConstantInsertionId()) {
			if (!INSERT_OP::UseInsertedVersion(view, ConstantInsertId())) {
				return 0;
			}
			if (!masked_deleted) {
				// the delete is not visible to this transaction - every row is visible
				return max_count;
			}
			// only the alive (mask-invalid) rows are visible
			if (!sel_vector) {
				return max_count - deleted_mask.CountValid(max_count);
			}
			// scan the mask a word at a time: skip fully-deleted words, take fully-alive words wholesale,
			// only extract bits for mixed words
			idx_t count = 0;
			const idx_t entry_count = ValidityMask::EntryCount(max_count);
			for (idx_t entry_idx = 0; entry_idx < entry_count; entry_idx++) {
				auto entry = deleted_mask.GetValidityEntry(entry_idx);
				if (ValidityMask::AllValid(entry)) {
					// every row in this word is deleted - skip
					continue;
				}
				const idx_t base = entry_idx * ValidityMask::BITS_PER_VALUE;
				const idx_t entry_end = MinValue<idx_t>(base + ValidityMask::BITS_PER_VALUE, max_count);
				if (ValidityMask::NoneValid(entry)) {
					// every row in this word is alive - select them all
					for (idx_t i = base; i < entry_end; i++) {
						sel_vector->set_index(count++, i);
					}
					continue;
				}
				for (idx_t i = base; i < entry_end; i++) {
					if (!ValidityMask::RowIsValid(entry, i - base)) {
						sel_vector->set_index(count++, i);
					}
				}
			}
			return count;
		}

Compare this loop with the one in the scalar executor, which walks the validity mask 64 rows at a time and skips all-ones or all-zeros words wholesale. It is the same algorithm applied to the same data structure. DuckDB reuses ValidityMask as its bitmap type everywhere — for NULLs, for deleted rows, for row-group validity — precisely because the word-at-a-time scan is such a good fit.

And the state machine collapses over time. CompressDeleteToMask folds a per-row id array into a mask plus one shared id:

cpp
// src/storage/table/chunk_info.cpp:336
void ChunkVectorInfo::CompressDeleteToMask(transaction_t mask_id) {
	D_ASSERT(delete_state == DeleteIdState::ARRAY);
	// the mask can only carry a single committed id shared by every deleted row
	D_ASSERT(IsCommitted(mask_id));
	// start all-valid (== all deleted), then mark the alive rows invalid
	deleted_mask.Initialize(STANDARD_VECTOR_SIZE);
	{
		auto segment = allocator.GetHandle(deleted_data);
		auto deleted = segment.GetPtr<transaction_t>();
		for (idx_t i = 0; i < STANDARD_VECTOR_SIZE; i++) {
			if (deleted[i] == NOT_DELETED_ID) {
				deleted_mask.SetInvalid(i);
			}
		}
	} // release the read handle before freeing the buffer
	allocator.Free(deleted_data);
	deleted_data = IndexPointer();
	mask_delete_id = mask_id;
	delete_state = DeleteIdState::MASKED;
}

The per-row array is freed. The mask replaces it. The NOT_DELETED_ID sentinel is what made the collapse possible in the first place — one sentinel value, and “which rows are alive” becomes a bitmap.

Seeing it yourself

sql
CREATE TABLE strict (id INTEGER NOT NULL, val INTEGER);
CREATE TABLE loose (id INTEGER, val INTEGER);

INSERT INTO strict SELECT range, range % 10 FROM range(100000);
INSERT INTO loose  SELECT range, range % 10 FROM range(100000);

-- the aggregate on the NOT NULL column builds a layout whose group columns
-- CannotHaveNull(), so the hash table uses COMPARE_EQUAL for every probe.
SELECT val, count(*) FROM strict GROUP BY val;
SELECT val, count(*) FROM loose  GROUP BY val;

-- and once a NULL shows up, the mask is allocated and the semantics change
INSERT INTO loose VALUES (NULL, 99);
SELECT val, count(*) FROM loose GROUP BY val;

The plans look identical. The generated code does not: strict’s group-by has no NULL checks in its probe loop at all, and loose’s does (until the NULL arrives, at which point loose behaves like strict for the rows that are clean and pays the price for the ones that are not).

You can also see the “no NULLs” fact survive a copy:

sql
-- the filter produces a dictionary vector; the validity mask is a view,
-- and if nothing was NULL there is nothing to view.
SELECT count(*) FROM strict WHERE id > 10;

What it costs

A branch in the hot path. RowIsValid has an if (!validity_mask) check. It is perfectly predicted, but it is a branch.
One allocation, once. The first SetInvalid on a mask allocates 32 words. If that happens for every vector, you have paid the allocation cost for the “all rows valid” case too — but you have not paid the 256-byte read cost in the common case where the mask is absent.
Loss of the “no NULLs” fact once a NULL appears. A vector with a single NULL in it needs the full mask for all 2048 rows. The mask is all-or-nothing per vector.
The CannotHaveNull() decision is only as good as the layout. If the aggregate’s group columns are nullable, DuckDB must use COMPARE_NOT_DISTINCT_FROM for the whole table, because one NULL anywhere forces the semantics for every row. This is a real trade: a single nullable group column costs the entire table the fast path.
The MVCC version has the same shape. MASKED requires every deleted row to share one committed transaction id. A delete that spans two concurrent transactions cannot use it and stays in ARRAY state until compression can prove otherwise.

The bottom line

The general lesson is that absence can be cheaper than presence, if you design the absence to mean something.

In DuckDB, a null validity_mask pointer means “all rows are valid”. That one convention buys:

Zero bytes of bitmap for a NOT NULL column, and zero mask reads in every kernel that touches it.
A compile-time decision in the aggregate hash table: CannotHaveNull() is checked once and turns into a template parameter that erases the NULL check from the probe loop.
Propagation: copying a NULL-free column keeps it NULL-free instead of materialising an all-ones mask.

And the same convention, applied to MVCC delete state, lets a chunk’s worth of per-row transaction ids collapse into one bitmap and one shared id — freeing the array entirely.

The design rule: when a piece of metadata is usually uniform, do not store it. Store the exception, and let the absence of the exception carry the common case.