magmalake parquet

parquet · API

parquet.bitio

Bit-level readers: little-endian bit packing and the RLE/bit-packed hybrid.

Parquet packs small integers two ways, and both are here:

  • bit packing — values of a fixed bit width laid down least-significant bit first, running across byte boundaries. This is the packing used inside a hybrid run and inside a DELTA_BINARY_PACKED miniblock. (It is not the BIT_PACKED legacy level encoding, which packs most-significant bit first; that one has its own reader below.)
  • the RLE/bit-packed hybrid — a sequence of runs, each either a repeated value or a block of bit-packed values, introduced by a ULEB128 header. Definition levels, repetition levels, dictionary indices and RLE-encoded booleans are all this.

Everything is bounds checked: a truncated buffer, a run that claims more values than remain, or a bit width above 64 raises rather than reading past the end of the span.

Structs

BitReader

struct BitReader[origin: ImmOrigin]

Reads little-endian bit-packed values out of a borrowed span.

Implements Copyable, Movable

Fields
data: Span[UInt8, origin]
bit_pos: Int

__init__

def __init__(out self, data: Span[UInt8, origin])

byte_pos

def byte_pos(self) -> Int

align

def align(mut self)

get

def get(mut self, width: Int) -> UInt64

Read one value of width bits, least-significant bit first.

HybridRuns

struct HybridRuns[origin: ImmOrigin]

An RLE/bit-packed hybrid stream, read a block at a time.

decode_hybrid_into materialises the whole stream. A consumer that reads each value once and then throws it away — the dictionary gather — pays for that array twice, once written and once read straight back, and pays for the allocation under it. This hands the same values out in blocks of HYBRID_BLOCK into a scratch buffer the caller reuses.

Every run header, bit width and length is validated exactly as decode_hybrid_into validates it, with the same errors.

Implements Copyable, Movable

Fields
data: Span[UInt8, origin]
width: Int
pos: Int
left: Int: Values still owed to the caller.
run_left: Int: Values still to come out of the run in progress.
run_value: UInt64
run_packed: Bool

__init__

def __init__(out self, data: Span[UInt8, origin], width: Int, count: Int)

next_block

def next_block(mut self, mut scratch: List[UInt32]) -> Tuple[Int, Bool]

Decode the next values into scratch[0 : n]; return (n, uniform).

n is zero once every value asked for has been handed out. uniform says the whole block came out of one repeated run, so a consumer that has to validate the values can do it with one comparison instead of a scan.

scratch must hold at least HYBRID_BLOCK values, and a block is that many — a multiple of eight, which is what lets a bit-packed run be taken a block at a time. Eight values of width bits are exactly width bytes, so a block boundary inside a run is still a byte boundary; only the very last block of the stream may be shorter, and nothing is read after it.

HybridDecoder

struct HybridDecoder[origin: ImmOrigin]

The RLE / bit-packed hybrid used for levels, dictionary indices and RLE booleans.

run        := bit-packed-run | rle-run
bit-packed := <ULEB128 (groups << 1 | 1)> <groups * 8 values, bit packed>
rle-run    := <ULEB128 (count << 1)> <value, ceil(width/8) bytes LE>

Implements Copyable, Movable

Fields
data: Span[UInt8, origin]
pos: Int
width: Int
buffer: List[UInt64]
buf_pos: Int
value: UInt64
remaining: Int
is_packed: Bool

__init__

def __init__(out self, data: Span[UInt8, origin], width: Int)

next

def next(mut self) -> UInt64

take

def take(mut self, count: Int, mut out: List[UInt64])

Append the next count values.

Functions

bit_width

def bit_width(max_value: Int) -> Int

The number of bits needed to hold max_value (0 for 0).

unpack_lsb

def unpack_lsb(data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[UInt64]) -> Int

Append count little-endian bit-packed values; return the end byte.

unpack_lsb_into

def unpack_lsb_into[dt: DType](data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[Scalar[dt]], at: Int) -> Int

Unpack count little-endian bit-packed values of width bits into out[at : at + count], which the caller has already sized. Returns the byte just past the run.

The body of the run is read one unaligned 64-bit window per value — a load, a shift and a mask — which is what makes bit-packed levels and dictionary indices cheap. Only the last few values, whose window would reach past the end of the buffer, take the byte-at-a-time path.

levels_all_equal

def levels_all_equal(data: Span[UInt8], width: Int, count: Int, value: Int) -> Bool

Is every one of the next count hybrid-encoded levels equal to value?

Only run headers are read, so this is O(runs), not O(values). A bit-packed run answers False without being unpacked: a page whose levels are all the maximum is written as RLE runs by every writer in the wild, and that is the case worth the fast path.

decode_hybrid_into

def decode_hybrid_into[dt: DType](data: Span[UInt8], width: Int, count: Int, mut out: List[Scalar[dt]], at: Int)

Decode count RLE/bit-packed hybrid values into out[at : at + count], which the caller has already sized.

Runs are handled whole — a repeated run is a fill, a bit-packed run is one unpack_lsb_into — so nothing goes through a per-value decoder. This is the hot path for dictionary indices.

decode_levels_into

def decode_levels_into(data: Span[UInt8], width: Int, count: Int, max_level: Int, mut out: List[UInt16]) -> Int

Append count hybrid-encoded levels to out; return how many of them equal max_level.

Runs are handled whole: a repeated run is a fill, a bit-packed run is one unpack_lsb_into call. Nothing goes through a per-value decoder.

unpack_msb

def unpack_msb(data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[UInt64]) -> Int

The legacy BIT_PACKED level encoding — most-significant bit first.

read_uleb128

def read_uleb128(data: Span[UInt8], pos: Int) -> Tuple[UInt64, Int]

Decode a ULEB128 at pos; return the value and the byte after it.

zigzag_decode

def zigzag_decode(u: UInt64) -> Int64

Undo zigzag: 0,1,2,3,4 -> 0,-1,1,-2,2.

read_zigzag

def read_zigzag(data: Span[UInt8], pos: Int) -> Tuple[Int64, Int]

Decode a zigzag ULEB128 at pos; return the value and the next byte.

Aliases

comptime HYBRID_BLOCK = 1024

How many values HybridRuns.next_block hands out at a time.

Four kilobytes of UInt32 scratch, which stays in L1 between the decode and whatever consumes it. parquet-cpp's ProcessValues and arrow-rs's RleDecoder::get_batch_with_dict both use exactly 1024. It has to be a multiple of eight, for the reason next_block gives.