Skip to main content

Module dedup

chronix_query

Module dedup 

Source
Expand description

K-way merge deduplication for overlapping segments.

When multiple segments for the same shard may overlap in time, their RecordBatch results must be merged and deduplicated. The dedup strategy is last-write-wins: on duplicate (series_key, timestamp), the value from the segment with the highest WAL sequence number is kept.

§Streaming Merge Architecture

The k-way merge uses a BinaryHeap of per-batch cursors and materialises the final result via arrow::compute::interleave instead of concat_batches + take. This avoids creating a full concatenated backing batch, cutting peak memory roughly in half.

§Algorithm

Instead of concatenating all batches and performing a full O(N log N) lexsort, this module uses a streaming k-way merge with a min-heap of segment cursors:

  1. Each input RecordBatch is internally sorted by (timestamp, series_hash, series_group_id).
  2. A BinaryHeap (used as a min-heap) maintains one cursor per batch, keyed on the current row’s sort key.
  3. On each step, the minimum entry is popped. If subsequent entries share the same dedup key (timestamp, group_id), they are also popped and the entry from the latest batch (highest batch_idx) wins (last-write-wins semantics).
  4. The merged result is collected as (cursor_idx, row_idx) pairs and materialised into a final RecordBatch via Arrow take on a concatenated backing batch.

Complexity: O(N log K) where K = number of overlapping batches, vs the previous O(N log N) full-sort approach. When segments are already sorted by timestamp (the common case), intra-batch sorting is nearly free.

Series identity is determined by the canonical form (measurement\0tag1=v1\0tag2=v2) — the FNV-1a hash is used as a fast grouping key for sort order, and unique canonical forms are mapped to integer group IDs to avoid O(N) heap-allocated strings while still preventing false-positive dedup from hash collisions.

Functions§

sort_merge_dedup
Merge and deduplicate multiple RecordBatches using k-way merge.
sort_merge_dedup_chunked
Streaming chunked variant of sort_merge_dedup.