apurtell opened a new pull request, #2635: URL: https://github.com/apache/phoenix/pull/2635
Design document: https://gist.github.com/apurtell/e4668cddf949c43955d4a919489d4228 --- ## Overview Apache Phoenix provides native vector indexing to support high performance low-latency approximate nearest neighbor search over massive unstructured data collections. Vector indexes in Phoenix are delivered in two different implementations: global vector indexes (`VECTOR_GLOBAL`), which are Inverted File (IVF) indexes stored in independent HBase tables, and local vector indexes (`VECTOR_LOCAL`), which are Hierarchical Navigable Small World (HNSW) graph indexes segmented by data table region. The `VECTOR_LOCAL` implementation colocates HNSW vector index segments directly within the data regions of the underlying data table. Because each data region owns and manages an independent key range of table rows, colocating the vector index graph with its underlying data guarantees that a segment's lifecycle, key space, partition splits, merges, snapshots, failovers, and transactional boundaries align identically with the data region. Every segment read, write, and graph traversal executes as a strictly region-local operation, completely eliminating cross-server RPCs from the indexing and query execution paths. ### Architectural Tenets - **Region-Owned Index Storage:** All HNSW graph segments for all vector indexes on a table reside within a single hidden MOB column family (`V#`) of the primary data table, partitioned into deterministic per-region anchor rows. Table drops, truncations, snapshots, and restores automatically apply to both data and vector segments as a single unit. - **Zero-RPC Local Segment I/O:** The `HnswSegmentStore` storage abstraction executes segment cell listings, payload reads, and atomic mutations directly against the hosting HBase `Region` instance. Administrative and MapReduce tooling interacts with `V#` through read-only table scans, delegating all segment mutations to the regions themselves. - **WAL-Free Segment Writes:** Because vector index segments represent derived state reconstructible from primary data rows, segment writes and retirements execute with `Durability.SKIP_WAL`. Each segment write is accompanied by a dedicated flush request targeting only the `V#` store. Segment payloads are written directly to MOB files without inflating Write-Ahead Logs (WAL), WAL replay pipelines, or cross-cluster replication streams. - **Definition and Writer Fences:** Every segment records a cryptographic SHA-256 digest of its index definition (`D`) and the encoded name of its authoring region (`W`). Regions ignore segments matching different definitions and automatically trigger full rebuilds whenever segments authored by foreign regions are discovered. - **Exact Reads for Uncovered and Overflowed States:** Whenever a region lacks covering index segments (such as an upper daughter region following a split, a truncated region, or a region recovering from payload corruption) or has entered overflow, query scans automatically fall back to exact candidate free scans. Rows are ranked using Phoenix's bounded server-side top-N distance evaluation, guaranteeing that query recall remains 100% accurate while background rebuilds catch up. - **Write Admission Without Refusal:** Under extreme write pressure, regions transition into overflow mode rather than rejecting client writes. Data mutations remain fully available and durable in primary column families, vector queries remain exact, and an expedited repair rebuild restores index coverage. - **Embedded Graph Engine:** The system embeds the JVector graph engine, supporting HNSW and Vamana graph topologies, multiple vector quantization codecs (`NONE`, `SQ8`, and `PQ`), off-heap direct memory management with LRU buffer eviction, and delta segment stacking. - **Candidate-Restricted Data Scans:** Client queries scan the data table directly. Regions leverage index segments to restrict scans to nearest neighbor candidates, evaluate query predicates through region scanners, and widen candidate sets dynamically when selective filters are present. - **Integrated Consistency and Repair Tooling:** The `IndexFsckTool` suite inspects `V#` via standard table scans, identifies structural anomalies, and repairs indexes by issuing server-side build and purge requests, maintaining strict encapsulation without client-side writes to `V#`. --- ## Architecture and System Components The `VECTOR_LOCAL` architecture spans client side query compilation and optimization, region level mutation and search execution, off-heap memory management, and physical MOB-backed storage. ```mermaid flowchart LR subgraph Client["Client Tier"] direction TB QO["QueryOptimizer<br/>addHnswPlan()"] HSP["HnswScanPlan<br/>(Data Table Scan)"] DDL["MetaDataClient / CQSI<br/>(CREATE, DROP, Purge)"] TOOLS["IndexTool / IndexFsckTool<br/>(TableStore Scans)"] QO --> HSP end subgraph Region["HBase Region (RegionServer)"] direction TB IRO["IndexRegionObserver<br/>(preBatchMutate, postBatchMutate,<br/>preScannerOpen, postScannerOpen)"] HIM["HnswIndexManager<br/>(MutableGraph, Flush, Rebuild,<br/>Replay, Overflow, Lifecycle)"] PROBE["HnswCandidateProbe<br/>(Candidate Filtering and Widening)"] RS["HnswSegmentStore.RegionStore<br/>(mutateRowsWithLocks, Get, Scan)"] ALLOC["HnswOffheapAllocator<br/>(Direct Buffers, LRU Eviction)"] DATA[("Primary Data Families<br/>(Row Keys, Vector Cells)")] VCF[("Hidden Column Family V#<br/>(Anchor Rows: Metadata Cells<br/>+ MOB Reference Cells)")] IRO --> HIM IRO --> PROBE PROBE --> HIM HIM --> RS HIM --> ALLOC RS --> VCF HIM -->|"Replay / Rebuild Scans"| DATA PROBE -->|"Probe Scans"| DATA end MOB[("HBase MOB Storage Area<br/>(Graph Payload Files and<br/>Large Tombstone Lists)")] HSP -->|"Scan with HNSW_SEARCH Attributes"| IRO DDL -->|"HNSW_PURGE Scans"| IRO TOOLS -->|"HNSW_BUILD / HNSW_PURGE /<br/>HNSW_OVERFLOW Scans"| IRO TOOLS -.->|"Read-Only V# Scans (TableStore)"| VCF VCF -->|"MOB Reference Resolution"| MOB ``` The primary components and their architectural responsibilities include: | Component | Package | Role and Responsibilities | |---|---|---| | `HnswSegment` | `org.apache.phoenix.hbase.index.hnsw` | Segment serialization, loading, and JVector graph search. Defines anchor key computation, qualifiers, descriptors, and listing rules. | | `HnswSegmentStore` | `org.apache.phoenix.hbase.index.hnsw` | Storage seam for `V#`. Implemented as `RegionStore` for server-side mutations (`SKIP_WAL` writes, flushes, retirement, purges) and `TableStore` for tooling scans. | | `HnswOffheapAllocator` | `org.apache.phoenix.hbase.index.hnsw` | RegionServer direct memory budget for graph structures with reference counting and LRU eviction outside locks. | | `HnswIndexManager` | `org.apache.phoenix.hbase.index.vector` | Coordinates per-region state: mutable graphs, flushes, deltas, full rebuilds, replay, definition/writer fences, coverage, and overflow. | | `VectorIndexManager` | `org.apache.phoenix.hbase.index.vector` | Interface exposed to `IndexRegionObserver` for managing vector index lifecycles. | | `HnswCandidateProbe` | `org.apache.phoenix.hbase.index.vector` | Translates search attributes into candidate filters; coordinates probing, widening against selective predicates, and TTL masking. | | `IndexRegionObserver` | `org.apache.phoenix.hbase.index` | Coprocessor intercepting pre-batch initialization, post-commit mutations, candidate injection, administrative dispatch, and compaction filtering. | | `HnswScanPlan` | `org.apache.phoenix.execute` | Phoenix execution plan for HNSW queries. Attaches search attributes to scans, models lookup costs, and integrates into `EXPLAIN`. | | `HnswRegionRequests` | `org.apache.phoenix.index.vector` | Dispatches targeted one-row scans carrying administrative attributes (`HNSW_BUILD`, `HNSW_PURGE`, `HNSW_OVERFLOW`) across regions. | | `IndexTool` | `org.apache.phoenix.mapreduce.index` | Orchestrates distributed index population and rebuilds by polling `TableStore` and dispatching server-side builds. | | `IndexFsckTool` Suite | `org.apache.phoenix.mapreduce.index.fsck.hnsw` | Validation suite inspecting `V#`, detecting anomalies, and repairing indexes via server-directed requests. | --- ## 1. DDL, Catalog, and the Hidden Column Family ### DDL Surface and Index Parameters The SQL extensions for defining and querying local vector indexes integrates directly into Phoenix's standard DDL and query grammar without requiring special syntax keywords: ```sql CREATE VECTOR INDEX idx_docs_hnsw ON documents (embedding) WITH ( metric='COSINE', algorithm='HNSW', M=16, ef_construction=200, quantization='PQ', pq_segments=96 ); SELECT /*+ HNSW_EF_SEARCH(150) */ doc_id, author, content FROM documents ORDER BY COSINE_DISTANCE(embedding, ?) LIMIT 10; ``` The algorithm parameter determines the underlying index type. Setting `algorithm='HNSW'` compiles the index as `IndexType.VECTOR_LOCAL`. Setting `algorithm='IVF'` or omitting the algorithm preserves the global vector index implementation (`VECTOR_GLOBAL`). The supported HNSW parameters and their constraints are defined as follows: | Parameter | Allowed Range | Default | Architectural Meaning | |---|---|---|---| | `M` | 4 to 64 | 16 | Maximum outgoing edge degree per node in the graph. | | `EF_CONSTRUCTION` | 16 to 512 | 100 | Size of dynamic candidate list during graph construction. | | `ALPHA` | 1.0 to 2.0 | 1.2 | Diversity factor for Vamana neighbor pruning. | | `QUANTIZATION` | `NONE`, `SQ8`, `PQ` | `NONE` | Vector quantization codec. All codecs convert input vectors to 32-bit floats. | | `PQ_SEGMENTS` | 1 to 256 | None | Number of sub-vector quantization segments. Required for `PQ`; must divide vector dimension. | | `METRIC` | `L2`, `COSINE` | None | Distance metric. `INNER_PRODUCT` is rejected for HNSW because dot product is only equivalent to cosine distance for normalized unit vectors. | Index parameters are validated during compilation in `CreateIndexCompiler.verifyVectorIndex` and persisted by `MetaDataClient.createIndex`. Validation enforces: - **Parameter Exclusivity:** IVF-only options are rejected on HNSW indexes, and HNSW parameters are rejected on IVF indexes. - **No Projected Columns (`INCLUDE`):** HNSW queries project columns directly from the data row via region-local scans. - **No `ROW_TIMESTAMP` Tables:** Tables with `ROW_TIMESTAMP` are rejected because crash replay relies on strict cell commit timestamps. - **Strict Consistency Required:** `CONSISTENCY=EVENTUAL` is rejected for all vector indexes. - **Identifier Naming Constraints:** Names containing delimiters (`.`, `:`, `#`) are rejected because RegionServers parse view prefixes using these delimiters. - **Physical Partitioning Restrictions:** Because `VECTOR_LOCAL` indexes share the data table descriptor, partition overrides (`SPLIT ON`, `SALT_BUCKETS`, table level HBase properties) are rejected. The same validation rules are exposed publicly via `validateHnswIndex` and executed on the server by `MetaDataEndpointImpl.validateVectorIndexMetadata` before catalog rows are committed. ### Algorithm Dispatch and Index Type Resolution Phoenix assigns `IndexType.VECTOR_LOCAL` a serialized integer value of 5. Both `VECTOR_LOCAL` and `VECTOR_GLOBAL` return true for `PTable.isVectorIndex()`, while `getVectorIndexType()` returns `HNSW` or `IVF`. `VECTOR_LOCAL` avoids traditional local index paths: it does not use index ID prefixes in row keys, does not participate in local index joins, does not construct `L#` column families, and does not install `IndexHalfStoreFileReaderGenerator` readers. ### Structure of the Index PTable A `VECTOR_LOCAL` index defines a logical `PTable` entry in `SYSTEM.CATALOG` that references the physical data table: | Property | Value and Architectural Handling | |---|---| | Table Type / Index Type | `INDEX` / `VECTOR_LOCAL`, algorithm `HNSW`, initial state `BUILDING`. | | Physical Table Link | Bound directly to the data table physical HBase table name. | | Default Column Family | Set to `V#`; the vector column is logically mapped into `V#`. | | Primary Key Schema | Inherits every primary key column of the data table, preserving key definitions so `IndexMaintainer` serializes without synthetic key columns. | | Salting Configuration | None. Inherits physical partitioning and salting from the data table. | | Time-To-Live (TTL) | Does not inherit data table TTL, preventing conditional TTL rules from rejecting index creation. | | Catalog Attributes | Five dedicated HNSW columns in `SYSTEM.CATALOG`, along with metric and dimension metadata. | Because a `VECTOR_LOCAL` index does not create an independent HBase table, dropping or truncating the index never attempts to drop physical tables. In `MetaDataEndpointImpl.doDropTable` and `MetaDataClient.truncateGlobalIndexes`, `VECTOR_LOCAL` indexes are skipped, leaving data rows and statistics untouched. ### The Hidden Column Family `V#` When the first HNSW index is created on a table, Phoenix dynamically adds the hidden column family `V#` to the HBase data table descriptor via `ConnectionQueryServicesImpl.createTable`, which issues an HBase `modifyTable` call and reopens regions. Subsequent HNSW indexes share `V#` without altering the descriptor. When the last HNSW index is dropped, `V#` remains in the descriptor and is removed only when the parent data table is dropped. The descriptor for `V#` is generated by `generateVectorLocalIndexColumnFamilyDescriptor` with fixed settings: | Property | Configured Value | Architectural Rationale | |---|---|---| | `IS_MOB` | `true` | Directs large graph payloads into HBase MOB files, bypassing StoreFile compaction rewrite cycles. | | `MOB_THRESHOLD` | `1024` bytes | Inlines metadata cells in StoreFiles while routing large payloads and tombstones to MOB files. | | `VERSIONS` | `1` | Graph segments are immutable. New segments are produced by flushes and rebuilds; obsolete ones are retired. | | `TTL` | `FOREVER` | Prevents data table TTL expiration from aging out index segments. | | `KEEP_DELETED_CELLS` | `FALSE` | Ensures retired payload reference cells are purged during compactions, allowing MOB cleaners to archive old files. | | `REPLICATION_SCOPE` | `0` (Local) | Graph segments are derived state managed locally per region. Sinks build their own local graphs. | | `BLOOMFILTER` | `ROW` | Optimizes point lookups against segment anchor rows. | The family name `V#` is explicitly reserved and does not contain the substring `L#`, ensuring it is never confused with standard Phoenix local indexes. ### Isolation Because `V#` resides in the physical HBase table descriptor, Phoenix implements strict isolation checks to prevent `V#` from being exposed to SQL queries or altered by data table maintenance: | Engine Subsystem | Isolation Check Implementation | Failure Prevented | |---|---|---| | User Schema DDL | `CreateTableCompiler` and `MetaDataClient.addColumn` reject user families containing `V#` (`UNALLOWED_COLUMN_FAMILY`). | Prevents user schema collisions with the internal segment family. | | Compaction Scanners | `UngroupedAggregateRegionObserver.preCompact` returns the raw scanner for `V#`; `BaseScannerRegionObserver` preserves scan options. | Prevents conditional-TTL compactions from purging active `V#` cells, while ensuring retired cells are reclaimed. | | Statistics Collection | `DefaultStatisticsCollector` explicitly skips column family `V#`. | Prevents `UPDATE STATISTICS` from computing guideposts over internal segment rows. | | Property Sync | `ConnectionQueryServicesImpl` skips `V#` in `setSyncedPropsForUnreferencedColumnFamilies` and index property syncing. | Prevents operations like `ALTER TABLE SET TTL` from overwriting the `FOREVER` TTL of `V#`. | | Descriptor TTL | `TTLRegionScanner` and `HnswCandidateProbe.masksExpiredRows` resolve descriptor TTL from the second family when `V#` sorts first. | Ensures data families sorting after `V#` apply the correct user TTL to data rows. | | Row Size Functions | `BaseResultIterators` projects only data table column families for `ROW_SIZE()` and `RAW_ROW_SIZE()`. | Prevents anchor rows from surfacing as result rows or causing scanner loops. | | DDL Maintenance Scans | `PostDDLCompiler` skips `VECTOR_LOCAL` references; `MetaDataUtil.deleteFromStatsTable` returns immediately. | Prevents `DROP INDEX` from deleting data rows that share keys with anchor rows. | | Local Index Repair | `IndexHalfStoreFileReaderGenerator.getRepairScanner` excludes `V#`. | Prevents anchor rows from being interpreted as corrupt local index rows on mixed tables. | | Online Transforms | `MetaDataUtil.hasLocalIndexTable` returns true for tables with `V#`, blocking transforms; `alterIndex` rejects transforms. | Prevents index segments from being orphaned in legacy physical tables. | | Compaction Hooks | `IndexRegionObserver.postCompact` ignores compactions targeting `V#`. | Eliminates redundant index rebuild notifications for internal segment file compactions. | | FSCK Table Checks | `GlobalIndexFsckProvider.checkTable` skips `GlobalIndexChecker` verification for `VECTOR_LOCAL` tables. | Prevents false coprocessor warnings on data tables hosting local vector indexes. | ### Catalog Metadata and Wire Protocol HNSW index parameters are stored in `SYSTEM.CATALOG` under dedicated columns (`VECTOR_HNSW_M`, `VECTOR_HNSW_EF_CONSTRUCTION`, `VECTOR_HNSW_ALPHA`, `VECTOR_QUANTIZATION_TYPE`, and `VECTOR_PQ_SEGMENTS`). These parameters are serialized in `PTable.proto` (fields 66 through 70) and exposed through immutable `PTable.getVectorIndex()` descriptors. The vector expression itself is serialized within `IndexMaintainer` (field 39 of `ServerCachingService.proto`). Maintainers are delivered to RegionServers for all index states except `DISABLED` and `PENDING_ACTIVE`, ensuring that data writes occurring while an index is in `BUILDING` state maintain the in-memory graph. --- ## 2. Segment Storage ### Anchor Rows Every segment cell written by a region is stored within a single row of the `V#` column family, known as the region's *anchor row*. The anchor row key is computed mathematically from the region's key boundaries: ``` anchor(start, end) = start || 0x00 if end != start || 0x00 = start otherwise anchor(empty, 0x00) = none (empty region holding no rows) ``` This formulation guarantees that the anchor row key strictly resides within the region's semi-open interval `[start, end)`. For the first region in a table (empty start key), the anchor key is `0x00`. Because anchor keys end in `0x00`, they rarely coincide with valid Phoenix data row keys. In the rare event of a key collision, data integrity is fully preserved because data scans project only data column families, and Phoenix row deletions are scoped strictly to specific column families. The anchor row is derived directly from a segment's covered range rather than stored as an explicit attribute. A segment written by a region remains at that region's historical anchor row throughout subsequent splits and merges. As a result, merged regions can contain segments across multiple historical anchor rows. Segment discovery scans the entire `V#` family within the region's range. ### Qualifiers, Identity, and Cell Tags An index segment comprises a set of distinct HBase cells residing on a single anchor row. The column qualifier layout is: ``` qualifier = [index key][0x00][start key length (4B)][start key][segment timestamp (8B)][tag (1B)] ``` The *segment identity* is defined as the qualifier excluding the trailing single byte tag. The segment identity uniquely names the covered key range and swap timestamp, replacing row key based segment naming across descriptors, logging, error handling, and stack masks. Every cell belonging to a segment shares the segment timestamp. | Tag | Meaning | Storage | Content and Structure | |---|---|---|---| | `P` | Graph Payload | MOB File | Serialized graph data: `[OnDiskGraphIndex][ordinal-to-key mapping][mapping length][MAGIC]`. Absent if segment has zero vectors. | | `E` | Range End Key | Inline StoreFile | Raw byte array defining the segment's upper key boundary. | | `N` | Vector Count | Inline StoreFile | 4-byte integer recording the total number of indexed vectors. | | `B` | Base Timestamp | Inline StoreFile | 8-byte timestamp referencing the parent base segment. Present only on delta segments. | | `T` | Tombstone Keys | Inline or MOB | Encoded row keys of deleted vectors. Present only on deltas with deletes; excluded from listings. | | `R` | Replay Timestamp | Inline StoreFile | 8-byte timestamp indicating the WAL replay boundary. | | `D` | Definition Digest | Inline StoreFile | 32-byte SHA-256 digest computed from the index definition. | | `W` | Authoring Region | Inline StoreFile | Encoded region name of the RegionServer that wrote the segment, enforcing the writer fence. | Segment listings decode a segment only if all required metadata cells (`E`, `N`, `R`, `D`, `W`, plus `B` for deltas) are valid, and the row matches the anchor of the segment range. Malformed segments are excluded from searches and scheduled for retirement. ### The Segment Store Abstraction (`HnswSegmentStore`) All reads and writes against `V#` route through the `HnswSegmentStore`: | Operation | `RegionStore` (Server-Side Operations) | `TableStore` (Client and MapReduce Tooling) | |---|---|---| | `list(indexKey)` | Local region scan of `V#` with `MOB_SCAN_RAW`, `ColumnPrefixFilter` on index key, and `QualifierFilter` retaining metadata tags (`E`, `N`, `B`, `R`, `D`, `W`). Never transfers payload data. | Equivalent read-only scan over the data table via client APIs. | | `readPayload` | Local region `Get` for tag `P` with `EMPTY_VALUE_ON_MOBCELL_MISS`. | Equivalent client `Get` over RPC. | | `readTombstones` | Local region `Get` for tags `T` and `N` with `EMPTY_VALUE_ON_MOBCELL_MISS`. | Equivalent client `Get` over RPC. | | `write` | Single `SKIP_WAL` atomic `Put` across anchor row via `HRegion.mutateRowsWithLocks`, followed by a `V#`-specific flush request. | Prohibited. Administrative tools never write directly to `V#`. | | `retire` | Single `SKIP_WAL` atomic `DeleteColumns` mutation via `mutateRowsWithLocks` across historical anchor rows at exact segment timestamps. | Prohibited. | | `retireMalformed` | Scans index prefix and deletes cells not belonging to well-formed segments, preserving valid segments of alternative definitions. | Prohibited. | | `purge` | Deletes all cells under the index prefix across anchor rows using standard durability. | Prohibited. | | `listCells`, `payloadSize` | Internal helper methods. | Streams key-only, `MOB_SCAN_RAW` cells to inspect metadata and payload sizes without transferring graph payloads. | ### Write Path: `SKIP_WAL` and Dedicated Flushes When a background flush or full rebuild produces a new segment, the manager materializes the graph off-heap, writes the segment cells, executes an in-memory cutover, and retires superseded segments. Segment writes in `RegionStore.write` follow a two-step sequence: 1. **Atomic Mutation:** All cells for the segment are assembled into a single `Put` applied to the anchor row using `Durability.SKIP_WAL` via `HRegion.mutateRowsWithLocks`. In-process region mutations bypass RegionServer RPC serialization and cell-size validation (`RSRpcServices.checkCellSizeLimit`), allowing large payloads (exceeding 64 MB) to be written without configuration overrides. 2. **Dedicated Store Flush:** A flush request targeting only column family `V#` is submitted to the RegionServer's `FlushRequester`. The flush transfers the payload from memstore to an HBase MOB file and writes a lightweight MOB reference cell into a StoreFile: - **Base Segments:** The writing thread synchronously waits until the flushable memstore size of `V#` drops to zero or the region closes. If the flush requester is congested, requests are retried with exponential backoff. - **Delta Segments:** Delta writes submit a non-blocking flush request and return immediately. Because the delta thread is shared across all regions on a RegionServer, blocking on a delta flush could cause an unhealthy region to stall delta processing for healthy regions. Any unflushed delta cells are captured by subsequent base flushes, data table flushes, or region close events. To prevent deadlocks between data writes and segment flushes, `HnswIndexManager` never holds internal monitors while acquiring HBase region row locks. Data write mutations hold row locks while applying graph changes under the manager's monitor. Segment flushes execute row mutations outside the monitor and install state only after mutations succeed. ### Correctness and Durability of `SKIP_WAL` Writes Avoiding WAL logging for multi-megabyte graph payloads eliminates massive write amplification, avoids clogging WAL replication pipelines, and prevents shared WAL appender stalls across unrelated tables. Omitting segment writes from the WAL is fully correct and safe because graph segments are derived state. All underlying data rows and vector values are durably committed to primary column families and protected by standard WAL logging. Segment timestamps are generated monotonically and never reused, preventing recovery paths from encountering partially written or colliding segment cells. An HBase memstore flush captures a consistent point-in-time snapshot of `V#`. Because retirement deletes are applied only after the replacing segment is written and flushed, surviving on-disk state consists either of old segments only, old plus new segments (resolved by newest-first shadowing), or new segments only. A state containing retired old segments without new replacing segments cannot occur. If a RegionServer crashes before a segment flush completes, the region reopens, discovers the surviving segment stack, and replays unindexed data mutations from the recorded replay timestamp `R`. ### Retirement, Purge, and Cell Timestamps Retirement and purge mutations delete cells using explicit cell timestamps rather than HBase's `LATEST_TIMESTAMP`. When HBase processes a `DeleteColumns` mutation stamped with `LATEST_TIMESTAMP`, it assigns the current server clock timestamp. If clock skew exists across RegionServers, a delete applied on a server with a slightly lagging clock could fail to mask a cell written with a slightly advanced timestamp. Stamping deletes with the exact segment timestamp guarantees deterministic cell reclamation regardless of clock skew. | Condition | Storage Result | System Recovery Action | |---|---|---| | Tag `P` cell absent | `NotFoundException` | During open: re-scan the listing. If still absent, mark the segment as unreadable and trigger a repair rebuild. During search: reload sources if a cutover occurred; otherwise, treat as lost. | | Tag `P` present, MOB file missing or corrupt | Empty value; payload framing check throws `DoNotRetryIOException` ("Corrupt HNSW segment") | The segment is excluded from the active stack (`leaveOut`), the region rebuilds immediately, and the segment is never decoded as a graph. | | Delta tag `N` absent | `NotFoundException` | Indicates the delta was retired concurrently; safe to skip. | | Delta tag `T` missing or corrupt | Empty or undecodable value; throws `DoNotRetryIOException` | Treated identically to a lost payload. In addition, the delta's parent stack is marked uncovered, forcing exact scans until a rebuild completes. | When a search encounters a lost payload during segment reloading, `HnswIndexManager.leaveOut` immediately marks the region as uncovered, prioritizes its background rebuild, and fails the active scan with a retryable `IOException`. The client automatically retries the query, which then executes as an unrestricted, exact scan over the data table. --- ## 3. Index Codec and Off-Heap Memory Management The index codec interfaces directly with the JVector graph engine. When building a segment, table rows are sorted by primary key so that graph node ordinals correspond strictly to key order. This guarantees that any key range maps to a contiguous ordinal interval, enabling binary searches for boundary ordinals. The engine constructs hierarchical small-world graphs using parameters `M`, `EF_CONSTRUCTION`, and `ALPHA` with a neighbor overflow factor of 1.2. Graph serialization computes the exact payload byte size in an initial pass before serializing graph connectivity, ordinals, and vectors into a contiguous byte buffer. Vector representation within segments depends on the configured quantization codec: | Quantization Codec | Physical Segment Storage | Query Traversal Scoring | |---|---|---| | `NONE` | Full-precision 32-bit floating-point vectors stored inline in the graph payload. | Exact floating-point distance computation. | | `SQ8` | Scalar Quantization: 8-bit Non-Uniform Vector Quantization (NVQ) codes. | Approximate distance scoring via SIMD-accelerated NVQ integer operations. | | `PQ` | Product Quantization: Fused PQ neighbor codes combined with NVQ codebooks. | Fast asymmetric distance traversal using fused PQ lookup tables, followed by NVQ reranking of top candidates. | Segments configured with `PQ` that contain fewer than 256 vectors automatically fall back to storing full-precision vectors, as codebook training requires a minimum statistical sample. PQ codebook centroids are centered for L2 distance metrics and uncentered for Cosine distance. Full rebuilds never extract vectors from existing segments. Instead they rescan the underlying data region to retrain quantization codebooks from raw data. Graph materialization is managed off-heap by `HnswOffheapAllocator`. When a segment is opened, its metadata and key mappings are loaded into JVM heap, while the graph connectivity structure is copied into direct off-heap memory. The allocator enforces a RegionServer-wide direct memory budget configured by `phoenix.vector.hnsw.offheap.max.bytes` (defaulting to 2 GB, capped at 50% of direct memory remaining after BucketCache and memstore allocations). When memory allocations exceed the configured budget, the allocator evicts the least recently used segments. Eviction callbacks execute outside allocator synchronization locks to prevent contention. In-flight searches retain reference counts on direct memory blocks, ensuring that active queries are never invalidated by concurrent evictions. An evicted segment releases its off-heap buffer and reloads from `V#` upon its next query. If a single graph exceeds the total memory budget, off-heap loading is rejected with a non-retryable `TooLargeException`, while primary key mappings are retained in heap to permit candidate masking during writes. --- ## 4. Write Pipeline and Mutation Lifecycle The write pipeline processes incoming mutations through HBase coprocessor hooks while maintaining consistency between data table StoreFiles and in-memory vector graphs. ```mermaid sequenceDiagram autonumber actor Client participant IRO as IndexRegionObserver participant Region as HBase Region / WAL participant HIM as HnswIndexManager Client->>+IRO: Upsert / Delete Batch Mutation Note over IRO,HIM: preBatchMutate (Prior to Phoenix Row Locks) IRO->>IRO: Record batch start timestamp in hnswBatches IRO->>HIM: getVectorIndexManager(index) (Lazy initialization) IRO->>Region: Acquire Phoenix Row Locks IRO->>IRO: prepareIndexMutations: Strictly evaluate vector expression,<br/>queue onMutation(current, next, vector) IRO->>Region: Commit primary data mutations and WAL entries Region-->>IRO: Commit confirmation Note over IRO,HIM: postBatchMutateIndispensably (Under Row Locks) alt Batch Succeeded IRO->>HIM: Execute queued onMutation calls in commit order Note over HIM: Update MutableGraph and mask obsolete keys in segments else Batch Failed IRO->>IRO: Discard mutation queue (Graph untouched) end IRO->>IRO: Release row locks, remove batch start timestamp IRO-->>-Client: Mutation Result ``` The write execution flow maintains several architectural invariants: - **Manager Initialization Prior to Row Locks:** In `preBatchMutate`, before Phoenix row locks are acquired, `IndexRegionObserver` initializes the `HnswIndexManager` for each active index. If an initialization fails, new manager openings for that index are throttled for 10 seconds. - **Strict Vector Evaluation on Ingestion:** During write evaluation, malformed vector expressions immediately abort the write. If a vector has an invalid dimension or contains NaN or infinite values, the mutation is rejected with an explanatory `SQLException`. Replay and rebuild pipelines, by contrast, evaluate vectors leniently, logging warnings and skipping invalid rows without failing background jobs. - **Post-Commit Graph Updates:** Graph modifications execute within `postBatchMutateIndispensably` only after primary data rows have successfully committed to HBase StoreFiles and WAL, but before Phoenix row locks are released. Graph mutations never throw exceptions; unexpected errors schedule an immediate background repair rebuild. - **Batch Start Tracking:** Each batch mutating an HNSW index records its start timestamp prior to acquiring commit timestamps. The oldest active batch timestamp dynamically bounds the replay start timestamp `R` assigned to segments flushed while mutations are in flight. - **Bypassing Secondary Index Rows:** HNSW maintainers generate zero secondary index mutations and do not participate in client side index maintenance. - **Mutable Graph Concurrency:** In-memory updates update `MutableGraph`. Updates to different keys execute concurrently under a shared read lock, while segment cutovers and flushes acquire an exclusive write lock. Deleted rows are added to a tombstone set and masked across all existing segments. --- ## 5. Flushes, Delta Segments, and Rebuilds `HnswIndexManager` coordinates the lifecycle of in-memory mutations, flushing them into immutable segments and consolidating them via full rebuilds. Each manager publishes an immutable `State` snapshot that queries inspect lock free: ```mermaid flowchart TD T["apply(): Mutable graph reaches FLUSH_THRESHOLD<br/>(10,000 entries)"] REP{"Repair Pending?"} WAIT["Suppress Delta:<br/>Repair Full Rebuild Must Swap First"] ELIG{"deltaBase() Eligible?<br/>- Exact base stack exists<br/>- Deltas < MAX_DELTAS (4)<br/>- Cumulative changes < REBUILD_RATIO (25%)"} QUEUE["queueFull(): Queue full rebuild on hnsw-rebuild<br/>(Unrestricted regions first, then FIFO)"] HOLD{"Rebuild Queued and Graph reaches<br/>QUEUED_FLUSH_MULTIPLIER x Threshold<br/>with exact base?"} SWAPD["Swap Graph, Submit Delta Task<br/>(Dedicated hnsw-delta thread)"] DELTA["writeDelta(): Build delta segment,<br/>atomic SKIP_WAL Put with B and T tags,<br/>non-blocking V# flush request"] CUTD["Cutover: Mount delta on top of stack,<br/>mask keys updated since swap"] START["startFull(): Await active delta,<br/>absorb queued or failed delta graphs, swap"] SCAN["Rescan data table region<br/>(Apply TTL masks, bypass BlockCache),<br/>build graph, materialize off-heap"] WRITE["write(): Atomic SKIP_WAL Put,<br/>synchronously wait for V# flush"] CUTB["Cutover: New base replaces entire stack,<br/>mask keys updated since swap,<br/>clear overflow state"] RET["retireMalformed(), then atomically retire<br/>superseded segments across anchor rows"] T --> REP REP -- Yes --> WAIT REP -- No --> ELIG ELIG -- Yes --> SWAPD ELIG -- No --> QUEUE QUEUE --> HOLD HOLD -- Yes --> SWAPD SWAPD --> DELTA --> CUTD QUEUE --> START --> SCAN --> WRITE --> CUTB --> RET ``` The thresholds governing flush and rebuild operations are: | Parameter | Default Value | Architectural Function | |---|---|---| | `FLUSH_THRESHOLD` | 10,000 | Number of entries in the mutable graph (upserts plus deletes) that initiates a flush. | | `MAX_DELTAS` | 4 | Maximum number of delta segments permitted on top of a base segment before forcing a full rebuild. Guarantees that query searches scan at most five segments per stack. | | `REBUILD_RATIO` | 0.25 (25%) | Ratio of cumulative delta changes to base segment size that triggers a full rebuild. For bases up to 200,000 rows, this yields an optimal $O(\log N)$ amortized rebuild cost per mutation; above 200,000 rows, `MAX_DELTAS` caps segment count. | | `QUEUED_FLUSH_MULTIPLIER` | 2 | While a full rebuild waits in the rebuild queue, a region continues flushing deltas whenever its graph reaches 2 times the flush threshold, preventing memstore bloat. | | `phoenix.vector.hnsw.split.multiplier` | 3 | Multiplier triggering an automated region split request to the master when the mutable graph reaches 3 times the flush threshold, bounding rebuild duration. | | `OVERFLOW_MULTIPLIER` | 4 | Maximum mutable graph capacity before transitioning into overflow mode. | | `RETRY_DELAY_MS` | 60,000 ms | Delay before retrying transient flush or rebuild failures. | Thread scheduling isolates light delta writes from heavy full rebuilds: - **Dedicated Worker Pools:** Full rebuilds execute on a single RegionServer-wide thread (`hnsw-rebuild`) to strictly bound CPU and memory consumption during table scans. Tasks queue within a `PriorityBlockingQueue`, prioritizing unrestricted and uncovered regions over routine rebuilds. Delta segments execute on an independent thread (`hnsw-delta`), ensuring that routine flushes are never blocked behind large table rebuilds. - **Delta Takeover on Rebuild:** When a full rebuild transitions to `STARTING`, it waits for any active delta write to finish, absorbs any queued or failed delta graphs, and generates a fresh swap timestamp. This guarantees that retried rebuilds never reuse segment identities or collide with failed cell writes. - **Atomic Cutovers:** When a base segment completes, it replaces the entire segment stack. Keys modified after the initial swap are dynamically masked in the new segment. Base cutovers establish region coverage (`covered = true`); delta cutovers preserve existing coverage flags. --- ## 6. Write Admission and Overflow Handling Under sustained write ingestion, in-memory graph flushes can be delayed by congested rebuild queues, long table scans, or transient I/O stalls. In traditional index designs, reaching memory thresholds causes RegionServers to throw `RegionTooBusyException`, blocking client writes. In a distributed data store, blocking writes because of secondary index lag creates severe availability degradation, particularly following region splits when neither daughter region initially possesses an exact base segment. To provide uninterrupted write availability, Phoenix avoids write refusal by implementing an overflow state machine instead: ```mermaid stateDiagram-v2 [*] --> Normal Normal --> Dropping : Mutable graph reaches OVERFLOW_MULTIPLIER x FLUSH_THRESHOLD (40,000 entries) Dropping --> Recovering : Full repair rebuild executes swap Recovering --> Normal : Base cutover of rebuild swapping after newest overflow generation Recovering --> Dropping : Mutable graph overflows again during recovery Normal : Scans restricted to HNSW candidates Dropping : apply() drops graph updates -- scans fall back to exact brute force top-N Recovering : apply() updates new graph -- scans remain exact brute force top-N ``` The overflow lifecycle operates as follows: 1. **Entering Overflow:** When mutations push `MutableGraph` to the overflow limit (4x FLUSH_THRESHOLD): - The region increments its internal `overflowGeneration`. - It atomically installs a new `State` with an empty mutable graph and sets flags `overflowed = true` and `dropping = true`. - Any active flush state clears its set of keys changed since swap, preventing subsequent rebuilds from incorrectly masking new row versions. - It requests an expedited full rebuild and promotes any queued rebuild for the region to the front of the `hnsw-rebuild` priority queue. 2. **Dropping Phase:** While `dropping = true`, incoming data mutations commit normally to the HBase data table, but graph updates are discarded. The query scanner reads the region's range directly, ranking rows via Phoenix's exact server-side top-N distance engine. Query results remain 100% accurate. 3. **Catch-Up and Recovery:** Because deltas are suppressed while in repair mode, only a full rebuild can swap. When the rebuild swaps, it clears the `dropping` flag and begins populating a fresh `MutableGraph`. The rebuild's table scan, which executes after the swap, reads every committed row from the primary data table, capturing all mutations dropped during the overflow period. 4. **Exiting Overflow:** When the full rebuild completes its cutover, it compares the current `overflowGeneration` with the generation recorded at swap time. If no subsequent overflow occurred, `overflowed` is cleared, and the region returns to normal candidate-restricted indexing. During startup replay, if the number of unindexed mutations exceeds the overflow threshold, replay halts immediately and the region opens in overflow mode, avoiding prolonged startup delays. --- ## 7. Durability, Crash Recovery, and Write Replay The durability of `VECTOR_LOCAL` indexes combines primary StoreFile/WAL durability with lightweight segment checkpoints: - **Replay Start Timestamp ($R$):** Every segment stores a replay timestamp $R$ representing the server time of its swap, bounded by the start time of the oldest in-flight mutation batch (`replayFrom`). A region's overall replay boundary is the minimum $R$ among the newest segments across all active stacks (`replayStartTime`). - **Crash Recovery Replay:** When a region opens, `changedRowsScan` executes a raw, key-only scan over indexed data families across the time window $[R, \text{latest})$ without polluting the BlockCache. For each identified row key, the manager reads the current row state from the data table and reapplies the vector or tombstone to `MutableGraph`. Replay is completely idempotent. - **Trust Verification (`trusted`):** During region opening, an existing segment stack is retained without triggering a rebuild only if: 1. The stack forms an exact coverage covering the region's range. 2. Every segment's authoring region tag $W$ matches the opening region's encoded name. 3. No StoreFile in an indexed data family has a major compaction timestamp newer than $R$ (major compactions can purge raw delete tombstones known only to the prior manager's memory). If any trust check fails, the region opens in an uncovered state and schedules an immediate repair rebuild. - **Compaction Notifications:** In `IndexRegionObserver.postCompact`, major compactions on indexed families trigger a flush: on tables without TTL, a lightweight segment is flushed to advance $R$ past the compaction timestamp; on tables with TTL, a repair rebuild is scheduled to purge aged-out vectors from the graph. - **Lost Segment Writes:** If an un-flushed `V#`memstore is lost in a RegionServer crash, the segment is absent upon restart. Because retirement deletions occur after flushes, discovery locates the preceding valid stack and replays all mutations occurring since the earlier $R$. --- ## 8. Region Lifecycle Events ### Segment Discovery and Definition Fencing `HnswIndexManager` initializes lazily upon the first query or mutation targeting an index in the region. It lists all segment cells across all anchor rows in `V#`, applies the *definition fence* by comparing cell tag $D$ against the SHA-256 digest of the current index definition, and selects active segments using `currentSegments`: - Bases overlapping the region that are not superseded by newer bases. - Deltas associated with those bases, ordered newest first. - Wider segments (such as those inherited from a parent region or merge predecessor) are clipped dynamically during query execution to the region's key boundaries using ordinal binary search. Coverage is derived strictly from readable base segments. If a delta segment is lost or unreadable, its entire stack is disqualified from coverage, ensuring that missing delta mutations force an exact scan rather than returning incomplete results. ### Writer Fencing To ensure that regions only rely on MOB files they control, segments record the authoring region's encoded name in cell tag $W$. In HBase, MOB files are named after the region that flushes them. If an authoring region is closed or split, the HBase MOB cleaner can archive its files once its directory is removed. If a region discovers segments where tag $W$ does not match its own encoded name, it serves the segments temporarily while immediately enqueuing a full rebuild. This guarantees that cloned tables, merged regions, or split regions rebuild their own MOB files before upstream cleaners can delete inherited files. ### The Uncovered-Region Exact Read Rule If a region's key range is not completely covered by valid base segments, the region enters the *uncovered state*. While uncovered, queries execute without candidate restriction. The scan evaluates all rows across the region's range, and Phoenix's server-side top-N engine ranks results by exact distance. Uncovered regions prioritize their rebuilds at the head of the `hnsw-rebuild` queue. Once the full rebuild completes its cutover, the region transitions to covered status and resumes candidate-restricted search. ### Region Splits Without Reference Inheritance When an HBase data region splits, segment inheritance is handled asymmetrically between the daughter regions: ```mermaid sequenceDiagram participant P as Split Parent Region participant A as Lower Daughter Region (Start = P.start) participant B as Upper Daughter Region (Start = Split Row) Note over P: Anchor row anchor(P) = P.start || 0x00 holds segment stack S<br/>covering [P.start, P.end) P->>A: HBase passes link to parent V# StoreFile (Anchor is below split row) P--xB: Upper daughter receives no V# StoreFile links Note over A: Discovers stack S, clips search to range [P.start, Split Row),<br/>Writer fence detects foreign W, schedules priority rebuild Note over B: Discovers no segments, enters uncovered state,<br/>Serves queries via exact brute force top-N scans B->>B: Executes priority first rebuild, writes new base at anchor(B) Note over B: Transitions to covered state, restricts subsequent scans A->>A: Completes rebuild, writes new base at anchor(A),<br/>Retires inherited parent stack S from its V# family ``` The split parent's anchor row resides at $\text{P.start} \parallel \text{0x00}$, which naturally falls into the lower daughter's key range. Consequently: - **Lower Daughter:** Inherits the parent's `V#` StoreFile reference link, discovers the parent segment stack, clips traversals to its range, and serves candidate restricted scans. Because the writer fence detects the parent's region name in $W$, it immediately schedules a full rebuild. Upon cutover, it writes a new base at its own anchor and retires the parent segments from its local store. - **Upper Daughter:** Contains no anchor row and receives no StoreFile links. It opens in an uncovered state, serving HNSW queries via exact brute force scans. Its rebuild is queued at highest priority on `hnsw-rebuild`. Upon completing its first build, it writes an exact base at its anchor and transitions to candidate-restricted mode. Providing exact brute force reads for the upper daughter during its initial build window guarantees complete correctness and prevents silent data corruption. ### Region Merges When regions merge, HBase provides the merged region with reference links to all predecessor StoreFiles. Because each predecessor's anchor row falls within the merged boundaries, the merged region discovers all historical segment stacks. It serves queries across the union of these stacks (clipping each to its historical range) and immediately initiates a full rebuild. The rebuild cutover writes a single consolidated base segment at the merged region's anchor row and atomically retires all predecessor segments. ### Region-Scoped Retirement Retirement of obsolete segments is strictly region-scoped. When a full rebuild completes, `retireSupersededSegments` executes: 1. **Malformed Cell Cleanup:** Deletes any cell under the index prefix that does not belong to a valid, well-formed segment (`RegionStore.retireMalformed`), preserving valid segments belonging to other index definitions. 2. **Superseded Segment Retirement:** Deletes every base segment whose range is fully subsumed by newer bases of the current definition, along with their associated deltas. Because retirement deletes only cells stored within the region's own `V#` store, regions operate completely independently. No region waits for neighboring regions to complete splits or merges, eliminating split parent tracking leaks. --- ## 9. Population and Rebuilds via IndexTool Initial population of an HNSW index executes via `IndexTool` using a distributed, server-managed architecture: ```mermaid sequenceDiagram autonumber actor IT as IndexTool participant IRO as IndexRegionObserver participant HIM as HnswIndexManager participant VCF as V# (via TableStore) Note over IT,VCF: Build Bar = Index DDL Creation Timestamp loop Every Second Until All Regions Covered IT->>VCF: List base segments matching current definition digest IT->>IT: Evaluate build status: Region covered if exact base has timestamp >= Build Bar opt Unbuilt Regions (Every 30 Poll Cycles) IT->>+IRO: One-row scan carrying HNSW_BUILD = [Accepted Time][Index Key] IRO->>HIM: rebuild(after) queues full rebuild unless active build covers request IRO-->>-IT: Returns cell with accepted timestamp (Becomes region's accepted bar) end Note over IT: Abort only if zero progress observed for 1 hour end IT->>IT: Mark index state ACTIVE in SYSTEM.CATALOG IT->>VCF: Perform secondary verification listing to build concurrent split daughters ``` Key build properties include: - **Server-Side Build Execution:** `IndexTool` does not construct graph structures within MapReduce client tasks. Instead, it issues targeted one-row scans carrying the `HNSW_BUILD` attribute to each region, directing RegionServers to execute rebuilds locally via `HnswIndexManager.startFull`. - **Accepted Timestamp Bar:** Build requests carry the region's previously accepted timestamp. If a full rebuild is already running that started after that timestamp, redundant rebuilds are suppressed. - **Handling Concurrent Splits During Activation:** After all regions report covering bases and `IndexTool` updates the catalog state to `ACTIVE`, the tool executes a final listing pass. Any daughter region created by a split occurring during the activation window is detected and built, ensuring complete coverage. - **Bulk Loading Integration:** Phoenix bulk load tools (`CsvBulkLoadTool`) bypass `V#` during MapReduce HFile generation. Upon completing a bulk import, the tool dispatches `HNSW_BUILD` requests across all regions, initiating full background rebuilds to incorporate newly loaded vectors. --- ## 10. Lifecycle Operations: DROP INDEX, DROP COLUMN, and Purge Dropping an HNSW index updates catalog metadata without altering physical HBase tables: 1. `MetaDataClient` removes index metadata rows from `SYSTEM.CATALOG`. 2. Following catalog commit, `MetaDataClient` broadcasts a one-row scan carrying `HNSW_PURGE = <index key>` to every data region using `HnswRegionRequests`. The same purge flow is initiated when `ALTER TABLE DROP COLUMN` removes an indexed vector column. 3. Purge operations are best-effort: transient RPC failures log warnings but do not fail DDL execution. 4. Upon receiving `HNSW_PURGE`, `IndexRegionObserver` invokes `HnswIndexManager.checkPurge`: - It verifies via `isHnswIndexOf` that the catalog contains no active HNSW index matching the key on that table. If an active index exists, the purge is rejected with `DoNotRetryIOException`, protecting live indexes from unauthorized purge scans. - The region closes and deregisters the manager for that index. - `RegionStore.purge` issues standard-durability deletions across all anchor rows for all cells prefixed by the index key. If a region misses a purge request (e.g., due to network partitioning or RegionServer failover), lingering cells are ignored by the definition fence and safely reclaimed by subsequent full rebuilds or `IndexFsckTool repair`. --- ## 11. Query Planning and Execution ### Query Optimization and Plan Selection During query compilation, `QueryOptimizer.addHnswPlan` evaluates whether a SQL query can leverage an HNSW vector index. The query must include an `ORDER BY` clause matching the index's vector expression and distance metric (`COSINE_DISTANCE` or `L2_DISTANCE`), ordered ascending with `NULLS LAST`. The query must also specify a constant literal or bind parameter target vector. Historical flashback queries (`AS OF SCN`) are rejected because graph segments maintain only current state. Valid queries compile into an `HnswScanPlan` via `QueryCompiler.withHnswIndex`. The plan attaches search parameters to the data table scan and disables guidepost splitting in `BaseResultIterators`, ensuring each region executes a single consolidated graph search. ### Server-Side Candidate Probing and Widening During scan initialization on primary replicas, `IndexRegionObserver.preScannerOpen` invokes `HnswCandidateProbe.candidateFilter` to construct a candidate filter conjoined with the query's SQL filter: 1. **Graph Traversal:** `HnswIndexManager.candidates` queries the segment stack from oldest to newest within the ordinal interval corresponding to the scan's key range, skipping masked ordinals. It then traverses the flushing graph (excluding keys modified after swap) and the mutable graph. If the scan specifies key range boundaries or a `SkipScanFilter`, keys failing range checks are excluded during traversal while still acting as routing nodes. 2. **Direct Candidate Injection (Unfiltered Queries):** For queries without non-vector filters or TTL masks, candidates are transformed directly into an HBase `MultiRowRangeFilter`, restricting the table scan to candidate rows. 3. **Iterative Probing and Widening (Filtered Queries):** If selective SQL predicates or TTL masks are present: - The probe opens an internal region scanner (`ServerScanUtil.openRegionScanner`) evaluating a copy of the SQL filter against candidate rows. - It counts passing rows against the query target count ($\text{LIMIT} + \text{OFFSET}$). - If passing rows are insufficient, the probe widens its search beam geometrically (by a growth factor of 4) or proportionally based on observed selectivity. - If candidate requirements exceed `MAX_CANDIDATES` (10,000) or 10% of indexed keys in the range, the probe falls back to an unrestricted scan (`return null`). 4. **Fallback to Unrestricted Scans:** Scans execute unrestricted across their range when a region is uncovered, in overflow mode, on secondary replicas, or when candidate widening exceeds safety thresholds. ### Ranking and Cost Estimation Candidate rows emitted by the scan are sorted and bounded using Phoenix's existing server-side top-N execution operator with exact distance expressions. Quantization codes are utilized strictly for graph navigation. Final result ranking evaluates full precision vector expressions from data rows. Query plan costing models HNSW lookups using `CostUtil.estimateLookupCost(min(rows, scans * candidates))`, placing `HnswScanPlan` in the vector optimization tier on equal footing with covering IVF plans. --- ## 12. Verification, Consistency Checking, and Repair Vector index maintenance and integrity validation are provided through the `IndexFsckTool` command-line suite (`bin/indexfsck.py`). Segment access is routed through `TableStore` scans over `V#`, ensuring administrative tools never execute raw mutations against StoreFiles. ```mermaid flowchart TD subgraph Inspection["Integrity Inspection Flow"] READ["HnswIndexReader.readCatalog()<br/>- MOB_SCAN_RAW scan of V# metadata<br/>- Zero payload bytes transferred"] CLASS{"Classify Findings per Region"} VERIFY["verify Command<br/>- Compare data rows vs segment graph<br/>- Report divergence and ROWS_UNCOVERED"] FSCK["fsck Command<br/>- Evaluate catalog and segment structural rules<br/>- Detect corrupt, malformed, or stray cells"] end subgraph Repair["Server-Directed Repair Actions"] ACT{"Repair Action Selection"} PURGE["PURGE_STRAY_CELLS<br/>Dispatch HNSW_PURGE to regions holding<br/>orphan or dropped index keys"] BUILD["REBUILD_REGIONS<br/>Dispatch HNSW_BUILD to regions holding<br/>corrupt, malformed, or foreign segments"] WAIT["awaitRetirement()<br/>Wait up to 60s for server cutovers and<br/>malformed cell retirement"] end READ --> CLASS CLASS --> VERIFY CLASS --> FSCK FSCK --> ACT ACT --> PURGE ACT --> BUILD BUILD --> WAIT ``` ### Verification (`verify`) `HnswVerifyMapper` executes a distributed MapReduce comparison between data rows and index segments across all regions: - **Data-to-Graph Pass:** Ensures every data row containing a valid vector matches an active segment entry within a relative divergence threshold ($\le 10^{-6}$ for full precision, $\le 0.02$ for NVQ quantization). - **Graph-to-Data Pass:** Ensures every active graph entry corresponds to an existing data table row. - **Classification:** Mutations occurring after $R$ are categorized as `ROWS_BACKLOG`. Rows present in regions lacking complete segment coverage are classified as `ROWS_UNCOVERED` (warning), distinguishing expected split windows from missing data. ### Structural Integrity (`fsck`) The `fsck` command classifies structural integrity across two scopes: | Scope | Finding Code | Severity | Description and Meaning | |---|---|---|---| | `CATALOG` | `ACTIVE_UNBUILT` | ERROR | Index marked `ACTIVE` in catalog but possesses no segments on table with data. | | `CATALOG` | `STRAY_ROW` | ERROR | Cells present under unreferenced index key, or segments of obsolete definition. | | `CATALOG` | `SEGMENT_MALFORMED` | ERROR | Undecodable qualifiers, missing metadata tags (`W`, `D`, `E`, `N`), or cells off anchor row. | | `CATALOG` | `RANGE_UNCOVERED` | WARN | Region range not fully covered by valid base segments (e.g. upper split daughter). | | `CATALOG` | `STACK_UNTRUSTED` | WARN | Segment stack contains segments authored by a foreign region (tag W mismatch). | | `CATALOG` | `SEGMENT_SUPERSEDED` | WARN | Segments eligible for retirement not cleaned up following a rebuild. | | `SEGMENTS` | `PAYLOAD_UNRESOLVED` | ERROR | Segment missing `P` tag, or payload resolves to empty value (lost MOB file). | | `SEGMENTS` | `SEGMENT_CORRUPT` | ERROR | Graph payload fails magic framing or protobuf decoding. | | `SEGMENTS` | `SEGMENT_INVALID` | ERROR | Violations of node counts, key ordering, degree constraints, or vector dimensions. | | `SEGMENTS` | `GRAPH_UNREACHABLE` | WARN | Graph disconnected: >5% nodes unreachable from entry node. | | `SEGMENTS` | `RECALL` | WARN | Recall@10 against brute force baseline on sampled queries falls below 0.90. | ### Introspection (`inspect`) The `inspect` command provides granular inspection of internal structures: - `list`: Displays all segments, authoring regions, anchor rows, definition statuses, and payload byte sizes. - `coverage`: Displays per-region coverage maps, identifying uncovered gaps or foreign stacks. - `dump` and `export`: Serializes graph topology and metadata into DOT or binary formats. - `delta`: Inspects backlog counters, replay timestamps, and active overflow statuses via `HNSW_OVERFLOW`. ### Automated Repair (`repair`) The `repair` command executes server-directed corrective workflows: - **`PURGE_STRAY_CELLS`:** Issues `HNSW_PURGE` requests to regions hosting cells belonging to dropped or invalid index keys. - **`REBUILD_REGIONS`:** Issues `HNSW_BUILD` requests to regions exhibiting corrupt, malformed, foreign, or superseded segments. The server-side rebuild cutover replaces corrupted structures and retires obsolete cells atomically. - **Retirement Synchronization (`awaitRetirement`):** Following rebuild requests, the repair coordinator polls regions for up to 60 seconds until all obsolete cells are completely retired. --- ## 13. Compatibility, Security, and Configuration ### Runtime and Build Compatibility Phoenix requires a minimum runtime of Java 11 to support JVector 4.0.1. JVector is packaged within `phoenix-server` as a multi-release JAR, preserving version-specific vector acceleration classes. Client JARs shade and relocate JVector according to standard Phoenix packaging conventions. ### Catalog and Protocol Wire Compatibility Catalog schema evolution appends five optional columns to `SYSTEM.CATALOG` within the 5.4.0 metadata block. Protocol buffer definitions extend `PTable.proto` (fields 66 through 70) and `ServerCachingService.proto` (field 39). Scan attributes include: - `HNSW_SEARCH_INDEX` and `HNSW_SEARCH_QUERY` (query execution) - `HNSW_BUILD` (server rebuild requests) - `HNSW_PURGE` (segment purge requests) - `HNSW_OVERFLOW` (overflow status introspection) Clients and servers must both support the `VECTOR_LOCAL` specification; heterogeneous clusters running older Phoenix releases cannot process local vector indexes. ### Security Model and Authorization Administrative scan attributes are processed by `IndexRegionObserver.postScannerOpen`: - `HNSW_OVERFLOW` is strictly read-only and requires standard HBase table `READ` privilege. - `HNSW_BUILD` requires table `READ` authorization. Rebuilds open managers only for validated HNSW indexes on the target table (`checkIndexOf`) and cannot alter raw data rows. Repeated build requests coalesce into a single pending rebuild per region. - `HNSW_PURGE` requires table `READ` authorization. Purges are validated by `checkPurge`, which rejects requests if the index key corresponds to an active HNSW index on that table. Purges delete only orphan cells belonging to dropped or renamed indexes. Restricting `HNSW_BUILD` and `HNSW_PURGE` to principals holding explicit `ADMIN` or `WRITE` privileges on the table represents a planned future enhancement. ### Configuration Reference | Configuration Property | Default Value | Configuration Scope | Architectural Description | |---|---|---|---| | `phoenix.vector.hnsw.ef_search.default` | 64 | Client | Default beam width used during graph search. Overridden dynamically per query via the `/*+ HNSW_EF_SEARCH(n) */` hint. | | `phoenix.vector.hnsw.offheap.max.bytes` | 2 GB | RegionServer / Tool JVM | Direct off-heap memory ceiling allocated for materialized graph structures. Capped at 50% of direct memory remaining after BucketCache and memstore allocation. | | `phoenix.vector.hnsw.split.multiplier` | 3 | RegionServer | Multiplier of `FLUSH_THRESHOLD` triggering an automated region split request to the master, bounding rebuild duration. Setting $\le 0$ disables split requests. | ### Operational Characteristics and Known Considerations - **Region Reopening on Index Creation:** Adding the first HNSW index to a table modifies the data table descriptor to introduce `V#`, causing HBase to reopen all regions of the table. Subsequent HNSW indexes share `V#` without reopening regions. - **Transient Memstore Ingestion Spikes:** Segment writes pass through the data region's memstore before being flushed to MOB files. Writing an exceptionally large base segment can briefly elevate memstore utilization, occasionally triggering transient `RegionTooBusyException` responses for regular writes until the `V#` flush completes. - **Split Catch-Up Window:** Upper daughter regions serve exact, brute force scans until their initial base rebuild completes. Query latency across that specific region is proportional to region row count during this temporary window. - **MOB File Cleaner Reclamation Lag:** When segments are retired, reference cells are deleted immediately, but underlying MOB files remain on disk until StoreFile compactions remove the reference markers and HBase's `MobFileCleanerChore` completes its archiving cycle. - **Verification Result Namespacing:** Because `VECTOR_LOCAL` indexes share the data table's physical descriptor, MapReduce verification output rows in `PHOENIX_INDEX_TOOL_RESULT` are keyed by the data table name rather than the index name. -- 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]
