Login

u/vinaykakade

r/databasedevelopment
A search index that's also a valid Parquet file: the storage format behind an object-storage-native retrieval engine
▲ 19 r/databasedevelopment

A search index that's also a valid Parquet file: the storage format behind an object-storage-native retrieval engine

Disclosure: I work on infino, an Apache-2.0 embedded retrieval engine in Rust. This is an internals post about one design decision: the risk of Parquet as our on-disk format. I'd like this sub's read on it, links to the relevant code are inline.

Our constraint

We are building SQL + full-text (BM25) + vector search over a single copy of data living on a Parquet file in object storage (S3/Azure/local). Two requirements fall out of that (design doc: superfile format):

  1. the file has to carry its own indexes, and
  2. the file format should remain a valid Parquet file, so that any Parquet reader (pyarrow, DataFusion, Spark, DuckDB, …) can read the raw bytes.

Embedding indexes in Parquet

We store data in a "superfile": a Parquet file with embedded indexes.

PAR1
[ Parquet row groups ]     <- written by parquet-rs / Arrow, untouched
[ full-text index blob ]   <- inverted index (postings)
[ vector index blob    ]   <- IVF clusters + 1-bit quantized codes
[ Parquet footer ]         <- standard footer, rewritten with inf.* offsets
PAR1

We write the columnar body with the normal Arrow ArrowWriter, embed the FTS and vector blobs, then re-emit a standard Parquet footer with extra key/value entries under an inf.* namespace recording each blob's offset and length. The splice lives in src/superfile/format/footer.rs (assembled by src/superfile/builder.rs).

How it stays valid Parquet:

  • Row groups are addressed by absolute offset in the footer, so appending blobs before the footer doesn't move them.
  • The footer is an ordinary Thrift Parquet footer; the file still starts and ends with PAR1.
  • Parquet readers ignore KV metadata they don't recognize, so inf.* is invisible to everyone but us.

The exact file we run BM25/vector/SQL against, pyarrow can open as a plain table. cargo run --example demo builds one, then reads it back with vanilla DataFusion to confirm the bytes are real Parquet. There's a Python version of the same proof in parquet_interop.py, which reads a superfile back with both pyarrow and DuckDB.

The two blobs: (1) the FTS side is a postings/inverted index (src/superfile/fts/), (2) the vector side is IVF (k-means centroids, vector/kmeans.rs) + RaBitQ 1-bit codes (vector/quant.rs) with an optional full-precision rerank tier (vector/rerank_codec.rs), are both are addressed by the footer offsets.

A table is a manifest over many superfiles

One superfile is immutable; a table is a manifest snapshot pointing at a set of them (design doc: supertable). The manifest also serves as a data-skipping index. For every superfile it carries min/max stats per column, term bloom filters (manifest/bloom.rs, manifest/term_range.rs), and vector centroids, side by side. So a query prunes in two tiers (query/skip.rs, query/prune.rs):

  1. Manifest skip: WHERE conjuncts run as scalar predicates against per-superfile min/max; a keyword term checks the term Bloom; a vector query checks centroids. Superfiles that can't match are dropped before data is fetched from object storage. Scalar, keyword, and vector signals prune through one shared layer.
  2. Parquet skip: surviving superfiles' bytes are handed to DataFusion's Parquet reader (via an in-memory object store trait, query/df_object_store.rs), which does its own row-group/page pruning.

Indexes also act as physical access paths inside SQL, not just a bolt-on search API (query/provider.rs, query/exec/). An equality/IN on an indexed text column resolves through the inverted index to a candidate row set before any column is read. And the search operators are table functions (relations), so a ranked candidate set is the first stage of a plan:

-- rank first; join + aggregate over just the candidates
SELECT a.name, COUNT(*) AS hits
FROM bm25_search('posts', 'body', 'rust async', 100) p
JOIN authors a ON a.author_id = p.author_id
GROUP BY a.name;

They're registered as DataFusion UDTFs in src/catalog/search_tvf.rs; pushed filters are reported Inexact, so the planner re-applies the full predicate above the scan (in other words, index pruning only narrows the candidate set, making full text search indices actually help answer sql queries faster).

Commit / concurrency model

Superfiles are immutable and append-only. A write stages new superfiles, then commits a new manifest snapshot via an object-store conditional write (create-if-absent / If-Match etag) leveraging optimistic concurrency. A stale writer loses the compare-and-swap and retries. (manifest/commit.rs, supertable/writer.rs.) Reads are snapshot-isolated against the manifest they opened. Deletes are tombstones (roaring bitmaps) layered over the immutable files (supertable/tombstones/).

Tradeoffs

  • Cold first-query latency: the first query against an un-cached superfile pays object-storage round trips (tens to hundreds of ms).
  • Append-only: Atomic manifest commit is the durability boundary; updates/deletes are tombstones.
  • Embedded library: no wire protocol / SQL endpoint yet (commercial hosted service is in the works).
  • Optimized for query latency: the design optimizes for warm query latency.

Stack: Rust, Arrow/Parquet 58, DataFusion 53, object_store 0.13, roaring; Apache-2.0 license. Repo: https://github.com/infino-ai/infino

Where to read the code

Paths point at main and may move as we refactor. If a link 404s, the module names below and the architecture docs are the stable references, or just search the repo.

Two things I'd like this sub's take on:

  1. Embedding secondary indexes in Parquet KV metadata + offsets (vs. a sidecar file, vs. a fully custom container): is this a sharp edge I'll regret? My specific worry is a stricter future parquet reader that objects to bytes living next to the footer, making such improvements of parquet not supported.
  2. The manifest-as-data-skipping-layer (term Blooms + centroids + min/max in one pass): has anyone fused keyword/vector/scalar pruning in a single manifest pass, and where does it fall over at scale?

(Disclosure repeated: there's a commercial hosted version in the works; everything above is the OSS engine and this post is about the design.)

u/vinaykakade — 7 days ago