cqlite_core::storage::write_engine::merge

Struct KWayMerger

pub struct KWayMerger { /* private fields */ }

Expand description

K-way merger for combining multiple SSTables

Uses a min-heap to efficiently merge k sorted SSTable runs into a single output. Each run maintains a small peek buffer for efficient lookahead.

§Usage

// Create merger from input SSTable paths
let merger = KWayMerger::new(input_paths, &schema)?;

// Option 1: Full merge to output writer
let stats = merger.merge(&mut output_writer)?;

// Option 2: Incremental merge (step-by-step)
loop {
    match merger.step()? {
        MergeStep::Partition { key, rows } => {
            // Process partition
        }
        MergeStep::Complete => break,
    }
}

Implementations§

Source §

impl KWayMerger

Source

pub fn from_row_iterators( runs: Vec<Box<dyn SSTableRowIterator>>, schema: &TableSchema, ) -> Result<Self>

Build a k-way merger from pre-constructed run iterators (issue #2207).

Unlike KWayMerger::new, which opens each input SSTable and streams its WHOLE compaction scan, this accepts runs the caller has already scoped — the single-partition point-read path hands one run per candidate SSTable, each yielding ONLY the target partition’s entries (a seeked Vec or a key-filtered stream). The reconciliation, heap, and per-partition merge are IDENTICAL to the full-scan path — only the inputs are narrower — so the point path reconciles byte-identically to the scan.

runs must be non-empty and ordered newest-to-oldest (run index = LWW tie-break rank), exactly as KWayMerger::new’s input_paths are.

Source §

impl KWayMerger

Source

pub fn new_from_readers( readers: Vec<Arc<SSTableReader>>, schema: &TableSchema, scan_cancel: ScanCancel, token_bound: Option<ScanTokenBound>, ) -> Result<Self>

Build a k-way merger over already-open, possibly-SHARED SSTableReaders (issue #2346): a warm-handle cache can hand this constructor Arc clones of readers it keeps parsed across requests, instead of the per-request path-based open (KWayMerger::new_cancellable).

readers must be ordered newest-to-oldest generation (run index = LWW tie-break rank), exactly as the path-based constructors’ input_paths are. Reconciliation is byte-identical to the path-based merge — only WHO opens/owns the SSTableReader differs.

token_bound (issue #2412 §C / #2413 Option A): when Some, each reader’s Summary-guided walk is scoped to the split’s (start, end] token range so out-of-range partition bodies are never read; None walks the full ring. Compaction never uses this seam, so it keeps full-ring parity walks.

UDT-registry guard (issue #2346, WS1 #2345): this seam takes NO udt_registry parameter (see the module doc — a shared Arc reader has no &mut self for set_udt_registry). Each caller-supplied reader MUST therefore be opened WITH its UDT registry already resolved BEFORE it is wrapped in Arc. Wiring that resolution into the warm-handle registry caller is WS1 #2345’s responsibility — if a warm caller opens a UDT-bearing table’s reader WITHOUT the registry, frozen/nested UDT cells silently decode as Blob (the #1234 data-loss class), NOT an error. The merge layer cannot detect this here; #2345 owns that end-to-end guarantee.

Source §

impl KWayMerger

Source

pub fn new(input_paths: Vec<PathBuf>, schema: &TableSchema) -> Result<Self>

Create a new k-way merger from input SSTable paths

§Arguments

input_paths - Paths to input SSTable Data.db files (ordered newest to oldest)
schema - Table schema for schema-aware merging

§Returns

A new KWayMerger ready to merge the input SSTables.

§Errors

Returns an error if any input SSTable cannot be opened.

§Example

let input_paths = vec![
    PathBuf::from("data/nb-1-big-Data.db"),
    PathBuf::from("data/nb-2-big-Data.db"),
];
let merger = KWayMerger::new(input_paths, &schema)?;

Source

pub fn new_cancellable( input_paths: Vec<PathBuf>, schema: &TableSchema, scan_cancel: ScanCancel, ) -> Result<Self>

Like KWayMerger::new, but wires a cooperative ScanCancel into every input reader’s compaction scan (issue #2264). Used by the Flight do_get merge so a client disconnect abandons an in-flight, index-less full-Data.db walk within milliseconds instead of the ~1–2 min transport backstop.

Source

pub fn new_with_gc( input_paths: Vec<PathBuf>, schema: &TableSchema, gc_before_secs: Option<i64>, now_secs: Option<i64>, ) -> Result<Self>

Create a new k-way merger with explicit purge parameters.

Identical to KWayMerger::new but threads an explicit gc_grace cutoff (gc_before_secs) and TTL evaluation time (now_secs) into the merge. This is the deterministic entry point used by compact_sstables (the cqlite compact CLI command) and the compaction-parity harness (issue #842): Cassandra’s compaction takes the same gcBefore, so purge decisions cannot diverge between the two engines.

§Arguments

input_paths - Paths to input SSTable Data.db files (ordered newest to oldest)
schema - Table schema for schema-aware merging
gc_before_secs - gc_grace cutoff (seconds since epoch), or None to not purge
now_secs - “now” (seconds since epoch) for TTL expiry, or None for engine default

Source

pub fn new_with_gc_and_registry( input_paths: Vec<PathBuf>, schema: &TableSchema, gc_before_secs: Option<i64>, now_secs: Option<i64>, udt_registry: Option<UdtRegistry>, ) -> Result<Self>

Like KWayMerger::new_with_gc, but threads an authoritative UdtRegistry onto every input SSTable reader so the compaction read path can decode a top-level frozen<UDT> cell structurally (issue #1234). The one-shot compact_sstables_with_registry and the WriteEngine background compaction pass their configured registry here; the registry-free new/new_with_gc paths pass None.

Source

pub fn new_with_gc_and_registry_cancellable( input_paths: Vec<PathBuf>, schema: &TableSchema, gc_before_secs: Option<i64>, now_secs: Option<i64>, udt_registry: Option<UdtRegistry>, scan_cancel: ScanCancel, ) -> Result<Self>

K-way merge constructor that opens the input SSTables under a cooperative ScanCancel (issue #2264).

The token is wired onto every per-run reader so the compaction scan each run’s producer thread drives — which, for an index-less (Summary.db absent) SSTable, otherwise fully materialises the whole Data.db in one uninterruptible pass — polls it at a bounded interval and abandons the walk promptly when a driving Flight do_get is cancelled. new/new_with_gc* delegate here with a never-cancelled default token, so non-Flight callers are unaffected.

Source

pub fn with_purge_safe(self, purge_safe: bool) -> Self

Mark this merge as overlap-safe for tombstone purging (#921 finding 1).

Set true ONLY when the compaction inputs provably span EVERY SSTable for the table (a major/full compaction), so no non-included overlapping SSTable can hold data shadowed by a purged tombstone. When false (the default) the gc_grace purge stage is a strict no-op — tombstones are retained — which can never resurrect data in a partial compaction.

Source

pub fn with_max_purgeable_timestamp( self, max_purgeable_timestamp: Option<i64>, ) -> Self

Supply the overlap-aware max-purgeable timestamp for a PARTIAL compaction (#935, parity with Cassandra CompactionController.maxPurgeableTimestamp).

max_purgeable_timestamp is the MINIMUM write timestamp (markedForDeleteAt, micros) across every NON-INCLUDED overlapping SSTable for the table (their Statistics.db min-timestamp bound). With it set, the gc_grace purge stage additionally purges a tombstone in a partial compaction when the tombstone’s own deletion timestamp is STRICTLY LESS THAN this bound — proving it shadows nothing outside the compaction set. None keeps the conservative #921 behavior (a partial compaction does not purge). Ignored when purge_safe is true (a full compaction already has no non-included overlap, so the effective bound is +inf).

Source