hudi-agent commented on code in PR #19309: URL: https://github.com/apache/hudi/pull/19309#discussion_r3682418882
########## rfc/rfc-109/rfc-109.md: ########## @@ -0,0 +1,714 @@ +<!-- + 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) +- [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. Benchmark Evidence, Rollout, and MVP Scope](#11-benchmark-evidence-rollout-and-mvp-scope) +- [12. References](#12-references) + +--- + +## 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: + +> **The posting block.** Instead of one MDT record per indexed vector, 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.824, 0.843, and 0.845 at `nprobe=16`, `32`, and `64`; exact reranking reaches +0.983 at `nprobe=32` with `refineFactor=50` (§11). 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: probe a few clusters, scan contiguous key + ranges, score on 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. + +--- + +## 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 +``` + +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: 🤖 The exact re-rank fetches candidates by stored `rowPosition`, but §6.3 only re-resolves *moved* keys via RLI — and RLI returns a file group, not a position. A data-table compaction or clustering that rewrites a file group in place shifts every row's position without changing its RLI location, so a query on a pinned snapshot whose MDT locators haven't been refreshed yet (§7.2 lags behind) could positionally read the wrong base row and silently mis-rank. Could you specify that the positional fetch validates the fetched row's `_hoodie_record_key` against the finalist key (with key-based fallback on mismatch), and how a fresh position is derived after RLI re-resolution? @yihua does this positional-vs-RLI-location gap read as a real correctness risk to you? <sub><i>⚠️ AI-generated; verify before applying. React 👍/👎 to flag quality.</i></sub> -- 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]
