Full Text Search in SmithDB: Constructing and Querying our Inverted Index (Pt. 2)

Overview

In our earlier blog post on supporting full text search in SmithDB, we went over how we designed our object-storage backed inverted index implementation. In this blog post, we will cover how we construct, compact, and query this index in SmithDB.

Inverted index construction and merging

Index construction happens inline during ingestion. New runs become searchable within seconds, and because the freshest data is still resident on the node that wrote it, leading-edge queries read both the indexes and core data files directly from local storage instead of paying a round trip through object storage. On compaction, we merge indexes associated with different data files.

Payload parsing

Recall that SmithDB indexes the large inputs and outputs fields (among a few others) present in run payloads. For deeply nested and large payloads, JSON parsing dominates construction time. We only need flattened key paths and leaf values, so we built a JSON tape adapted from Apache Arrow's arrow-json crate, which is itself inspired by simdjson's tape format.

Our implementation consists of a flat sequential array of tokens with all string bytes in one contiguous buffer: no per-field allocation, no numeric conversion. A single-pass iterator then flattens each document into (path, leaf_value) pairs: nested objects become dotted paths, array elements collapse onto their parent key: {"agent": "deep agents", "tags": ["langchain", "engine"]} yields (agent, "deep agents"), (tags, "langchain"), (tags, "engine").

Tokenization

Before a value becomes an index term, it is tokenized: split on non-alphanumeric boundaries, lowercased, dropped of stop words, and capped at 256 characters.

Sorting and interning

Recall that we use finite state transducers (FSTs) for our term layout in our inverted index implementation. The flat postings table must be sorted by term before it can feed the FST writer.

Across agent traces, the same JSON paths and token values repeat in virtually every document for a particular tenant and tracing project. When implemented naively, this sort is dominated by string comparisons. To get around this, we leverage string interning: a technique that maps each unique term to a compact integer ID upfront. As a result, comparison cost scales with distinct terms, not occurrences, cutting construction time by ~2.2× in our benchmark.

We use ahash for hashing (stdlib ~20% slower, Tantivy's MurmurHash2 ~30% slower), store all bytes in one contiguous buffer, and use Hashbrown's raw API to hash each string exactly once per intern call. Each occurrence is then recorded as a (doc_id, term_rank, position) triple in a flat table. We leverage radix sort to group postings by term in O(n) before the sorted run feeds the FST writer.

Flush thresholds

Accumulating an entire batch before writing would let a single high-frequency term (5, agent, or a common JSON key) grow unboundedly. During index write, we have optimized flush boundaries on three thresholds:

• a row group: 32 MB postings / 500 K terms / 64 MB raw term bytes, sized to keep the in-memory FST writer within addressable memory
• an aligned chunk: ~2 MB, postings and positions flush at matching document boundaries so a query reading both gets contiguous byte ranges in a single GET
• a mid-term position spill: 8 MB, an escape hatch for Zipfian tail terms like 5 that would otherwise accumulate hundreds of millions of positions before the term finishes

Index merge

Our compaction service merges smaller files written by ingestion into larger files more optimal for querying. Along with compacting core files, the service processes each core file’s per-file indexes with a streaming merge.

A min-heap advances one term at a time across all inputs; each input holds only one decoded chunk in memory at a time, never the full segment. The merged terms emerge already sorted (required by FST writing) and the same three flush thresholds from construction (row group, aligned chunk, mid-term position spill) bound the output builder after every term. Memory scales with the number of inputs being merged, not the total index size, regardless of how many segments are involved.

Query time

The read path reuses the same machinery the rest of SmithDB queries already flow through (DataFusion and Vortex's LayoutReader pipeline) and slots the inverted index in as another layout that the planner pushes predicates into. Nothing about the SQL surface or the query planner had to learn that an index exists: it’s all handled internally by our TableProvider and LayoutReader implementations.

For a given query, after resolving the candidate segments from our metastore, the planner checks which of those segments actually have an index built for the column being queried. Segments missing an index for the queried column are quietly routed to a column scan instead; segments with an index are routed to the index. All of this happens before any object-storage request.

One segment, many files

In SmithDB, each metastore entry points to one core file holding the row data, plus a sibling file per indexed column. The challenge at query time is making this collection of files behave like a single addressable entity (both to DataFusion above and to the IO scheduler below) while still letting each predicate pick which files it actually needs to open.

At plan time, each predicate is inspected once per segment and routed to one of three outcomes: read it through the index (the column is indexed in this segment), fall back to a column scan on the core file (no index available), or short-circuit to "no matches" (the column isn't projected at all).

At runtime, the core file and each index file compose into a single virtual layout. DataFusion sees one logical file segment. The IO scheduler sees the actual byte ranges from each underlying file.

From layout to GETs

Our earlier blog post outlined how we organize our inverted index data into row-groups. Each row-group read has two phases: range registration, then decode. The reader resolves the term against the FST, reads its term_info entry to obtain postings (for phrase queries, positions as well) offsets and lengths, and registers all required ranges with the Vortex segment scheduler before issuing any object-store request. The scheduler merges adjacent ranges, combines non-adjacent ranges separated by gaps of up to 1 MB, and caps the coalesced window at 16 MB.

Once a row group's ranges are fetched, decode happens entirely within the returned buffer, with no further object-store requests. Even seeking is local: block-bitpacked deltas record their per-block bit width inline, so skipping a block advances the cursor by a constant offset without decoding it and without issuing a GET.

Three query shapes, three lookup paths

Once routing has handed the predicate to the index layout, each of the three query shapes maps directly onto the v2 columns (term, term_info, postings, positions).

Path-only (json_key) walks the term_key FST and returns postings. Positions are never read since this isn’t a phrase query.

Keyed-search (json_key_search) does one or more FST lookups against term_value, using the token\0path keying introduced in the v2 layout. A single-token lookup is a single FST exact-match plus a single postings fetch.

Full-text (search) reuses the same term_value FST in two modes. For plain-text columns it's an exact lookup. For free-text over JSON values, the token\0 prefix scan walks every path the token appears under and unions their postings: one FST serving both keyed and unkeyed search.

Multi-token phrases on any of the three shapes run through PhraseQuery, which works in two stages: first intersect postings to narrow the candidate documents, then decode positions only for those candidates and verify adjacency.

Handling recently ingested data

The "indexes built inline during ingestion" construction model makes searching recent data possible, but it requires the read path to span two storage tiers:

• L0: local SSD on the ingestion node. When ingestion accepts a batch of runs to ingest, the per-column inverted index for that batch is written to local SSD.
• L1: object storage. A best-effort compaction in the ingestion service promotes L0 segments and their indexes to object storage.

Routing at query time keeps the two tiers coherent without coordination. Sticky routing ensures queries land on the writer node, where the layout reader composes that node's in-memory L0 indexes alongside the L1 indexes for older segments.

What’s next

We’ll be making and documenting quite a few optimizations to our full text search and inverted index implementation in the near future. Additionally, we’ll be writing more blog posts on SmithDB internals including how we support sub-second stats on massive datasets through a combination of storage layout optimizations and distributed query execution.