BenoStreamDB Roadmap & Architecture Status¶

Vision: Make Apache Iceberg executable as a high-performance database with rebuildable secondary index overlays (CSR graph, HNSW vector, BM25 text, Roaring bitmaps).

🎯 Architecture & Status at a Glance¶

Status	Capability Area	Key Components / Interfaces
✅ Developer Preview	Core Lakehouse Engine	Apache Iceberg V2/V3 format, Parquet storage, DataFusion ANSI SQL, MVCC lock-free commits, WAL, Ingest RAM backpressure.
✅ Developer Preview	Concurrency & Durability	Unified atomic write buffer (`PendingWrite`), Table-wide maintenance barriers (`maintenance_lock`), Fenced vacuum/orphan GC.
✅ Developer Preview	Vector Search Overlays	Zero-copy Arrow IPC HNSW & IVF-PQ, TurboQuant™ (TQ8; TQ4 retiring), SIMD intrinsics, GPU acceleration (`benostream-gpu-ann`: CUDA, Metal, Vulkan).
✅ Developer Preview	Text & Scalar Overlays	Inverted BM25 Okapi indexes, Roaring Bitmap scalar indexes, Composite multi-column filters, Statistics pruning.
✅ Developer Preview	Core Graph Primitives	Zero-copy Memory-Mapped CSR Graph Index (`MmapCsrGraph`), Core Graph Traversal operator (`Table::graph_neighborhood`), Graph SQL UDFs.
✅ Developer Preview	JSON Path Functions & Index	PostgreSQL `json_*` UDFs (`json_extract_path`, `json_contains`, `json_path_query`, …) over `Utf8` columns, plus a `json_path` `(path, value) -> row_ids` Puffin overlay with planner pushdown.
✅ Developer Preview	Lakehouse Connectors	Native Apache Spark connector (`spark-benostreamdb`), Trino connector (`trino-benostreamdb`), Official dbt adapter (`dbt-benostreamdb`). Full engine function-surface parity across Python/dbt/Spark/Trino, guarded by `tests/python/test_function_parity.py`.
✅ Developer Preview	Ecosystem Interfaces	Optional Arrow Flight SQL server (`server/flight_sql`), Contrib Search Gateway (`contrib/benostreamdb-search`: OpenSearch 7.10 & Qdrant REST), stateless auth (API key + JWT, shared module).
✅ Developer Preview	AI-Native & Search Extensions	MCP server (`contrib/benostreamdb-mcp`), SQL graph traversal (`FROM graph_neighbors(...)`), `Table::subscribe()` change feed + predicate-filtered subscriptions.

🏛️ Architectural Foundations (Completed)¶

BenoStreamDB implements an indexed, compute-disaggregated lakehouse architecture:

The Overlay Invariant: Parquet data files in Apache Iceberg are the authoritative source of truth. All secondary indexes (CSR graph, HNSW vector, BM25 text, Roaring bitmaps) are advisory, rebuildable sidecar overlays. If an index is lost or deleted, queries fall back to Parquet scans while the overlay rebuilds.
Serverless-First, Server-Optional: The core database is an in-process, embeddable library (Python/Rust/JVM) operating directly against object storage (S3/GCS/Azure/Local). Arrow Flight SQL provides an optional single-process network access layer for remote clients and BI tools.
Lakehouse Independence: All core connectors (dbt-benostreamdb, spark-benostreamdb, trino-benostreamdb) and optional servers (server/flight_sql) operate independently of contrib compatibility packages.

Key Completed Milestones¶

