# Cloud Storage Engine - Vector Index Analysis

> [!NOTE]
> Generated by AI. Some details may be incorrect or outdated.

## Overview

This document provides comprehensive architectural analysis of Cloud Storage Engine's vector index system to guide future development efforts. Vector indexes enable similarity search on high-dimensional vector data using the usearch library for approximate nearest neighbor (ANN) search.

**Development Focus**: Understanding the design patterns, architectural decisions, and implementation strategies that drive vector index lifecycle management, compaction rules, and distributed operations across shards.

### Key Architectural Insights for Developers

1. **Incremental Updates**: The `snap_version` system enables efficient delta-based processing
2. **Version Monotonicity**: Critical for consistency across distributed shard operations
3. **Multi-file Strategy**: Balance between search performance and memory constraints
4. **Format Evolution**: V2 format adds nulls bitmap for improved MVCC handling
5. **Threshold-based Triggering**: Delta size and file count drive compaction decisions

## Architecture and Components

### Core Components

- **VectorIndexes** (`VectorIndexes` struct): Collection managing all vector indexes in a shard, provides add/get/retain operations
- **VectorIndex** (`VectorIndex` struct): Container for vector index metadata and files for a specific (table_id, index_id, col_id) combination
- **VectorIndexFile** (`VectorIndexFile` struct): Individual vector index file with usearch index data and version tracking
- **VectorIndexBuilder** (`VectorIndexBuilder` struct): Builder for creating vector index files from columnar data with streaming support

### File Format Evolution

**V1 Format (DEPRECATED)**:

```
index | versions | handles | props | footer
```

**V2 Format (Current)**:

```
index | versions | handles | nulls | props | footer
```

Key improvements in V2:

- Added nulls bitmap for MVCC delete information
- Better tombstone handling during searches

## Data Flow: Row Storage -> Columnar -> Vector Index

### 1. Row to Columnar Conversion

**Process**:

1. Row data in LSM-Tree (MemTable -> L0 SSTable -> Ln SSTable)
2. `L0ToColumnar` compaction converts row data to columnar format
3. `ColumnarFileBuilder` (`components/kvengine/src/table/columnar/builder.rs:61`) organizes data by column
4. Each columnar file can contain multiple TiDB tables with column-oriented layout

**Columnar File Structure**:

```
+-----------------------------------+
| Table 1: Handle Column Packs      |
| Table 1: Version Column Packs     |
| Table 1: Column A Packs           |
| ...                               |
| Table N: Column X Packs           |
| Table Metadata (Index)            |
| File Properties                   |
| Footer                            |
+-----------------------------------+
```

### 2. Columnar to Vector Index Conversion

**Triggering Process**:

- Triggered during `UpdateVectorIndex` compaction tasks
- `VectorIndexBuilder` reads columnar data using `ColumnarMergeReader`
- Builds usearch indexes from vector column data

**Build Process** (in `build_vector_index` function):

1. Load schema file to get vector index definition
2. Create `ColumnarMergeReader` from relevant columnar files
3. Read columnar data in blocks (1024 rows at a time)
4. Use `VectorIndexBuilder.add_block()` to process vector data
5. Build usearch index with vectors, handles, versions, and null markers
6. Split into multiple files if size exceeds `max_file_size` (default: 2GB)
7. Store as `.vec` files on DFS with metadata

## Compaction Rules and Priority System

### CompactionPriority Enum

```rust
pub(crate) enum CompactionPriority {
    // ... other priorities
    UpdateVectorIndex {
        score: f64,
        table_id: i64,
        index_id: i64,
        col_id: i64,
        rebuild: bool,
    },
}
```

### Triggering Conditions

**1. Delta Size Threshold** (in `should_trigger_vector_index_update` function):

```rust
total_size >= self.opt.vector_index_build_options.delta_size  // Default: 16MB
```

- Calculated as: `unindexed_rows * dimension * 4 bytes`
- Triggers when sufficient new vector data exists

**2. File Count Threshold**:

```rust
if vec_idx.files_count() >= self.opt.vector_index_build_options.rebuild_file_count {
    return (1.1, true); // rebuild = true, Default: 4 files
}
```

- Prevents excessive file fragmentation
- Triggers complete rebuild when too many files exist

