brainy/METADATA_PERFORMANCE_ANALYSIS.md

Brainy Metadata Filtering Performance Analysis

Executive Summary

The metadata filtering system in Brainy provides powerful search capabilities with indexing optimizations, but comes with specific performance trade-offs. This analysis examines the performance impact across five key dimensions: index build time, storage overhead, search performance, memory usage, and write operations.

Key Findings

1. Index Build Time Impact

Performance Overhead: 8.8%

• Without indexing: 138.24ms per item for 100 items
• With indexing: 150.46ms per item for 100 items
• Overhead: 8.8% slower initialization when metadata indexing is enabled

The overhead is primarily due to:

• Building inverted indexes for each metadata field
• Writing index entries to storage
• Initial cache population

2. Index Storage Overhead

Storage Overhead: 26 bytes per item

From test with 100 items containing 6 indexed fields each:

• Total index entries: 26 unique field-value combinations
• Total indexed IDs: 600 (100 items × 6 fields average)
• Index size: 2,600 bytes (26 bytes per item)
• Storage efficiency: Very compact representation

Index Structure:

• Storage Location: _system directory with __metadata_index__ prefix
• Index Format: Inverted indexes mapping field:value → Set<id>
• Cached Fields: department, level, location, salary, remote, active (excludes id, createdAt, updatedAt by default)

3. Search Performance Analysis

Critical Finding: 379-386% overhead when filtering is enabled

Performance Breakdown:

• No filtering: 31.46ms average
• Simple filter (department='Engineering'): 150.82ms average (379.4% overhead)
• Complex filter (multiple conditions): 153.05ms average (386.5% overhead)

Root Cause Analysis:

The performance overhead stems from the 3x ef multiplier implementation in /src/hnsw/hnswIndex.ts:377:

const ef = filter ? Math.max(this.config.efSearch * 3, k * 3) : Math.max(this.config.efSearch, k)

This multiplier compensates for potential filtering but significantly increases the search space:

• Default efSearch: Typically 50-100
• With filtering: 150-300+ candidates evaluated
• Impact: 3x more vector calculations and distance computations

Search Process with Metadata Filtering:

1. Pre-filtering Phase:

   • Query metadata index for candidate IDs: ~0.1ms
   • Create filtered ID set: ~0.05ms

2. HNSW Search Phase (Major bottleneck):

   • Search with 3x larger ef parameter: ~150ms
   • Evaluate 3x more vector similarities
   • Apply metadata filter to results: ~0.2ms

3. Post-processing:

   • Re-rank and limit results: ~0.1ms

4. Memory Usage Impact

Memory Overhead: ~26 bytes per indexed item

The metadata index system uses:

• Index Cache: In-memory Map storing field-value → ID mappings
• LRU Eviction: Automatic cleanup of unused entries
• Dirty Tracking: Efficient batch writes to storage
• Memory Efficiency: Minimal overhead per item

5. Write Performance Impact

Excellent Write Performance with Indexing

• ADD: 154.35ms per item (includes embedding generation)
• UPDATE: 0.03ms per item (very fast)
• DELETE: 0.10ms per item (very fast)

Write operations benefit from:

• Efficient Index Updates: O(1) hash lookups
• Batch Operations: Dirty tracking for efficient storage writes
• Automatic Cleanup: Empty index entries are automatically removed

Performance Recommendations

1. Immediate Optimizations

A. Dynamic ef Multiplier

Current Issue: Fixed 3x multiplier regardless of filter selectivity

Recommendation: Implement dynamic ef calculation based on index statistics:

const estimateSelectivity = async (filter: MetadataFilter): Promise<number> => {
  if (!this.metadataIndex) return 1.0
  
  const totalItems = this.index.getSize()
  const candidateIds = await this.metadataIndex.getIdsForCriteria(filter)
  return candidateIds.length / totalItems
}

// Use in search:
const selectivity = await this.estimateSelectivity(filter)
const multiplier = selectivity < 0.1 ? 2.0 : selectivity < 0.3 ? 1.5 : 1.2
const ef = Math.max(this.config.efSearch * multiplier, k * multiplier)

Expected Impact: 50-70% reduction in search overhead for high-selectivity filters

B. Index-First Search Strategy

Current: Always search full HNSW then filter Proposed: Pre-filter significantly when index suggests high selectivity

if (candidateIds.length < totalItems * 0.1) {
  // High selectivity: search only candidate vectors
  return this.searchCandidatesOnly(candidateIds, queryVector, k)
} else {
  // Low selectivity: use current HNSW + filter approach
  return this.searchWithFilter(queryVector, k, filter)
}

2. Configuration Recommendations

A. Selective Field Indexing

Default: Index all metadata fields (can be wasteful) Recommended: Configure specific fields for indexing

metadataIndex: {
  indexedFields: ['department', 'level', 'location'], // Only frequently filtered fields
  excludeFields: ['id', 'createdAt', 'updatedAt', 'description'],
  autoOptimize: true
}

B. Index Size Limits

Configure appropriate limits based on use case:

metadataIndex: {
  maxIndexSize: 50000, // Increase for large datasets
  rebuildThreshold: 0.05, // More aggressive rebuilding
}

3. Use Case Specific Optimizations

High-Selectivity Scenarios (< 10% match rate)

• Use smaller ef multiplier (1.2-1.5x)
• Enable aggressive index pre-filtering
• Consider dedicated filtered search paths

Low-Selectivity Scenarios (> 50% match rate)

• Disable metadata indexing for better performance
• Use post-filtering instead of HNSW filtering
• Consider vector-first search strategies

Mixed Workloads

• Implement adaptive ef multipliers
• Use query pattern analysis
• Enable smart caching strategies

Implementation Architecture

MetadataIndexManager Design

Strengths:

• ✅ Efficient inverted index structure
• ✅ LRU cache for frequently accessed entries
• ✅ Automatic index maintenance
• ✅ Storage in separate _system directory
• ✅ Backward compatibility with non-indexed searches

Areas for Improvement:

• ⚠️ Fixed 3x ef multiplier regardless of selectivity
• ⚠️ No query optimization based on index statistics
• ⚠️ Limited index compression for large datasets

Storage Integration

Well-designed storage patterns:

• Index entries stored with __metadata_index__ prefix
• Efficient serialization of Sets to Arrays
• Proper cleanup of empty index entries
• Flush batching for write performance

Benchmark Summary

Operation	Without Index	With Index	Overhead
Initialization	138.24ms/item	150.46ms/item	+8.8%
Simple Search	31.46ms	150.82ms	+379.4%
Complex Search	31.46ms	153.05ms	+386.5%
Add Operations	N/A	154.35ms/item	(includes embedding)
Update Operations	N/A	0.03ms/item	(very fast)
Delete Operations	N/A	0.10ms/item	(very fast)
Storage Overhead	0 bytes	26 bytes/item	minimal

Conclusion

The metadata filtering system provides powerful search capabilities with reasonable storage and initialization overhead. However, the current search implementation has significant performance bottlenecks due to the fixed 3x ef multiplier.

Key Takeaways:

1. Index building is efficient with only 8.8% overhead
2. Storage overhead is minimal at 26 bytes per item
3. Write operations are very fast due to efficient index updates
4. Search performance needs optimization - currently 300-400% slower when filtering
5. Memory usage is reasonable and well-managed

Priority Action Items:

1. Implement dynamic ef multiplier based on filter selectivity
2. Add index-first search for high-selectivity filters
3. Provide configuration guidance for different use cases
4. Consider query pattern analysis for automatic optimization

The system architecture is solid and well-designed; the performance issues are primarily in the search optimization logic and can be addressed with the recommended improvements.