apurtell opened a new pull request, #2631: URL: https://github.com/apache/phoenix/pull/2631
Design document: https://gist.github.com/apurtell/e4668cddf949c43955d4a919489d4228 --- ## Summary PHOENIX-8009 adds Hierarchical Navigable Small World (HNSW) graph indexes as an approximate nearest neighbor search algorithm alongside the Inverted File (IVF) indexes introduced in PHOENIX-7998. While IVF partitions vector spaces into Voronoi cells requiring periodic centroid retraining, HNSW proximity graphs provide higher recall at comparable query latencies without retraining. This design targets recall-sensitive workloads, frequent updates, and vector collections whose regional graphs reside in RegionServer memory. The implementation builds on the PHOENIX-7998 infrastructure: relational vector types, distance functions, `CREATE VECTOR INDEX` grammar, catalog metadata, `IndexMaintainer`, `IndexRegionObserver`, server-side bounded Top-N ranking, and cost-based query optimization. The key capabilities provided by this implementation include: - **Embedded JVector Engine:** JVector 4.0.1, a pure Java graph search library combining HNSW hierarchical layers with Vamana pruning, embedded in the RegionServer with Panama SIMD kernels on newer JDKs. - **Per-Region Graph Indexes:** Each data table region owns its index. Immutable graph segments are built from the region's own rows, and an in-memory mutable graph absorbs committed changes between flushes. - **MOB Segment Storage:** Each segment is one self-describing row of the index table whose payload is an HBase Medium Object (MOB) cell, kept out of compaction rewrites. - **Off-Heap Materialization:** Segments are materialized into direct buffers under a RegionServer-wide byte budget with lock-free LRU eviction and transparent reload. - **Native Quantization:** Full-precision (`NONE`), scalar NVQ (`SQ8`), and product quantization (`PQ`) codecs, trained per segment. - **Post-Commit Graph Maintenance:** Row changes reach the region's graph only after the data table batch commits, with no remote calls under row locks. - **Delta Segments and Ratio-Triggered Rebuilds:** Flushes write only the changed rows as delta segments. A full rebuild runs when the deltas reach a fixed share of the base, bounding the amortized cost per change. - **Durability Through Replay:** Committed rows are durable in the data table, and a region replays recent changes when it opens. - **Candidate-Restricted Data Table Scans:** Queries scan the data table, restricted per region to the candidate rows its graph finds, and are ranked by exact distance through the existing server side top-N. - **Coexistence with IVF:** IVF and HNSW indexes can share a table and a column. Every IVF hook is gated so HNSW indexes bypass centroid training, scorecards, generational rebuilds, and index row generation. - **Verification and Repair Tooling:** `IndexFsckTool` verifies HNSW indexes row by row against their segments, checks segment rows and graphs, inspects segments, and repairs by removing bad segments and rebuilding regions on their servers. - **Shared Compatibility Gating:** HNSW indexes use the PHOENIX-7998 vector version check and catalog upgrade. --- ## Architecture and System Components ```mermaid flowchart LR subgraph Client["Client Layer"] direction TB QC["Query Compiler<br/>& Cost Optimizer"]:::client HSP["HnswScanPlan"]:::client CM["Client Merge &<br/>Global Top-K"]:::client QC --> HSP HSP -.-> CM end subgraph RS["RegionServer Execution Layer"] direction TB subgraph ReadPath["Read Path"] direction TB PSO["IndexRegionObserver<br/>(preScannerOpen)"]:::rs HIM_R["HnswIndexManager<br/>(search)"]:::rs JV["Off-Heap JVector Graph Search<br/>(Direct Buffers, SIMD)"]:::rs MRF["MultiRowRangeFilter<br/>(Candidate Restriction)"]:::rs TOPN["Server-Side Top-N<br/>(Exact Distance Re-Ranking)"]:::rs PSO --> HIM_R HIM_R --> JV JV --> MRF MRF --> TOPN end subgraph WritePath["Write Path"] direction TB PBM["IndexRegionObserver<br/>(postBatchMutateIndispensably)"]:::rs IMG["In-Memory Mutable Graph<br/>(OnHeapGraphIndex)"]:::rs FLUSH["Flush Coordinator<br/>(Delta Segment / Full Rebuild)"]:::rs REP["Startup Replay Engine"]:::rs PBM --> IMG IMG --> FLUSH REP --> IMG end end subgraph Storage["Storage Layer"] direction TB BDT[("HBase Base Data Table<br/>(Primary Keys & Vectors)")]:::storage HIT[("HNSW Index Table<br/>(Inline Metadata: E, N, B, T)")]:::storage MOB[("HBase MOB Storage<br/>(Graph Payload: P)")]:::storage CAT[("SYSTEM.CATALOG<br/>(HNSW Metadata 66-70)")]:::storage end %% Cross-layer interactions HSP -->|Scan RPC + Query Vector| PSO TOPN -->|Filtered Candidates| CM QC -.->|Catalog Metadata| CAT TOPN -->|Read Candidate Rows| BDT PBM -->|Post-Commit Vectors| IMG FLUSH -->|Write Deltas / Bases| HIT FLUSH -->|Store MOB Payloads| MOB HIM_R -->|Materialize Segments| MOB REP -->|Scan Recent Mutations| BDT ``` The principal components are: | Component | Package | Role | |---|---|---| | `HnswSegment` | `org.apache.phoenix.hbase.index.hnsw` | Segment codec for constructing, serializing to MOB index rows, discovering, and searching JVector graphs. | | `HnswOffheapAllocator` | `org.apache.phoenix.hbase.index.hnsw` | RegionServer-wide off-heap direct memory budget with lock-free LRU eviction. | | `HnswIndexManager` | `org.apache.phoenix.hbase.index.vector` | Manages segment stacks, deletion masks, in-memory mutable graphs, flushes, rebuilds, and recovery replay per data region. | | `VectorIndexManager` | `org.apache.phoenix.hbase.index.vector` | Coprocessor interface used by `IndexRegionObserver` for HNSW lifecycle management and write operations. | | `HnswScanPlan` | `org.apache.phoenix.execute` | Client execution plan for candidate-restricted base table scans with server-side top-N re-ranking. | | `HnswIndexFsckProvider` | `org.apache.phoenix.mapreduce.index.fsck.hnsw` | `IndexFsckTool` provider for row-level verification, consistency checking, inspection, and offline repair. | --- ## 1. Algorithm Dispatch and Catalog Integration ### JVector Overview and Integration JVector is an embedded pure Java approximate nearest neighbor search engine for high performance vector indexing. Phoenix embeds JVector directly inside the HBase RegionServer process. JVector adopts the multi-layer hierarchy of Hierarchical Navigable Small World (HNSW) graphs. Analogous to a probabilistic skiplist extended to metric spaces, HNSW constructs multiple layers of proximity graphs. The top layers contain a small, sparse subset of vectors connected by long range links that span wide distances across the vector manifold, facilitating logarithmic greedy routing toward the target neighborhood. Successive layers grow progressively denser down to layer 0, which encompasses the entire dataset. During graph navigation, search begins at a fixed entry point in the highest layer, greedily tracks the local optimum, and descends layer by layer to seed fine grained local exploration in the base layer. JVector augments HNSW construction with Vamana edge pruning heuristics. In standard proximity graphs, neighbors of a node often cluster in the same spatial direction, consuming degree capacity without adding exploration power. Vamana edge pruning enforces neighbor diversity through an angular pruning rule, scaled by an `alpha` parameter. This preserves long range shortcut edges across clusters while eliminating redundant parallel paths. The resulting graph maintains high connectivity and recall at significantly lower degree bounds, reducing both traversal latency and memory footprint. To eliminate Java heap overhead and garbage collection pressure, JVector departs from object oriented graph representations in favor of a flat contiguous binary `OnDiskGraphIndex` structure designed for sequential or memory mapped random access via `ByteBufferReader`. Each node's adjacency list, metadata, and optional quantized feature codes reside in contiguous byte slices. Traversal navigates these direct off heap buffers directly without allocating Java objects, isolating graph memory from the JVM garbage collector and improving cache line efficiency. Underlying all graph operations are distance calculations, which dominate construction and traversal compute budgets. JVector leverages the Java Panama Vector API via `VectorizationProvider` packaged in multi-release JARs. On modern JDKs with CPU architecture support (such as AVX-512, AVX2, or ARM Neon), floating point Euclidean, dot product, and cosine operations execute across hardware SIMD vector lanes simultaneously. #### Key JVector Subsystems Used by Phoenix Phoenix integrates JVector through two core components: `HnswSegment` handles segment serialization, off-heap buffering, and search; `HnswIndexManager` coordinates region lifecycle, in-memory buffering, and multi-segment query execution. - **Graph Construction and Mutation:** Segment flushes and rebuilds use `GraphIndexBuilder` to construct immutable graph segments in parallel. Post-commit mutations buffer into an in-memory mutable graph (`OnHeapGraphIndex`), providing immediate read visibility without synchronous disk writes. - **Off-Heap Storage and Traversal:** Persisted segments are serialized into HBase MOB cells. `HnswSegment` loads segments into off-heap direct buffers via `HnswOffheapAllocator`, traversing them through `OnDiskGraphIndex` and `ByteBufferReader` with lock-free LRU cache management. - **Search Execution:** Beam search runs via `GraphSearcher` across immutable segments and active in-memory graphs. Distance evaluation is driven by `SearchScoreProvider`. Phoenix distance metrics map directly to JVector `VectorSimilarityFunction` definitions (`EUCLIDEAN`, `DOT_PRODUCT`, `COSINE`). - **Feature and Quantization Encoding:** Quantization uses `NVQuantization` for 8-bit non-uniform scalar quantization (`SQ8`) and `ProductQuantization` for sub-vector compression (`PQ`). Under `PQ`, JVector packs neighbor codes directly into node adjacency lists (`FusedPQ`), maximizing memory locality during graph traversal. - **Ordinal-to-Key Translation:** JVector identifies nodes by dense integer ordinals (`0 <= ordinal < N`). Phoenix maps ordinals to base table primary keys by appending a dense key trailer (`[count (int)] ([key length (int)][key])*`) to the serialized segment payload. Candidate ordinals returned by graph traversal are translated to row keys to drive data table scans. #### Quantization Modes Phoenix supports three quantization configurations tailored to memory density and recall requirements: - **Full Precision (`QUANTIZATION = 'NONE'`):** Raw 32-bit floating-point vectors are stored inline with node adjacency lists. Graph traversal evaluates exact similarities using `DefaultSearchScoreProvider.exact`. This mode provides lossless recall at 4 bytes per dimension per vector. - **Scalar Non-Uniform Quantization (`QUANTIZATION = 'SQ8'`):** An 8-bit non-uniform scalar quantization model (`NVQuantization`) is trained over segment vectors during construction, mapping each dimension to one byte. Traversal calculates distances against quantized vectors, achieving ~4x compression with low training overhead and minimal recall loss (>98% relative recall). - **Product Quantization with Fused Adjacency (`QUANTIZATION = 'PQ'`):** Vectors are partitioned into $m$ sub-vectors (`PQ_SEGMENTS`), each quantized to 256 centroids via k-means clustering. Under `FusedPQ`, quantized neighbor codes are embedded directly into node adjacency lists, eliminating secondary lookups during graph walks. Search runs in two phases: `FusedPQ` drives beam traversal, and candidate ordinals are refined using `NVQ_VECTORS` before returning candidates to Phoenix. If a segment contains fewer than 256 vectors, it automatically defaults to `NONE`. Because candidate rows retrieved from the base data table are re-ranked using exact Phoenix distance expressions before returning results to the client, quantization approximations only affect candidate graph routing, not the final distance ranking. #### Parameter Mapping from Phoenix DDL to JVector The parameters defined in Phoenix DDL (`CREATE VECTOR INDEX ... WITH (...)`) map directly to JVector's constructor and runtime tuning knobs: | Phoenix Parameter | JVector Equivalent | Role in JVector Architecture | |---|---|---| | `M` | `int maxDegree` | Maximum outgoing edge degree per node across graph layers. Controls connectivity, graph density, and per-node adjacency storage size. | | `EF_CONSTRUCTION` | `int efConstruction` | Size of the dynamic priority queue (beam width) maintained during index construction. Higher values search deeper candidate paths to find optimal neighbors when wiring nodes. | | `ALPHA` | `float alpha` | Vamana neighbor diversity pruning factor ($\alpha \ge 1.0$). When selecting edges from candidate neighbors, an edge to candidate $y$ is rejected if an edge already exists to $x$ such that $d(x, y) < \alpha \cdot d(query, y)$. An $\alpha > 1.0$ enforces angular diversity and creates long-range routing shortcuts across the graph. | | `QUANTIZATION` | `FeatureId` / Codec | Selects `NONE` (uncompressed), `SQ8` (`NVQuantization` / `NVQ`), or `PQ` (`ProductQuantization` / `FusedPQ`). | | `PQ_SEGMENTS` | `int subvectorCount` | Number of sub-spaces for Product Quantization, passed to `ProductQuantization.compute(vectors, pqSegments, 256, true)`. | | `NEIGHBOR_OVERFLOW` (internal) | `float neighborOverflow` | Fixed at `1.2f` in Phoenix. Permits up to $1.2 \times M$ temporary neighbor connections during node insertion before triggering Vamana pruning. | | `HNSW_EF_SEARCH` (hint / config) | `int efSearch` | Dynamic candidate queue depth during `GraphSearcher.search(...)`. Balances traversal latency against candidate recall. | | `metric` | `VectorSimilarityFunction` | Maps Phoenix SQL distance metrics: `COSINE` $\to$ `VectorSimilarityFunction.COSINE`, `L2` $\to$ `VectorSimilarityFunction.EUCLIDEAN`, `INNER_PRODUCT` $\to$ `VectorSimilarityFunction.DOT_PRODUCT`. | ### DDL and Parameters HNSW indexes use the same `CREATE VECTOR INDEX` statement as IVF indexes, selecting the algorithm and its build parameters in the `WITH` clause: ```sql CREATE VECTOR INDEX idx_embeddings ON documents (embedding) WITH (algorithm='HNSW', metric='COSINE', M=32, ef_construction=200, quantization='PQ', pq_segments=96); ``` | Parameter | Range | Default | Meaning | |---|---|---|---| | `M` | 4 to 64 | 16 | Maximum node degree. | | `EF_CONSTRUCTION` | 16 to 512 | 100 | Construction beam width. | | `ALPHA` | 1.0 to 2.0 | 1.2 | Vamana neighbor diversity factor. | | `QUANTIZATION` | `NONE`, `SQ8`, `PQ` | `NONE` | Segment vector codec. `SQ8` requires single-precision vectors. | | `PQ_SEGMENTS` | 1 to 256, dividing the dimension | — | Required if and only if `QUANTIZATION = 'PQ'`. | DDL processing and validation adhere to the following design constraints: - **Parameter Extraction:** `CreateIndexStatement` strips vector configuration options from statement properties to prevent them from leaking into HBase table descriptors. - **Unified Validation:** `CreateIndexCompiler.verifyVectorIndex` validates parameter ranges, quantization constraints, and algorithm compatibility, resolves defaults, and instantiates the `PTable.VectorIndex` descriptor. - **Compatibility Restrictions:** Cross-algorithm parameters (e.g., `LISTS` on HNSW, `M` on IVF) are rejected with `VECTOR_ALGORITHM_PARAM_MISMATCH`. Covered columns (`INCLUDE`) are rejected with `HNSW_INCLUDE_NOT_SUPPORTED` because segments do not store covered relational data. `CONSISTENCY = EVENTUAL` is rejected with `HNSW_EVENTUAL_CONSISTENCY_NOT_SUPPORTED` because HNSW maintenance executes post-commit on the data table. Tables defining `ROW_TIMESTAMP` are rejected with `HNSW_ROW_TIMESTAMP_NOT_SUPPORTED` because startup replay requires monotonically increasing commit timestamps. Transactional tables remain unsupported. - **Server Metadata Validation:** `MetaDataEndpointImpl.validateVectorIndexMetadata` verifies HNSW parameter validity on catalog updates while bypassing IVF centroid and sampling validation. ### Catalog Metadata The five HNSW fields are persisted in new `SYSTEM.CATALOG` columns (`VECTOR_HNSW_M`, `VECTOR_HNSW_EF_CONSTRUCTION`, `VECTOR_HNSW_ALPHA`, `VECTOR_QUANTIZATION_TYPE`, `VECTOR_PQ_SEGMENTS`) and serialized as optional `PTable.proto` fields 66–70. `PTable` keeps the PHOENIX-7998 flat accessors and adds one flat accessor per HNSW field. The default methods `getVectorIndex()` and `getVectorIndexType()` assemble an immutable view of the build parameters for the HNSW classes that consume them. `isVectorIndex()` retains its PHOENIX-7998 meaning, `getIndexType() == VECTOR_GLOBAL`. ### Physical Index Layout HNSW index tables hold graph segments, not per-row index entries. They keep the data table's primary key layout, `[Salt Byte (opt)] [Tenant ID (opt)] [Base Table Primary Key]`, with no `_CENTROID_ID` column, and their column families are created with `IS_MOB=true` and `MOB_THRESHOLD=1024`. A new HNSW index starts in `BUILDING` state and becomes `ACTIVE` once `IndexTool` has built every region. --- ## 2. Graph Segments and Off-Heap Storage ### Segment Row Layout A segment is one row of the HNSW index table: ``` +---------------------------------------------------------------------------------------+ | Segment Row Key | | [Data Region Start Key] [Segment Time (8B, big endian)] | +---------------------------------------------------------------------------------------+ | Column Family Values | | - P: Payload (MOB) = [JVector OnDiskGraphIndex][Ordinal->Row Key Map][Length][Magic] | | - E: Region End Key (inline) | | - N: Vector Count (inline) | | - B: Base Segment Time (inline, delta segments only) | | - T: Tombstoned Row Keys (delta segments only) | +---------------------------------------------------------------------------------------+ ``` Segment rows are keyed by data region boundaries and build timestamps, making them independent of index table region splits and RegionServer assignments. `HnswSegment.list` scans only inline metadata cells (`E`, `N`, and `B`), discovering segment topology without reading MOB payloads. Malformed rows (invalid key lengths or malformed qualifier widths) are bypassed during scan discovery, logged for `IndexFsckTool` reporting, and purged during repair. Dropping an index drops the underlying HBase table and MOB files. HBase snapshots capture both segment rows and referenced MOB payloads. ### Segment Codec and Quantization `HnswSegment.build` constructs each graph using JVector's parallel `GraphIndexBuilder` with configured parameters (`M`, `EF_CONSTRUCTION`, `ALPHA`), building hierarchical layers with refinement passes. Vectors are encoded according to the selected codec: | Quantization | Segment Contents | Search Scoring | |---|---|---| | `NONE` | Full-precision vectors inline. | Exact inline scores. | | `SQ8` | NVQ codes only (8 bits per dimension). | NVQ scores. | | `PQ` | Fused PQ codes plus NVQ codes. | Fused PQ approximation reranked by NVQ. | Quantized segments store only encoded representations. Segment rebuilds reread vector data from the base table, maintaining minimal off-heap memory footprints. If a `PQ` segment contains fewer than 256 vectors—the minimum needed to train 256 centroids per subspace—it falls back to storing full-precision vectors (`NONE`). ### Off-Heap Materialization `HnswSegment.open` reads the payload cell (with transparent MOB resolution), validates the trailer magic, decodes the row key mapping into heap memory, and buffers the graph into direct memory allocated via `HnswOffheapAllocator`. JVector traverses graphs through direct `ByteBufferReader` instances over independent buffer duplicates, ensuring concurrent queries do not contend on buffer positions. Off-heap memory allocation is bounded globally per RegionServer by `phoenix.vector.hnsw.offheap.max.bytes` (default 2 GB). Allocations exceeding available headroom evict segments via a lock-free LRU policy. Eviction callbacks execute outside allocator synchronization locks. An evicted segment drops its graph reference, and subsequent queries transparently reload it. Concurrently executing queries retain references to their active segment buffers until search completion. --- ## 3. Distributed Write Pipeline The region's graph is updated from committed row changes by `IndexRegionObserver`: ```mermaid sequenceDiagram autonumber actor Client participant IRO as IndexRegionObserver participant Region as HBase Region / WAL participant Ctx as BatchMutateContext participant HIM as HnswIndexManager Client->>+IRO: Upsert / Delete Batch Note over IRO,HIM: Phase 1: preBatchMutate() IRO->>HIM: Pre-warm centroids and open manager<br/>(catalog reads before row locks) IRO->>Region: Lock rows IRO->>Ctx: prepareIndexMutations() Note over Ctx: • IVF and Global maintainers: generate index rows<br/>• HNSW maintainers: queue (current, next) row states Note over IRO,Region: Atomic Commit Phase IRO->>Region: Atomic Data Table Mutation (+ IVF / global index rows) Region-->>IRO: Batch status (Success / Failure) Note over IRO,HIM: Phase 2: postBatchMutateIndispensably() alt Batch Succeeded loop For each queued row state IRO->>HIM: onMutation(current, next) Note over HIM: Update mutable graph and mask stale ordinals in segments end else Batch Failed IRO->>Ctx: Discard queue (graph untouched) end IRO->>Region: Unlock rows (preserves commit-order application) IRO-->>-Client: Return mutation result ``` ### Write Path Mechanics HNSW maintains vectors in memory and off-heap rather than writing per-mutation index table rows. `IndexMaintainer` serializes compiled vector expressions (column references or functional expressions like `BSON_VECTOR_VALUE(...)`) alongside source column dependencies (`ServerCachingService.proto` fields 39 and 40), allowing RegionServers to extract vector values during mutation processing. Because graph maintenance occurs on RegionServers, HNSW maintainers are distributed upon index creation, including during the `BUILDING` state, capturing writes concurrent with initial builds. To avoid remote catalog and table metadata lookups under row locks, `HnswIndexManager` instances are pre-warmed during `preBatchMutate()` before lock acquisition. Graph updates execute within `postBatchMutateIndispensably()` after the base data table mutation commits. Because updates execute before row locks are released, concurrent mutations apply to the graph in commit order. If a batch fails, queued mutations are discarded and index state remains unmodified. HNSW indexes bypass HBase KeyValue index mutation generation; `IndexMaintainer.generateIndexMutationsForRow()` and IVF scorecard metrics ignore HNSW maintainers, preserving existing mutation pipelines. During mutation processing, `HnswIndexManager.onMutation` evaluates previous and new vector states: - If the vector value is unchanged, the mutation is skipped. - If the vector value changed, the new vector is inserted into the in-memory mutable graph, and previous segment ordinals for the row key are masked out. - For row deletions, the row key is marked tombstoned in the mutable graph and masked in active segments. - If a vector cannot be parsed, it is treated as null to avoid aborting mutations post-commit. --- ## 4. Flush, Delta Segments, and Rebuild Graph indexes require random access for incremental edge rewiring and quantization maintenance, making direct in-place updates impractical on immutable storage. Phoenix decouples writes from immutable segment storage by buffering mutations in an in-memory graph and flushing immutable segments through the HBase region lifecycle. Mutations buffer in an active in-memory graph (`OnHeapGraphIndex`), while persisted segments remain immutable disk graphs stored in HBase MOB cells. Updates and deletions do not rewrite existing segment files; instead, they record tombstone bitmasks that filter out stale ordinals during graph traversal. Query execution traverses the active in-memory graph, any in-flight flush snapshot, and stacked delta segments down to the base segment in newest-first order. When delta segment counts or row churn exceed configured limits, a background rebuild consolidates the stack into a fresh base segment. ### Mutable Graph and Search Sources Each `HnswIndexManager` exposes an immutable `State` snapshot that query operations traverse concurrently without lock contention: 1. Active mutable graph (`OnHeapGraphIndex`) backed by a concurrent map-based vector store. 2. Swapped mutable graph during active flushes, excluding mutations committed after snapshot cutover. 3. Persisted segments ordered newest to oldest, consisting of delta segments stacked above a base segment, with stale ordinals excluded via JVector accept bitsets. Search queries traverse sources in newest-to-oldest order. The first candidate entry encountered for a row key takes precedence, ensuring recent mutations shadow older versions. If all nodes in a mutable graph are deleted, the graph is reset to prevent traversal from invalid entry points. ### Flush Policy A flush triggers when the mutable graph accumulates `FLUSH_THRESHOLD` (default 10,000) row mutations (upserts and deletes). Flushes are threshold-driven rather than time-based, serving primarily to bound heap utilization; unpersisted updates are recovered via startup replay. ```mermaid flowchart TD THRESH["Mutable graph reaches FLUSH_THRESHOLD<br/>(10,000 changed rows)"] SWAP["Swap in empty mutable graph<br/>(record swap timestamp)"] CHECK{"Delta segment eligible?<br/>• Exactly 1 stack covering region<br/>• Fewer than MAX_DELTAS (4) deltas<br/>• Total delta churn < REBUILD_RATIO (1/4) of base"} DELTA["Write Delta Segment<br/>• Swapped out graph rows<br/>• Deleted keys stored in T cell<br/>• Reads no region rows"] CUT_DELTA["Cutover:<br/>Delta appended to stack"] REBUILD["Full Rebuild (Background Thread)<br/>• Scan region rows (authoritative)<br/>• Apply swapped out graph over scan<br/>• Build and write new base segment"] CUT_REBUILD["Cutover:<br/>New base replaces stack;<br/>superseded bases and deltas retired"] MASK["Mask rows changed since swap<br/>in the new segment"] THRESH --> SWAP SWAP --> CHECK CHECK -- Yes --> DELTA DELTA --> CUT_DELTA CUT_DELTA --> MASK CHECK -- No --> REBUILD REBUILD --> CUT_REBUILD CUT_REBUILD --> MASK ``` ### Flush and Rebuild Architecture - **Delta Segments Without Base Scans:** Mutations committed prior to snapshot swap reside entirely within the swapped-out graph under manager monitor synchronization. Generating delta segments requires no base table scan, keeping write overhead strictly proportional to mutation volume. - **Bounded Amortized Overhead:** Full rebuilds trigger at most once every `REBUILD_RATIO · N` changes, bounding amortized write costs to $O(\log N)$ and limiting query evaluation to at most `MAX_DELTAS + 1` (default 5) segments per stack. - **Authoritative Table Rebuilds:** Full rebuilds scan the base table directly to incorporate committed vectors, reflect purged deletes from major compactions, and retrain PQ quantization codebooks against current vector distributions. - **Deterministic Retry Handling:** Failed flushes retry automatically after `RETRY_DELAY_MS` (60 seconds) using the preserved swapped snapshot. Rebuild execution is serialized across a single RegionServer-wide thread to cap memory usage during full region vector scans. - **Rebuild Consolidation Over In-Place Merges:** Delta consolidation avoids incremental graph merging. Because quantized segments omit raw vector data, merging would still require base table scans to recover full vectors, while increasing memory pressure and relying on experimental on-disk compaction routines. ### Durability and Recovery Replay Graph state is persisted across base segments and stacked delta segments. Mutations in the in-memory graph that have not yet been flushed when a region crashes or reassigns are recovered through region replay on startup. When an `HnswIndexManager` opens, it scans the base data region for mutations committed since the newest segment timestamp, minus a safety lookback margin (`REPLAY_MARGIN_MS`, defaulting to 60 seconds). A raw key-only scan encompassing delete markers reads recent row mutations and applies current row states idempotently to the in-memory graph. Tombstones and updated keys in newer delta segments mask older segment entries. Replay relies on cell timestamps reflecting actual commit times. Because Phoenix rejects SCN-based writes on indexed tables and disallows `ROW_TIMESTAMP` columns on HNSW-indexed tables, timestamp monotonicity is preserved. --- ## 5. Region Lifecycle and Index Population ### Segment Discovery Segment lifecycle management is decoupled from HBase region splits and merges to avoid synchronous graph file rewriting during region transitions. When an `HnswIndexManager` opens, it scans the index table to discover and reconcile segments covering the region's `[startKey, endKey)` boundaries. - **Base Coverage:** Segment boundaries are determined by base segments. Delta segments are loaded only when their associated base segment is selected. - **Shadowing:** Overlapping base segments are processed newest to oldest. Older base segments (and associated deltas) are skipped if their key ranges within the region are fully covered by newer segments. - **Boundary Filtering:** When an inherited segment spans beyond the current region's boundaries (e.g., following a region split), candidate ordinals outside the region's `[startKey, endKey)` range are masked during search using JVector accept bitsets, preventing split daughters from returning sibling keys. | Lifecycle Scenario | Segments Discovered on Open | Query Behavior | |---|---|---| | **Normal Open / Move / Restart / Snapshot** | The region's existing base segment and delta stack. | Direct search over the region's stack. | | **Split Daughter (before rebuild)** | The parent region's wider segment stack. | Searches the parent stack, masking out ordinals outside the daughter's key boundaries. | | **Split Daughter (after rebuild)** | The daughter's newly built base segment. | Searches only the daughter's stack; the parent segment is retired once all daughters rebuild. | | **Merged Region** | The overlapping segment stacks from all merged inputs. | Searches across all input stacks until an immediate rebuild consolidates them. | ### Rebuild and Segment Retirement If discovered segments do not form a single stack covering the region's exact boundaries, the manager triggers an immediate background rebuild. This resolves split daughters, merged regions, coverage gaps, and uninitialized regions on `ACTIVE` indexes. Queries continue serving from existing segments until rebuild cutover. An index in `BUILDING` state with no segments awaits population by `IndexTool`. Following cutover to a new base segment, obsolete segments are retired: base segments whose ranges are entirely covered by newer bases are deleted alongside their deltas, as well as orphaned deltas. Parent segments from splits are retired once all daughter regions complete rebuilds. Merged input segments are retired after the merged region finishes its initial rebuild. Secondary region replicas do not execute index maintenance or lifecycle mutations; they consume index state produced by the primary region. ### Population with `IndexTool` `IndexTool` builds HNSW indexes server-side, region by region: ```mermaid sequenceDiagram autonumber actor IT as IndexTool participant IRO as IndexRegionObserver participant Worker as Background Rebuild Worker participant Catalog as Index Table and System Catalog Note over IT,Catalog: 1. Trigger Async Rebuilds Across Data Regions loop For each data region IT->>+IRO: One-row scan carrying HNSW_BUILD = <index> IRO->>Worker: preScannerOpen() triggers background rebuild IRO-->>-IT: Return scan immediately (non-blocking) end Note over Worker,Catalog: 2. Server-Side Graph Construction Worker->>Worker: Scan region data rows and train quantization Worker->>Worker: Build JVector HNSW graph Worker->>Catalog: Write new base segment row (+ MOB payload) Note over IT,Catalog: 3. Poll and Supervise Coverage loop Poll every 30 seconds (timeout after 1 hour) IT->>Catalog: Check for segments covering region range built after run start Catalog-->>IT: Segment coverage status opt Region segment missing IT->>IRO: Re-trigger build scan for missing region end end Note over IT,Catalog: 4. Mark Index Active IT->>Catalog: Mark index ACTIVE in SYSTEM.CATALOG ``` `ALTER INDEX ... REBUILD [ASYNC]` sets the index state to `BUILDING` and delegates graph construction to `IndexTool`. --- ## 6. Query Planning, Optimization, and Execution ### Query Pattern Recognition HNSW indexes support nearest-neighbor queries structured with an ascending distance expression against a constant query vector, bounded by a `LIMIT` clause. Because index tables store graph segments rather than per-row relational postings, query execution scans the base **data table**, routing candidate restriction through RegionServer graph lookups. ### Plan Selection Because HNSW index tables store graph segments and MOB references rather than indexed relational keys, the query optimizer resolves HNSW candidate paths before evaluating uncovered index joins. This prevents routing HNSW plans into semi-join or index-merge execution paths. To qualify for an HNSW plan: - The distance metric in the `ORDER BY` clause must match the index definition. - The distance expression must target the indexed vector column or expression. When selected, the optimizer constructs an `HnswScanPlan` from the base table statement via an HNSW-aware query resolver. The plan targets the base table, passing vector search parameters to RegionServers via scan attributes. ### Server-Side Candidate Restriction Candidate search executes directly on RegionServers within the base table scan path: 1. **Client Plan Configuration:** `HnswScanPlan` computes the candidate budget as `max(ef_search, LIMIT + OFFSET)` and attaches the target index name (`HNSW_SEARCH_INDEX`), candidate count, and serialized query vector (`HNSW_SEARCH_QUERY`) as scan attributes. 2. **Coprocessor Interception:** `IndexRegionObserver.preScannerOpen()` intercepts the scan attributes and delegates to `HnswIndexManager.search()`. 3. **Multi-Source Search:** The manager executes beam searches across active mutable graphs, flush snapshots, and persisted segments, applying deletion masks and key range boundaries. For keys appearing across multiple sources, the newest candidate entry takes precedence. 4. **Scan Restriction:** Candidate row keys are conjoined into the scan filter via a `MultiRowRangeFilter` (wrapped in a `PagingFilter` if paging is enabled). 5. **Data Table Read and Top-N Ranking:** The scan reads candidate rows directly from the base table, evaluating projected columns and ranking candidates through the server-side bounded Top-N pipeline using exact distance expressions. 6. **Client Merge:** The client merges per-region streams into the final global Top-K result set. Projected columns are read directly from base data rows, eliminating secondary index joins. While JVector guides candidate discovery using similarity approximations, final ordering is evaluated with exact Phoenix distance expressions. ### Search Beam Width The search beam width (`ef_search`) defaults to `phoenix.vector.hnsw.ef_search.default` (64) and can be tuned per query using the `HNSW_EF_SEARCH(n)` hint. The candidate count dynamically expands to `LIMIT + OFFSET` whenever that value exceeds `ef_search`. ### Cost-Based Optimization and Plan Ranking The optimizer estimates the cost of an `HnswScanPlan` as the cost of reading candidate rows from the base table using `CostUtil.estimateLookupCost(candidates, dataTable)`, treating in-memory graph traversal as negligible overhead. On non-trivial tables, this cost is substantially lower than a full table scan. When IVF and HNSW indexes coexist on the same table or column, the optimizer evaluates both access paths independently based on cost. In plan ranking, `HnswScanPlan` is classified in the vector tier at lookup rank 0, matching the precedence of covered IVF plans. In `EXPLAIN` output, the scan is annotated with `SERVER HNSW SEARCH <index> (<n> CANDIDATES)` and attributes plan selection to the HNSW index. ### Deterministic Planning Plan selection depends strictly on index definitions, query structure, hints, and cost models without relying on table statistics. --- ## 7. Verification, Inspection, and Repair Tooling HNSW indexes integrate into the `IndexFsckTool` suite (`bin/indexfsck.py`), supporting `verify`, `fsck`, `repair`, and `inspect` operations. Provider dispatch routes HNSW tables to `HnswIndexFsckProvider` based on `VectorIndexType`, extending `GlobalIndexFsckProvider` for table-level validation and iterative repair workflows. Tooling operations execute client-side via Phoenix JDBC, HBase client APIs, MapReduce jobs over data tables, and client-side JVector graph decoders without requiring custom server RPC endpoints. Tooling leverages core engine components directly: - `HnswSegment` handles segment decoding and candidate search. - `HnswIndexManager` exposes methods (`currentSegments`, `replayStartTime`, `segmentsToRetire`) to determine segment discovery, replay boundaries, and retirement policies. - `HnswRegionSegments` manages multi-segment stack traversal, ordinal-to-key resolution, and region boundary filtering. ### Row-Level Verification Because HNSW indexes do not maintain individual index table rows per base row, `IndexTool -v` and `-fi` flags are rejected, directing verification to `indexfsck.py verify`. The `verify` command runs `HnswVerifyMapper` across base table regions via `TableInputFormat`: - **Data Table Pass:** Each row containing a vector is read through `IndexMaintainer`. The mapper verifies that the vector exists within the region's segment stack. Full-precision vectors must match within $10^{-6}$ of the norm. Quantized vectors (`SQ8` and `PQ` NVQ codes) are validated against reconstructed values within a 2% tolerance. - **Segment Pass:** Unmasked segment ordinals within region boundaries that have no corresponding base table rows are identified as orphaned or TTL-expired entries. - **Backlog Accounting:** Rows modified after `replayStartTime` are marked as backlog rather than validation errors, as they are served from active in-memory graphs. Verification failures and summary statistics are recorded in `PHOENIX_INDEX_TOOL` and `PHOENIX_INDEX_TOOL_RESULT`. HNSW verification operates on current table state, rejecting time range parameters (`-st`, `-et`). Unreadable segments are recorded as `SEGMENTS_UNREADABLE` findings without aborting the verification job. ### Consistency Checks `fsck` adds two scopes to the shared table checks: | Scope | Finding | Severity | |---|---|---| | `CATALOG` | `ACTIVE_UNBUILT`: an `ACTIVE` index with no segments on a table holding vectors. | `ERROR` | | | `SEGMENT_MALFORMED`, `STRAY_ROW`: index rows that are not well-formed segment rows. | `ERROR` | | | `RANGE_UNCOVERED`: a live region with key ranges no base segment covers (it rebuilds on open). | `WARN` | | | `SEGMENT_SUPERSEDED`: a segment wholly covered by newer segments, or a delta whose base is gone, not yet retired. | `WARN` | | `SEGMENTS` | `PAYLOAD_UNRESOLVED`: the payload's MOB file is missing. | `ERROR` | | | `SEGMENT_CORRUPT`: the payload cannot be decoded (trailer, mapping framing, JVector header or footer). | `ERROR` | | | `SEGMENT_INVALID`: `N` disagrees with the mapping, row keys not strictly ascending or outside the segment's range, wrong dimension, node count or id bound mismatch, invalid entry node, out-of-range or self neighbors, excess degree, non-finite inline vectors. | `ERROR` | | | `GRAPH_UNREACHABLE`: nodes not reachable from the entry node over any level's edges. | `WARN` above 5%, else `INFO` | | | `RECALL`: recall@10 of a default-`ef_search` search against brute force over the stored vectors, for 10 queries sampled from the segment's rows. | `WARN` below 0.9, else `INFO` | Reachability and recall metrics serve as advisory quality indicators. Because parallel graph construction can occasionally produce isolated nodes in small graphs, reachability warnings apply above a 5% threshold. ### Inspection Subcommands The `inspect` command provides diagnostic utilities using `name=value` arguments: - `list`, `coverage`: Displays segment metadata, active regional segment stacks, boundary coverage, and candidate retirable segments. - `dump [time=T] [nodes] [dot]`: Decodes segment payloads, reporting graph levels, degree histograms, entry points, and optional GraphViz DOT representations. - `export <directory> [time=T]`: Exports raw segment payloads accompanied by JSON metadata descriptors. - `search <[v1,...] | @file | key values> [k=K] [ef=EF]`: Executes client-side multi-segment searches against regional boundaries, comparing results against brute-force baselines and reporting search statistics. - `neighbors`, `lookup`: Inspects forward and reverse adjacency edges for node ordinals, alongside ordinal mapping and distance metrics. - `delta`: Analyzes pending regional mutations and replay scope since the newest segment timestamp. ### Repair Workflow The `repair` workflow operates conservatively without fabricating segment data. Repairs are blocked while indexes are in `BUILDING` state or while base regions are actively splitting or merging. Repair executes in iterative rounds: 1. **Purge Stray Rows:** Removes unreferenced or malformed index table rows after re-verifying their status. 2. **Purge Corrupt Segments:** Deletes corrupt or unresolvable segment rows prior to rebuild triggers. 3. **Region Rebuild:** Executes `verify` and triggers regional rebuilds for regions overlapping deleted segments, uncovered key ranges, or row verification discrepancies via `IndexTool.buildHnswRegions`. 4. **Retire Superseded Segments:** Cleans up obsolete segments fully superseded by newer base segments once all child regions complete rebuilds. Each round re-evaluates consistency checks and row verification to confirm error resolution before completing or initiating subsequent rounds. --- ## 8. Compatibility and Upgrade Management ### Compatibility and Version Gating HNSW indexing leverages the existing `Feature.VECTOR_INDEX` handshake against `MIN_VECTOR_INDEX_VERSION`. Catalog schema additions are incorporated directly into the 5.4.0 metadata upgrade sequence. HNSW execution requires RegionServer runtimes on Java 11 or later to support JVector dependencies. ### Catalog and Wire Format Evolution - **Catalog Upgrade:** Five HNSW parameter columns are appended to the 5.4.0 upgrade block with one timestamp each. `MIN_SYSTEM_TABLE_TIMESTAMP_5_4_0` advances from `MIN_TABLE_TIMESTAMP + 52` to `+ 57`. - **Protobuf Compatibility:** HNSW fields are `optional` with dedicated tags: `PTable.proto` 66–70 and `ServerCachingService.proto` 39–40, following the PHOENIX-7998 fields 59–65 and 34–38. - **Identifier Allocation:** New `SQLExceptionCode` entries occupy 313–318 (`23111`–`23116`), after PHOENIX-7998's 312. `HintNode.Hint.HNSW_EF_SEARCH` is appended after `MAX_PROBE_LIMIT`. - **Configuration:** Two server properties are added, `phoenix.vector.hnsw.ef_search.default` and `phoenix.vector.hnsw.offheap.max.bytes`. --- ## 9. Design Verification Strategy Validation ensures approximate search accuracy and failure isolation: ### Brute-Force Ground Truth Validation Integration tests validate approximate nearest neighbor search against exact brute-force baselines. Target recall thresholds enforce: - $\ge 0.95$ for full-precision (`NONE`) segments. - $\ge 0.90$ for scalar quantized (`SQ8`) segments and end-to-end SQL Top-K queries. - $\ge 0.70$ for product quantized (`PQ`) segments. Vector update tests negate previous vector coordinates, verifying that searches do not return obsolete vector states. ### Suite Coverage | Suite | Coverage | |---|---| | `HnswCatalogIT` | Row key schema, initial `BUILDING` state, DDL validation, eventual-consistency rejection at `CREATE` and `ALTER`, `ROW_TIMESTAMP` rejection (accepted for IVF), catalog persistence of explicit and default parameters, MOB configuration. | | `HnswSegmentIT`, `HnswOffheapAllocatorTest` | MOB round trip and recall per codec, small `PQ` segments, eviction and reload, corrupt payload rejection, delta segments with and without payload, LRU accounting, callbacks outside the allocator lock. | | `HnswIndexIT` | IVF and HNSW coexistence, `IndexTool` builds, row changes before, during, and after rebuilds, replay on reopen, compacted deletes, delete-triggered flushes, failed rebuild retry, BSON functional indexes, splits, merges, and delta stacks. | | `HnswIndexManagerTest`, `HnswSegmentTest` | Pure stack logic over descriptors: discovery, replay start, retirement, exact-stack detection, coverage by bases only. | | `HnswIndexFsckIT` | Dispatch with IVF and HNSW on one table; `IndexTool -v`/`-fi` redirect; healthy `NONE`, `SQ8`, `PQ` indexes verify and check clean; backlog and delta verification; crafted segments with missing, divergent, and orphan rows recorded in the result tables and repaired by rebuilding exactly that region; injected stray, malformed, MOB-missing, corrupt, miscounted, out-of-range, unordered, and superseded segments detected and repaired; interlocks. | | `HnswIndexInspectIT` | Every `inspect` command; lookups on salted, composite, and multi-tenant keys; split daughters searching a clipped parent segment; uncovered ranges repaired. | | `HnswIndexFsckProviderTest`, `IndexFsckToolTest` | Graph reachability before and after removing level-0 edges from a payload, option and vector parsing, HNSW provider dispatch. | | `HnswQueryIT`, `VectorIndexScanPlanTest` | SQL top-K recall, candidate-only reads, unflushed changes, filtered-query fallback, candidate counts from `HNSW_EF_SEARCH(n)` and `LIMIT`, IVF and HNSW on one column, top-K over delta stacks. | --- ## Summary of Core Changes by Subsystem | Subsystem | Primary Components | Key Modifications | |---|---|---| | **DDL & Catalog** | `CreateIndexStatement`, `CreateIndexCompiler`, `MetaDataClient`, `MetaDataEndpointImpl`, `PTable`, `VectorIndexType` | Added the HNSW algorithm, parameter extraction and validation, five catalog columns with their upgrade, a read-only `VectorIndex` view, data-table-keyed MOB index tables, and eventual-consistency and `ROW_TIMESTAMP` rejection. | | **Segment Storage** | `HnswSegment`, `HnswOffheapAllocator`, shaded artifact poms | Added the JVector dependency, a single segment codec stored as one self-describing MOB row, three quantization codecs, and an off-heap budget with lock-free LRU eviction. | | **Write Pipeline** | `IndexMaintainer`, `IndexRegionObserver`, `VectorIndexManager` | Carried the indexed vector expression in maintainers, opened managers before row locks, applied graph updates post-commit, and kept HNSW out of index row generation and client-side maintenance. | | **Graph Maintenance** | `HnswIndexManager` | Built the mutable graph, segment masks, delta flushes, ratio-triggered full rebuilds, retries, and replay on open. | | **Region Lifecycle** | `HnswIndexManager`, `HnswSegment.Descriptor` | Implemented hook-free segment discovery, range-filtered search of wider segments, immediate rebuild, and coverage-based retirement. | | **Population** | `IndexTool`, `IndexRegionObserver#preScannerOpen` | Added server-side per-region builds via the `HNSW_BUILD` scan attribute and routed HNSW `REBUILD` to `IndexTool`. | | **Query Engine** | `HnswScanPlan`, `QueryOptimizer`, `VectorSearchUtil`, `HintNode` | Added data-table scans restricted to graph candidates, exact top-N ranking, lookup costing, vector-tier ranking, and the `HNSW_EF_SEARCH(n)` hint. | | **Tooling** | `IndexFsckProviders`, `HnswIndexFsckProvider`, `HnswVerifyMapper`, `HnswIndexInspector`, `HnswIndexReader`, `HnswRegionSegments`, `IndexTool` | Added HNSW verification, consistency checks, inspection, and repair on the shared runner, rejected `IndexTool` verification of HNSW, and shared the region rebuild loop between `IndexTool` and repair. | | **IVF Coexistence** | `MetaDataClient`, `IndexMaintainer`, `IndexRegionObserver`, `IndexTool`, `QueryOptimizer` | Gated each PHOENIX-7998 IVF hook on the algorithm with a single condition, leaving IVF behavior unchanged. | -- 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]