**3. Legacy Format Migration**:

```rust
if vec_idx.files.iter().any(|file| file.is_legacy_format()) {
    return (2.0, true); // High priority rebuild
}
```

- Automatically migrates V1 format to V2
- Highest priority (score: 2.0)

**4. Snap Version Lag**:

```rust
if vec_idx.snap_version() < l2_snap_after_compaction {
    return Some(CompactionPriority::UpdateVectorIndex { rebuild: false, .. });
}
```

- Ensures vector indexes stay synchronized with columnar data
- Prevents stale indexes after L1->L2 columnar compaction

### Build Options Configuration

```rust
pub struct VectorIndexBuildOptions {
    pub delta_size: usize,        // 16MB - minimum data to trigger build
    pub rebuild_file_count: usize, // 4 - max files before rebuild
    pub max_file_size: usize,     // 2GB - max single file size
}
```

### Priority Scores

- **Legacy format migration**: 2.0 (highest)
- **File count rebuild**: 1.1
- **New index creation**: 1.1 (when snap_version == 0)
- **Regular updates**: 1.1

### Override Logic

**L1 Columnar Compaction Override** (in `pick_compaction` function):

- Vector index updates can override L1 columnar compaction
- Prevents invalidating existing vector indexes during columnar compaction
- Ensures vector indexes are updated before columnar L1->L2 compaction

## Vector Index Lifecycle

### 1. Creation (New Index in Schema)

**Detection Logic**:

```rust
let snap_version = if let Some(vec_idx) = data.vector_indexes.get(...) {
    vec_idx.snap_version()
} else {
    0  // New index - no existing vector index files
};
// ...
(1.1, snap_version == 0)  // rebuild=true for new indexes
```

**Process**:

1. Schema contains vector index definition but no corresponding files exist
2. System treats it as new index (rebuild=true)
3. Reads ALL relevant columnar files to build initial vector index
4. Creates initial `.vec` files with complete data

### 2. Incremental Updates

**Process**:

1. New columnar L0/L1 files contain additional vector data
2. Delta size threshold check determines if update needed
3. Read only new columnar data since last snap_version
4. Build additional vector index files
5. Update snap_version to latest columnar snap_version

### 3. File Splitting

**Condition**:

```rust
fn should_build_vector_index(
    builder: &VectorIndexBuilder,
    build_opts: &VectorIndexBuildOptions,
    delta_vector_size: usize,
) -> bool {
    builder.estimated_size() >= build_opts.max_file_size  // 2GB
}
```

**Process**:

- During build, if estimated size exceeds max_file_size
- Current builder is finalized into a file
- New builder created for remaining data
- Results in multiple files with same snap_version

### 4. Rebuild Operations

**Triggers**:

- File count exceeds threshold (default: 4)
- Legacy format detected
- Manual rebuild requested

**Process**:

1. Remove all old vector index files
2. Read all relevant columnar data from scratch
3. Build completely new vector index files
4. Update snap_version and file list

## Shard Split and Merge Operations

### Split Process (in `create_new_shard` function)

**1. Table ID Scope Filtering**:

```rust
let mut new_vec_indexes = VectorIndexes::default();
for vec_index in old_data.vector_indexes.get_all() {
    if !columnar_table_ids.contains(&vec_index.table_id) {
        continue; // Skip if table not in this shard's scope
    }
}
```

**2. File Boundary Overlap Check**:

```rust
for file in &vec_index.files {
    if new_shard.overlap_bound(file.data_bound()) {
        new_vec_indexes.add_index_file(file.clone());
    }
}
```

**3. Snap Version Preservation**:

```rust
new_vec_indexes.update_snap_version(
    vec_index.table_id,
    vec_index.index_id,
    vec_index.col_id,
    vec_index.snap_version, // Preserves original snap_version
);
```

**Split Metadata Distribution** (`components/kvengine/src/meta.rs`):

```rust
for vec_idx in &old.vector_indexes {
    if !new_shard.columnar_table_ids.contains(&vec_idx.table_id) {
        continue;
    }
    let mut files = vec![];
    for vec_file in vec_idx.get_files() {
        if new_shard_bound.overlap_bound(vec_file.data_bound()) {
            files.push(vec_file.clone());
        }
    }
    if !files.is_empty() {
        let mut new_vec_idx = vec_idx.clone();
        new_vec_idx.set_files(files.into());
        new_shard.vector_indexes.push(new_vec_idx);
    }
}
```

