Module units 

Unit-based compaction picks for one TWCS window.

Picks select a contiguous interval of units in a fixed order. Grouping prefers rewriting related files together, but input limits and fallback paths may split groups or use single-file units. Separate admission checks preserve each pick’s progress guarantees under the assumptions below.

• pick_active_l1 reduces the L1 file count of the active window.
• pick_small_l1 reduces small L1 files without rewriting large peers.
• pick_closed_merge only merges intervals of an inactive window whose outputs cannot add conflicts. Compaction outputs stay inside the bounding box of the inputs, so they can only overlap files intruding on that box.

When a window’s split-unit conflict graph is too dense to materialize, pick_closed_merge falls back to a bounded file reduction and admits it only when the same conflict bound holds.

Termination

Let P be the number of conflicting file pairs (Extent::conflicts) in an inactive window and N its file count. A merge removes every pair among its inputs. Its outputs are one sorted run with no internal conflicts, so they only conflict with the I files intruding on the inputs’ box, at most outputs · I pairs. An inactive pick only merges inputs that had at least as many pairs with other files, so P does not grow; without intruders the inputs are closed and add no pairs. Every inactive pick either resolves a pair (P drops) or removes a file (P does not grow and N drops), so (P, N) strictly decreases in lexicographic order until the window receives new writes. Active-window picks may add conflicts, so each of them must remove a file: N strictly decreases.

The argument relies on how the compactor writes outputs:

• Outputs hold a subset of the input rows, so each output’s time and key bounds lie inside the inputs’ bounding box.
• Outputs are one stream in (key, time) order. For regions with a primary key, the writer only splits between complete series, so output key ranges are disjoint. Without a primary key, outputs have disjoint or touching time ranges. Neither is an Extent::conflicts pair.
• A split only starts a new file once the current one reaches the size threshold, and outputs are not larger than inputs in total, so PickLimits::predicted_outputs bounds the output count.

test_closed_merges_terminate and test_active_l1_picks_terminate replay random windows with outputs written under these rules.

Structs

ClosedMergeCandidate 🔒

A scored interval retained until the best candidate(s) are materialized.

ClosedMergeOptions 🔒

Thresholds of the closed merge pick.

DisjointSet 🔒

Union-find over file indices; each root is the smallest index of its set.

Extent 🔒

Time and primary key bounds of a file or a group of files.

ExtentIndex 🔒

Files of a window ordered by their lower primary key, in a segment tree holding the bounds of each subtree.

IntervalStats 🔒

Totals of a contiguous interval of units.

PickLimits 🔒

Output size limits and input limits shared by both picks.

SubtreeBounds 🔒

Key and time bounds of the files in a subtree of ExtentIndex.

Unit 🔒

Files that are compacted together.

UnitPick 🔒

A selected compaction input.

Enums

UpperKey 🔒

Upper primary key bound, ordered after every key when unknown.

Constants

CONFLICT_GRAPH_BUDGET 🔒

Maximum number of index nodes visited while building conflict structures for a pick. Above this, the picker falls back to a bounded file reduction instead of materializing an unbounded conflict graph.

MAX_REWRITE_FILES_PER_REDUCED_FILE 🔒

An L1 file reduction may rewrite at most this many output files’ worth of bytes per SST it removes.

SMALL_L1_SIZE_FACTOR 🔒

A small L1 file occupies at most one quarter of the output size budget.

Functions

adds_no_conflicts 🔒

Whether merging units into outputs files adds no more conflicts than their files have with other files. Outputs stay inside the bounding box of the inputs, so each of them may conflict with every file intruding on that box. An interval without intruders is closed and adds no conflicts.

close_units 🔒

Merges units until no file intrudes on a unit it does not belong to.

collect_inputs 🔒

conflict_units 🔒

Groups files into connected components of Extent::conflicts, each with its number of conflicting pairs. Each file only checks the files the index finds near it: O((N + M) log N) for M pairs of files whose key and time ranges meet.

extents_of 🔒

for_each_interval 🔒

Visits every contiguous interval of units with at most max_input_files files: O(U · K) intervals for an input limit K. Each interval counts the conflicts of its split files from split_conflicts (see split_conflicts) with a binary search; an empty split_conflicts skips them.

has_balanced_components 🔒

Whether every group of conflicting files among units is balanced, see has_balanced_runs. Runs of separate groups never overlap, so pairing a dominant run with the peer of another group would hide it. Takes O(K²) conflict checks for K files.

has_balanced_runs 🔒

Whether the largest sorted run among files holds at most tolerance bytes more than all other runs together. Runs are built greedily in time order, which takes O(K²) conflict checks for K files.

interval_stats_exact 🔒

Totals of an interval without materializing split_conflicts.

is_admissible_dense_interval 🔒

File reduction and rewrite limits are checked by the interval picker; each dense candidate must also respect the closed-window conflict policy.

is_more_efficient 🔒

Whether benefit per size bytes beats the best so far; ties prefer fewer bytes, then the earlier interval.

is_single_key 🔒

pick_active_l1 🔒

Picks L1 files of the active window whose compaction removes files.

pick_active_l1_with_budget 🔒

pick_active_l1 with an explicit work budget, so tests can exercise the single-file fallback without a window-sized conflict graph.

pick_closed_merge 🔒

Picks an interval of units among all files of an inactive window.

pick_closed_merge_by_class 🔒

Discovers file reduction and overlap resolution together, sharing both the conflict graph and interval traversal. The first slot is file reduction.

pick_closed_merge_candidates 🔒

pick_closed_merge_with_budget 🔒

pick_closed_merge with an explicit work budget, so tests can exercise the dense fallback without building a window-sized conflict graph.

pick_dense_closed_merge 🔒

Picks a bounded file reduction when the split-unit conflict graph is too dense to materialize.

pick_reducing_interval 🔒

Picks the interval of units that removes the most files within the rewrite budget, then rewrites the fewest bytes.

pick_reducing_interval_where 🔒

Selects a reducing interval of sorted units, with an additional filter so the dense fallback can retry without duplicating the reduction guards.

pick_small_l1 🔒

Reduces small L1 files left behind by a closed merge, including in settling windows. The input bytes fit in one output and no input dominates its peers, so each merge removes files without repeatedly rewriting an accumulator.

single_file_units 🔒

Treats every file as its own split unit, for the dense fallback that cannot afford to build conflict components.

sort_units 🔒

Orders units by minimum primary key, then by time, so adjacent units are key-adjacent. Compaction outputs and time-sliced flushes split a window by key ranges, so merging neighbors in this order keeps outputs from covering the key ranges of files left behind.

split_conflicts 🔒

Positions of the split units each unit conflicts with, sorted. Files of different units never conflict, so only split files have any.

split_oversized_units 🔒

Replaces units with more files than one compaction accepts by single files, which are no longer closed.