Null Representation: Validity Bitmaps Against Sentinel Values

A column of 32-bit integers has $2^{32}$ representable values. If the column may also be absent for some rows, it needs at least one more state, and there is no spare bit pattern in the type. Every format resolves this by choosing between two strategies: store a second structure that says which values exist, or reserve one of the bit patterns as a marker for absence. The first keeps the type intact and adds storage. The second saves storage and destroys the ability to represent one legitimate value.

The choice is not cosmetic. It determines whether a reader can distinguish “the value is zero” from “the value is missing”, whether arithmetic on the column is a plain loop or a branchy one, and whether a schema can be widened later without a rewrite.

The bitmap and its accounting

A validity bitmap spends one bit per value, in a buffer aligned to the same length as the value buffer. Value $i$ is present when bit $i$ is set and absent when it is clear, with bits packed least-significant-first within each byte, the convention Apache Arrow specifies for its buffers. A null count stored alongside lets a reader skip the bitmap entirely when it is zero, which is the common case for columns that are mostly populated.

For a million-row int32 column the values occupy 4 MB and the bitmap 125 KB, 3.1 percent overhead. The same bitmap over an int8 column costs 12.5 percent, and over a boolean column, where the values themselves are one bit each, it doubles the storage. That ratio, not absolute size, is what makes the representation attractive for wide columns and awkward for narrow ones. Some formats drop the bitmap for required fields, which is why schema-level optionality is worth being honest about at design time: a column declared non-nullable can omit 125 KB per million rows and, more importantly, lets every downstream operator assume presence.

Reading a bitmap is cheap but not free. Testing one bit is a shift and a mask; counting the set bits of a byte is a single popcnt instruction on any x86-64 part since Nehalem and on ARMv8, so a null count over a whole buffer runs at roughly one instruction per eight values.

#include <stdint.h>
#include <stddef.h>

/* Bit i of the validity bitmap: byte i/8, bit i%8, least significant first. */
static inline int present(const uint8_t *bitmap, size_t i) {
    return (bitmap[i >> 3] >> (i & 7)) & 1;
}

/* Count present values over n slots, ignoring any bits past n. */
static size_t present_count(const uint8_t *bitmap, size_t n) {
    size_t full = n >> 3, rem = n & 7, total = 0;
    for (size_t b = 0; b < full; b++)
        total += (size_t)__builtin_popcount(bitmap[b]);
    if (rem)
        total += (size_t)__builtin_popcount(bitmap[full] & ((1u << rem) - 1));
    return total;
}

The trailing mask in the second function matters: the final byte of a bitmap is padded, and without masking the count would include slots that were never written.

The expensive part is using the bitmap during a computation, because a branch per value defeats vectorization. The standard fix is to compute over the values unconditionally, using whatever the buffer holds for null slots, and then select the results with a mask derived from the bitmap, so the null path costs a masked store rather than a mispredicted branch. This is why columnar engines care about the distinction between “the value is meaningless” and “the value is not there”: meaningless values can participate in arithmetic as long as their results are masked out at the end.

Semantics need the same discipline. SQL three-valued logic says NULL = NULL is unknown, not true, so a naive comparison over a bitmap column must combine the comparison result with the two operands’ validity bits. Two nulls compare to unknown, a null against a value compares to unknown, and only two present values compare normally. Aggregates diverge: count(*) counts rows, count(x) counts set bits, sum(x) skips nulls, and avg(x) divides by the set-bit count rather than the row count. A format that stores only a sentinel has no way to make these distinctions cheap, because it must first translate the sentinel back into a missing-value marker at read time.

What a sentinel buys and what it destroys

The sentinel approach reserves a value inside the type’s domain. The most defensible instance is the floating-point NaN payload: IEEE 754 reserves an entire exponent range for NaNs, so a format can declare that a specific NaN payload means “absent” without stealing any finite value. Even here the cost is real, since a computation that produces a NaN for arithmetic reasons becomes indistinguishable from absence unless the payload is checked explicitly, and payload propagation through hardware arithmetic is not guaranteed on every platform.

For integers there is no such reserved range, so a sentinel must take a real value. Choosing -1 for an unsigned counter, or the minimum signed integer for a signed one, or 9999-12-31 for a date, works exactly until the data contains that value. The failure is silent: the reader produces a null where the producer meant a number, and downstream aggregates shift without any error being raised. Zero as a sentinel is the worst variant because zero is the most common value in most columns and the most likely to be legitimate.

A narrower variant is a separate presence flag stored beside the value, which is a bitmap with worse packing: 8 bits per value instead of 1, and a struct alignment penalty on top. It buys byte-addressable checks and predictable layout for languages that lack bit manipulation, which is why some in-memory representations use it despite the 8x overhead. The trade is bandwidth for simplicity, and it is defensible only for small columns or for formats that are decoded once and cached.

Sentinels also break type evolution. Widening an int32 sentinel column to int64 preserves the sentinel only if the marker value is re-chosen, and every existing file still carries the old marker in the old width. A bitmap is width-independent, so widening the value buffer leaves the validity buffer untouched. This is the reason formats that expect schema change, such as the one described in Schema Evolution Without Rewriting Files, carry validity separately.

Nesting, repetition, and the three states

The bitmap story becomes more complicated once a column is nested, because “absent” splits into two different facts: the list itself is absent, or the list is present and empty. A validity bitmap alone cannot express both, since a null slot in a repeated column could mean either. The Dremel encoding solves this with two integers per value, a definition level recording how much of the path is defined and a repetition level recording where a new record starts, so absence at any depth is encoded without a sentinel. Repetition and Definition Levels works through that encoding.

Nested formats that use a bitmap instead rely on a parallel structure per level, so a column of lists of structs carries a validity bitmap for the list, another for each struct field, and the offsets array that delimits the lists. The per-value overhead multiplies by depth, which is one reason deeply nested schemas are expensive to scan even when the leaf values are small.

Storage interactions

Compression interacts with both representations in opposite directions. A dense validity bitmap compresses to very little when nulls cluster, because long runs of identical bytes are what run-length encoding handles best; a column that is 99 percent present compresses its bitmap to a handful of bytes per thousand rows. A sentinel column instead puts the marker inside the value stream, where it may help or hurt: a run of sentinels compresses well, but scattered sentinels break the runs that a dictionary or delta encoder would otherwise find, and they enlarge the dictionary by one entry while polluting the statistics that a reader uses to skip pages. A min/max range that includes a sentinel is misleading, because the extremes may be entirely absent values.

Sorting shows a related asymmetry. A bitmap column sorts by comparing values and treating nulls as a separate class, which most engines place at one end, and the comparison needs the validity bits at every step. A sentinel column sorts naturally because the marker is ordered with the rest of the domain, but the resulting order groups nulls wherever the marker happens to fall, which is rarely where the query semantics want them.

The asymmetry that decides the question is that a bitmap is correct for every value the type can hold and a sentinel is correct only for the values it excludes. Formats that must represent arbitrary user data have no choice but the bitmap. Formats that control their own value domain, such as a counter that cannot be negative, can reserve a sentinel and document the exclusion in the type rather than in a convention. Mixing the two inside one schema is where a decoder acquires the special cases that make it hard to trust, and where a reader that assumes one convention silently misreads the other.