Integer Compression

Integer Compression

MemCP can store an integer column relative to its minimum and bit-pack the remaining range. A range of eight values needs three value bits instead of a fixed 32- or 64-bit slot. Constant, sparse, low-cardinality, and arithmetic-sequence representations may win for other distributions.

Frame-of-reference layout

The compact structure is easiest to understand without the later batch and JIT optimizations:

• find minimum and maximum inside one rebuilt shard;
• store offset = minimum;
• choose bitwidth = ceil(log2(maximum - minimum + 1)) (plus a code when the chosen NULL representation needs one);
• allocate enough 64-bit words for row_count × bitwidth bits;
• encode row item_id at bit position item_id × bitwidth as value - offset.

type packedFrame struct {
    offset   int64
    bitwidth uint8
    words    []uint64
}

bitpos := uint64(itemID) * uint64(frame.bitwidth)
word := bitpos / 64
shift := bitpos % 64
// read/write the value bits; a value may cross into words[word+1]

This is a frame-of-reference, fixed-bit packed representation sometimes discussed alongside FOR/PFOR techniques. The current StorageInt does not need a classic Patched-FOR exception list: the observed shard range determines one lossless width, while sparse/default and sequence wrappers handle distributions for which another representation wins. See also FastPFor and Patrick Damme's work on lightweight compression.

For observed minimum min and maximum max, the encoder stores value - min using enough bits for the complete range. Packed values cross 64-bit word boundaries when necessary; batch readers share bit-position work across consecutive RecordIDs. Binary values can therefore approach one payload bit per row, while IDs and local timestamp ranges use only the width their shard actually needs.

Representation selection happens per rebuilt physical column. Scan code uses range and multi-record batch access so unpacking remains sequential and cache-friendly. Delta values written since the last rebuild are merged with main storage visibility by the scan path.

NULLs, defaults, and alternatives

NULL/default-heavy columns can store exceptions sparsely instead of paying a full value slot for every row. A constant column needs no per-row payload, while a low-cardinality column may use dictionary or entropy-oriented identifiers. A regular counter or timestamp can be represented as arithmetic runs. The analyzer chooses among these options; “integer column” therefore does not imply one fixed byte width.

When a packed range has a spare code, an implementation can reserve it for NULL; distributions where that would increase width may favor a sparse/default wrapper instead. The important contract is lossless SQL NULL round-trip, not one mandatory representation. Format choice is made from the actual shard values during rebuild.

The reduced decision looks like this:

if value == nil {
    hasNull = true
    return
}
observe(value)

// During final width selection, reserve a code for NULL if it fits.
// Otherwise choose a lossless wrapper/representation that keeps NULL separate.

Example: values from 1,000 through 1,031 need five payload bits after subtracting 1,000. Adding a nullable sentinel may require another code, while a column with only a handful of NULL rows can encode those exceptional RecordIDs separately.

For random values spanning most of a 64-bit range, bit packing may save little. Sorting or clustering can create smaller local ranges and longer sequences, but changing application order only for compression must be weighed against write behavior and query access paths.

Space and speed depend on range width, null/default density, ordering, shard size, and access pattern. Publish the dataset and storage statistics with any ratio. Persistent layout changes must preserve old magic/version readers.

In one early workload, nullable columns that had fallen back to the generic representation contributed to a reported 23 MiB footprint; after NULL-capable integer packing, the same workload was reported at 16 MiB. The old article described that as “40% savings”; arithmetically it is about a 30% reduction from 23 MiB. The dataset and measurement method were not preserved, so the result documents why the NULL code mattered but is not a current benchmark guarantee.

See Columnar Storage, Sequence Compression, and Performance Measurement.