Tantivy Search Engine Library

The tantivy-sstable crate provides a Sorted String Table (SSTable) implementation designed primarily for use in quickwit. It serves as an alternative to the default tantivy FST dictionary and as a storage mechanism for column indices in dynamic fast fields.

Key benefits include:

• Locality: Unlike the fst crate, which requires downloading the entire dictionary to search a key, tantivy-sstable allows a get operation to be performed with a single fetch once the index is downloaded.

Note: Current performance for get operations is considered poor due to the specific block index and default block size design optimized for Quickwit.

For tables containing very few keys, the standard SSTable footer (which costs ~70 bytes) is inefficient. To mitigate this, SingleBlockSStable omits the Fst and BlockAddrStore.

Instead, it implicitly uses a single block with:

• FirstOrdinal: 0
• RangeStart: 0
• RangeEnd: IndexOffset

All operations are performed against this implicit block.

Users interact with the index through a Searcher. A Searcher provides a point-in-time snapshot of the index by holding a list of SegmentReader objects.

Crucially, because the Searcher holds a snapshot, search results remain consistent even if background processes like segment merges, commits, or file garbage collection occur. To maintain a consistent view of the data, reuse the same Searcher instance.

Fast fields (equivalent to Lucene's DocValues) provide column-oriented storage optimized for random access and aggregations. They use bitpacking compression and are designed for minimal memory overhead via mmap.

Common Use Cases:

• Ranking/Scoring: Combining values (like upvotes) with relevancy scores.
• Aggregations: Computing metrics like the mean price of items in a result set.
• Filtering: Post-filtering a DocSet based on a range (e.g., price).
• Learning-to-Rank: Storing byte payloads for advanced model features.
• Faceting: Specialized fast fields for facet navigation.

Technical Detail: Fetching a value for a DocId is highly efficient, typically requiring only one memory fetch using the formula: min_value + fetch_bits(num_bits * doc_id..num_bits * (doc_id+1))

As of version 0.17, Tantivy supports a JSON object type to enable schema-less searching. When indexing a JSON object, Tantivy "flattens" the structure by emitting terms represented as a triplet: (json_path, value_type, value).

For example, indexing the following document:

{
    "user": {
        "name": "Paul Masurel",
        "address": {
            "city": "Tokyo",
            "country": "Japan"
        },
        "created_at": "2018-11-12T23:20:50.52Z"
    }
}

results in emitted tokens such as:

• ("name", Text, "Paul")
• ("name", Text, "Masurel")
• ("address.city", Text, "Tokyo")
• ("address.country", Text, "Japan")
• ("created_at", Date, 15420648505)

Tantivy's aggregation system is designed to mimic Elasticsearch's aggregation model. Aggregations are categorized into two main types:

1. Bucket Aggregations (bucket submodule): These group documents into buckets (e.g., range aggregation). They support nested sub-aggregations.
2. Metric Aggregations (metric submodule): These perform calculations on document values (e.g., average aggregation) and do not support sub-aggregations.

The aggregation lifecycle involves several distinct data structures that evolve as the request moves from a user query to a final result:

To optimize key storage, SSTables use Delta encoding. Each Delta consists of a KeepAdd instruction and a Suffix (the actual bytes to append to the previous key).

KeepAdd Representations

KeepAdd determines how many bytes to pop from the previous key (Keep) and how many to push from the current suffix (Add).

1. Compact Representation (used when keep < 16 and add < 16):

   • A single byte containing Add (4 bits) and Keep (4 bits).

2. Variable-length Representation (used otherwise):

   • A prefix byte 0x01 followed by Keep (VInt) and Add (VInt).

Note: Because SSTables do not support redundant keys, there is no ambiguity between these representations. Add is always non-zero, except for the very first key where Keep is guaranteed to be zero.