Query Iterator Performance Analysis

Executive Summary

This document analyzes the performance characteristics of query iterators in liblevenshtein-rust, focusing on the ordered query iterator after fixing two critical bugs.

Bugs Fixed

Bug #1: Large Distance Queries Dropping Results

Location: src/transducer/ordered_query.rs:126-197

Problem: Queries with large max_distance (e.g., 99) were only returning a subset of results.

Root Cause: The advance() method had a strict equality check distance == self.current_distance which caused results to be silently dropped when their actual distance (from infer_distance()) differed from their bucket's distance (from min_distance()).

Solution: Implemented re-queuing logic that moves intersections to the correct distance bucket when distance > current_distance.

Impact: All matching terms within max_distance are now correctly returned.

Bug #2: Lexicographic Ordering Not Maintained

Location: src/transducer/ordered_query.rs:64-83, 126-197

Problem: Results at the same distance level were not properly sorted lexicographically.

Root Cause: VecDeque is FIFO - results came out in insertion order rather than lexicographic order. DAWG edges are iterated in sorted order, but items discovered at different tree depths don't maintain this ordering.

Solution:

• Added sorted_buffer: Vec<OrderedCandidate> and buffer_index: usize fields to the struct
• Modified advance() to collect all results at the current distance level, sort them by term, then yield them in order
• This ensures proper lexicographic ordering within each distance bucket

Impact: Results now correctly satisfy the ordering guarantee: distance-first, then lexicographic.

Performance Characteristics

Ordered Query Iterator (OrderedQueryIterator)

Current Implementation

pub struct OrderedQueryIterator<N: DictionaryNode> {
    pending_by_distance: Vec<VecDeque<Box<Intersection<N>>>>,
    current_distance: usize,
    max_distance: usize,
    query: Vec<u8>,
    algorithm: Algorithm,
    state_pool: StatePool,
    substring_mode: bool,
    sorted_buffer: Vec<OrderedCandidate>,
    buffer_index: usize,
}

Hot Paths

1. advance() method (lines 126-197):

   • Called on every next() iteration
   • Contains the core logic for distance-level iteration
   • Key operations:
     • Buffer checking and yielding (lines 127-131)
     • Distance bucket exhaustion loop (lines 135-194)
     • Result collection into buffer (line 162)
     • Buffer sorting (line 185): sorted_buffer.sort_by(|a, b| a.term.cmp(&b.term))
     • Term materialization (line 161): intersection.term()

2. queue_children() method (lines 199-212):

   • Called for each intersection to explore children
   • Iterates over DAWG edges (lexicographically sorted)
   • Calls transition_state_pooled() - likely expensive
   • Creates PathNode boxes for parent chain
   • Creates Intersection boxes

Potential Bottlenecks

1. Buffer Sorting Overhead:

   • Location: Line 185 in advance()
   • Operation: sorted_buffer.sort_by(|a, b| a.term.cmp(&b.term))
   • Frequency: Once per distance level
   • Complexity: O(n log n) where n = number of results at current distance
   • Impact: For queries returning many results at the same distance (e.g., distance 3-5), this could be significant
   • Mitigation Options:
     • Use a heap/priority queue structure (BinaryHeap) instead of Vec + sort
     • Consider maintaining sorted order during insertion (insertion sort for small n)
     • Profile to determine if this is actually a bottleneck

2. Term Materialization:

   • Location: Line 161 and line 148 in advance()
   • Operation: intersection.term() - reconstructs the full term string from PathNode chain
   • Frequency: Once per result
   • Complexity: O(k) where k = term length, involves string allocation
   • Impact: Could be significant for long terms or many results
   • Note: Necessary for sorting, but could be optimized if term construction is expensive

3. Box Allocations:

   • Location: Lines 196-204 in queue_children()
   • Operations:
     • Box::new(PathNode::new(...)) (line 196)
     • Box::new(Intersection::with_parent(...)) (line 199)
   • Frequency: Once per edge traversed
   • Impact: Memory allocation overhead, though StatePool mitigates this for States

