Implementation:Lance format Lance RepDef

Knowledge Sources	Lance
Domains	Encoding, Columnar_Data
Last Updated	2026-02-08 19:33 GMT

Overview

The RepDef module provides utilities for encoding and decoding repetition and definition levels, which compress multiple validity bitmaps and offset arrays from nested Arrow structures into compact level buffers used in Lance 2.1+ structural encoding.

Description

Repetition and definition levels are a technique from the Dremel paper (also implemented in Apache Parquet, though Lance's implementation is not necessarily compatible). They allow encoding the full nesting structure -- including nullability at every level and list offsets -- into one or two dense integer buffers.

Repetition Levels:

Repetition levels convert sparse offset arrays into a dense array of integers. A non-zero value at position i indicates that a new list begins at nesting depth corresponding to that level. For example, with three levels of list nesting, a repetition value of 3 marks the start of a new outermost list. The number of repetition values may exceed the number of data values because empty lists must also be represented.

Lance uses 0 for the innermost level and higher values for outer levels (the opposite of Parquet's convention).

Definition Levels:

Definition levels zip together validity bitmaps from multiple nesting layers. Instead of storing separate bitmaps, a single integer per value indicates the "depth" at which a null occurs. If the outermost struct is null, there is no need to record inner validity. This is more compact than storing independent bitmaps.

Key Utilities:

• RepDefBuilder -- Accumulates validity and offset information as Arrow arrays are shredded into primitive leaf arrays during encoding. Supports add_validity_bitmap, add_offsets, and add_fsl to record each nesting layer. The serialize method produces final rep and def level buffers.
• CompositeRepDefUnraveler -- The reverse operation for decoding. Takes rep/def level buffers and reconstructs validity bitmaps and offset buffers via unravel_validity and unravel_offsets. It is "composite" because it can combine levels from multiple miniblock chunks.
• RepDefSlicer -- Slices rep/def buffers into miniblock-sized chunks, handling the complication that rep/def levels do not map 1:1 with values due to empty/null lists.
• build_control_word_iterator -- Produces byte-padded control words from rep/def levels for use in fullzip encoding.
• ControlWordParser -- Parses control words during fullzip decoding.

DefinitionInterpretation Variants:

• AllValidItem -- Non-nullable struct/primitive field
• NullableItem -- Nullable struct/primitive field
• AllValidList -- Non-nullable list (but may have empty lists)
• NullableList -- Nullable list (may have nulls)
• EmptyableList -- Non-nullable list that may be empty
• NullableAndEmptyableList -- Nullable list that may also be empty

Usage

Use this module when:

• Implementing structural encoders that need to shred nested Arrow data
• Implementing structural decoders that reconstruct nested Arrow arrays from flat encoded data
• Working with miniblock or fullzip encodings that interleave rep/def with values

Code Reference

Source Location	rust/lance-encoding/src/repdef.rs
Key Types	RepDefBuilder, CompositeRepDefUnraveler, RepDefSlicer, ControlWordParser, DefinitionInterpretation
Type Alias	LevelBuffer = Vec<u16>
Import	use lance_encoding::repdef::{RepDefBuilder, CompositeRepDefUnraveler};

I/O Contract

RepDefBuilder (Encoding Side):

Method	Input	Description
add_validity_bitmap	BooleanBuffer	Record a struct/primitive validity layer
add_offsets	Offsets, validity, empty info	Record a list layer with offsets
add_fsl	Validity, dimension	Record a fixed-size list layer
serialize	--	Produces (Option<LevelBuffer>, Option<LevelBuffer>) for rep and def

CompositeRepDefUnraveler (Decoding Side):

Method	Input	Output
unravel_validity	--	Option<BooleanBuffer> (validity bitmap)
unravel_offsets	--	OffsetBuffer (list offsets)

Level Encoding:

Level Type	Bits Used	Range
Repetition	u16	0 = innermost continuation, higher = new list at depth N
Definition	u16	0 = valid at all levels, higher = null at depth N

Usage Examples

use lance_encoding::repdef::RepDefBuilder;

// Build rep/def levels from nested array structure
let mut builder = RepDefBuilder::new();

// Add an outer nullable struct layer
// builder.add_validity_bitmap(outer_validity);

// Add a list layer with offsets
// builder.add_offsets(offsets, list_validity, has_empty_lists);

// Serialize to level buffers
// let (rep_levels, def_levels) = builder.serialize();
// rep_levels: Option<Vec<u16>> - only present if there are list types
// def_levels: Option<Vec<u16>> - only present if there is nullability

Related Pages

• Lance_format_Lance_CoreEncoder - Structural encoders use RepDefBuilder to collect nesting information
• Lance_format_Lance_BatchDecodeStream - Decoders use CompositeRepDefUnraveler to reconstruct Arrow arrays
• Lance_format_Lance_EncodingFormat - DefinitionInterpretation maps to RepDefLayer in protobuf metadata
• Lance_format_Lance_DataBlock - Decoded data blocks are combined with unraveled validity to produce Arrow arrays