### Merge Process (in `merge_shard` function)

**1. Vector Index Combination**:

```rust
let mut vector_indexes = old_data.vector_indexes.clone(); // Start with target
for source_vec_index in source_snap.get_vector_indexes() {
    for source_vec_idx_file_id in source_vec_index.files.iter().map(|f| f.id) {
        let vec_idx_file = source.vec_index_files.get(&source_vec_idx_file_id).unwrap().clone();
        vector_indexes.add_index_file(vec_idx_file); // Add source files
    }
}
```

**2. Snap Version Management**:

```rust
let old_snap_version = vector_indexes
    .get(source_vec_index.table_id, source_vec_index.index_id, source_vec_index.col_id)
    .map(|v| v.snap_version)
    .unwrap_or(0);
vector_indexes.update_snap_version(
    source_vec_index.table_id,
    source_vec_index.index_id,
    source_vec_index.col_id,
    std::cmp::max(old_snap_version, source_vec_index.snap_version), // Take maximum
);
```

**Merge Deduplication** (`components/kvengine/src/meta.rs`):

```rust
fn merge_vector_index(&mut self, vec_idx: &VectorIndex) {
    if let Some(old_idx) = self.vector_indexes.iter_mut().find(|v| {
        v.table_id == vec_idx.table_id
            && v.index_id == vec_idx.index_id
            && v.col_id == vec_idx.col_id
    }) {
        let old_file_ids: HashSet<u64> = old_idx.files.iter().map(|f| f.id).collect();
        for file in vec_idx.files.iter() {
            if !old_file_ids.contains(&file.id) {
                old_idx.files.push(file.clone()); // Add non-duplicated files
            }
        }
    } else {
        self.vector_indexes.push(vec_idx.clone()); // Add completely new index
    }
}
```

### Key Challenges and Solutions

**1. Snap Version Rollback Issue**:

_Problem_: After split, columnar snap_version may not be monotonically increasing

_Solution_ (`components/kvengine/src/compaction.rs`):

```rust
// `Shard::get_columnar_snap_version` may not monotonically increase after
// split, so we need to use the max of the vector index snap version and
// the columnar snap version to avoid vector snap version rollback.
let snap_version = std::cmp::max(
    shard.get_vector_index(table_id, index_id, col_id).map(|v| v.snap_version()).unwrap_or_default(),
    shard.get_columnar_snap_version(),
);
```

**2. Cross-Keyspace Merge Handling**:

When merging shards from different keyspaces:

```rust
let (clear_source, clear_target) = need_clear_region_data_on_merge(&source_snap.outer_start, &old_shard.outer_start);
if clear_target {
    // Clear all data including vector indexes
    old_shard.set_data_opt(ShardData::new_empty(...), false);
}
```

**3. Table Scope Filtering**:

```rust
fn retain_columnar_and_vector(
    columnar_table_ids: &[i64],
    col_levels: &mut ColumnarLevels,
    vector_indexes: &mut VectorIndexes,
) {
    vector_indexes.retain(|idx| columnar_table_ids.contains(&idx.table_id));
}
```

## Search and Query Operations

### Vector Search Process

**Search Flow** (`components/kvengine/src/table/vector_index/vector_index.rs:245`):

1. Query multiple vector index files (sorted by snap_version descending)
2. Use usearch `filtered_search` with MVCC filtering
3. Handle version visibility and tombstone filtering
4. Deduplicate results across files (newer versions take precedence)
5. Apply handle range filtering if specified
6. Sort and limit results

**MVCC Handling**:

- Each vector has associated version (commit_ts)
- Tombstone vectors marked in nulls bitmap (V2 format)
- Search filters by start_ts for snapshot isolation
- Newer index files take precedence for same handle

**Distance Projection Mode**:

- Special mode where only distance column is projected
- No actual vector data read, only distances from index
- Used for TableScan operations expecting distance column

## Architectural Performance Design

### Build Architecture Patterns

