chrevanthreddy commented on code in PR #19309: URL: https://github.com/apache/hudi/pull/19309#discussion_r3677431349
########## rfc/rfc-109/rfc-109.md: ########## @@ -0,0 +1,594 @@ +<!-- + 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 and Consistency](#9-correctness-and-consistency) +- [10. Test Plan](#10-test-plan) +- [11. Rollout and MVP Scope](#11-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 (`ARRAY<FLOAT>` produced by ML models) next to +their business data, 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. + +Prototype measurements on a **1-billion-row, 128-dimensional table** show exact-reranked +recall@10 = 0.985 at nprobe=128 with query latency in low single-digit seconds on a modest +Spark cluster, versus ~15s for brute force. + +--- + +## 1. Goals and Non-Goals + +### 1.1 Goals + +1. Keep authoritative vector values in the base table (`ARRAY<FLOAT>` / `VECTOR(D)` 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. Review Comment: Addressed in §5.3–§5.5 and §9.1 in commit `b902152fa6`. Bootstrap and full rebuild are Spark-only in v1. The incremental contract is separated from generation construction: routing, encoding, vector-record construction, and freshness-marker emission belong to the common metadata-writer index hook, so feature-aware Spark, Flink, and Java writers can maintain the active generation without implementing Spark ML/KMeans. The common batch metadata dispatch invokes each enabled indexer for every data commit rather than only when another index produced records. The vector hook therefore emits `F|generation|dataInstant` even when the commit changes no vector rows; that marker is the non-empty vector-index update and is committed atomically with any posting deltas. A writer that does not understand the vector partition keeps the standard MDT layer-2 skip behavior rather than failing the table write. Its commit leaves a marker gap, which the vector planner detects before serving the index; policy then fails, warns, or uses an exact fallback until catch-up replay repairs the gap. Native Flink/Java bootstrap and query execution remain future work, while Flink/Java-written tables can use the Spark bootstrap/rebuild job in v1. -- 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]