Core Concurrency Hardening:
- Unified pending_writes: Arc<RwLock<Vec<PendingWrite>>> ensuring atomic WAL-to-buffer pairing.
- Table-level maintenance_lock establishing an exclusive barrier between concurrent writes and destructive operations (truncate, vacuum, compaction).
- Strict manifest load error propagation across all mutation paths.
- Regression verified under parallel stress testing (tests/test_h1_h2_concurrency_regression.rs).
Core Graph Engine:
- Memory-mapped Compressed Sparse Row (.graph_v2.csr.{offsets,edges,dict}) engine.
- Core Table::graph_neighborhood() traversal operator with fast-path CSR execution, relation filtering, and unindexed edge fallback.
- Graph-scoped vector and BM25 queries callable directly from Python, SQL, and search APIs.
Native Ingest Orchestrator (Table::ingest_async):
- Cluster-free bulk ingestion with memory-budgeted chunking (malloc_trim heap policy), lock-free OCC manifest commits, and resume idempotency.
Multi-Catalog Resolution:
- Seamless integration with Apache Polaris, Nessie, AWS Glue, Hive Metastore, and file-based Iceberg catalogs.
PostgreSQL json Path Functions:
- json_extract_path / json_extract_path_text (variadic path), json_contains (recursive @>), json_exists, json_typeof, and json_path_exists / json_path_query (jsonpath subset: $.a.b[0], [*]). Implemented in src/core/sql/udf/json.rs.
Cross-connector function parity:
- The engine’s full custom function surface (vector scalar UDFs, vector aggregates, JSON, graph UDAFs) is exposed consistently across Python, dbt, Spark, and Trino, and guarded by tests/python/test_function_parity.py (source of truth: udf::registered_function_names()). The Spark DSv2 FunctionCatalog exposes 30 functions, and a pass-through reader (option("query", "<engine SQL>")) makes the vector aggregates and graph UDAFs — which have no DSv2 scalar equivalent — reachable from Spark. The engine’s ad-hoc Table::sql() context now registers the full surface via the shared udf::register_all_custom_udfs helper.
Ingest back-pressure liveness:
- The ingest RAM high-water mark is now baseline-relative (it bounds the engine’s growth since the write began) with a bounded fail-open grace (BSDB_INGEST_BACKPRESSURE_GRACE_SECS, default 60s), so a writer can no longer block forever when process RSS is already at/above the cap for reasons the write cannot relieve.
MCP Server (contrib/benostreamdb-mcp):
- Dedicated MCP server exposing BenoStreamDB tables, schemas, SQL queries, and hybrid vector/graph retrieval as native tools for Claude Desktop, Cursor, and Antigravity. Windows .msi installer via cargo-wix.
- 0.13.0: local, no-LLM embeddings (pure-Rust Candle BERT, BGE-small by default) with Ollama/OpenAI/TEI HTTP providers, list_embedding_models, and embedding provenance shared with the core engine.
JSON-Path Inverted Index:
- IndexAlgorithm::JsonPath { paths } builds a (path, value) -> row_ids Parquet overlay in src/core/index/json_path.rs, packed into the segment’s Puffin bundle under the json_path category. The planner rewrites json_contains / json_exists / json_path_exists / json_extract_path_text(...) = 'value' into index lookups (HybridReader::query_json_path_first), falling back to a full scan for unindexed paths. Verified by a differential oracle against a full scan (tests/test_json_path_index.rs).
SQL Graph Traversal Operator Extensions:
- DataFusion table functions expose graph walks directly in FROM clauses (graph_neighbors, graph_shortest_path, graph_all_shortest_paths, graph_subgraph, graph_connecting_paths), following the in-memory / out-of-core GraphMode pattern. Implemented in src/core/sql/graph_udf/graph_table_functions.rs; reachable from Python, dbt, Spark (pass-through), Trino, and Flight SQL.
Declarative Edge Table DDL:
- First-class table metadata (via Manifest.properties): table_type (node | edge | table), src_col, dst_col, relation_col, weight_col, id_col, label_col. create_edge_table / create_node_table stamp the convention; Session.list_graph_tables() enumerates them. Declaring table_type = 'edge' auto-configures the forward and reverse CSR graph indexes (Table::ensure_edge_indexes_async).
Table::subscribe() + predicate-filtered subscriptions:
- Per-table tokio::sync::broadcast channel emitting committed RecordBatches plus a Commit marker; exposed in Python, as the subscribe_events SQL table function, a Flight streaming ticket, and an MCP tool. Table::subscribe_filtered("age > 30") re-applies the predicate above each batch.
End-to-end benchmark suite:
- Vector ANN (SIFT/HNSW/TurboQuant), graph analytics, SQL OLAP, lexical & hybrid (BEIR), production concurrency/maintenance/recovery, and the shared-envelope Docker competitor matrix (FAISS, hnswlib, LanceDB, pgvector, OpenSearch, Neo4j+GDS, cuGraph).
Workflow tutorials:
- One runnable tutorial per workflow: (1) AI/semantic retrieval via MCP, (2) JSON/document retrieval with a JSON-path index, (3) graph traversal via graph_neighbors(...). Python versions are Jupyter notebooks (examples/tutorials/*.ipynb, verified to execute end-to-end); the SQL/connector forms (Spark/Trino/dbt/Flight/MCP/Rust) are markdown pages under docs/tutorials/.

📋 Active Roadmap Themes¶

Tracking. Actionable open items are tracked as GitHub issues labeled roadmap. The themes below retain the design rationale and priority; the issue list is the source of truth for status. status: committed marks current-cycle work, status: exploratory marks ideas awaiting user or benchmark validation, and status: deferred marks work that is intentionally unscheduled.

Release line. v0.13.0 shipped embedding provenance (core benostream.embedding.* table properties, the write/commit vector-space guard, and local BGE-small embeddings in the MCP server). v0.14.0 shipped connector parity — file-split parallel scans in Spark and Trino, Spark CALL procedures and row-level operations, exactly-once Spark writes (data files written in the task, metadata committed on the driver), multi-metric vector_search, hybrid search filter pushdown, Trino scalar-function parity, Flight SQL streaming execution, remote dbt through the Trino connector, and an MCP HTTP + SSE transport. v0.14.1 is a performance/correctness follow-up: angular recall on the TQ8/HNSW path is restored, HNSW-IVF cluster search runs in parallel, and the benchmark suite now records the machine state each sweep ran in (with a report that refuses to mix sessions). TQ4 removal is the highest-priority item for v0.15.0.

Themes are ordered by priority.

Theme 1: Isotropic Quantization (BenoQuant BQ8 & BQ4) and Native SQ8 — 🟢 Shipped / Retained in Core¶

Retain and upgrade 4-bit quantization with float16 length renormalization; preserve PQ for legacy sidecar compatibility.

Status & Resolution. Initial benchmarks showed 4-bit quantization suffering severe recall collapse under uncalibrated nibble packing. However, the introduction of the 2-byte IEEE 754-2008 float16 length normalization scalar ($\alpha$) combined with 7.5-centered nibbles in BenoQuant (hnsw_bq4) fully resolved norm bias and recall collapse, enabling 4-bit quantization to pack 128-dim vectors into 66 bytes total.

Rather than removing TQ4 and PQ from the core engine (GH Issue #120 closed as won’t do), both algorithms are retained as supported options in the core engine:

TurboQuant TQ4 (hnsw_tq4 / hnsw_bq4): Retained and upgraded for ultra-compact out-of-core datasets.

TurboQuant TQ8 (hnsw_tq8 / hnsw_bq8): Production isotropic INT8 quantization with Walsh-Hadamard rotation ($H \cdot D$).

Native SQ8 (hnsw_sq8): Shipped for axis-aligned INT8 scalar quantization.

Product Quantization (hnsw_pq): Retained in the core engine for legacy Iceberg index sidecar compatibility and research baselines.

TQ4 and PQ are omitted from standard public marketing benchmark reports to keep publications focused on f32 vs tq8/sq8, but remain fully supported in core Rust and PyO3 APIs.

[x] 2-byte float16 length scalar fix for 4-bit quantization — 🟢 Shipped:
- Implemented IEEE 754 binary16 length normalization scalar ($\alpha = \frac{\langle y, \hat{y} \rangle}{|\hat{y}|^2}$) trailer and 7.5-centered nibble math in src/core/index/benoquant.rs and distance.rs.
[x] Native SQ8 index type and routing — 🟢 Shipped:
- Added hnsw_sq8 as a first-class IndexAlgorithm variant and PyO3 bindings.
[x] Preserve PQ and BQ4 in engine core — 🟢 Shipped:
- Retained IndexAlgorithm::HnswPq and IndexAlgorithm::HnswBq4 in core segment writers, readers, and physical planners.

Theme 2: Multi-Precision Vector Indexes¶

Let one vector column serve both exact and compressed search. — 🔴 High

Current state. A vector column holds a single index: adding a second replaces the first (see Table::add_index in src/core/table/index_config.rs), and the default is now full-precision hnsw. Quantized variants are opt-in: hnsw_tq8 (TurboQuant 8-bit, ≈4× smaller) and hnsw_pq — trading recall for a smaller index and cheaper distance computation. The reader already ranks multiple index files for a column (vector_search_index_raw), but with float-first precedence and no per-query override.

[ ] Multiple vector indexes per column + query-time selection — 🟠 High:
- Allow a column to carry a float hnsw (exact / best recall) and a TurboQuant hnsw_tq8/hnsw_pq index, chosen per query, e.g. table.vector_search(..., index='tq8') — exact precision for recall-critical reads, the compressed index for latency-sensitive scans.
- Requires: (1) add_index to append a vector variant instead of replacing the whole family; (2) a query-time selector threaded through vector_search_index/vector_search_index_raw/vector_search_scored and the Python/SQL surfaces; (3) defining precedence when no selector is given (full precision first).

Theme 3: Overlay Indexes on Read-Only Delta & Hudi (Native Rust Translator)¶

Attach the overlay indexes to existing Delta / Hudi tables — writing only indexes, never data. — 🔴 High

Current state. Delta and Hudi tables are Parquet under the hood, and the overlay index engine already treats any Parquet file as data. The authoritative data files and the advisory index overlays are stored completely separately (s3://my-index-bucket/overlays/), so the upstream table does not even need to know BenoStreamDB exists. The existing Table.register_external(overlay_uri, iceberg_metadata_uri) path already attaches an overlay to an external, read-only Iceberg table without write permission on the upstream storage or catalog.

Approach: a read-side TableFormat trait, not a metadata materializer. XTable/UniForm solve a bidirectional metadata-sync problem (Delta↔Iceberg↔Hudi with write-back); we need one direction, read-only, in-process. So we do not materialize Iceberg metadata files. Instead, generalize the read path behind a TableFormat trait that produces the existing Manifest/ManifestEntry/ DeleteFile structures directly: IcebergFormat is today’s code, and DeltaFormat/HudiFormat parse the native logs. Nothing is written upstream and no Avro manifests are generated — the overlay bucket holds only our sidecars. Both existing translators are JVM-based (Apache XTable is Java; Delta UniForm is Scala/Java), so a native Rust implementation avoids a JVM runtime dependency entirely.

[ ] Extract a read-side TableFormat trait — 🟠 High:
- load_snapshot() → data files + delete files + schema + partition spec + snapshot id; read_deletes(); partition_transform(). IcebergFormat is a lift-and-shift of today’s read path (pure refactor, no behaviour change).
[ ] DeltaFormat (read-only) — 🟠 High:
- Parse _delta_log/NNN.json (newline-delimited add/remove/metaData/ protocol actions) + .checkpoint.parquet; merge-on-read via deletion vectors (Delta 3.x, RoaringBitmap .bin — we already have Roaring). The quick win: a bounded, well-documented parser.
[ ] HudiFormat (read-only) — 🟢 Deferred:
- Parse the .hoodie/ timeline (commit/deltacommit instants) + base Parquet + MOR log files (Avro HoodieLogBlock). COW first, MOR later; Hudi 1.0’s timeline format change is a moving target. The long pole.
[ ] Incremental-on-staleness builds (tail the log, don’t LIST) — 🟠 High:
- The upstream writer is external (Databricks/Flink), so we cannot hook its stream. A background crawler tails the latest _delta_log entry / timeline instant and compares it to the last-seen version — no full LIST, no per-file stat; steady-state cost is one small GET per poll. On change, it incrementally builds indexes for the new files only (HNSW append-insert + BM25 posting merge). Poll interval adapts to the observed change rate (backoff + jitter), with an explicit refresh() for query-time staleness.
[ ] Out-of-band append correctness (the Overlay Invariant) — 🟠 High:
- Until the background build catches up, the planner searches the existing HNSW/BM25 index for the old data and falls back to a Parquet scan for the newly appended files — 100% snapshot correctness at all times.
[ ] Out-of-core sidecars (mmap) — 🟢 Deferred:
- Extend the existing MmapCsrGraph pattern to the HNSW/BM25 sidecars: mmap the graph/postings, keep only the hot top-level (centroids, entry points) resident, and page in on demand via BSDB_DISK_CACHE_DIR. This is the only way a sidecar can exceed host memory.

Theme 4: Hardware-Accelerated CPU Distance Kernels via SimSIMD (ARM NEON, AVX-512, VNNI) — 🔴 High¶

Deliver hand-tuned SIMD vector distance execution on ARM64 and modern x86 without manual assembly maintenance.

Current state & Performance Gap. Vector distance calculations in src/core/index/distance.rs dominate HNSW graph traversal and point queries. Today, x86_64 uses manual 256-bit AVX2/FMA intrinsics, but:

ARM64 (Apple Silicon, AWS Graviton 3/4, Windows ARM / Snapdragon X Elite) currently lacks explicit SIMD intrinsics in distance.rs and falls back to scalar loop unrolling (dot_product_portable), missing out on 1.5×–2.5× throughput gains from hardware vector registers.

AVX-512 on modern AMD Zen 4/5 and Intel Xeon/Core processors is unutilized, leaving 512-bit registers (16 floats/instruction) and 32 ZMM registers untapped.

Quantized Vector Math: CPU lacks hardware VNNI (int8 dot products) and half-precision (f16/bf16) SIMD instructions, forcing software conversions.

Approach: Integrate Unum’s simsimd crate. simsimd provides production-hardened, zero-dependency C/assembly kernels with automatic runtime CPU dispatching across AVX2, AVX-512, AVX-512-FP16, ARM NEON, and ARM SVE. Integrating simsimd accelerates CPU-bound HNSW traversals across all platforms while eliminating ~400 lines of fragile unsafe architecture-specific intrinsics.

[ ] Integrate simsimd dependency into benostreamdb and benostream-gpu-ann — 🟠 High:
- Add simsimd (Apache-2.0, pure Rust bindings with compiled SIMD kernels) to workspace dependencies.
[ ] Wire runtime dispatch in src/core/index/distance.rs — 🟠 High:
- Replace manual dot_product_avx2, l2_distance_squared_avx2, and dot_product_portable with simsimd::spatial / simsimd::binary dispatches.
- Automatically route L2, Inner Product (Dot), Cosine, Hamming, and Jaccard distances through hardware-detected kernels.
[ ] Native Quantized CPU Distance Acceleration (i8 / f16 / bf16) — 🟠 High:
- Expose hardware-accelerated integer dot products (VNNI / ARM SDOT) and f16 distance kernels for TurboQuant / quantized vector scans on CPU.
[ ] Multi-Architecture Benchmarking — 🟡 Medium:
- Measure search latency improvements across Apple Silicon M-series (NEON), AWS Graviton 4 (SVE), AMD Zen 4/5 (AVX-512), and Windows on ARM.

Theme 5: GPU Scaling (single-query multi-GPU + cross-call batching) — 🟠 Medium¶

Shipped in 0.12.0. The multi-GPU device pool (gpu::set_gpu_device_pool, wired into Trino/Spark) round-robins devices across worker threads, and each kernel call is already batched (one H2D → launch → D2H over the whole vector set, with a 50k floor: GPU_DISPATCH_THRESHOLD).

Remaining. The round-robin only spreads work across concurrent dispatches — a single large query still runs on one device (HnswIvfIndex::search makes one synchronous compute_distance call), and there is no overlap of transfer with compute across calls.

[ ] Single-query multi-GPU sharding — shard the candidate set (e.g. HnswIvfIndex::search’s centroid / distance batch) across the devices in the pool, launch concurrently on each, and merge top-k. This is what turns the pool from a concurrency-only feature into a genuine per-query speedup.
[ ] Cross-call batching + streams — overlap H2D / compute / D2H across successive batches with CUDA streams instead of one synchronous round trip per call; pipeline rather than block.
[ ] Avoid redundant transfers — keep vectors/centroids device-resident and cache the uploaded query. Today each call re-uploads the query and copies the whole batch to host (htod_copy(vectors.to_vec())).
[ ] Adaptive dispatch threshold — GPU_DISPATCH_THRESHOLD (50k) is a coarse floor; make it adaptive to the measured launch/transfer overhead so mid-size batches can still benefit without paying H2D/D2H for nothing.

Theme 6: AI Agent Tools & Client Ecosystem¶

Native interfaces for AI frameworks and autonomous agent runtimes. — 🟠 Medium

[ ] LangChain & LlamaIndex Partner Integrations — 🟢 Deferred:
- langchain-benostreamdb: LangChain-compatible VectorStore and Retriever implementations with metadata filtering.
- llama-index-vector-stores-benostreamdb: LlamaIndex vector store index adapter.
[ ] Broker Event Adapters — 🟢 Deferred:
- Pluggable Kafka, RabbitMQ, and NATS consumers for automated event-driven lakehouse ingestion.
- Placement: a new contrib/benostreamdb-ingest crate, not the core. The publish/subscribe seam already lives in the core — the WorkCoordinator trait (with WorkUnit / Lease), its only implementation ObjectStoreCoordinator, and the claim → read → write → commit loop in ingest_with_coordinator. A broker adapter is therefore just another impl WorkCoordinator, so no new core API is required:
```
contrib/benostreamdb-ingest/
  Cargo.toml            # [[lib]] + [[bin]] bsdb-ingest; features = kafka/nats/rabbitmq
  src/kafka.rs          # KafkaWorkCoordinator    : impl WorkCoordinator
  src/nats.rs           # NatsWorkCoordinator     : impl WorkCoordinator
  src/rabbitmq.rs       # RabbitMqWorkCoordinator : impl WorkCoordinator
  src/main.rs           # bsdb-ingest daemon → Table::ingest_with_coordinator(..)
  tests/
```
- Why contrib/ and not core: the broker clients are heavy and platform-sensitive (rdkafka/librdkafka is a C dependency, plus lapin and async-nats); pulling them into the default engine build would regress build time, binary size, and cross-platform reach. This mirrors the existing boundary — core = engine + traits, contrib/ = deployment surfaces (bsdb-search, bsdb-mcp) — with bsdb-ingest as the third column.
- Semantics to settle at implementation: a broker consumer is a source of work, whereas WorkCoordinator is the queue/lease authority. Either implement the trait directly against the broker’s consumer-group offsets (broker is the queue), or keep ObjectStoreCoordinator as the lease authority and add a broker → queue enqueue bridge.
- Config: follow the BSDB_ / BSDB_SEARCH_ convention → BSDB_INGEST_* (brokers, topics, group id, lease TTL, coordinator backend selection: object-store | kafka | nats).
- Deploy / docs: a deploy/ compose entry (Kafka/NATS alongside the RustFS/Nessie stack) and docs/integrations/INGEST.md + its docs/source/guides/ copy, consistent with SEARCH_GATEWAY and MCP.
[ ] Named embedding profiles and per-provider credentials — 🟠 Medium:
- Add embedding.profiles (name → provider/model/URL/dimension, with api_key_env references) and an optional benostream.embedding.profile table property.
- Resolve secrets at runtime from the environment or a secret manager; never store API keys in table metadata. This lets one MCP process serve multiple HTTP providers without a raw key dictionary, while preserving the table-scoped model/dimension contract.
- Keep the current single-config behavior as the default profile for backward compatibility.
[ ] Per-session MCP scratch namespace + TTL — derive the agent scratch schema from the authenticated subject (JWT sub / API-key id, sanitized to scratch_<subject>) and give ephemeral tables a TTL + background GC, so two agents never share a namespace. Today scratch is a single shared schema.
[ ] Policy tooling & observability — a bsdb policy show|set|lint CLI (lint flags schemas present in storage but absent from the policy), an effective-permissions read endpoint, and a benostream_policy_denials_total{schema,action} metric so over-restriction is visible instead of looking like missing data.

Theme 7: Graph Overlays¶

Elevating knowledge graphs into a first-class lakehouse data modeling primitive. — 🟠 Medium

Partially delivered. The programmatic edge-table API has shipped: Table.create_edge_table(...), Table.from_networkx(...), and Table.to_networkx(...) create and round-trip standard edge tables with automatic endpoint/embedding sidecar indexes. The graph UDAFs (graph_neighbors, graph_pagerank, graph_shortest_path, …) are now reachable from every connector surface — including Spark, via the pass-through reader. Typed global URNs below remain open.

[ ] Typed Global Entity URNs (table:id) — 🟢 Deferred:
- Extend the CSR graph dictionary to support composite entity identifiers (e.g. users:101, orders:5002) so a single CSR graph overlay can seamlessly traverse across heterogeneous Iceberg tables.

Theme 8: Semi-Structured & JSON¶

First-class access to JSON documents without forcing a rigid column schema. — 🟢 Deferred

Current state. JSON is stored as a Utf8 string column (text, not a decomposed binary form, so the functions use PostgreSQL’s json_* names, not jsonb_*). The search gateway (contrib/benostreamdb-search/src/infer.rs) already infers an Arrow schema from sample documents (ES 7.10 dynamic mapping).

[ ] Iceberg v3 variant Mapping — 🟢 Deferred:
- Map semi-structured columns to Iceberg v3 variant (the spec-native semi-structured type) so JSON round-trips through catalogs instead of being a bespoke engine-only type; Arrow-side representation is Struct/Utf8 with path pushdown. This is a storage-fidelity improvement — it still needs the JSON-path index above to make containment fast.

Theme 9: Reactive Lakehouse Streaming¶

Bringing change data capture (CDC) and reactive streaming to the lakehouse. — 🟢 Deferred

[ ] Arrow Flight SQL Streaming Subscriptions — 🟢 Deferred:
- Implement Flight DoExchange / DoGet streaming endpoints allowing remote clients (Python, DuckDB, web dashboards) to subscribe to table diffs in real time without polling. Build this once somebody actually needs remote subscriptions.

Theme 10: Domain-Specific Text Analyzers for BM25¶

Specialized tokenization pipelines for enterprise code, legal, and multilingual knowledge bases. — 🟢 Deferred

[ ] Configurable Table Analyzer Configurations:
- Allow table schemas to declare custom text analyzers in metadata (analyzer = 'code_camelcase', stopwords = 'en').
[ ] Built-in Tokenizer Suite:
- Code Tokenizer: Splits on CamelCase, snake_case, and symbol delimiters for source code search.
- Multilingual Stemming: Integration of Snowball stemmers for English, Spanish, French, and German.
- CJK Segmentation: Character/bi-gram tokenization for Chinese, Japanese, and Korean corpora.

Theme 11: Distributed Query Fan-Out (Multi-Node Scale)¶

Scatter-gather over Arrow Flight for corpora that exceed one node’s memory envelope. — 🟠 Exploratory

Why now. The NeurIPS BigANN envelope — 8 vCPU / 16 GiB — is a deliberate constraint. It forces a 76 GB index through an 8 GB cache. The f32 Pareto curve at 100M (15 of 16 points, ef_search 32–256 × n_probe 4–32) is a clean monotone trade:

n_probe

Recall@10

QPS

p50

4

0.14

8.7

859 ms

8

0.25

5.8

1,268 ms

16

0.43

2.1

3,630 ms

32

0.62

0.9

8,704 ms

ef_search is nearly inert across an 8× range (0.1401 → 0.1427 at n_probe=4), so recall is dominated by IVF list pruning, not graph beam width. At 100M the IVF list count is sqrt(n)/5 ≈ 2,000, which makes n_probe=32 only 1.6% of the lists — the default sweep is calibrated for 1M–10M, not 100M. Reaching 0.90 recall extrapolates to n_probe ≈ 100–128, at roughly 0.2–0.3 QPS. The quantized modes have not been run at 100M yet, and they are the ones that matter: a 42 GB index cuts I/O per probe by 1.8× against the 76 GB f32 baseline.

The leaderboard is not the right comparison. Most entries are RAM-resident — they hold the index in memory, or let the page cache hold it — so a QPS rank compares an out-of-core engine against an in-memory one. The axis that matters is cost per vector at a fixed memory budget: 76 GB of index served from an 8 GB cache on commodity NVMe, versus 76 GB of RAM on a memory-optimized instance. That is the claim to make, and it is a TCO claim, not a QPS rank.

This theme answers a different question: what does a customer do when the corpus needs more than one node’s envelope? At 420 B/vector of quantized index, 1B vectors is ~420 GB — 13 nodes at 64 GiB, or 53 at the d8lds envelope. Fan-out is the only path past that. It is a product capability that sits alongside the challenge result, not a correction to it.

n_probe	Recall@10	QPS	p50
4	0.14	8.7	859 ms
8	0.25	5.8	1,268 ms
16	0.43	2.1	3,630 ms
32	0.62	0.9	8,704 ms

One binary, two topologies. The engine is already stateless with respect to data: rows live in Iceberg/Parquet on object storage, the index lives in Puffin sidecars, and a node holds only a cache. That makes serverless and distributed the same deployment with a different N:

Serverless (today)

Distributed (this theme)

Processes

1, embedded

N workers + 1 coordinator

Data

S3 / local

S3 / local, shared

Index

Puffin sidecar, cached

Puffin sidecar, sharded cache

Coordination

none

catalog commit + shard map

New code

—

routing index, DistributedScanExec, shard map

The coordinator is the same binary in a different role, not a separate service. The shard map and the routing index are metadata, not data. And the failure mode degrades gracefully: if a worker dies, the coordinator can read that shard directly from object storage — slower, but correct — because the node never owned the data in the first place. That property is what serverless already gives us, and it is what makes the distributed mode an addition rather than a second product.

	Serverless (today)	Distributed (this theme)
Processes	1, embedded	N workers + 1 coordinator
Data	S3 / local	S3 / local, shared
Index	Puffin sidecar, cached	Puffin sidecar, sharded cache
Coordination	none	catalog commit + shard map
New code	—	routing index, `DistributedScanExec`, shard map

[ ] Coordinator-side global routing index — 🟠 Exploratory:
- Hold a coarse centroid table at the coordinator (~128 KB for 1B vectors over 1,000 centroids at 128 dims × 1 byte) and route each query to the top-p partitions instead of broadcasting to every node. Per-segment centroids already exist; the cross-node union does not.
[ ] Flight scatter-gather ExecutionPlan — 🟠 Exploratory:
- A DistributedScanExec that fans a query vector to N FlightEndpoints and merges local top-k into global top-k. This is a UnionExec + SortExec + LimitExec over remote streams, not a scheduler.
[ ] Recall contract for distributed top-k — 🟠 Exploratory:
- Local top-k ≠ global top-k. State an oversample factor (3–5×) and publish a measured recall curve against the single-node baseline. Without it, fan-out is a latency win with an unmeasured accuracy cost.
[ ] Coordination via the catalog, not consensus — 🟠 Exploratory:
- Read-only fan-out needs no Raft: every worker reads the same Iceberg snapshot, and the catalog’s atomic commit is the only coordination point. Node-to-segment assignment belongs in a manifest property or a sidecar table.
[ ] Failure semantics — 🟠 Exploratory:
- Fail-fast on worker loss for v1, with the partial-result recall caveat documented rather than implied.

Alternatives considered.

Ballista — right reference architecture, wrong dependency. It already implements ExecutionPlan → stage → task → Flight exchange, and its execution_plans/ module is worth reading. But it is a batch SQL engine: the scheduler round-trip alone exceeds our 10M p50 of 44–49 ms, and it distributes relational operators, not top-k fan-out.

Ray — belongs on the build path, not the query path. Parallel segment builds, the ef_construction sweep, and embedding generation are throughput-bound and tolerate scheduler overhead; per-query fan-out does not.

Spark connector — analytics interop, not retrieval. Spark already reads the Iceberg table; a DSv2 connector adds pushdown. Its 100 ms+ task overhead rules it out for ANN.

Trino connector — enterprise federation bridge, not low-latency ANN routing. Trino is built for cross-catalog interactive OLAP, but its JVM coordinator, split scheduling, and HTTP exchange buffers impose a 50–200 ms latency floor before vector distance computation begins, turning a 48 ms in-process index traversal into a batch query and requiring a heavy Java daemon cluster.

Resolved in v0.14.2. The hnsw_tq8 OOM at segment 2 of 20 was buffered graph serialization, not global IVF training: the builder held the whole graph in memory before writing the Puffin, so peak memory scaled with the corpus rather than the segment. f9015e7c replaced it with streaming bucket-graph serialization, a direct-to-disk Puffin writer, and a per-segment jemalloc heap trim. The quantized index now builds per segment, which is the precondition for a per-node shard map. The remaining blocker for this theme is query latency, not build memory.

Theme 12: High-Throughput Vector Indexing Suite (e-means + Residuals + SIMD FastScan) (v0.16.0) — 🟢 Shipped in v0.16.0¶

10× faster index construction via e-means coarse clustering, 70–85% variance reduction via residual encoding, and 4–6× faster query scans via 4-bit in-register SIMD FastScan. — 🟢 Shipped in v0.16.0 (the engine work; the comparative Lloyd-vs-e-means benchmark below is still open)

Why now. Rather than treating vector indexing bottlenecks in isolation, this theme unifies coarse clustering, inverted list layout, and SIMD query traversal into an integrated vector pipeline:

Coarse Clustering Bottleneck (Solved via e-means): Replaces truncated Lloyd’s algorithm with Meta FAIR’s stochastic Exponential Moving Average (EMA) e-means algorithm (“e-means: outperforming k-means in one-tenth the epochs”, Bessa et al., arXiv:2611.09501), achieving true convergence in 1.2–2.5 epochs (~10× faster training, zero dead clusters).

Dynamic Range & DC Offset Bottleneck (Solved via Residual Encoding): Storing inverted list vectors as residuals $r = x - c_j$ compresses coordinate variance by 70–85%, eliminating the large DC offsets that distort 4-bit and 8-bit quantization.

CPU Scan Throughput Bottleneck (Solved via SIMD FastScan): Storing 4-bit subvector codes interleaved in contiguous blocks allows distance lookup tables to fit entirely inside SIMD registers. Lookups execute via hardware byte shuffles (_mm256_shuffle_epi8 on x86, vtbl1_u8 on ARM NEON), evaluating 32 vector distances per cycle without L1/L2 cache misses.

[x] e-means Coarse Quantizer Engine (benostream-gpu-ann/src/e_means.rs & src/core/index/e_means.rs) — ✅ Completed:
- Bumped sub-crate benostream-gpu-ann to v0.2.0.
- Implemented streaming mini-batch accumulator, cosine step schedule ($\alpha_0 \to 0.1\alpha_0$), and mass-proportional donor splitting with alternating coordinate perturbation ($\epsilon = 10^{-4}$).
- Hardware dispatch across GPU (CUDA/Metal/WGPU) and multi-core CPU with Rayon.
- Gated dispatch in src/core/index/ivf.rs (simple_kmeans_with_seed), preserving capacity-capped Voronoi balancing. Verified: 10,000 vectors clustered into 64 partitions in 150ms.
[x] Fuzzing & Robustness (fuzz/fuzz_targets/e_means.rs) — ✅ Completed:
- Registered e_means fuzz target fuzzing degenerate inputs (zero vectors, colinear points, extreme norms, NaNs).
[x] Residual Inverted List Encoding (src/core/index/ivf.rs & benostream-gpu-ann/src/ivf_flat.rs) — ✅ Completed in v0.16.0:
- Subtract coarse centroid $c_j$ during inverted list insertion ($r = x - c_j$): IvfIndex::use_residuals defaults to enabled.
- Compute query residual $q_r = q - c_j$ once per probed cluster during fine search, preserving exact distance equivalence while shrinking storage and quantization noise.
[x] In-Register 4-bit SIMD FastScan Engine (benostream-gpu-ann/src/) — ✅ Completed in v0.16.0:
- 4-bit codebook quantization and interleaved block packing live in fastscan.rs, the residual-encoded IVF scan in ivf_fastscan.rs, with benostream-gpu-ann/tests/test_ivf_fastscan.rs as the regression gate. These are in the benostream-gpu-ann sub-crate, not src/core/index/.
[ ] Empirical Benchmarks (SIFT-1M & Cohere-10M) — 🔴 Still open:
- Benchmark index construction wall-clock time and query recall@10 vs. latency curves across Lloyd, e-means, and FastScan.
- The v0.16.0 runs measured quantizer modes (SQ8, PQ) on BigANN-10M and Cohere-10M, not clustering algorithms. What is missing is a controlled A/B of Lloyd against e-means at matched recall, and a FastScan-vs-scalar-scan latency pair; no artifact exists for either yet.

Benchmarks as Product Work¶

Benchmarks and demonstrations are part of the product, not marketing polish. The Launch Candidate requires excellent end-to-end benchmarks and documentation/tutorials that show the three workflows concretely. Both have shipped — see Key Completed Milestones.