4. State Transitions:

   • Location: Lines 182-190 in queue_children()
   • Operation: transition_state_pooled()
   • Frequency: Once per edge traversed
   • Complexity: Depends on algorithm (Standard/Transposition/MergeAndSplit)
   • Impact: Likely the primary computational cost
   • Note: Already uses StatePool for allocation reuse

5. Distance Bucket Requeuing:

   • Location: Lines 166-169 in advance()
   • Operation: Moving intersections to correct distance bucket when min_dist underestimates
   • Frequency: Varies based on query and dictionary
   • Impact: Adds extra processing, but necessary for correctness

Performance Comparison

Ordered vs Unordered Query

Ordered Query:

• Must process entire distance level before moving to next
• Requires sorting results within each distance
• Memory overhead: sorted_buffer
• Benefit: Enables efficient top-k queries and early termination

Unordered Query:

• Can yield results immediately upon discovery
• No sorting overhead
• Less memory overhead
• Drawback: Results in arbitrary order

Expected Performance Trade-offs

1. Distance 0 (exact match): Ordered and unordered should be roughly equivalent
2. Distance 1-2: Ordered has sorting overhead, but minimal for small result sets
3. Distance 3+: Sorting overhead grows as result sets expand
4. Large distances (10+): Significant sorting overhead if many results per distance level

Optimization Opportunities

High Priority

1. Profile Buffer Sorting:

   • Measure actual time spent in sort_by
   • If significant, consider BinaryHeap or other sorted data structure
   • Benchmark: bench_ordered_query_sorting_overhead in query_iterator_benchmarks.rs

2. Optimize Term Materialization:

   • Profile intersection.term() cost
   • Consider caching if terms are accessed multiple times
   • Investigate PathNode traversal efficiency

Medium Priority

3. Reduce Allocations:

   • Consider arena allocator for PathNode boxes
   • Investigate if Intersection boxes can be pooled
   • Profile allocation overhead

4. Early Buffer Optimization:

   • For small buffer sizes (< 10), insertion sort might be faster than sort_by
   • Consider adaptive sorting strategy

Low Priority

5. Buffer Capacity Hints:

   • Pre-allocate buffer based on heuristics (e.g., 2^distance)
   • Reduce reallocation overhead

6. SIMD Optimizations:

   • String comparison in sorting could use SIMD
   • Would require unsafe code and architecture-specific implementation

Benchmarks Created

benches/query_iterator_benchmarks.rs

Comprehensive criterion benchmarks covering:

• Ordered vs unordered comparison
• Distance scaling (0-99)
• Prefix vs standard mode
• Algorithm comparison
• Early termination (take/take_while)
• Sorting overhead stress test
• Dictionary size scaling

benches/query_profiling.rs

Flamegraph-focused benchmarks for identifying hotspots:

• Ordered query with moderate distance (2)
• Ordered query with large distance (10)
• Buffer sorting stress test
• Prefix query profiling
• Transposition algorithm profiling

Testing Coverage

tests/query_comprehensive_test.rs

19 comprehensive tests covering:

• All distance levels (0, 1, 2, 10, 99)
• Ordered and unordered queries
• Prefix mode
• All three algorithms
• Lexicographic ordering verification
• Edge cases and regression tests

Status: All 139 tests passing

Next Steps

1. ✅ Fix bugs in ordered query
2. ✅ Create comprehensive test suite
3. ✅ Create profiling benchmarks
4. 🔄 Generate flame graphs
5. ⏳ Analyze flame graphs to identify actual bottlenecks
6. ⏳ Implement optimizations based on profiling data
7. ⏳ Re-test and verify performance improvements

Conclusion

The ordered query iterator has been successfully debugged and now correctly:

1. Returns all results within max_distance
2. Maintains lexicographic ordering within each distance level

The primary potential bottleneck is the buffer sorting operation, which occurs once per distance level. Profiling is needed to determine if this is actually significant in practice, or if the state transition operations dominate the runtime.

The comprehensive benchmarks and tests provide a solid foundation for identifying and validating optimizations.