Expand description
§SST Files with Inverted Index Format Specification
§File Structure
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.
§Inverted Index Internals
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.
§Footer Details
The footer encapsulates the metadata for inversion mappings:
footer_payload footer_payload_size
footer_payload
: Protobuf-encodedInvertedIndexMetas
describing the metadata of each inverted index.footer_payload_size
: Size in bytes of thefooter_payload
, displayed as au32
integer.- The footer aids in the interpretation of the inverted indices, providing necessary offset and count information.
§Reference
More detailed information regarding the encoding of the inverted indices can be found in the RFC.