index::inverted_index

Module format

Source
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.

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.

§Reference

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

Modules§

Constants§