- **Block-based Processing**: 1024-row chunks balance memory usage vs I/O efficiency
- **Streaming Design**: Handles arbitrarily large datasets without memory overflow
- **File Splitting Strategy**: Prevents memory constraints while maintaining search performance
- **Distributed Processing**: Remote compaction architecture for resource-intensive operations

### Search Architecture Patterns

- **usearch Integration**: Fast ANN with configurable precision/recall tradeoffs
- **Multi-file Coordination**: Parallel search with version-based result prioritization
- **MVCC Integration**: Efficient filtering during search without post-processing overhead
- **Memory Management**: VectorIndexCache provides access optimization and resource control

### Storage Architecture Principles

- **Compression Strategy**: LZ4 balances ratio with decompression speed requirements
- **Anti-fragmentation**: Automatic rebuild prevents long-term performance degradation
- **Resource Sharing**: Columnar foundation enables efficient multi-index scenarios

## Design Parameters and Architectural Tradeoffs

### Core Configuration Parameters

```rust
VectorIndexBuildOptions {
    delta_size: 16 * 1024 * 1024,    // 16MB - balance I/O vs latency
    rebuild_file_count: 4,           // Prevent fragmentation vs rebuild cost
    max_file_size: 2 * 1024^3,      // 2GB - memory vs file management
}

// usearch Index Configuration
IndexOptions {
    connectivity: 16,               // Graph connectivity - recall vs build time
    expansion_add: 128,            // Build-time search expansion
    expansion_search: 64,          // Query-time search expansion
    quantization: ScalarKind::F32, // Vector precision vs memory usage
}
```

### Design Rationale

**Delta Size (16MB)**:

- **Too Small**: Frequent rebuilds, high I/O overhead
- **Too Large**: Delayed index updates, higher search latency
- **Current Choice**: Balances build frequency with search freshness

**File Count Threshold (4)**:

- **Trade-off**: Fewer files improve search performance but trigger expensive rebuilds
- **Alternative**: Dynamic thresholds based on workload patterns

**Max File Size (2GB)**:

- **Memory Constraint**: usearch loads entire index into memory
- **Storage Efficiency**: Larger files reduce metadata overhead
- **Future Consideration**: Streaming or memory-mapped access

### Development Considerations

**Critical Design Metrics**:

- `files_count()`: Drives rebuild decision logic
- `snap_version`: Enables incremental update architecture
- `estimated_size()`: Controls file splitting strategy
- File overlap analysis: Essential for distributed shard operations

**Architectural Challenges**:

- Snap version monotonicity across shard operations
- File count management and rebuild thresholds
- Legacy format migration strategy
- Cross-keyspace merge complexity

## Snap Version System: The Key to Incremental Updates

### Overview

The snap_version system is crucial for efficient vector index management, enabling incremental updates by tracking which columnar data has already been processed. This prevents redundant reprocessing and ensures data consistency across the storage hierarchy.

### Version Hierarchy

**1. Shard Level Versions**:

```rust
// Shard snap_version: Latest L0 table version
pub(crate) snap_version: AtomicU64,  // base_version + data_sequence

// Columnar L2 snap_version: Version when L2 columnar files were created
pub(crate) l2_snap_version: u64,
```

**2. File Level Versions**:

```rust
// l0_version in columnar files: Version when source L0 SSTable was flushed
l0_version: Option<u64>,  // Stored in columnar file properties

// Vector index file snap_version: Version when this index file was built
snap_version: u64,  // Stored in VectorIndexFileCore
```

**3. Vector Index Level Versions**:

```rust
// Vector index snap_version: Highest l0_version of columnar data included
snap_version: u64,  // Tracks incremental indexing progress
```

### Version Flow Through the System

**1. Data Ingestion to Flush**:

```
Write -> MemTable (version = base_version + sequence)
v
Flush -> L0 SSTable (stores version in properties)
```

**2. LSM to Columnar Conversion**:

```
L0 SSTable (l0_version = X) -> Columnar File (l0_version = X)
```

**3. Columnar to Vector Index**:

```
Columnar Files (l0_versions: [X, Y, Z])
v
Vector Index (snap_version = max(X, Y, Z))
```

### Key Usage Patterns

**1. Incremental Update Detection** (`components/kvengine/src/shard.rs:1777`):

