Module queue_index 

Queue-Optimized Index Policy

This module extends the per-table index policy with queue-specific optimizations that ensure efficient priority queue operations.

Queue Access Patterns

Queues have specific access patterns that differ from general tables:

Operation	Pattern	Requirement
Enqueue	Insert at any position	O(log N) or better
Dequeue	Find minimum key, delete it	O(log N) find + O(1) delete
Peek	Read minimum key without deletion	O(log N)
Count	Get queue size	O(1)

Why Queue Tables Need ScanOptimized Policy

The dequeue operation requires “find minimum key”, which is:

• O(log N) with ordered index (ScanOptimized)
• O(N) without ordered index (WriteOptimized/Balanced with deferred sort)

For a queue with 10,000 tasks:

• With ScanOptimized: ~14 comparisons per dequeue
• With WriteOptimized: ~10,000 comparisons per dequeue

Avoiding Deferred-Sort Latency Spikes

The Balanced policy uses “deferred sorting” where writes are O(1) append and scans trigger O(N log N) sort-on-demand. This creates latency spikes:

Pop #1: 0.1ms (memtable small)
Pop #2: 0.1ms
...
Pop #1000: 50ms (sort triggered!) ← Latency spike
Pop #1001: 0.2ms (now sorted)

ScanOptimized maintains order on every write, giving predictable latency.

Queue Index Configuration

let config = QueueIndexConfig::new("task_queue")
    .with_priority_column("priority")
    .with_timestamp_column("ready_at")
    .with_fifo_column("sequence")
    .build();

Structs

CompositeQueueKey

Composite key for queue ordering

QueueIndex

A queue-optimized ordered index

QueueIndexConfig

Configuration for queue tables

QueueIndexStats

Statistics for a queue index

QueueTableRegistry

Registry extension for queue tables