Struct tantivy_columnar::column_index::OptionalIndex

pub struct OptionalIndex { /* private fields */ }

This codec is inspired by roaring bitmaps. In the dense blocks, however, in order to accelerate select we interleave an offset over two bytes. (more on this lower)

The lower 16 bits of doc ids are stored as u16 while the upper 16 bits are given by the block id. Each block contains 1<<16 docids.

Serialized Data Layout

The data starts with the block data. Each block is either dense or sparse encoded, depending on the number of values in the block. A block is sparse when it contains less than DENSE_BLOCK_THRESHOLD (6144) values. [Sparse data block | dense data block, .. #repeat*; Desc: Either a sparse or dense encoded block]

Sparse block data

[u16 LE, .. #repeat*; Desc: Positions with values in a block]

Dense block data

[Dense codec for the whole block; Desc: Similar to a bitvec(0..ELEMENTS_PER_BLOCK) + Metadata for faster lookups. See dense.rs]

The data is followed by block metadata, to know which area of the raw block data belongs to which block. Only metadata for blocks with elements is recorded to keep the overhead low for scenarios with many very sparse columns. The block metadata consists of the block index and the number of values in the block. Since we don’t store empty blocks num_vals is incremented by 1, e.g. 0 means 1 value.

The last u16 is storing the number of metadata blocks. [u16 LE, .. #repeat*; Desc: Positions with values in a block][(u16 LE, u16 LE), .. #repeat*; Desc: (Block Id u16, Num Elements u16)][u16 LE; Desc: num blocks with values u16]

Opening

When opening the data layout, the data is expanded to Vec<SparseCodecBlockVariant>, where the index is the block index. For each block byte_start and offset is computed.

Implementations

impl OptionalIndex

pub fn for_test(num_rows: RowId, row_ids: &[RowId]) -> OptionalIndex

pub fn num_docs(&self) -> RowId

pub fn num_non_nulls(&self) -> RowId

pub fn iter_rows(&self) -> impl Iterator<Item = RowId> + '_

pub fn select_batch(&self, ranks: &mut [RowId])

Trait Implementations

impl Clone for OptionalIndex

fn clone(&self) -> OptionalIndex

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for OptionalIndex

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<OptionalIndex> for ColumnIndex

fn from(optional_index: OptionalIndex) -> ColumnIndex

Converts to this type from the input type.

impl Set<u32> for OptionalIndex

fn rank(&self, doc_id: DocId) -> RowId

Any value doc_id is allowed. In particular, doc_id = num_rows.

fn rank_if_exists(&self, doc_id: DocId) -> Option<RowId>

Any value doc_id is allowed. In particular, doc_id = num_rows.

type SelectCursor<'b> = OptionalIndexSelectCursor<'b> where Self: 'b

fn contains(&self, row_id: RowId) -> bool

Returns true if the elements is contained in the Set

fn select(&self, rank: RowId) -> RowId

Return the rank-th value stored in this bitmap.

fn select_cursor(&self) -> OptionalIndexSelectCursor<'_>

Creates a brand new select cursor.