OLAP – Phase 3 Compression
Columnar storage has a property that row-based storage doesn’t: values in a column tend to be similar. A status column might have only 5 distinct values across millions of rows. A timestamp column is monotonically increasing. A year column spans a narrow range. Compression codecs exploit these patterns to shrink data 5-10x, and because columns are stored independently, each column gets the codec that fits its data best.
This phase implements four compression codecs — RLE, Dictionary, Bitpacking, and Delta — with automatic selection that tries all applicable codecs and picks the smallest.
In DuckDB, these correspond to compression functions in src/storage/compression/ — rle.cpp, dictionary_compression.cpp, bitpacking.cpp, and patas.cpp (DuckDB uses PATAS for floating-point; we use delta for integers).
Here is the roadmap for the phases to come:
- Phase 3: Compression
- Phase 4: Table, catalog, and bulk loading
- Phase 5: Vectorized expressions and scan/filter/project
- Phase 6: Hash aggregation
- Phase 7: Hash join
- Phase 8: SQL parser
- Phase 9: Query planner and optimizer
- Phase 10: Sorting, parallel execution, REPL, and server
Full Source Code
The code referenced in this post can be found in https://gitlab.com/kimserey.lam/olap-learn.
Codec Interface
All compression codecs implement a simple interface:
1
2
3
4
5
type Codec interface {
Type() CompressionType
Compress(data []byte, count int, typ vector.LogicalType) ([]byte, error)
Decompress(data []byte, count int, typ vector.LogicalType) ([]byte, error)
}
The input/output is raw bytes — the column segment serializes its typed values into bytes before compression, and deserializes after decompression. This keeps the codecs type-aware but data-agnostic.
Auto-Selection
Rather than choosing a codec per-table or per-column, we try all applicable codecs for each segment and pick the one that produces the smallest output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func AutoSelectCompression(data []byte, count int, typ vector.LogicalType) (CompressionType, []byte) {
bestType := CompressionNone
bestData := data
for ct, codec := range codecs {
if !codecApplies(ct, typ) {
continue
}
compressed, err := codec.Compress(data, count, typ)
if err != nil {
continue
}
if len(compressed) < len(bestData) {
bestType = codec.Type()
bestData = compressed
}
}
return bestType, bestData
}
Not every codec applies to every type:
| Codec | Bool | Int32 | Int64 | Float64 | Varchar |
|---|---|---|---|---|---|
| RLE | yes | yes | yes | yes | yes |
| Dictionary | yes | yes | yes | yes | yes |
| Bitpacking | - | yes | yes | - | - |
| Delta | - | yes | yes | - | - |
RLE (Run-Length Encoding)
RLE replaces consecutive repeated values with (value, count) pairs. It’s best for sorted or low-cardinality columns where the same value appears many times in a row.
Example: [1, 1, 1, 2, 2, 3, 3, 3, 3] becomes [(1,3), (2,2), (3,4)]
For fixed-width types, the format is:
1
[numRuns: 4 bytes] [value: N bytes, runLength: 4 bytes] ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func rleCompressFixed(data []byte, count, typeSize int) ([]byte, error) {
var buf bytes.Buffer
buf.Write(make([]byte, 4)) // placeholder for numRuns
numRuns := uint32(0)
i := 0
for i < count {
valStart := i * typeSize
val := data[valStart : valStart+typeSize]
runLen := uint32(1)
for j := i + 1; j < count; j++ {
nextStart := j * typeSize
if bytes.Equal(val, data[nextStart:nextStart+typeSize]) {
runLen++
} else {
break
}
}
buf.Write(val)
b := make([]byte, 4)
binary.LittleEndian.PutUint32(b, runLen)
buf.Write(b)
numRuns++
i += int(runLen)
}
// write numRuns at the start
out := buf.Bytes()
binary.LittleEndian.PutUint32(out[0:4], numRuns)
return out, nil
}
When it wins: a sorted column with many consecutive duplicates. A status column sorted as ["active","active",...,"inactive","inactive",...] compresses to just a few runs.
When it loses: columns with high cardinality or random order — each value is its own run, and we pay 4 bytes of run-length overhead per value.
Dictionary Encoding
Dictionary encoding builds a table of unique values, then replaces each value with its integer code. It’s best for low-cardinality columns regardless of sort order.
Example: ["US","UK","US","FR","US","UK"] becomes dictionary {US→0, UK→1, FR→2} plus codes [0, 1, 0, 2, 0, 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func dictCompressFixed(data []byte, count, typeSize int) ([]byte, error) {
dict := make(map[string]uint32)
var dictOrder [][]byte
codes := make([]uint32, count)
for i := 0; i < count; i++ {
val := string(data[i*typeSize : (i+1)*typeSize])
code, exists := dict[val]
if !exists {
code = uint32(len(dict))
dict[val] = code
dictOrder = append(dictOrder, []byte(val))
}
codes[i] = code
}
var buf bytes.Buffer
// write dict size, then dict entries, then codes
// ...
return buf.Bytes(), nil
}
When it wins: a column with 5 distinct country codes across 100,000 rows. The dictionary is 5 entries (tiny), and each row stores a 4-byte code instead of a variable-length string.
When it loses: columns where every value is unique (like a UUID column) — the dictionary is as large as the original data, plus we still store the codes.
Bitpacking (Frame-of-Reference)
Bitpacking subtracts the minimum value from all values, then stores only the bits needed to represent the range. It’s best for integer columns with a small value range.
Example: values [1000, 1001, 1002, 1003] have range 3. ceil(log2(3)) = 2 bits per value instead of 32.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func bitpackCompressInt32(data []byte, count int) ([]byte, error) {
values := make([]int32, count)
for i := 0; i < count; i++ {
values[i] = int32(binary.LittleEndian.Uint32(data[i*4 : i*4+4]))
}
minVal := values[0]
maxVal := values[0]
for _, v := range values[1:] {
if v < minVal { minVal = v }
if v > maxVal { maxVal = v }
}
rangeVal := uint32(maxVal - minVal)
bitWidth := bits.Len32(rangeVal)
if bitWidth == 0 {
bitWidth = 1
}
packedSize := (count*bitWidth + 7) / 8
out := make([]byte, 1+4+packedSize) // bitWidth(1) + baseVal(4) + packed
out[0] = byte(bitWidth)
binary.LittleEndian.PutUint32(out[1:5], uint32(minVal))
packed := out[5:]
bitOffset := 0
for _, v := range values {
offset := uint32(v - minVal)
packBits32(packed, bitOffset, offset, bitWidth)
bitOffset += bitWidth
}
return out, nil
}
Savings example: 122,880 Int32 values in range [1000, 1015]. Range = 15, so bitWidth = 4 bits per value.
- Uncompressed: 122,880 × 4 = 491,520 bytes
- Bitpacked: 122,880 × 4 bits / 8 = 61,440 bytes + 5 bytes header = 8x reduction
Delta Encoding
Delta encoding stores the first value, then the difference between consecutive values as variable-length integers (varints). It’s best for monotonically increasing or slowly changing sequences like timestamps or auto-increment IDs.
Example: [100, 102, 105, 106] becomes first=100, deltas=[+2, +3, +1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func deltaCompressInt32(data []byte, count int) ([]byte, error) {
if count == 0 {
return nil, nil
}
out := make([]byte, 4, 4+count*binary.MaxVarintLen64)
first := int32(binary.LittleEndian.Uint32(data[0:4]))
binary.LittleEndian.PutUint32(out[0:4], uint32(first))
prev := first
varintBuf := make([]byte, binary.MaxVarintLen64)
for i := 1; i < count; i++ {
cur := int32(binary.LittleEndian.Uint32(data[i*4 : i*4+4]))
delta := int64(cur) - int64(prev)
n := binary.PutVarint(varintBuf, delta)
out = append(out, varintBuf[:n]...)
prev = cur
}
return out, nil
}
When it wins: a timestamp column with 1-second increments. Each delta is 1, which encodes as a single byte. 122,880 Int64 values: 983KB uncompressed → ~123KB delta-encoded.
When it loses: random integers with large, unpredictable gaps — deltas need as many bits as the originals, plus varint overhead.
How It All Fits Together
When a Vector is serialized into a ColumnSegment (Phase 2), the raw bytes pass through AutoSelectCompression:
- Serialize the vector’s typed values into raw bytes
- Try RLE, Dictionary, Bitpacking, and Delta (where applicable)
- Pick whichever produces the smallest output
- Store the compression type in the segment header
On read, the segment header’s Compression field tells the reader which codec to use for decompression before converting bytes back to a Vector.
The compression type is stored per-segment (not per-table or per-column), so the same column might use bitpacking in one row group and dictionary in another — whatever fits that particular chunk of data best.