```rust
fn need_build_vector_index(..., snap_version: u64) -> bool {
    for col_level in &data.col_levels.levels {
        if col_level.level == 2 && snap_version > 0 {
            continue; // L2 data already indexed
        }
        for file in &col_level.files {
            if snap_version > 0 && file.get_l0_version().unwrap_or_default() <= snap_version {
                continue; // This file already indexed
            }
            // Process this file...
        }
    }
}
```

**2. Vector Index Currency Check** (`components/kvengine/src/shard.rs:1519`):

```rust
if vec_idx.snap_version() < l2_snap_after_compaction {
    return Some(CompactionPriority::UpdateVectorIndex { rebuild: false, .. });
}
```

**3. File Inclusion Logic** (`components/kvengine/src/table/vector_index/vector_index.rs:289`):

```rust
pub fn contains_columnar_file(&self, col_file: &ColumnarTable) -> bool {
    if col_file.get_l0_version().unwrap_or_default() <= self.snap_version() {
        return true; // Already indexed
    }
    false // Needs to be indexed
}
```

### Statistics and Monitoring

**Unindexed Data Detection** (`components/kvengine/src/table_stats.rs`):

```rust
let snap_version = snap_versions.get(&(table_id, index_id)).copied().unwrap_or(0);
let mut is_indexed = false;
if snap_version > 0 && (col_level.level == 2 || file.get_l0_version().unwrap_or_default() <= snap_version) {
    is_indexed = true;
}
if !is_indexed {
    result_entry.unindexed_columnar_rows += row_count;
}
```

### Split/Merge Snap Version Handling

**Split Operation**:

```rust
// Preserve snap_version from parent to children
new_vec_indexes.update_snap_version(
    vec_index.table_id,
    vec_index.index_id,
    vec_index.col_id,
    vec_index.snap_version, // Preserved from parent
);
```

**Merge Operation**:

```rust
// Take maximum snap_version from both sources
vector_indexes.update_snap_version(
    source_vec_index.table_id,
    source_vec_index.index_id,
    source_vec_index.col_id,
    std::cmp::max(old_snap_version, source_vec_index.snap_version),
);
```

### Anti-Rollback Protection

**Problem**: After shard splits, columnar snap_version may not increase monotonically

**Solution** (in version comparison logic):

```rust
// Use max of vector index snap_version and columnar snap_version to avoid rollback
let snap_version = std::cmp::max(
    shard.get_vector_index(table_id, index_id, col_id).map(|v| v.snap_version()).unwrap_or_default(),
    shard.get_columnar_snap_version(),
);
```

### File Sorting by Snap Version

**Vector Index Files** (`components/kvengine/src/table/vector_index/vector_index.rs:134`):

```rust
pub(crate) fn sort(&mut self) {
    self.files.sort_by(|a, b| {
        b.snap_version()
            .cmp(&a.snap_version())  // Newest first for search priority
            .then_with(|| b.file_id().cmp(&a.file_id()))
    });
}
```

### Backward Compatibility

**Legacy Support** (`components/kvengine/src/table/vector_index/vector_index.rs:178`):

```rust
pub fn snap_version(&self) -> u64 {
    // For backward compatibility, if snap_version is 0, use first file's version
    if self.snap_version == 0 && !self.files.is_empty() {
        return self.files[0].snap_version();
    }
    self.snap_version
}
```

### Performance Implications

**Benefits**:

- **Incremental Processing**: Only new data since last snap_version is processed
- **Efficient Skip Logic**: O(1) check to skip already-indexed files
- **Reduced I/O**: Avoids reading already-processed columnar files
- **Consistency**: Ensures data is indexed exactly once

**Considerations**:

- **Version Tracking Overhead**: Multiple version fields per index/file
- **Split/Merge Complexity**: Version synchronization across shards
- **Rollback Protection**: Additional logic to prevent version regression

## Recent Stability Improvements and Development Changes

### Vector Index File Sorting Stability (Issue #3190)

- **Problem**: Vector index file sorting was not stable, potentially causing non-deterministic behavior
- **Solution**: Enhanced the `sort()` function to use `file_id` as secondary sort key for deterministic ordering
- **Impact**: Ensures consistent search behavior across multiple runs and operations

