Module format

Expand description

§SST Files with Inverted Index Format Specification

Each SST file includes a series of inverted indices followed by a footer.

inverted_index₀ inverted_index₁ ... inverted_indexₙ footer

Each inverted_indexᵢ represents an index entry corresponding to tag values and their locations within the file.
footer: Contains metadata about the inverted indices, encoded as a protobuf message.

An inverted index comprises a collection of bitmaps, a null bitmap, and a finite state transducer (FST) indicating tag values’ positions:

null_bitmap bitmap₀ bitmap₁ bitmap₂ ... bitmapₙ fst

null_bitmap: Bitset tracking the presence of null values within the tag column.
bitmapᵢ: Bitset indicating the presence of tag values within a row group.
fst: Finite State Transducer providing an ordered map of bytes, representing the tag values.

The footer encapsulates the metadata for inversion mappings:

footer_payload footer_payload_size

footer_payload: Protobuf-encoded InvertedIndexMetas describing the metadata of each inverted index.
footer_payload_size: Size in bytes of the footer_payload, displayed as a u32 integer.
The footer aids in the interpretation of the inverted indices, providing necessary offset and count information.

More detailed information regarding the encoding of the inverted indices can be found in the RFC.