# 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**:
1. **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.
2. **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.
3. **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 `RecordBatch`es
    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`](https://github.com/benolabsai/benostreamdb/issues?q=is%3Aissue+is%3Aopen+label%3Aroadmap).
> 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:
> 1. **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.
> 2. **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.
> 3. **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](https://github.com/benolabsai/benostreamdb/blob/main/src/core/table/coordinator.rs#L89) (with
    `WorkUnit` / `Lease`), its only implementation
    [`ObjectStoreCoordinator`](https://github.com/benolabsai/benostreamdb/blob/main/src/core/table/coordinator.rs#L112), and the
    claim → read → write → commit loop in
    [`ingest_with_coordinator`](https://github.com/benolabsai/benostreamdb/blob/main/src/core/table/ingest.rs#L304). 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.

> **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.

- [ ] **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 `FlightEndpoint`s 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:
> 1. **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).
> 2. **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.
> 3. **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**.