### Vector Index Update Limiting (Issue #3175)

- **Problem**: Vector index compaction could be triggered too frequently, impacting performance
- **Solution**: Added vector index update limiter to control compaction frequency
- **Development Guidance**: Consider rate limiting when implementing new vector index triggers

### Snap Version Rollback Prevention (Issue #3152)

- **Problem**: Vector index snap_version could decrease after certain operations, causing data inconsistencies
- **Solution**: Enhanced version comparison logic to prevent rollback scenarios
- **Development Guidance**: Always use `std::cmp::max` when updating snap versions to maintain monotonicity

### Development Architecture Insights

#### Vector Index Build Optimization Opportunities

1. **File Size Management**: Current 2GB limit may need adjustment for large-scale deployments
2. **Delta Size Tuning**: 16MB threshold works well but could be configurable per table
3. **Rebuild Frequency**: 4-file threshold prevents fragmentation but may be too aggressive for write-heavy workloads

#### Performance Considerations for Future Development

- **Build Performance**: Block-based processing (1024 rows) is efficient but could benefit from adaptive sizing
- **Search Optimization**: File-level parallelism scales well with multiple index files
- **Memory Usage**: usearch library memory footprint should be monitored in large deployments

#### Architectural Decision Points

- **V1 to V2 Migration**: High priority (score 2.0) ensures consistent nulls handling
- **Snap Version Synchronization**: Critical for data consistency across split/merge operations
- **File Splitting Strategy**: Size-based splitting prevents performance degradation

## Future Development Directions

### High-Priority Architectural Improvements

#### 1. Legacy Format Deprecation Strategy

- **Objective**: Remove V1 format support to simplify codebase
- **Approach**: Gradual migration with monitoring and rollback capabilities
- **Development Impact**: Reduces conditional logic and maintenance overhead

#### 2. Snap Version Architecture Refinement

- **Current Issue**: Complex version tracking across split/merge operations
- **Proposed Solution**: Simplified monotonic version scheme
- **Benefits**: Reduced bugs, easier reasoning, improved performance

#### 3. Dynamic Configuration System

- **Current Limitation**: Static thresholds don't adapt to workload patterns
- **Development Opportunity**: Runtime-adjustable parameters based on metrics
- **Implementation**: Configuration hot-reloading with validation

### Scalability and Performance Enhancements

#### 1. Memory-Efficient Index Loading

- **Challenge**: 2GB file size limit due to memory constraints
- **Research Areas**: Streaming access, memory-mapped files, partial loading
- **Development Priority**: High for large-scale deployments

#### 2. Adaptive Build Scheduling

- **Current**: Fixed delta size and file count thresholds
- **Evolution**: Machine learning-based prediction of optimal build timing
- **Benefits**: Reduced latency while maintaining resource efficiency

#### 3. Cross-Shard Index Optimization

- **Opportunity**: Global optimization across shard boundaries
- **Challenges**: Coordination complexity, consistency guarantees
- **Research Direction**: Distributed index management protocols

### Integration and Extensibility

#### 1. Pluggable Distance Metrics

- **Current**: Fixed usearch integration
- **Extension**: Support for custom distance functions and index types
- **Architecture**: Interface-based design for multiple backends

#### 2. Columnar Storage Evolution Compatibility

- **Requirement**: Maintain compatibility with columnar format changes
- **Strategy**: Version-aware readers, progressive migration support
- **Development Focus**: Robust abstraction layers

### Developer Guidance Summary

**Key Architectural Principles**:

1. **Incremental Processing**: Always design for delta-based updates using snap_version
2. **Version Monotonicity**: Prevent rollbacks through careful version management
3. **File Size Balance**: Consider memory constraints vs. management overhead
4. **Split/Merge Awareness**: Design with distributed operations in mind

**Critical Code Patterns**:

- Use `std::cmp::max` for version updates to prevent rollback
- Implement stable sorting for deterministic behavior
- Consider rate limiting for resource-intensive operations
- Design with backward compatibility for gradual migrations

This analysis provides the architectural foundation for future vector index development in Cloud Storage Engine, emphasizing the design decisions and patterns that ensure scalable, consistent, and performant similarity search capabilities.