This is a tracking issue for implementing blocked Frame of Reference (FoR) encoding. This is not a new encoding, but rather an evolution of the existing FoR encoding. The evolution will be supported with editions.
Motivation
Our current FoR encoding uses one global reference for an entire array. This works well for arrays that are clustered around a single value, but less so for arrays whose values drift over the length of the array or with more localized patterns.
For example, consider a 3000-row array spread over three 1024-row chunks:
chunk 0 values: 1_000_000 .. 1_000_900
chunk 1 values: 5_000_000 .. 5_000_700
chunk 2 values: 9_000_000 .. 9_000_950
With the current FoR, we select the global min as the one reference (1_000_000):
chunk 0 values: 0 .. 900
chunk 1 values: 4_000_000 .. 4_000_700
chunk 2 values: 8_000_000 .. 8_000_950
With blocked FoR, we select local minima per chunk (1_000_000, 5_000_000, 9_000_000):
chunk 0 values: 0 .. 900
chunk 1 values: 0 .. 700
chunk 2 values: 0 .. 950
Blocked FoR gives each 1024-element chunk its own reference. 1024 is the FastLanes chunk size, so FoR chunks line up with bit-packed chunks. This lets decoding unpack a chunk and add its reference in one pass, and it pairs naturally with upcoming per-chunk bit widths in bit-packing.
Design
Array
We change the in-memory FoRArray in the following ways:
- Add a non-nullable
references array child and remove the reference field from metadata. Each value value[i] is the reference chosen for the ith chunk of 1024 values.
- Add an
offset field in metadata denoting the first element within the first chunk. It is nonzero only for sliced arrays, and keeps slicing zero-copy.
Element i decodes as encoded[i] + references[(offset + i) / 1024] with wrapping arithmetic.
Encoding
The encoder first determines a reference per 1024-len chunk instead of one global reference. The reference for a chunk is the minimum of its valid values. A chunk with no valid values reuses the previous chunk's reference, so references chunk compresses into runs.
Wire format
There are two serialized IDs for the one in-memory array:
fastlanes.for is the existing format, unchanged. It is written whenever the references are constant, so existing files read exactly as before, and default writes stay byte-identical.
fastlanes.for_v2 is a new format for varying references. Its children are [encoded, references], and its metadata holds the offset. The references child is serialized like any other child, so the compressor can compress it.
Compressor
FoRScheme gains a per-chunk mode. Scheme::refine selects it when fastlanes.for_v2 is allowed, and falls back to the single-reference mode otherwise.
This is a tracking issue for implementing blocked Frame of Reference (FoR) encoding. This is not a new encoding, but rather an evolution of the existing FoR encoding. The evolution will be supported with editions.
Motivation
Our current FoR encoding uses one global reference for an entire array. This works well for arrays that are clustered around a single value, but less so for arrays whose values drift over the length of the array or with more localized patterns.
For example, consider a 3000-row array spread over three 1024-row chunks:
With the current FoR, we select the global min as the one reference (
1_000_000):With blocked FoR, we select local minima per chunk (
1_000_000,5_000_000,9_000_000):Blocked FoR gives each 1024-element chunk its own reference. 1024 is the FastLanes chunk size, so FoR chunks line up with bit-packed chunks. This lets decoding unpack a chunk and add its reference in one pass, and it pairs naturally with upcoming per-chunk bit widths in bit-packing.
Design
Array
We change the in-memory
FoRArrayin the following ways:referencesarray child and remove thereferencefield from metadata. Each valuevalue[i]is the reference chosen for theith chunk of 1024 values.offsetfield in metadata denoting the first element within the first chunk. It is nonzero only for sliced arrays, and keeps slicing zero-copy.Element
idecodes asencoded[i] + references[(offset + i) / 1024]with wrapping arithmetic.Encoding
The encoder first determines a reference per 1024-len chunk instead of one global reference. The reference for a chunk is the minimum of its valid values. A chunk with no valid values reuses the previous chunk's reference, so references chunk compresses into runs.
Wire format
There are two serialized IDs for the one in-memory array:
fastlanes.foris the existing format, unchanged. It is written whenever the references are constant, so existing files read exactly as before, and default writes stay byte-identical.fastlanes.for_v2is a new format for varying references. Its children are[encoded, references], and its metadata holds the offset. The references child is serialized like any other child, so the compressor can compress it.Compressor
FoRSchemegains a per-chunk mode.Scheme::refineselects it whenfastlanes.for_v2is allowed, and falls back to the single-reference mode otherwise.