vinothchandar commented on code in PR #19309: URL: https://github.com/apache/hudi/pull/19309#discussion_r3920705037
########## rfc/rfc-109/rfc-109.md: ########## @@ -0,0 +1,1005 @@ +<!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> + +# RFC-109: Native Vector Search Support in Apache Hudi + +## Proposers + +@chrevanthreddy + +## Approvers + +- TBD + +## Status + +Umbrella issue: [apache/hudi#19094](https://github.com/apache/hudi/issues/19094) + +Related: [apache/hudi#18676](https://github.com/apache/hudi/issues/18676) + +State: UNDER REVIEW + +--- + +## Table of Contents + +- [Abstract](#abstract) +- [1. Goals and Non-Goals](#1-goals-and-non-goals) +- [Limitations](#limitations) +- [2. Architecture](#2-architecture) +- [3. IVF + RaBitQ Index Algorithm](#3-ivf--rabitq-index-algorithm) +- [4. Metadata Table Storage Model: the Posting Block](#4-metadata-table-storage-model-the-posting-block) +- [5. Bootstrap and Write Path](#5-bootstrap-and-write-path) +- [6. Read Path](#6-read-path) +- [7. Maintenance, Rebalancing, and Cleaner](#7-maintenance-rebalancing-and-cleaner) +- [8. Spark API Surface](#8-spark-api-surface) +- [9. Correctness, Compatibility, and Freshness](#9-correctness-compatibility-and-freshness) +- [10. Test Plan](#10-test-plan) +- [11. Rollout and MVP Scope](#11-rollout-and-mvp-scope) +- [12. References](#12-references) +- [Appendix A. Controlled BIGANN Research Evidence](#appendix-a-controlled-bigann-research-evidence) + +--- + +## Abstract + +This RFC proposes native approximate nearest-neighbor (ANN) vector search in Apache Hudi. +Tables increasingly carry embedding columns represented by Hudi's fixed-dimension +`VECTOR(D[, elementType])` logical type, and users want to ask *"find the K rows most +similar to this query vector"* — for semantic search, recommendations, RAG, and +deduplication — without copying data into a separate vector database. + +Today the only option on a Hudi table is a brute-force scan: read every vector, compute +every distance. That is correct but scales linearly with table size (tens of seconds at a +billion rows). This RFC adds an index so that vector queries read only a small, targeted +fraction of the index and the table, return results with high recall, and stay +transactionally consistent with the table under upserts and deletes — all with **no new +storage system**. The index lives in the Hudi Metadata Table (MDT), like Hudi's existing +record-level and secondary indexes, and is maintained by the same table services. + +The design combines three well-understood pieces — IVF clustering, RaBitQ quantization, and +exact re-ranking — with one storage innovation that makes them practical on an immutable, +columnar, object-store-resident lakehouse. A **posting** is the index entry for one logical +record: its generation-scoped cluster membership, compressed scoring material, record key, +and source locator. A **generation** is an atomically published, versioned namespace for one +complete index state: schema contract, centroids, quantizer, routing, postings, and freshness +frontier. Its model identity is immutable after activation; postings and frontier advance only +through snapshot-atomic MDT commits within that namespace. + +> **The posting block.** Instead of one MDT record per posting, the index packs +> ~1–4K vectors into a single MDT record laid out column-wise (structure-of-arrays), keyed +> so that one IVF cluster forms one contiguous, prefix-scannable key range. This reduces MDT +> record count by roughly three orders of magnitude, turns "scan a cluster" into a single +> contiguous range read, and lets a query touch only the columns a given scan pass needs. + +The base table remains the source of truth for exact vector values. The MDT stores only +routing, pruning, and approximate-scoring metadata; final ranking always reads exact vectors +from the base table. + +Artifacted measurements on a **1-billion-row, 128-dimensional table** show approximate-only +recall@10 of 0.822, 0.857, and 0.871 at `nprobe=16`, `32`, and `64`; exact reranking reaches +0.960 at `nprobe=32` with `refineFactor=50` (Appendix A). These modes serve different goals: +approximate-only provides the latency floor, while exact reranking is the recommended +quality mode. + +--- + +## 1. Goals and Non-Goals + +### 1.1 Goals + +1. Keep authoritative vector values in a top-level base-table `VECTOR(D[, elementType])` column. +2. Store the vector index in the MDT, maintained by Hudi metadata-table commits, compaction, + and cleaning — no hidden or generated columns in base-table files. +3. Make candidate discovery cheap and targeted: prune to requested table partitions, probe a few + clusters, scan contiguous key ranges, and score compressed codes with a provable pruning + bound. +4. Make results trustworthy: approximate math selects candidates; **exact** distance on + base-table vectors ranks them. +5. Stay transactionally consistent: snapshot-pinned reads, correct behavior under inserts, + updates, deletes, and clustering. +6. Be engine-neutral in design; Spark is the first implementation. +7. Maintain the index incrementally (no global rebuild for normal churn) and support + versioned, zero-downtime rebuilds. + +### 1.2 Non-Goals (initial landing) + +- ANN families beyond IVF + RaBitQ (e.g. HNSW, DiskANN). +- Filtered search (arbitrary predicate + kNN) as a first-class planned operation. +- Time-travel-consistent index reads for historical snapshots. +- Native non-Spark generation construction, GPU encoding, and workload-specific auto-tuning. + +### 1.3 Alternatives considered + +- **One index record per vector** is simple but creates billions of MDT records and excessive + write, compaction, and scan amplification; posting blocks preserve MDT ownership while + amortizing that overhead. +- **Dedicated index files in the table** permit specialized layouts but introduce a second + commit, cleaning, and snapshot protocol. MDT records reuse Hudi's existing transaction and + table-service machinery. +- **External sidecar indexes or vector databases** may offer richer serving features but lose + atomic Hudi snapshot semantics and require another storage system. They remain valid when + independent serving infrastructure is desired. +- **Native ANN libraries** improve local kernels but do not define durable object-store layout, + multi-writer maintenance, or snapshot visibility. They may be used behind the interfaces in + this RFC without changing the persisted contract. + +--- + +## Limitations + +The first implementation deliberately fails closed or falls back when it cannot prove the +following contracts: + +- **Vector schema evolution.** Changing the indexed vector's dimension or element type makes + the active generation incompatible. Existing-index maintenance and indexed queries fail + closed after such a change; rebuilding or recreating the index establishes and atomically + activates a compatible generation. This RFC does not claim transparent online migration + across incompatible vector schemas. +- **Filtered ANN.** The initial implementation is intended to support partition pruning: posting + dictionaries preserve partition paths so the query path can exclude postings outside the + requested table partitions before candidate-heap selection and exact reranking. This produces + partition-local top-K rather than filtering a global top-K after search. Arbitrary + predicate-plus-kNN planning over non-partition columns is not part of the initial implementation. +- **Index quality.** IVF quality depends on the training sample and corpus geometry. A fixed + seed makes fitting repeatable for fixed inputs and partitioning, but does not make centroids + invariant to changed file/RDD partition layouts. Recall must therefore be measured for each + built generation. +- **Local incremental rebalancing.** LIRE split/merge is design-specified but not part of the + first implementation. Until it lands, sustained skew or centroid drift is corrected by a + full generation rebuild and atomic activation. +- **Maintenance scale evidence.** Bootstrap and query paths are measured at one billion rows. + Incremental COW/MoR mutation, compaction/clustering relocation, and multi-writer races require + the test evidence in §10 before their implementations are declared complete. +- **MoR exact-fetch cost.** Log-resident finalists are resolved by key through the pinned + merged file slice. This preserves correctness but can cost more than base-file positional + fetch and requires explicit scale measurement. + +--- + +## 2. Architecture + + + +The design splits responsibilities the way Hudi already does between the data table and the +metadata table: + +```text +DATA TABLE (parquet/orc) METADATA TABLE (vector_index partition) + authoritative vectors + payload ←── the index: centroids, quantizer, posting blocks, + read only for final re-ranking cluster manifests, generation manifest + read for candidate generation +``` + +### 2.1 Design principles + +- **Correct before optimized.** Delta postings and RLI arbitration make every completed update + immediately discoverable and prevent stale versions from being served before any table + service runs. Exact reranking resolves MoR log-resident finalists through the pinned merged + file slice; compaction may reduce that additional read cost but is never a prerequisite for + candidate visibility, exact materialization, or stale-version suppression. +- **Side-effect-free queries.** The query path never writes the MDT or data table. Workload + signals such as log-resident finalist count, stale-candidate crowding, and fetch-key mismatch + travel only through metrics. Maintenance may consume an externally aggregated, decayed + snapshot of those signals and must remain correct when it is absent. +- **One pinned view.** MDT, RLI, file-slice, base-table, routing, and cache reads for a query use + one pinned snapshot and one ACTIVE generation. +- **Derived state is replaceable.** The data table remains authoritative. Index artifacts may + be compacted, locally rebalanced, rebuilt, or retired without changing logical table data. + +Each vector index is one MDT partition. RFC-109 adds no table properties, common writer- +dispatch changes, timeline-semantics changes, or behavior visible to non-vector readers or +writers. Every consistency mechanism is either a record in the vector-index MDT partition or +logic in the RFC-owned vector indexer and query planner. Creating an index: + +```sql +CREATE INDEX embedding_idx +ON products +USING VECTOR (embedding) +OPTIONS ( + 'vector.metric' = 'cosine', + 'vector.quantizer' = 'IVF_RABITQ', + 'vector.num_clusters'= '4096' +); +``` + +creates: + +```text +.hoodie/metadata/vector_index_embedding_idx/ +``` + +and does not add generated columns to the base-table schema. RFC-109 consumes rather than +redefines the RFC-99 vector contract: the source must be a top-level Hudi +`VECTOR(D[, elementType])`. The table schema is authoritative for `D` and element type; +index definitions and generation manifests repeat them only for integrity validation. + +The current RFC-99 storage backing is fixed-width bytes: Avro `FIXED` and Parquet +`FIXED_LEN_BYTE_ARRAY(D × elementWidth)`. Engine adapters expose idiomatic values—Spark uses +an annotated `ArrayType(FloatType|DoubleType|ByteType)`—and convert at the storage boundary. +This fixed width also avoids Parquet LIST repetition-level traversal during positional exact +fetch. A plain `ARRAY<FLOAT>` is not implicitly indexable and requires explicit migration or +backfill to `VECTOR(D)`; index creation neither reinterprets nor rewrites it. + +The query path uses the MDT first to discover candidates, then reads base-table vectors for +exact re-ranking: + +```text +query vector + → compare to centroids, pick nprobe clusters (in-memory, ms) + → MDT prefix-scan those clusters' posting blocks (targeted range reads) + → two-pass RaBitQ scoring, keep refineFactor·K best (bit math + error bounds) + → validate candidate freshness via Record Level Index (batched point lookups) + → fetch ONLY those rows from the base table by position (page-level reads) Review Comment: @chrevanthreddy may take up the follow up.. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
