[Feature][Vector] Sub-Shard Granularity for Primary-Key Vector Index Segments
- Dominant language
- Java
- Stars
- 3.4k
- Forks
- 1.4k
- Avg merge
- 1d 11h
- Merged PRs (30d)
- 396
Description
### Search before asking
- [x] I searched in the [issues](https://github.com/apache/paimon/issues) and found nothing similar.
### Motivation
```markdown
## Motivation
The current primary-key vector index maintains one ANN segment per `(partition, bucket, level)`. When any file in a level changes due to compaction, the **entire level's segment must be fully rebuilt**, even if only a small subset of files was affected.
For a level with 10 files totaling 10M rows, replacing just 2 files (2M rows) forces a rebuild of all 10M rows. This creates:
- Excessive rebuild cost for DiskANN/HNSW (minutes for large levels)
- Low `canAccept()` success rate when compact frequency > build time
- Delayed index availability under `waitCompaction=false`
## Proposal
Introduce a **Sub-Shard** mechanism that splits a level's index into finer-grained segments, so that only affected shards are rebuilt when compaction changes files.
### Three Granularity Options
| Scope | Segment Covers | Rebuild Unit | Segments per Level (10 files) |
|-------|---------------|--------------|-------------------------------|
| **LEVEL** (current) | All files in level | Entire level | 1 |
| **FILE_GROUP** | 2-4 adjacent files by key range | Affected group only | 3-5 |
| **PER_FILE** | Single compact-output file | Single file only | 10 |
### Example: 10 files, compact replaces 2
| Metric | LEVEL (current) | FILE_GROUP | PER_FILE |
|--------|----------------|-----------|---------|
| Rebuild data volume | 10M rows | 3M rows | **2M rows** |
| IVF-Flat rebuild time | ~50s | ~15s | **~10s** |
| DiskANN rebuild time | ~300s | ~90s | **~60s** |
| Unchanged segments | 0 | 2 groups | 8 files |
| canAccept success rate | Low | Medium | **High** |
### Algorithm Compatibility
| Algorithm | Precision Impact (PER_FILE) | Recommendation |
|-----------|---------------------------|----------------|
| IVF-Flat / IVF-PQ | ≈0% (IVF is partition-based) | PER_FILE |
| DiskANN / HNSW | -3~8% (graph connectivity severed) | FILE_GROUP |
**IVF algorithms are naturally suited for sub-sharding** since they search each partition independently. Graph-based indexes (DiskANN/HNSW) lose cross-shard neighbor connectivity, so FILE_GROUP with larger shards (2-5M rows) is recommended for them.
## Design Overview
### Core Changes
1. **`ShardPartitioner`** (new): Partitions level files into shards based on configured scope
2. **`PrimaryKeyIndexLevels.pick()`**: Returns plans for individual shards instead of entire levels
3. **`PkVectorBucketIndexState`**: Validates segments per-shard (partial match) instead of exact full-level match
4. **`BucketedVectorIndexMaintainer`**: Supports multiple parallel `PendingBuild` tasks for different shards
5. **`PrimaryKeyVectorBucketSearch`**: Searches multiple sub-shard segments and merges results
6. **`PrimaryKeyIndexSourceMeta`**: Extended with `shardIndex` field (version 2, backward compatible)
### Configuration
```sql
'pk-vector.shard.scope' = 'per-file' -- level | file-group | per-file
'pk-vector.shard.target-row-count' = '5000000' -- file-group mode: target rows per group
'pk-vector.shard.max-files-per-group' = '4' -- file-group mode: max files per group
'pk-vector.shard.max-parallel-builds' = '3' -- max concurrent shard builds
```
### Search Path
```
Per-File mode, 10 segments in a level:
→ Parallel ANN search on 10 small segments (each ~1M rows, ~0.8ms)
→ Merge results → global topK
→ Total latency (parallel): ~1.8ms vs current 5ms (faster due to smaller graphs)
```
### Backward Compatibility
- `PrimaryKeyIndexSourceMeta` version upgrade (V1 → V2), V1 still readable
- Default `scope=level` preserves existing behavior
- Online upgrade: change scope → next compact cycle gradually replaces segments
- Downgrade: set `scope=level` → next compact rebuilds full-level segment
## Performance Summary
| Dimension | LEVEL | FILE_GROUP | PER_FILE |
|-----------|-------|-----------|---------|
| Rebuild cost | High (full) | Medium (1/3-1/5) | Low (1/N) |
| Search precision (IVF) | Baseline | ≈Same | ≈Same |
| Search precision (graph) | Highest | -2~3% | -3~8% |
| Search latency (parallel) | Baseline | Faster | Fastest |
| `canAccept` success | Low | Medium | High |
| Storage overhead | Baseline | +5% | +10% |
| Best for IVF | ✓ | ✓✓ | ✓✓✓ |
| Best for DiskANN | ✓✓✓ | ✓✓ | ✓ |
## Key Code References
- `PrimaryKeyIndexLevels.java` - current single-segment-per-level enforcement
- `PkVectorBucketIndexState.java` - current exact full-level match validation
- `BucketedVectorIndexMaintainer.java` - current single PendingBuild model
- `PrimaryKeyVectorBucketSearch.java` - current single-segment search path
- PR #8672 "Align primary-key index maintenance with data levels"
### Solution
_No response_
### Anything else?
_No response_
### Are you willing to submit a PR?
- [x] I'm willing to submit a PR!
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the referenced `PrimaryKeyIndexLevels.java`, `PkVectorBucketIndexState.java`, `BucketedVectorIndexMaintainer.java`, and `PrimaryKeyVectorBucketSearch.java`, along with PR #8672 for context. The proposal requires coordinated shard planning, state validation, parallel builds, search merging, and metadata compatibility. Done means supporting configurable shard scopes while preserving the stated backward compatibility and existing default behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100