Skip to main content

mito2/compaction/
twcs.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15mod units;
16
17use std::collections::hash_map::Entry;
18use std::collections::{BTreeMap, HashMap, HashSet};
19use std::fmt::Debug;
20use std::sync::{Arc, LazyLock};
21
22use common_base::readable_size::ReadableSize;
23use common_telemetry::{debug, info};
24use common_time::Timestamp;
25use common_time::range::TimestampRange;
26use common_time::timestamp::TimeUnit;
27use common_time::timestamp_millis::BucketAligned;
28use prometheus::{HistogramVec, IntCounterVec};
29use snafu::ResultExt;
30use store_api::storage::RegionId;
31
32use crate::compaction::CompactionOutput;
33use crate::compaction::buckets::infer_time_bucket;
34use crate::compaction::compactor::CompactionRegion;
35use crate::compaction::picker::{Picker, PickerOutput, get_expired_ssts};
36use crate::compaction::run::{
37    Ranged, SortedRun, files_overlap, files_overlap_inclusive, find_sorted_runs,
38    find_sorted_runs_by_time_range, merge_primary_key_ranges, primary_key_ranges_overlap,
39};
40use crate::compaction::twcs::units::{ClosedMergeOptions, PickLimits};
41use crate::error::{JoinSnafu, Result};
42use crate::metrics::{TWCS_PICK_ELAPSED, TWCS_SCANNED_WINDOWS};
43use crate::region::options::MergeMode;
44use crate::sst::file::{self, FileHandle, Level, overlaps};
45use crate::sst::primary_key::PrimaryKeyRangeMapper;
46use crate::sst::version::LevelMeta;
47
48const LEVEL_COMPACTED: Level = 1;
49
50/// Scheduling priority of a window's pick. Earlier classes are scheduled first,
51/// and newer windows first within a class.
52#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
53pub(crate) enum PickClass {
54    /// Merges L0 files, which also absorbs late data of inactive windows.
55    L0Merge,
56    /// Merges files to reduce the window's file count.
57    FileReduction,
58    /// Merges files of an inactive window to resolve their overlaps.
59    OverlapResolution,
60}
61
62impl PickClass {
63    pub(crate) fn as_str(self) -> &'static str {
64        match self {
65            Self::L0Merge => "l0_merge",
66            Self::FileReduction => "file_reduction",
67            Self::OverlapResolution => "overlap_resolution",
68        }
69    }
70}
71
72/// Compaction inputs picked for one window.
73#[derive(Debug)]
74pub(crate) struct WindowPick {
75    pub(crate) class: PickClass,
76    /// Name of the strategy that picked the inputs, for logs.
77    branch: &'static str,
78    pub(crate) inputs: Vec<FileHandle>,
79    /// Number of sorted runs or units the strategy considered, for logs.
80    found_runs: usize,
81}
82
83/// A discovered alternative, not yet selected or admitted by the scheduler.
84#[derive(Debug)]
85pub(crate) struct WindowCandidate {
86    pub(crate) window: i64,
87    pub(crate) pick: WindowPick,
88}
89
90/// Discovery snapshot retained until the scheduler chooses its alternatives.
91/// Only selected candidates incur tombstone checks and pick-result logging.
92pub(crate) struct TwcsCandidates {
93    pub(crate) candidates: Vec<WindowCandidate>,
94    expired_ssts: Vec<FileHandle>,
95    time_window_size: i64,
96    windows: Arc<BTreeMap<i64, Window>>,
97    active_window: Option<i64>,
98    primary_key_mapper: Arc<PrimaryKeyRangeMapper>,
99    region_id: RegionId,
100    append_mode: bool,
101    max_output_file_size: Option<u64>,
102}
103
104impl TwcsCandidates {
105    /// Materializes the selected candidates off the async runtime. The snapshot
106    /// supplies unselected peers for tombstone safety, even after truncation.
107    pub(crate) async fn finish(self) -> Result<PickerOutput> {
108        common_runtime::spawn_blocking_compact(move || {
109            let outputs = self
110                .candidates
111                .into_iter()
112                .rev()
113                .map(|candidate| {
114                    let WindowCandidate { window, pick } = candidate;
115                    let files = &self.windows[&window];
116                    let filter_deleted = !self.append_mode
117                        && !window_has_overlap(files, &self.windows)
118                        && !selected_overlaps_unselected(
119                            &pick.inputs,
120                            files,
121                            &self.primary_key_mapper,
122                        );
123                    if pick.inputs.len() > 1 {
124                        log_pick_result(
125                            self.region_id,
126                            window,
127                            self.active_window,
128                            &pick,
129                            files.files.len(),
130                            self.max_output_file_size,
131                            filter_deleted,
132                        );
133                    }
134                    CompactionOutput {
135                        output_level: LEVEL_COMPACTED,
136                        inputs: pick.inputs,
137                        filter_deleted,
138                        output_time_range: None,
139                    }
140                })
141                .collect();
142            PickerOutput {
143                outputs,
144                expired_ssts: self.expired_ssts,
145                time_window_size: self.time_window_size,
146                // The picker treats zero as unlimited; the writer must not split every batch.
147                max_file_size: self
148                    .max_output_file_size
149                    .filter(|size| *size > 0)
150                    .map(|size| size as usize),
151            }
152        })
153        .await
154        .context(JoinSnafu)
155    }
156}
157
158/// Snapshot-wide inputs shared by each independent window strategy.
159struct WindowPickContext<'a> {
160    all_candidates: bool,
161    region_id: RegionId,
162    active_window: Option<i64>,
163    time_window_size: Option<i64>,
164    region_sequence: u64,
165    mapper: &'a PrimaryKeyRangeMapper,
166}
167
168struct WindowOutputContext {
169    all_candidates: bool,
170    expired_ssts: Vec<FileHandle>,
171    active_window: Option<i64>,
172    time_window_size: Option<i64>,
173    max_outputs: Option<usize>,
174    primary_key_mapper: Arc<PrimaryKeyRangeMapper>,
175}
176
177/// A mixed L0/L1 compaction may rewrite at most this many L1 rows per L0 row.
178const MAX_L1_L0_ROW_RATIO: usize = 2;
179
180/// Default maximum number of input SST files in one compaction input.
181const DEFAULT_MAX_INPUT_FILES: usize = 16;
182
183const MAX_INPUT_FILES_ENV: &str = "GREPTIME_TWCS_MAX_INPUT_FILES";
184
185/// Maximum number of input SST files in one compaction input.
186/// Configurable via [`MAX_INPUT_FILES_ENV`].
187static MAX_INPUT_FILES: LazyLock<usize> = LazyLock::new(|| {
188    let env_value = std::env::var(MAX_INPUT_FILES_ENV).ok();
189    parse_max_input_files(env_value.as_deref())
190});
191
192/// A closed merge in an inactive window may take this many times
193/// [`MAX_INPUT_FILES`]. Resolving overlaps across a whole window needs all of
194/// its overlapping files at once, and each byte is rewritten once per window.
195const CLOSED_MERGE_INPUT_FACTOR: usize = 4;
196
197fn parse_max_input_files(env_value: Option<&str>) -> usize {
198    env_value
199        .and_then(|env_value| env_value.parse().ok())
200        .filter(|max_input_files| *max_input_files >= 2)
201        .unwrap_or(DEFAULT_MAX_INPUT_FILES)
202}
203
204/// Cloneable planning metric handles, shared with spawned window evaluations.
205#[derive(Clone, Debug)]
206pub(crate) struct TwcsPickMetrics {
207    elapsed: HistogramVec,
208    scanned_windows: IntCounterVec,
209}
210
211impl Default for TwcsPickMetrics {
212    fn default() -> Self {
213        Self {
214            elapsed: TWCS_PICK_ELAPSED.clone(),
215            scanned_windows: TWCS_SCANNED_WINDOWS.clone(),
216        }
217    }
218}
219
220/// `TwcsPicker` picks files of which the max timestamp are in the same time window as compaction
221/// candidates.
222#[derive(Clone, Debug)]
223pub struct TwcsPicker {
224    /// Production uses registered handles; tests can use unregistered instances.
225    pub(crate) metrics: TwcsPickMetrics,
226    /// Minimum file num to trigger a compaction in the active window.
227    pub trigger_file_num: usize,
228    /// Minimum L1 file num to allow a safety compaction in the active window.
229    pub active_window_l1_merge_trigger: usize,
230    /// Minimum file num to trigger a compaction in an inactive window.
231    pub inactive_window_trigger_file_num: usize,
232    /// Minimum L1 file num to trigger a compaction in an inactive window.
233    pub inactive_window_l1_merge_trigger: usize,
234    /// Compaction time window in seconds.
235    pub time_window_seconds: Option<i64>,
236    /// Max allowed compaction output file size. The picker also uses it to predict
237    /// output splits when scoring candidates.
238    pub max_output_file_size: Option<u64>,
239    /// Whether the target region is in append mode.
240    pub append_mode: bool,
241    /// LastNonNull picks expand to an overlap closure, so cannot use partial
242    /// small-file reductions that must leave large peers untouched.
243    pub(crate) merge_mode: MergeMode,
244    /// Max background compaction tasks.
245    pub max_background_tasks: Option<usize>,
246    /// Optional time range that constrains candidate compaction windows.
247    pub(crate) time_range: Option<TimestampRange>,
248    /// Picks the active window like an inactive one. Manual compactions set it,
249    /// so a window that stopped receiving writes still gets its overlaps
250    /// resolved.
251    pub(crate) all_windows_inactive: bool,
252}
253
254impl TwcsPicker {
255    /// Discovers window alternatives. Stateless callers retain their legacy
256    /// first-strategy ordering and early output limit; full discovery does not
257    /// rank or truncate candidates.
258    async fn build_candidates(
259        &self,
260        region_id: RegionId,
261        time_windows: BTreeMap<i64, Window>,
262        context: WindowOutputContext,
263    ) -> Result<TwcsCandidates> {
264        let all_candidates = context.all_candidates;
265        let mode = if all_candidates { "fair" } else { "stateless" };
266        let _timer = self
267            .metrics
268            .elapsed
269            .with_label_values(&[mode])
270            .start_timer();
271        let scanned_windows = self.metrics.scanned_windows.with_label_values(&[mode]);
272        let WindowOutputContext {
273            all_candidates: _,
274            expired_ssts,
275            active_window,
276            time_window_size,
277            max_outputs,
278            primary_key_mapper,
279        } = context;
280        let region_sequence = time_windows
281            .values()
282            .flat_map(|window| window.files())
283            .filter_map(|file| file.meta_ref().sequence)
284            .map(|sequence| sequence.get())
285            .max()
286            .unwrap_or(0);
287        let windows = time_windows
288            .values()
289            .rev()
290            .filter(|window| {
291                !window.files.is_empty()
292                    && self.time_range.as_ref().is_none_or(|time_range| {
293                        time_window_size.is_none_or(|time_window_size| {
294                            time_window_intersects_range(
295                                window.time_window,
296                                time_window_size,
297                                time_range,
298                            )
299                        })
300                    })
301            })
302            .map(|window| window.time_window)
303            .collect::<Vec<_>>();
304        let time_windows = Arc::new(time_windows);
305        let max_outputs = max_outputs.unwrap_or(usize::MAX);
306        // Enumerating all LastNonNull seeds must not increase the number of
307        // concurrently planned windows along with the output limit.
308        let chunk_size = self.max_background_tasks.unwrap_or(windows.len()).max(1);
309        let mut picks = Vec::new();
310        for chunk in windows.chunks(chunk_size) {
311            let mut handles = Vec::with_capacity(chunk.len());
312            for &window in chunk {
313                let picker = self.clone();
314                let time_windows = time_windows.clone();
315                let primary_key_mapper = primary_key_mapper.clone();
316                let scanned_windows = scanned_windows.clone();
317                handles.push(common_runtime::spawn_blocking_compact(move || {
318                    let mut picks = Vec::new();
319                    if let Some(files) = time_windows.get(&window) {
320                        scanned_windows.inc();
321                        picks.extend(
322                            picker
323                                .pick_window(
324                                    files,
325                                    &WindowPickContext {
326                                        all_candidates,
327                                        region_id,
328                                        active_window,
329                                        time_window_size,
330                                        region_sequence,
331                                        mapper: &primary_key_mapper,
332                                    },
333                                )
334                                .into_iter()
335                                .map(|pick| WindowCandidate { window, pick }),
336                        );
337                    }
338                    picks
339                }));
340                tokio::task::yield_now().await;
341            }
342            for result in futures::future::join_all(handles).await {
343                picks.extend(result.context(JoinSnafu)?);
344            }
345            // Windows are visited newest first, so older windows cannot displace
346            // a full set of picks of the first class.
347            if !all_candidates
348                && picks
349                    .iter()
350                    .filter(|candidate| candidate.pick.class == PickClass::L0Merge)
351                    .count()
352                    >= max_outputs
353            {
354                break;
355            }
356        }
357
358        if !all_candidates {
359            // Manual/stateless callers retain their existing early-exit policy.
360            picks.sort_by_key(|candidate| candidate.pick.class);
361            if picks.len() > max_outputs {
362                debug!(
363                    "Region ({:?}) compaction output limit ({}) reached, remaining candidates discarded",
364                    region_id, max_outputs
365                );
366                picks.truncate(max_outputs);
367            }
368        }
369        Ok(TwcsCandidates {
370            candidates: picks,
371            expired_ssts,
372            // Snapshot discovery always supplies the width; direct window tests
373            // may omit it to disable settling-window behavior.
374            time_window_size: time_window_size.unwrap_or_default(),
375            windows: time_windows,
376            active_window,
377            primary_key_mapper,
378            region_id,
379            append_mode: self.append_mode,
380            max_output_file_size: self.max_output_file_size,
381        })
382    }
383
384    /// Prepares one window once. Fair discovery exposes independent alternatives;
385    /// stateless/manual discovery retains the first eligible strategy.
386    fn pick_window(&self, window: &Window, context: &WindowPickContext<'_>) -> Vec<WindowPick> {
387        let WindowPickContext {
388            all_candidates,
389            region_id,
390            active_window,
391            time_window_size,
392            region_sequence,
393            mapper,
394        } = *context;
395        // Shared files remain in the window map for overlap/tombstone safety,
396        // but only the table executor may rewrite them.
397        let mut files: Vec<_> = window
398            .files()
399            .filter(|file| file.level() < file::LEVEL_SHARED)
400            .cloned()
401            .collect();
402        let quiet = is_quiet_window(&files, region_sequence);
403
404        // Filter out large files in append mode - they won't benefit from compaction
405        if self.append_mode
406            && let Some(max_size) = self.max_output_file_size
407        {
408            let (kept_files, ignored_files) =
409                files.into_iter().partition(|file| file.size() <= max_size);
410            files = kept_files;
411            if !ignored_files.is_empty() {
412                info!(
413                    "Skipped {} large files in append mode for region {}, window {}, max_size: {}",
414                    ignored_files.len(),
415                    region_id,
416                    window.time_window,
417                    max_size
418                );
419            }
420        }
421
422        let (l0_files, l1_files): (Vec<_>, Vec<_>) =
423            files.into_iter().partition(|file| file.level() == 0);
424        if !self.all_windows_inactive && active_window == Some(window.time_window) {
425            self.pick_active_window(l0_files, l1_files, mapper, all_candidates)
426        } else if window.files.len() < self.inactive_window_trigger_file_num
427            && l1_files.len() < self.inactive_window_l1_merge_trigger
428        {
429            Vec::new()
430        } else {
431            let settling = !self.all_windows_inactive
432                && is_settling_window(window.time_window, active_window, time_window_size);
433            let num_l1_files = l1_files.len();
434            let mut picks = self.pick_inactive_window(
435                l0_files,
436                l1_files,
437                mapper,
438                settling,
439                quiet,
440                all_candidates,
441            );
442            let needs_reduction = if all_candidates {
443                !picks
444                    .iter()
445                    .any(|pick| pick.class == PickClass::FileReduction)
446            } else {
447                picks.is_empty()
448            };
449            if needs_reduction
450                && self.merge_mode != MergeMode::LastNonNull
451                && num_l1_files >= self.inactive_window_l1_merge_trigger
452                // Include even append-mode files excluded from normal picks:
453                // a small-file merge must not add conflicts with large peers.
454                && let Some(pick) = units::pick_small_l1(&window.files, mapper, self.pick_limits())
455            {
456                picks.push(WindowPick {
457                    class: PickClass::FileReduction,
458                    branch: "inactive:pick_small_l1",
459                    inputs: pick.inputs,
460                    found_runs: pick.units,
461                });
462            }
463            picks
464        }
465    }
466
467    /// The active window keeps receiving writes, so every pick must reduce its
468    /// file count:
469    ///
470    /// 1. Merge L0 files once they reach the trigger.
471    /// 2. Otherwise, merge L1 files once they reach the L1 safety trigger. L1
472    ///    files are merged separately from L0 files to avoid chained rewrites.
473    ///
474    /// Fair discovery considers both strategies; stateless/manual discovery
475    /// stops at the first eligible one.
476    ///
477    /// Overlaps are left for the window to resolve once it becomes inactive:
478    /// resolving them while data keeps arriving rewrites the window repeatedly,
479    /// and leaves a dominant run that blocks the inactive-window merge.
480    fn pick_active_window(
481        &self,
482        l0_files: Vec<FileHandle>,
483        l1_files: Vec<FileHandle>,
484        mapper: &PrimaryKeyRangeMapper,
485        all_candidates: bool,
486    ) -> Vec<WindowPick> {
487        let mut picks = Vec::new();
488        if l0_files.len() >= self.trigger_file_num {
489            let (inputs, found_runs) = pick_candidate_files(
490                l0_files,
491                self.max_output_file_size,
492                pick_count_first,
493                mapper,
494            );
495            if !inputs.is_empty() {
496                picks.push(WindowPick {
497                    class: PickClass::L0Merge,
498                    branch: "active:pick_count_first",
499                    inputs,
500                    found_runs,
501                });
502                if !all_candidates {
503                    return picks;
504                }
505            }
506        }
507        // Fair discovery must expose L1 even when L0 has an eligible merge.
508        if l1_files.len() >= self.active_window_l1_merge_trigger
509            && let Some(pick) = units::pick_active_l1(&l1_files, mapper, self.pick_limits())
510        {
511            picks.push(WindowPick {
512                class: PickClass::FileReduction,
513                branch: "active:pick_l1_file_reduction",
514                inputs: pick.inputs,
515                found_runs: pick.units,
516            });
517        }
518        picks
519    }
520
521    /// An inactive window should converge at a bounded rewrite cost:
522    ///
523    /// 1. Absorb L0 files (late data), see [`pick_inactive_l0`].
524    /// 2. Otherwise, merge a closed group of files that resolves overlaps or
525    ///    removes files, see [`units::pick_closed_merge`]. Pure file reduction
526    ///    waits for the L1 trigger; overlap resolution does not.
527    ///
528    /// Fair discovery keeps the L0 candidate and both closed-merge classes as
529    /// alternatives; stateless/manual discovery retains the fallback order.
530    ///
531    /// A `settling` window is the one right before the active window. Late data
532    /// still lands there, and any rewrite of its overlapping files would be
533    /// repeated once more late data arrives. It only merges L0 files among
534    /// themselves and conflict-free files, and leaves overlaps for when the
535    /// window is older.
536    ///
537    /// Late data can also land in older windows. Resolving such an overlap
538    /// rewrites a dominant sorted run for a small peer, which would repeat for
539    /// every late flush, so it waits until the window is `quiet`: the region
540    /// has written a window's worth of rows elsewhere since the window last
541    /// received data. Each quiet period then pays for at most one such rewrite.
542    /// A manual compaction is a one-off request to resolve overlaps, so it does
543    /// not wait.
544    ///
545    /// Without new writes each pick consumes an L0 file or makes progress on
546    /// the closed merge's termination measure, so the window stops compacting.
547    fn pick_inactive_window(
548        &self,
549        l0_files: Vec<FileHandle>,
550        l1_files: Vec<FileHandle>,
551        mapper: &PrimaryKeyRangeMapper,
552        settling: bool,
553        quiet: bool,
554        all_candidates: bool,
555    ) -> Vec<WindowPick> {
556        let num_l1_files = l1_files.len();
557        let mut picks = Vec::new();
558        if !l0_files.is_empty()
559            && let Some((inputs, found_runs, branch)) = pick_inactive_l0(
560                l0_files.clone(),
561                (!settling).then_some(l1_files.as_slice()),
562                self.max_output_file_size,
563                mapper,
564            )
565        {
566            picks.push(WindowPick {
567                class: PickClass::L0Merge,
568                branch,
569                inputs,
570                found_runs,
571            });
572            if !all_candidates {
573                return picks;
574            }
575        }
576
577        let options = ClosedMergeOptions {
578            limits: self.closed_merge_limits(),
579            allow_file_reduction: num_l1_files >= self.inactive_window_l1_merge_trigger,
580            allow_conflicts: !settling,
581            allow_unbalanced: (quiet || self.all_windows_inactive) && !settling,
582        };
583        // Both classes must see L0 peers: they can absorb late files stranded
584        // by the L0 strategies, and must not introduce conflicts with them.
585        let mut files = l1_files;
586        files.extend(l0_files);
587        let candidates = if all_candidates {
588            units::pick_closed_merge_by_class(&files, mapper, options)
589        } else {
590            [units::pick_closed_merge(&files, mapper, options), None]
591        };
592        for pick in candidates.into_iter().flatten() {
593            let (class, branch) = if pick.dense_fallback {
594                (PickClass::FileReduction, "inactive:dense_file_reduction")
595            } else if pick.reduces_files {
596                (PickClass::FileReduction, "inactive:pick_l1_file_reduction")
597            } else {
598                (PickClass::OverlapResolution, "inactive:pick_l1_overlap")
599            };
600            picks.push(WindowPick {
601                class,
602                branch,
603                inputs: pick.inputs,
604                found_runs: pick.units,
605            });
606        }
607        picks
608    }
609
610    fn pick_limits(&self) -> PickLimits {
611        PickLimits {
612            max_output_file_size: self.max_output_file_size,
613            max_input_files: *MAX_INPUT_FILES,
614        }
615    }
616
617    fn closed_merge_limits(&self) -> PickLimits {
618        PickLimits {
619            max_input_files: MAX_INPUT_FILES.saturating_mul(CLOSED_MERGE_INPUT_FACTOR),
620            ..self.pick_limits()
621        }
622    }
623}
624
625/// Absorbs L0 files of an inactive window, in order of preference:
626///
627/// 1. Balanced merges of L0 files, which leave L1 files untouched.
628/// 2. Mixed merges that bypass the balance checks, but only when the total
629///    rewrite fits in the output file budget, bounding write amplification.
630///    Skipped without `l1_files`.
631/// 3. Merges of L0 files among themselves regardless of balance. The rewrite
632///    is bounded by the L0 bytes and leaves large compacted files untouched.
633///
634/// Every pick consumes L0 files.
635fn pick_inactive_l0(
636    l0_files: Vec<FileHandle>,
637    l1_files: Option<&[FileHandle]>,
638    max_output_file_size: Option<u64>,
639    mapper: &PrimaryKeyRangeMapper,
640) -> Option<(Vec<FileHandle>, usize, &'static str)> {
641    let (inputs, found_runs) = pick_candidate_files(
642        l0_files.clone(),
643        max_output_file_size,
644        pick_count_first,
645        mapper,
646    );
647    if !inputs.is_empty() {
648        return Some((inputs, found_runs, "inactive:pick_count_first"));
649    }
650    if let Some(l1_files) = l1_files {
651        let mut all_files = l0_files.clone();
652        all_files.extend_from_slice(l1_files);
653        let (inputs, found_runs) = pick_candidate_files(
654            all_files,
655            max_output_file_size,
656            pick_mixed_within_budget,
657            mapper,
658        );
659        if !inputs.is_empty() {
660            return Some((inputs, found_runs, "inactive:pick_mixed_within_budget"));
661        }
662    }
663    let (inputs, found_runs) = pick_candidate_files(
664        l0_files,
665        max_output_file_size,
666        pick_unbalanced_count_first,
667        mapper,
668    );
669    (!inputs.is_empty()).then_some((inputs, found_runs, "inactive:pick_unbalanced_count_first"))
670}
671
672type CandidatePicker =
673    fn(Vec<SortedRun<FileHandle>>, Option<u64>, &PrimaryKeyRangeMapper) -> Vec<FileHandle>;
674
675fn pick_candidate_files(
676    mut files: Vec<FileHandle>,
677    max_output_file_size: Option<u64>,
678    picker: CandidatePicker,
679    mapper: &PrimaryKeyRangeMapper,
680) -> (Vec<FileHandle>, usize) {
681    let sorted_runs = if files.len() < 1024 {
682        find_sorted_runs(&mut files, |lhs, rhs| files_overlap(lhs, rhs, mapper))
683    } else {
684        find_sorted_runs_by_time_range(&mut files)
685    };
686    let found_runs = sorted_runs.len();
687    (
688        picker(sorted_runs, max_output_file_size, mapper),
689        found_runs,
690    )
691}
692
693#[derive(Debug)]
694struct OrderedFile<'a> {
695    file: &'a FileHandle,
696    run_id: usize,
697    position_in_run: usize,
698    /// Primary key range in the pick's schema, resolved once per pick.
699    primary_key_range: Option<(bytes::Bytes, bytes::Bytes)>,
700}
701
702impl OrderedFile<'_> {
703    /// Same as [`files_overlap_inclusive`] with the cached key ranges.
704    fn overlaps_inclusive(&self, other: &Self) -> bool {
705        self.file.overlap_inclusive(other.file)
706            && match (&self.primary_key_range, &other.primary_key_range) {
707                (Some(lhs), Some(rhs)) => primary_key_ranges_overlap(lhs, rhs),
708                _ => true,
709            }
710    }
711}
712
713/// Metrics of a candidate compaction input, accumulated one file at a time.
714#[derive(Debug, Default)]
715struct Candidate {
716    /// Number of input files.
717    num_files: usize,
718    /// Total input bytes.
719    total_size: usize,
720    /// Size of the largest single input file.
721    largest_file_size: usize,
722    /// Files in the interval that overlap another interval file from a different
723    /// sorted run. Resolving these overlaps is what reduces sorted runs.
724    overlap_participants: usize,
725    /// Number of rows contributed by uncompacted files.
726    l0_rows: usize,
727    /// Number of rows contributed by compacted files.
728    l1_rows: usize,
729    has_l0: bool,
730    has_l1: bool,
731    /// Whether at least one file uses 0 to represent an unknown row count.
732    has_unknown_rows: bool,
733}
734
735impl Candidate {
736    /// Absorbs `file` into the candidate. `preceding` holds the interval files added
737    /// before it and `participations` tracks which of them already participate in an
738    /// intra-interval overlap; both exist only for overlap accounting.
739    fn absorb(
740        &mut self,
741        file: &OrderedFile,
742        preceding: &[OrderedFile],
743        participations: &mut Vec<bool>,
744    ) {
745        self.absorb_file(file.file);
746
747        let mut participates = false;
748        for (offset, other) in preceding.iter().enumerate() {
749            if file.run_id != other.run_id && file.overlaps_inclusive(other) {
750                if !participations[offset] {
751                    participations[offset] = true;
752                    self.overlap_participants += 1;
753                }
754                participates = true;
755            }
756        }
757        participations.push(participates);
758        if participates {
759            self.overlap_participants += 1;
760        }
761    }
762
763    /// Accumulates file statistics independently of overlap accounting.
764    fn absorb_file(&mut self, file: &FileHandle) {
765        self.num_files += 1;
766        let file_size = file.size() as usize;
767        self.total_size += file_size;
768        self.largest_file_size = self.largest_file_size.max(file_size);
769        self.absorb_level_rows(file);
770    }
771
772    fn absorb_level_rows(&mut self, file: &FileHandle) {
773        let num_rows = file.num_rows();
774        self.has_unknown_rows |= num_rows == 0;
775        if file.level() == 0 {
776            self.has_l0 = true;
777            self.l0_rows = self.l0_rows.saturating_add(num_rows);
778        } else {
779            self.has_l1 = true;
780            self.l1_rows = self.l1_rows.saturating_add(num_rows);
781        }
782    }
783
784    /// Predicted number of output files after compacting this candidate. Compaction
785    /// output holds at most the input bytes, so a split threshold of
786    /// `max_output_file_size` yields at most `ceil(total_size / threshold)` files.
787    /// Without a threshold the output is a single file.
788    fn predicted_output_files(&self, max_output_file_size: Option<u64>) -> usize {
789        match max_output_file_size {
790            Some(max) if max > 0 => self.total_size.div_ceil(max as usize).max(1),
791            _ => 1,
792        }
793    }
794
795    /// Net file count reduction compacting this candidate would achieve, i.e. how
796    /// many fewer physical SSTs the window holds afterwards. Zero when the output
797    /// would be split back into at least as many files as the input.
798    fn file_reduction(&self, max_output_file_size: Option<u64>) -> usize {
799        self.num_files
800            .saturating_sub(self.predicted_output_files(max_output_file_size))
801    }
802
803    /// A large historical file is only rewritten once its peers contribute at least
804    /// the same amount of data, so every rewrite moves it into a larger size tier.
805    fn is_balanced(&self) -> bool {
806        self.largest_file_size <= self.total_size - self.largest_file_size
807    }
808
809    /// Bounds rewrite amplification for mixed L0/L1 candidates. Legacy files with
810    /// unknown row counts retain the byte-balance behavior above.
811    fn has_balanced_level_rows(&self) -> bool {
812        !self.has_l0
813            || !self.has_l1
814            || self.has_unknown_rows
815            || self.l1_rows <= self.l0_rows.saturating_mul(MAX_L1_L0_ROW_RATIO)
816    }
817
818    fn has_mixed_levels(&self) -> bool {
819        self.has_l0 && self.has_l1
820    }
821
822    /// Whether rewriting this candidate stays within the output file budget.
823    /// Inactive-window merges use this to bound write amplification when they
824    /// bypass the balance checks. An unset budget means no bound: the operator
825    /// removed the output size limit explicitly.
826    fn within_rewrite_budget(&self, max_output_file_size: Option<u64>) -> bool {
827        match max_output_file_size {
828            Some(limit) if limit > 0 => self.total_size <= limit as usize,
829            _ => true,
830        }
831    }
832
833    /// A candidate is worth compacting only if it makes progress on at least one
834    /// axis: it reduces the physical file count, or it resolves at least one
835    /// overlap (merging sorted runs and reducing read amplification). A pure
836    /// rewrite that achieves neither only burns I/O.
837    fn makes_progress(&self, max_output_file_size: Option<u64>) -> bool {
838        self.file_reduction(max_output_file_size) > 0 || self.overlap_participants > 0
839    }
840
841    fn score(&self, max_output_file_size: Option<u64>) -> CandidateScore {
842        CandidateScore {
843            file_reduction: self.file_reduction(max_output_file_size),
844            overlap_participants: self.overlap_participants,
845            total_size: self.total_size,
846        }
847    }
848}
849
850/// Score of a candidate compaction input. Higher is better: first by the predicted
851/// net file count reduction, then by the number of files participating in an
852/// overlap, then by smaller input bytes.
853#[derive(Debug)]
854struct CandidateScore {
855    file_reduction: usize,
856    overlap_participants: usize,
857    total_size: usize,
858}
859
860impl CandidateScore {
861    fn is_better_than(&self, other: &Self) -> bool {
862        self.file_reduction
863            .cmp(&other.file_reduction)
864            .then_with(|| self.overlap_participants.cmp(&other.overlap_participants))
865            .then_with(|| other.total_size.cmp(&self.total_size))
866            .is_gt()
867    }
868}
869
870/// Picks a contiguous (in global time order) interval of files to compact.
871///
872/// The picker reorders all files from all sorted runs by `(start asc, end desc)` and
873/// enumerates every interval of at most [`MAX_INPUT_FILES`] files as a [`Candidate`].
874/// An interval is eligible when it
875///
876/// - holds at least 2 files,
877/// - passes the caller-supplied eligibility predicate (e.g. the byte- and
878///   row-balance checks for regular picks, the rewrite budget for inactive
879///   window fallbacks),
880/// - makes progress on at least one axis: it reduces the physical file count given
881///   the output split threshold `max_output_file_size`, or it resolves at least one
882///   overlap between sorted runs.
883///
884/// The best interval wins by [`CandidateScore`]; ties keep the earliest interval.
885fn pick_count_first(
886    sorted_runs: Vec<SortedRun<FileHandle>>,
887    max_output_file_size: Option<u64>,
888    mapper: &PrimaryKeyRangeMapper,
889) -> Vec<FileHandle> {
890    pick_count_first_where(
891        sorted_runs,
892        max_output_file_size,
893        mapper,
894        is_balanced_candidate,
895    )
896}
897
898#[cfg(test)]
899fn pick_mixed_count_first(
900    sorted_runs: Vec<SortedRun<FileHandle>>,
901    max_output_file_size: Option<u64>,
902    mapper: &PrimaryKeyRangeMapper,
903) -> Vec<FileHandle> {
904    pick_count_first_where(sorted_runs, max_output_file_size, mapper, |candidate| {
905        candidate.has_mixed_levels() && is_balanced_candidate(candidate)
906    })
907}
908
909/// Mixed-level fallback for inactive windows: bypasses the balance checks but
910/// bounds the total rewrite to the output file budget.
911fn pick_mixed_within_budget(
912    sorted_runs: Vec<SortedRun<FileHandle>>,
913    max_output_file_size: Option<u64>,
914    mapper: &PrimaryKeyRangeMapper,
915) -> Vec<FileHandle> {
916    pick_count_first_where(sorted_runs, max_output_file_size, mapper, |candidate| {
917        candidate.has_mixed_levels() && candidate.within_rewrite_budget(max_output_file_size)
918    })
919}
920
921/// Last-resort pick for inactive windows with no balance requirement at all.
922/// Callers must only pass single-level (L0) files so the rewrite stays bounded
923/// by their bytes.
924fn pick_unbalanced_count_first(
925    sorted_runs: Vec<SortedRun<FileHandle>>,
926    max_output_file_size: Option<u64>,
927    mapper: &PrimaryKeyRangeMapper,
928) -> Vec<FileHandle> {
929    pick_count_first_where(sorted_runs, max_output_file_size, mapper, |_| true)
930}
931
932fn is_balanced_candidate(candidate: &Candidate) -> bool {
933    candidate.is_balanced() && candidate.has_balanced_level_rows()
934}
935
936fn pick_count_first_where(
937    sorted_runs: Vec<SortedRun<FileHandle>>,
938    max_output_file_size: Option<u64>,
939    mapper: &PrimaryKeyRangeMapper,
940    is_eligible: impl Fn(&Candidate) -> bool,
941) -> Vec<FileHandle> {
942    let files = ordered_files(&sorted_runs, mapper);
943
944    let mut best = None;
945    for left in 0..files.len() {
946        let mut candidate = Candidate::default();
947        let right_bound = left.saturating_add(*MAX_INPUT_FILES).min(files.len());
948        let mut participations: Vec<bool> = Vec::with_capacity(right_bound - left);
949        for right in left..right_bound {
950            candidate.absorb(&files[right], &files[left..right], &mut participations);
951            if candidate.num_files < 2
952                || !is_eligible(&candidate)
953                || !candidate.makes_progress(max_output_file_size)
954            {
955                continue;
956            }
957
958            let score = candidate.score(max_output_file_size);
959            if best
960                .as_ref()
961                .is_none_or(|(best_score, _)| score.is_better_than(best_score))
962            {
963                best = Some((score, &files[left..=right]));
964            }
965        }
966    }
967
968    let Some((_, best)) = best else {
969        return vec![];
970    };
971    best.iter().map(|file| file.file.clone()).collect()
972}
973
974/// Flattens sorted runs into files ordered by `(start asc, end desc)`, breaking ties
975/// by run and position to keep the order deterministic.
976fn ordered_files<'a>(
977    sorted_runs: &'a [SortedRun<FileHandle>],
978    mapper: &PrimaryKeyRangeMapper,
979) -> Vec<OrderedFile<'a>> {
980    let mut files = sorted_runs
981        .iter()
982        .enumerate()
983        .flat_map(|(run_id, run)| {
984            run.items()
985                .iter()
986                .enumerate()
987                .map(move |(position_in_run, file)| OrderedFile {
988                    file,
989                    run_id,
990                    position_in_run,
991                    primary_key_range: file.primary_key_range(mapper),
992                })
993        })
994        .collect::<Vec<_>>();
995    files.sort_unstable_by(|lhs, rhs| {
996        let (lhs_start, lhs_end) = lhs.file.range();
997        let (rhs_start, rhs_end) = rhs.file.range();
998        lhs_start
999            .cmp(&rhs_start)
1000            .then_with(|| rhs_end.cmp(&lhs_end))
1001            .then_with(|| lhs.run_id.cmp(&rhs.run_id))
1002            .then_with(|| lhs.position_in_run.cmp(&rhs.position_in_run))
1003    });
1004    files
1005}
1006
1007fn selected_overlaps_unselected(
1008    selected: &[FileHandle],
1009    window: &Window,
1010    mapper: &PrimaryKeyRangeMapper,
1011) -> bool {
1012    // The overall time span of the selection: a file outside it cannot overlap any
1013    // selected file (ranges are inclusive), so it needs no precise overlap check.
1014    let Some((span_start, span_end)) = selected
1015        .iter()
1016        .map(Ranged::range)
1017        .reduce(|(start_a, end_a), (start_b, end_b)| (start_a.min(start_b), end_a.max(end_b)))
1018    else {
1019        return false;
1020    };
1021    let selected_file_ids = selected
1022        .iter()
1023        .map(FileHandle::file_id)
1024        .collect::<HashSet<_>>();
1025    window
1026        .files()
1027        .filter(|file| {
1028            let (start, end) = file.range();
1029            start <= span_end && span_start <= end
1030        })
1031        .filter(|file| !selected_file_ids.contains(&file.file_id()))
1032        .any(|unselected| {
1033            selected
1034                .iter()
1035                .any(|selected| files_overlap_inclusive(selected, unselected, mapper))
1036        })
1037}
1038
1039fn log_pick_result(
1040    region_id: RegionId,
1041    window: i64,
1042    active_window: Option<i64>,
1043    pick: &WindowPick,
1044    file_num: usize,
1045    max_output_file_size: Option<u64>,
1046    filter_deleted: bool,
1047) {
1048    let input_file_str: Vec<String> = pick
1049        .inputs
1050        .iter()
1051        .map(|f| {
1052            let range = f.range();
1053            let start = range.0.to_iso8601_string();
1054            let end = range.1.to_iso8601_string();
1055            let num_rows = f.num_rows();
1056            format!(
1057                "File{{id: {:?}, range: ({}, {}), size: {}, num rows: {} }}",
1058                f.file_id(),
1059                start,
1060                end,
1061                ReadableSize(f.size()),
1062                num_rows
1063            )
1064        })
1065        .collect();
1066    let window_str = Timestamp::new_second(window).to_iso8601_string();
1067    let active_window_str = active_window.map(|s| Timestamp::new_second(s).to_iso8601_string());
1068    let max_output_file_size = max_output_file_size.map(|size| ReadableSize(size).to_string());
1069    info!(
1070        "Region ({:?}) compaction pick result: current window: {}, active window: {:?}, branch: {}, \
1071            found runs: {}, file num: {}, max output file size: {:?}, filter deleted: {}, \
1072            input files: {:?}",
1073        region_id,
1074        window_str,
1075        active_window_str,
1076        pick.branch,
1077        pick.found_runs,
1078        file_num,
1079        max_output_file_size,
1080        filter_deleted,
1081        input_file_str
1082    );
1083}
1084
1085#[async_trait::async_trait]
1086impl Picker for TwcsPicker {
1087    async fn pick(&self, compaction_region: &CompactionRegion) -> Result<Option<PickerOutput>> {
1088        self.pick_with_output_limit(compaction_region, self.max_background_tasks)
1089            .await
1090    }
1091}
1092
1093impl TwcsPicker {
1094    pub(crate) async fn pick_with_output_limit(
1095        &self,
1096        compaction_region: &CompactionRegion,
1097        max_outputs: Option<usize>,
1098    ) -> Result<Option<PickerOutput>> {
1099        let candidates = self
1100            .discover_with_limit(compaction_region, max_outputs, false)
1101            .await?;
1102        let output = candidates.finish().await?;
1103        Ok((!output.outputs.is_empty() || !output.expired_ssts.is_empty()).then_some(output))
1104    }
1105
1106    /// Enumerates all eligible classes/windows without applying scheduling policy.
1107    pub(crate) async fn discover(&self, region: &CompactionRegion) -> Result<TwcsCandidates> {
1108        self.discover_with_limit(region, None, true).await
1109    }
1110
1111    async fn discover_with_limit(
1112        &self,
1113        compaction_region: &CompactionRegion,
1114        max_outputs: Option<usize>,
1115        all_candidates: bool,
1116    ) -> Result<TwcsCandidates> {
1117        let region_id = compaction_region.region_id;
1118        let picker = self.clone();
1119        let compaction_region = compaction_region.clone();
1120        let primary_key_mapper = compaction_region.current_version.ssts.primary_key_mapper();
1121        let window_mapper = primary_key_mapper.clone();
1122        let (expired_ssts, time_window_size, active_window, windows) =
1123            common_runtime::spawn_blocking_compact(move || {
1124                let levels = compaction_region.current_version.ssts.levels();
1125                let expired_ssts = get_expired_ssts(
1126                    levels,
1127                    compaction_region.ttl,
1128                    Timestamp::current_millis(),
1129                );
1130                if !expired_ssts.is_empty() {
1131                    info!("Expired SSTs in region {}: {:?}", region_id, expired_ssts);
1132                }
1133                let expired_file_ids = expired_ssts
1134                    .iter()
1135                    .map(|file| file.file_id())
1136                    .collect::<HashSet<_>>();
1137
1138                let compaction_time_window = compaction_region
1139                    .current_version
1140                    .compaction_time_window
1141                    .map(|window| window.as_secs() as i64);
1142                let time_window_size = compaction_time_window
1143                    .or(picker.time_window_seconds)
1144                    .unwrap_or_else(|| {
1145                        let inferred = infer_time_bucket(levels[0].files());
1146                        info!(
1147                            "Compaction window for region {} is not present, inferring from files: {:?}",
1148                            region_id, inferred
1149                        );
1150                        inferred
1151                    });
1152
1153                let windows = assign_to_windows(
1154                    levels
1155                        .iter()
1156                        .flat_map(LevelMeta::files)
1157                        .filter(|file| !expired_file_ids.contains(&file.file_id())),
1158                    time_window_size,
1159                    &window_mapper,
1160                );
1161                // Compute activity from the candidate files so expired or
1162                // compacting files cannot identify a window absent from `windows`.
1163                let active_window = find_active_window_by_sequence(
1164                    windows.values().flat_map(Window::files)
1165                        .filter(|file| file.level() < file::LEVEL_SHARED),
1166                    time_window_size,
1167                )
1168                .or_else(|| {
1169                    find_latest_window_in_seconds(
1170                        windows
1171                            .values()
1172                            .flat_map(Window::files)
1173                            .filter(|file| file.level() == 0),
1174                        time_window_size,
1175                    )
1176                });
1177
1178                (expired_ssts, time_window_size, active_window, windows)
1179            })
1180            .await
1181            .context(JoinSnafu)?;
1182
1183        self.build_candidates(
1184            region_id,
1185            windows,
1186            WindowOutputContext {
1187                all_candidates,
1188                expired_ssts,
1189                active_window,
1190                time_window_size: Some(time_window_size),
1191                max_outputs,
1192                primary_key_mapper,
1193            },
1194        )
1195        .await
1196    }
1197}
1198
1199#[derive(Clone)]
1200struct Window {
1201    start: Timestamp,
1202    end: Timestamp,
1203    files: Vec<FileHandle>,
1204    /// Start of the half-open window, in seconds.
1205    time_window: i64,
1206    primary_key_range: Option<(bytes::Bytes, bytes::Bytes)>,
1207}
1208
1209impl Window {
1210    /// Creates a new [Window] with given file.
1211    fn new_with_file(file: FileHandle, mapper: &PrimaryKeyRangeMapper) -> Self {
1212        let (start, end) = file.time_range();
1213        let primary_key_range = file.primary_key_range(mapper);
1214        Self {
1215            start,
1216            end,
1217            files: vec![file],
1218            time_window: 0,
1219            primary_key_range,
1220        }
1221    }
1222
1223    /// Returns the time range of all files in current window (inclusive).
1224    fn range(&self) -> (Timestamp, Timestamp) {
1225        (self.start, self.end)
1226    }
1227
1228    /// Adds a new file to window and updates time range.
1229    fn add_file(&mut self, file: FileHandle, mapper: &PrimaryKeyRangeMapper) {
1230        let (start, end) = file.time_range();
1231        self.start = self.start.min(start);
1232        self.end = self.end.max(end);
1233        self.primary_key_range = merge_primary_key_ranges(
1234            self.primary_key_range.take(),
1235            file.primary_key_range(mapper),
1236        );
1237        self.files.push(file);
1238    }
1239
1240    fn files(&self) -> impl Iterator<Item = &FileHandle> {
1241        self.files.iter()
1242    }
1243}
1244
1245/// Whether `window` is the one right before `active_window`, where late data
1246/// still lands.
1247fn is_settling_window(
1248    window: i64,
1249    active_window: Option<i64>,
1250    time_window_size: Option<i64>,
1251) -> bool {
1252    active_window
1253        .zip(time_window_size)
1254        .is_some_and(|(active, size)| {
1255            // Windows at the timestamp limits may be too far apart to subtract.
1256            active
1257                .checked_sub(window)
1258                .is_some_and(|distance| (1..=size).contains(&distance))
1259        })
1260}
1261
1262/// Whether the region has written at least as many rows as `files` hold, and at
1263/// least one row, since the newest of them was written. Sequences are assigned
1264/// per row and compaction keeps the inputs' maximum, so this needs no state.
1265/// Files written before row counts were recorded have zero rows, so a window
1266/// holding them is not quiet.
1267fn is_quiet_window(files: &[FileHandle], region_sequence: u64) -> bool {
1268    if files.iter().any(|file| file.num_rows() == 0) {
1269        return false;
1270    }
1271    let Some(window_sequence) = files
1272        .iter()
1273        .filter_map(|file| file.meta_ref().sequence)
1274        .map(|sequence| sequence.get())
1275        .max()
1276    else {
1277        return false;
1278    };
1279    let rows: u64 = files.iter().map(|file| file.num_rows() as u64).sum();
1280    region_sequence.saturating_sub(window_sequence) >= rows.max(1)
1281}
1282
1283/// Assigns files to windows with predefined window size (in seconds) by their max timestamps.
1284fn assign_to_windows<'a>(
1285    files: impl Iterator<Item = &'a FileHandle>,
1286    time_window_size: i64,
1287    mapper: &PrimaryKeyRangeMapper,
1288) -> BTreeMap<i64, Window> {
1289    let mut windows: HashMap<i64, Window> = HashMap::new();
1290    // Iterates all files and assign to time windows according to max timestamp
1291    for f in files {
1292        if f.compacting() {
1293            continue;
1294        }
1295        let (_, end) = f.time_range();
1296        let time_window = time_window_start(end, time_window_size);
1297
1298        match windows.entry(time_window) {
1299            Entry::Occupied(mut e) => {
1300                e.get_mut().add_file(f.clone(), mapper);
1301            }
1302            Entry::Vacant(e) => {
1303                let mut window = Window::new_with_file(f.clone(), mapper);
1304                window.time_window = time_window;
1305                e.insert(window);
1306            }
1307        }
1308    }
1309    windows.into_iter().collect()
1310}
1311
1312/// Uses the same half-open windows as memtables, including timestamps in the first
1313/// second after a boundary. An unrepresentable window start is clamped to `i64::MIN`.
1314fn time_window_start(timestamp: Timestamp, time_window_size: i64) -> i64 {
1315    // Conversion to seconds cannot overflow.
1316    timestamp
1317        .convert_to(TimeUnit::Second)
1318        .and_then(|ts| ts.value().align_by_bucket(time_window_size))
1319        .unwrap_or(i64::MIN)
1320}
1321
1322fn time_window_intersects_range(
1323    window_start: i64,
1324    time_window_size: i64,
1325    time_range: &TimestampRange,
1326) -> bool {
1327    if time_range.is_empty() {
1328        return false;
1329    }
1330    let first_window = time_range
1331        .start()
1332        .map_or(i64::MIN, |start| time_window_start(start, time_window_size));
1333    let last_window = match time_range.end() {
1334        None => i64::MAX,
1335        Some(end) => {
1336            // The range end is exclusive; keep the last second that intersects it.
1337            let Some(last_second) = end
1338                .convert_to_ceil(TimeUnit::Second)
1339                .and_then(|timestamp| timestamp.value().checked_sub(1))
1340            else {
1341                return false;
1342            };
1343            time_window_start(Timestamp::new_second(last_second), time_window_size)
1344        }
1345    };
1346    (first_window..=last_window).contains(&window_start)
1347}
1348
1349fn window_has_overlap(this: &Window, windows: &BTreeMap<i64, Window>) -> bool {
1350    windows
1351        .values()
1352        .filter(|that| this.time_window != that.time_window)
1353        .any(|that| {
1354            overlaps(&this.range(), &that.range()) && {
1355                match (&this.primary_key_range, &that.primary_key_range) {
1356                    (Some(l), Some(r)) => primary_key_ranges_overlap(l, r),
1357                    _ => true,
1358                }
1359            }
1360        })
1361}
1362
1363/// Finds the latest active writing window among all files.
1364/// Returns `None` when there are no files.
1365fn find_latest_window_in_seconds<'a>(
1366    files: impl Iterator<Item = &'a FileHandle>,
1367    time_window_size: i64,
1368) -> Option<i64> {
1369    let mut latest_timestamp = None;
1370    for f in files {
1371        let (_, end) = f.time_range();
1372        if let Some(latest) = latest_timestamp {
1373            if end > latest {
1374                latest_timestamp = Some(end);
1375            }
1376        } else {
1377            latest_timestamp = Some(end);
1378        }
1379    }
1380    latest_timestamp.map(|ts| time_window_start(ts, time_window_size))
1381}
1382
1383/// Finds the active window from the file with the highest sequence number.
1384///
1385/// Flush and compaction outputs inherit the max input sequence, so the
1386/// max-sequence file always tracks the most recent write: the active window
1387/// survives the transient state where level 0 is empty right after its files
1388/// were compacted away. Returns `None` when no file carries a sequence.
1389///
1390/// The window key is its inclusive start, as in [`assign_to_windows`].
1391fn find_active_window_by_sequence<'a>(
1392    files: impl Iterator<Item = &'a FileHandle>,
1393    time_window_size: i64,
1394) -> Option<i64> {
1395    files
1396        .filter(|f| f.meta_ref().sequence.is_some())
1397        .max_by_key(|f| f.meta_ref().sequence)
1398        .map(|f| time_window_start(f.time_range().1, time_window_size))
1399}
1400
1401#[cfg(test)]
1402mod tests {
1403    use std::collections::HashSet;
1404    use std::num::NonZeroU64;
1405    use std::sync::Arc;
1406    use std::time::{Duration, Instant};
1407
1408    use common_base::Plugins;
1409    use common_time::range::TimestampRange;
1410    use store_api::storage::FileId;
1411
1412    use super::*;
1413    use crate::cache::CacheManager;
1414    use crate::compaction::compactor::CompactionVersion;
1415    use crate::compaction::scheduler::history::{PickHistory, PickKey};
1416    use crate::compaction::scheduler::pick_automatic_for_test;
1417    use crate::compaction::test_util::{
1418        compaction_region_with_ssts, new_file_handle, new_file_handle_with_sequence,
1419        new_file_handle_with_size_and_sequence,
1420        new_file_handle_with_size_sequence_and_primary_key_range, pk_range,
1421        primary_key_mapper_for_test,
1422    };
1423    use crate::config::MitoConfig;
1424    use crate::region::options::RegionOptions;
1425    use crate::sst::file::{FileMeta, Level};
1426    use crate::sst::version::SstVersion;
1427    use crate::test_util::memtable_util::metadata_for_test;
1428    use crate::test_util::scheduler_util::SchedulerEnv;
1429
1430    fn assign_to_windows<'a>(
1431        files: impl Iterator<Item = &'a FileHandle>,
1432        time_window_size: i64,
1433    ) -> BTreeMap<i64, Window> {
1434        super::assign_to_windows(files, time_window_size, &primary_key_mapper_for_test())
1435    }
1436
1437    fn pick_count_first(
1438        sorted_runs: Vec<SortedRun<FileHandle>>,
1439        max_output_file_size: Option<u64>,
1440    ) -> Vec<FileHandle> {
1441        super::pick_count_first(
1442            sorted_runs,
1443            max_output_file_size,
1444            &primary_key_mapper_for_test(),
1445        )
1446    }
1447
1448    fn pick_mixed_count_first(
1449        sorted_runs: Vec<SortedRun<FileHandle>>,
1450        max_output_file_size: Option<u64>,
1451    ) -> Vec<FileHandle> {
1452        super::pick_mixed_count_first(
1453            sorted_runs,
1454            max_output_file_size,
1455            &primary_key_mapper_for_test(),
1456        )
1457    }
1458
1459    impl TwcsPicker {
1460        async fn build_output_with_time_range(
1461            &self,
1462            region_id: RegionId,
1463            time_windows: BTreeMap<i64, Window>,
1464            active_window: Option<i64>,
1465            time_window_size: Option<i64>,
1466        ) -> Result<Vec<CompactionOutput>> {
1467            self.build_candidates(
1468                region_id,
1469                time_windows,
1470                WindowOutputContext {
1471                    all_candidates: false,
1472                    expired_ssts: Vec::new(),
1473                    active_window,
1474                    time_window_size,
1475                    max_outputs: self.max_background_tasks,
1476                    primary_key_mapper: Arc::new(primary_key_mapper_for_test()),
1477                },
1478            )
1479            .await?
1480            .finish()
1481            .await
1482            .map(|output| output.outputs)
1483        }
1484
1485        async fn build_output_with_history(
1486            &self,
1487            time_windows: BTreeMap<i64, Window>,
1488            active_window: Option<i64>,
1489            history: &mut PickHistory,
1490        ) -> Result<Vec<CompactionOutput>> {
1491            let mut candidates = self
1492                .build_candidates(
1493                    RegionId::from_u64(1),
1494                    time_windows,
1495                    WindowOutputContext {
1496                        all_candidates: true,
1497                        expired_ssts: Vec::new(),
1498                        active_window,
1499                        time_window_size: None,
1500                        max_outputs: None,
1501                        primary_key_mapper: Arc::new(primary_key_mapper_for_test()),
1502                    },
1503                )
1504                .await?;
1505            let now = Instant::now();
1506            candidates.candidates = history.rank_candidates(candidates.candidates, now);
1507            candidates
1508                .candidates
1509                .truncate(self.max_background_tasks.unwrap_or(usize::MAX));
1510            history.acknowledge(candidates.candidates.iter().map(PickKey::from), now);
1511            candidates.finish().await.map(|output| output.outputs)
1512        }
1513    }
1514
1515    #[test]
1516    fn test_cross_schema_pk_overlap_before_window_aggregation() {
1517        use crate::test_util::sst_util::{new_primary_key, sst_region_metadata};
1518
1519        let metadata = Arc::new(sst_region_metadata());
1520        let mut old = FileMeta {
1521            region_id: metadata.region_id,
1522            file_id: FileId::random(),
1523            time_range: (
1524                Timestamp::new_millisecond(0),
1525                Timestamp::new_millisecond(1000),
1526            ),
1527            primary_key_min: Some(new_primary_key(&["a"]).into()),
1528            primary_key_max: Some(new_primary_key(&["b"]).into()),
1529            ..Default::default()
1530        };
1531        let mut completed = new_primary_key(&["b"]);
1532        completed.push(0); // The appended nullable tag's default.
1533        let new = FileMeta {
1534            file_id: FileId::random(),
1535            time_range: (
1536                Timestamp::new_millisecond(500),
1537                Timestamp::new_millisecond(2000),
1538            ),
1539            primary_key_min: Some(completed.clone().into()),
1540            primary_key_max: Some(completed.clone().into()),
1541            ..old.clone()
1542        };
1543        assert!(old.primary_key_max < new.primary_key_min);
1544        let mut ssts = SstVersion::new(metadata);
1545        let old_id = old.file_id;
1546        let new_id = new.file_id;
1547        ssts.add_files(
1548            crate::test_util::new_noop_file_purger(),
1549            [old.clone(), new].into_iter(),
1550        );
1551        let old_file = &ssts.levels()[0].files[&old_id];
1552        let new_file = &ssts.levels()[0].files[&new_id];
1553        let ranges = ssts.primary_key_mapper();
1554        let windows = super::assign_to_windows([old_file, new_file].into_iter(), 1, &ranges);
1555        assert_eq!(2, windows.len());
1556        assert!(
1557            windows
1558                .values()
1559                .all(|window| window_has_overlap(window, &windows))
1560        );
1561
1562        let mut window = Window::new_with_file(old_file.clone(), &ranges);
1563        window.add_file(new_file.clone(), &ranges);
1564        assert!(selected_overlaps_unselected(
1565            std::slice::from_ref(new_file),
1566            &window,
1567            &ranges,
1568        ));
1569        assert_eq!(
1570            Some(completed.into()),
1571            window
1572                .primary_key_range
1573                .as_ref()
1574                .map(|range| range.1.clone())
1575        );
1576
1577        // In the same target schema, a genuinely disjoint range still prunes.
1578        old.file_id = FileId::random();
1579        old.primary_key_max = old.primary_key_min.clone();
1580        let disjoint_id = old.file_id;
1581        ssts.add_files(crate::test_util::new_noop_file_purger(), [old].into_iter());
1582        let files = &ssts.levels()[0].files;
1583        assert!(!files_overlap_inclusive(
1584            &files[&disjoint_id],
1585            &files[&new_id],
1586            &ranges
1587        ));
1588    }
1589
1590    #[test]
1591    fn test_valid_max_input_files_env_overrides_default() {
1592        assert_eq!(64, parse_max_input_files(Some("64")));
1593    }
1594
1595    #[test]
1596    fn test_invalid_max_input_files_env_falls_back_to_default() {
1597        for env_value in [None, Some(""), Some("invalid"), Some("0"), Some("1")] {
1598            assert_eq!(16, parse_max_input_files(env_value));
1599        }
1600    }
1601
1602    async fn compaction_region_with_expired_sst() -> CompactionRegion {
1603        compaction_region_with_ssts(
1604            (1..=4).map(|sequence| FileMeta {
1605                file_id: FileId::random(),
1606                time_range: (
1607                    Timestamp::new_millisecond(0),
1608                    Timestamp::new_millisecond(10),
1609                ),
1610                level: 0,
1611                sequence: NonZeroU64::new(sequence),
1612                ..Default::default()
1613            }),
1614            Duration::from_millis(1),
1615        )
1616        .await
1617    }
1618
1619    #[tokio::test]
1620    async fn test_pick_normalizes_zero_output_size_to_unlimited() {
1621        let mut compaction_region = compaction_region_with_ssts(
1622            (1..=4).map(|sequence| new_file(0, 10, sequence, 100).meta_ref().clone()),
1623            Duration::from_secs(3600),
1624        )
1625        .await;
1626        compaction_region.ttl = None;
1627
1628        for (max_output_file_size, expected_max_file_size) in
1629            [(Some(0), None), (None, None), (Some(1024), Some(1024))]
1630        {
1631            let picker = TwcsPicker {
1632                trigger_file_num: 4,
1633                active_window_l1_merge_trigger: 8,
1634                inactive_window_trigger_file_num: 4,
1635                inactive_window_l1_merge_trigger: 8,
1636                time_window_seconds: Some(3),
1637                max_output_file_size,
1638                append_mode: false,
1639                merge_mode: MergeMode::LastRow,
1640                max_background_tasks: None,
1641                time_range: None,
1642                all_windows_inactive: false,
1643                metrics: Default::default(),
1644            };
1645
1646            let output = picker.pick(&compaction_region).await.unwrap().unwrap();
1647
1648            assert_eq!(output.outputs.len(), 1);
1649            assert_eq!(output.outputs[0].inputs.len(), 4);
1650            assert!(output.expired_ssts.is_empty());
1651            assert_eq!(output.max_file_size, expected_max_file_size);
1652        }
1653    }
1654
1655    #[tokio::test]
1656    async fn test_pick_expired_ssts_without_marking_compacting() {
1657        let picker = TwcsPicker {
1658            trigger_file_num: 4,
1659            active_window_l1_merge_trigger: 8,
1660            inactive_window_trigger_file_num: 4,
1661            inactive_window_l1_merge_trigger: 8,
1662            time_window_seconds: Some(3),
1663            max_output_file_size: None,
1664            append_mode: false,
1665            merge_mode: MergeMode::LastRow,
1666            max_background_tasks: None,
1667            time_range: None,
1668            all_windows_inactive: false,
1669            metrics: Default::default(),
1670        };
1671        let compaction_region = compaction_region_with_expired_sst().await;
1672
1673        let output = picker.pick(&compaction_region).await.unwrap().unwrap();
1674
1675        assert!(output.outputs.is_empty());
1676        assert!(!output.expired_ssts.is_empty());
1677        assert!(output.expired_ssts.iter().all(|file| !file.compacting()));
1678    }
1679
1680    #[tokio::test]
1681    async fn test_expired_sst_does_not_determine_active_window() {
1682        let now = Timestamp::current_millis().value();
1683        let files = [
1684            FileMeta {
1685                file_id: FileId::random(),
1686                time_range: (
1687                    Timestamp::new_millisecond(0),
1688                    Timestamp::new_millisecond(10),
1689                ),
1690                level: 0,
1691                sequence: NonZeroU64::new(100),
1692                ..Default::default()
1693            },
1694            FileMeta {
1695                file_id: FileId::random(),
1696                time_range: (
1697                    Timestamp::new_millisecond(now - 1000),
1698                    Timestamp::new_millisecond(now),
1699                ),
1700                level: 0,
1701                sequence: NonZeroU64::new(1),
1702                ..Default::default()
1703            },
1704            FileMeta {
1705                file_id: FileId::random(),
1706                time_range: (
1707                    Timestamp::new_millisecond(now - 1000),
1708                    Timestamp::new_millisecond(now),
1709                ),
1710                level: 0,
1711                sequence: NonZeroU64::new(2),
1712                ..Default::default()
1713            },
1714        ];
1715        let compaction_region = compaction_region_with_ssts(files, Duration::from_secs(60)).await;
1716        let picker = TwcsPicker {
1717            trigger_file_num: 4,
1718            active_window_l1_merge_trigger: 8,
1719            inactive_window_trigger_file_num: 2,
1720            inactive_window_l1_merge_trigger: 8,
1721            time_window_seconds: Some(3),
1722            max_output_file_size: None,
1723            append_mode: false,
1724            merge_mode: MergeMode::LastRow,
1725            max_background_tasks: None,
1726            time_range: None,
1727            all_windows_inactive: false,
1728            metrics: Default::default(),
1729        };
1730
1731        let output = picker.pick(&compaction_region).await.unwrap().unwrap();
1732
1733        assert_eq!(1, output.expired_ssts.len());
1734        assert!(output.outputs.is_empty());
1735    }
1736
1737    #[tokio::test]
1738    async fn test_active_window_survives_l0_consumption() {
1739        // Simulates the transient state right after an L0 compaction: level 0 is
1740        // empty and only L1 files remain. The active window must still be the
1741        // window of the most recent write (tracked by the max-sequence file), so
1742        // the window is NOT compacted under the inactive rules.
1743        let env = SchedulerEnv::new().await;
1744        let metadata = metadata_for_test();
1745        let manifest_ctx = env.mock_manifest_context(metadata.clone()).await;
1746        let mut ssts = SstVersion::new(metadata.clone());
1747        ssts.add_files(
1748            Arc::new(crate::sst::file_purger::NoopFilePurger),
1749            [100, 101].into_iter().map(|sequence| FileMeta {
1750                region_id: metadata.region_id,
1751                file_id: FileId::random(),
1752                time_range: (
1753                    Timestamp::new_millisecond(0),
1754                    Timestamp::new_millisecond(10),
1755                ),
1756                level: 1,
1757                sequence: NonZeroU64::new(sequence),
1758                ..Default::default()
1759            }),
1760        );
1761        let compaction_region = CompactionRegion {
1762            region_id: metadata.region_id,
1763            region_options: RegionOptions::default(),
1764            engine_config: Arc::new(MitoConfig::default()),
1765            region_metadata: metadata.clone(),
1766            cache_manager: Arc::new(CacheManager::default()),
1767            access_layer: env.access_layer,
1768            manifest_ctx,
1769            current_version: CompactionVersion {
1770                metadata,
1771                options: RegionOptions::default(),
1772                ssts: Arc::new(ssts),
1773                memtable_min_sequence: None,
1774                compaction_time_window: None,
1775            },
1776            file_purger: None,
1777            ttl: None,
1778            max_parallelism: 1,
1779            plugins: Plugins::new(),
1780        };
1781        let picker = TwcsPicker {
1782            trigger_file_num: 4,
1783            active_window_l1_merge_trigger: 8,
1784            inactive_window_trigger_file_num: 2,
1785            inactive_window_l1_merge_trigger: 8,
1786            time_window_seconds: Some(3600),
1787            max_output_file_size: None,
1788            append_mode: false,
1789            merge_mode: MergeMode::LastRow,
1790            max_background_tasks: None,
1791            time_range: None,
1792            all_windows_inactive: false,
1793            metrics: Default::default(),
1794        };
1795
1796        assert!(picker.pick(&compaction_region).await.unwrap().is_none());
1797    }
1798
1799    #[test]
1800    fn test_find_active_window_by_sequence() {
1801        // The max-sequence file tracks the most recent write regardless of
1802        // level: here a compacted L1 file ending at 2999ms (window key 2) is
1803        // newer than the L0 file ending at 999ms (window key 0). Window keys
1804        // follow the assign_to_windows convention (truncate to seconds).
1805        let files = [
1806            new_file_handle_with_sequence(FileId::random(), 0, 999, 0, 1),
1807            new_file_handle_with_sequence(FileId::random(), 2000, 2999, 1, 10),
1808        ];
1809        assert_eq!(Some(2), find_active_window_by_sequence(files.iter(), 1));
1810
1811        // Backfill: the newest write lands in an older window, and that window
1812        // is the active one.
1813        let files = [
1814            new_file_handle_with_sequence(FileId::random(), 0, 999, 0, 10),
1815            new_file_handle_with_sequence(FileId::random(), 2000, 2999, 0, 1),
1816        ];
1817        assert_eq!(Some(0), find_active_window_by_sequence(files.iter(), 1));
1818
1819        // Files without a sequence are skipped; if none have one, the caller
1820        // falls back to the L0-based rule.
1821        let files = [new_file_handle_with_sequence(
1822            FileId::random(),
1823            0,
1824            999,
1825            1,
1826            0,
1827        )];
1828        assert_eq!(None, find_active_window_by_sequence(files.iter(), 1));
1829        assert!(find_active_window_by_sequence(Vec::<FileHandle>::new().iter(), 1).is_none());
1830    }
1831
1832    #[test]
1833    fn test_active_window_falls_back_to_l0_rule_without_sequence() {
1834        let active_window_of = |files: &[FileHandle]| {
1835            find_active_window_by_sequence(files.iter(), 1).or_else(|| {
1836                find_latest_window_in_seconds(files.iter().filter(|f| f.level() == 0), 1)
1837            })
1838        };
1839
1840        // Legacy files without sequence: the L0-based rule still applies.
1841        let files = [
1842            new_file_handle_with_sequence(FileId::random(), 0, 999, 1, 0),
1843            new_file_handle_with_sequence(FileId::random(), 2000, 2999, 0, 0),
1844        ];
1845        assert_eq!(Some(2), active_window_of(&files));
1846
1847        // No sequence and no L0: None, exactly as before.
1848        let files = [new_file_handle_with_sequence(
1849            FileId::random(),
1850            0,
1851            999,
1852            1,
1853            0,
1854        )];
1855        assert_eq!(None, active_window_of(&files));
1856    }
1857
1858    #[test]
1859    fn test_get_latest_window_in_seconds() {
1860        assert_eq!(
1861            Some(0),
1862            find_latest_window_in_seconds([new_file_handle(FileId::random(), 0, 999, 0)].iter(), 1)
1863        );
1864        assert_eq!(
1865            Some(1),
1866            find_latest_window_in_seconds(
1867                [new_file_handle(FileId::random(), 0, 1000, 0)].iter(),
1868                1
1869            )
1870        );
1871
1872        assert_eq!(
1873            Some(-9223372036857600),
1874            find_latest_window_in_seconds(
1875                [new_file_handle(FileId::random(), i64::MIN, i64::MIN + 1, 0)].iter(),
1876                3600,
1877            )
1878        );
1879
1880        assert_eq!(
1881            (i64::MAX / 10000000) * 10000,
1882            find_latest_window_in_seconds(
1883                [new_file_handle(FileId::random(), i64::MIN, i64::MAX, 0)].iter(),
1884                10000,
1885            )
1886            .unwrap()
1887        );
1888
1889        assert_eq!(
1890            Some((i64::MAX / 3600000) * 3600),
1891            find_latest_window_in_seconds(
1892                [
1893                    new_file_handle(FileId::random(), i64::MIN, i64::MAX, 0),
1894                    new_file_handle(FileId::random(), 0, 1000, 0)
1895                ]
1896                .iter(),
1897                3600
1898            )
1899        );
1900    }
1901
1902    #[test]
1903    fn test_window_assignment_and_activity_at_boundaries() {
1904        // Before, at, and after positive/negative boundaries, including the first
1905        // fractional second: all picker paths must agree with half-open partitions.
1906        for (unit, ticks_per_second) in [
1907            (TimeUnit::Second, 1),
1908            (TimeUnit::Millisecond, 1_000),
1909            (TimeUnit::Microsecond, 1_000_000),
1910            (TimeUnit::Nanosecond, 1_000_000_000),
1911        ] {
1912            for window_size in [1, 3, 86_400] {
1913                for boundary in [-window_size, 0, window_size] {
1914                    for (offset, expected_window) in [
1915                        (-1, boundary - window_size),
1916                        (0, boundary),
1917                        (ticks_per_second - 1, boundary),
1918                        (ticks_per_second, boundary + i64::from(window_size == 1)),
1919                    ] {
1920                        let timestamp = Timestamp::new(boundary * ticks_per_second + offset, unit);
1921                        let file = FileHandle::new(
1922                            FileMeta {
1923                                time_range: (timestamp, timestamp),
1924                                sequence: NonZeroU64::new(1),
1925                                ..Default::default()
1926                            },
1927                            crate::test_util::new_noop_file_purger(),
1928                        );
1929                        let files = [file];
1930                        let windows = assign_to_windows(files.iter(), window_size);
1931                        assert_eq!(
1932                            vec![expected_window],
1933                            windows.keys().copied().collect::<Vec<_>>(),
1934                            "{timestamp:?}, window size {window_size}"
1935                        );
1936                        assert_eq!(
1937                            Some(expected_window),
1938                            find_active_window_by_sequence(files.iter(), window_size)
1939                        );
1940                        assert_eq!(
1941                            Some(expected_window),
1942                            find_latest_window_in_seconds(files.iter(), window_size)
1943                        );
1944                    }
1945                }
1946            }
1947        }
1948    }
1949
1950    #[test]
1951    fn test_settling_window_at_timestamp_limits() {
1952        assert!(is_settling_window(0, Some(60), Some(60)));
1953        assert!(!is_settling_window(60, Some(60), Some(60)));
1954        assert!(!is_settling_window(-60, Some(60), Some(60)));
1955        assert!(!is_settling_window(0, None, Some(60)));
1956        // The distance between these windows does not fit in an i64.
1957        assert!(!is_settling_window(i64::MAX, Some(i64::MIN), Some(1)));
1958        assert!(!is_settling_window(i64::MIN, Some(i64::MAX), Some(1)));
1959    }
1960
1961    #[test]
1962    fn test_window_assignment_at_timestamp_limits() {
1963        for (seconds, expected_window) in [(i64::MIN, i64::MIN), (i64::MAX, i64::MAX - 1)] {
1964            let timestamp = Timestamp::new_second(seconds);
1965            let files = [FileHandle::new(
1966                FileMeta {
1967                    time_range: (timestamp, timestamp),
1968                    sequence: NonZeroU64::new(1),
1969                    ..Default::default()
1970                },
1971                crate::test_util::new_noop_file_purger(),
1972            )];
1973            let windows = assign_to_windows(files.iter(), 3);
1974            assert_eq!(
1975                vec![expected_window],
1976                windows.keys().copied().collect::<Vec<_>>()
1977            );
1978            assert_eq!(
1979                Some(expected_window),
1980                find_active_window_by_sequence(files.iter(), 3)
1981            );
1982            assert_eq!(
1983                Some(expected_window),
1984                find_latest_window_in_seconds(files.iter(), 3)
1985            );
1986            assert!(time_window_intersects_range(
1987                expected_window,
1988                3,
1989                &TimestampRange::single(timestamp)
1990            ));
1991        }
1992    }
1993
1994    #[tokio::test]
1995    async fn test_midnight_file_is_not_compacted_with_previous_day() {
1996        // Regression for #9441: flush already separates the midnight-only SST.
1997        let midnight = 86_400_000;
1998        CompactionPickerTestCase {
1999            window_size: 86_400,
2000            input_files: [
2001                (midnight - 240_000, midnight - 180_000),
2002                (midnight - 180_000, midnight - 90_000),
2003                (midnight - 90_000, midnight - 30_000),
2004                (midnight, midnight),
2005            ]
2006            .into_iter()
2007            .enumerate()
2008            .map(|(index, (start, end))| {
2009                new_file_handle_with_sequence(FileId::random(), start, end, 0, index as u64 + 1)
2010            })
2011            .collect(),
2012            expected_outputs: vec![ExpectedOutput {
2013                input_files: vec![0, 1, 2],
2014                output_level: 1,
2015            }],
2016        }
2017        .check()
2018        .await;
2019    }
2020
2021    #[test]
2022    fn test_assign_to_windows() {
2023        let windows = assign_to_windows(
2024            [
2025                new_file_handle(FileId::random(), 0, 999, 0),
2026                new_file_handle(FileId::random(), 0, 999, 0),
2027                new_file_handle(FileId::random(), 0, 999, 0),
2028                new_file_handle(FileId::random(), 0, 999, 0),
2029                new_file_handle(FileId::random(), 0, 999, 0),
2030            ]
2031            .iter(),
2032            3,
2033        );
2034        let fgs = &windows.get(&0).unwrap().files;
2035        assert_eq!(5, fgs.len());
2036
2037        let files = [FileId::random(); 3];
2038        let windows = assign_to_windows(
2039            [
2040                new_file_handle(files[0], -2000, -3, 0),
2041                new_file_handle(files[1], 0, 2999, 0),
2042                new_file_handle(files[2], 50, 10001, 0),
2043            ]
2044            .iter(),
2045            3,
2046        );
2047        assert_eq!(
2048            files[0],
2049            windows
2050                .get(&-3)
2051                .unwrap()
2052                .files()
2053                .next()
2054                .unwrap()
2055                .file_id()
2056                .file_id()
2057        );
2058        assert_eq!(
2059            files[1],
2060            windows
2061                .get(&0)
2062                .unwrap()
2063                .files()
2064                .next()
2065                .unwrap()
2066                .file_id()
2067                .file_id()
2068        );
2069        assert_eq!(
2070            files[2],
2071            windows
2072                .get(&9)
2073                .unwrap()
2074                .files()
2075                .next()
2076                .unwrap()
2077                .file_id()
2078                .file_id()
2079        );
2080    }
2081
2082    #[test]
2083    fn test_assign_files_to_windows() {
2084        let files = [
2085            FileId::random(),
2086            FileId::random(),
2087            FileId::random(),
2088            FileId::random(),
2089        ];
2090        let windows = assign_to_windows(
2091            [
2092                new_file_handle_with_sequence(files[0], 0, 999, 0, 1),
2093                new_file_handle_with_sequence(files[1], 0, 999, 0, 1),
2094                new_file_handle_with_sequence(files[2], 0, 999, 0, 2),
2095                new_file_handle_with_sequence(files[3], 0, 999, 0, 2),
2096            ]
2097            .iter(),
2098            3,
2099        );
2100        assert_eq!(windows.len(), 1);
2101        let window_files = &windows.get(&0).unwrap().files;
2102        assert_eq!(4, window_files.len());
2103        assert_eq!(
2104            window_files
2105                .iter()
2106                .map(|f| f.file_id().file_id())
2107                .collect::<HashSet<_>>(),
2108            files.into_iter().collect()
2109        );
2110    }
2111
2112    #[test]
2113    fn test_assign_compacting_to_windows() {
2114        let files = [
2115            new_file_handle(FileId::random(), 0, 999, 0),
2116            new_file_handle(FileId::random(), 0, 999, 0),
2117            new_file_handle(FileId::random(), 0, 999, 0),
2118            new_file_handle(FileId::random(), 0, 999, 0),
2119            new_file_handle(FileId::random(), 0, 999, 0),
2120        ];
2121        files[0].set_compacting(true);
2122        files[2].set_compacting(true);
2123        let mut windows = assign_to_windows(files.iter(), 3);
2124        let window0 = windows.remove(&0).unwrap();
2125        assert_eq!(3, window0.files.len());
2126        let candidates = window0
2127            .files
2128            .iter()
2129            .map(|f| f.file_id().file_id())
2130            .collect::<HashSet<_>>();
2131        assert_eq!(candidates.len(), 3);
2132        assert_eq!(
2133            candidates,
2134            [
2135                files[1].file_id().file_id(),
2136                files[3].file_id().file_id(),
2137                files[4].file_id().file_id()
2138            ]
2139            .into_iter()
2140            .collect::<HashSet<_>>()
2141        );
2142    }
2143
2144    /// (Window value, overlapping, files' time ranges in window)
2145    type ExpectedWindowSpec = (i64, bool, Vec<(i64, i64)>);
2146
2147    fn check_assign_to_windows_with_overlapping(
2148        file_time_ranges: &[(i64, i64)],
2149        time_window: i64,
2150        expected_files: &[ExpectedWindowSpec],
2151    ) {
2152        let files: Vec<_> = (0..file_time_ranges.len())
2153            .map(|_| FileId::random())
2154            .collect();
2155
2156        let file_handles = files
2157            .iter()
2158            .zip(file_time_ranges.iter())
2159            .map(|(file_id, range)| new_file_handle(*file_id, range.0, range.1, 0))
2160            .collect::<Vec<_>>();
2161
2162        let windows = assign_to_windows(file_handles.iter(), time_window);
2163        assert_eq!(expected_files.len(), windows.len());
2164
2165        for (expected_window, overlapping, window_files) in expected_files {
2166            let actual_window = windows.get(expected_window).unwrap();
2167            let actual_overlapping = window_has_overlap(actual_window, &windows);
2168            assert_eq!(*overlapping, actual_overlapping);
2169            let mut file_ranges = actual_window
2170                .files
2171                .iter()
2172                .map(|f| {
2173                    let (s, e) = f.time_range();
2174                    (s.value(), e.value())
2175                })
2176                .collect::<Vec<_>>();
2177            file_ranges.sort_unstable_by(|l, r| l.0.cmp(&r.0).then(l.1.cmp(&r.1)));
2178            assert_eq!(window_files, &file_ranges);
2179        }
2180    }
2181
2182    #[test]
2183    fn test_assign_to_windows_with_overlapping() {
2184        check_assign_to_windows_with_overlapping(
2185            &[(0, 999), (1000, 1999), (2000, 2999)],
2186            2,
2187            &[
2188                (0, false, vec![(0, 999), (1000, 1999)]),
2189                (2, false, vec![(2000, 2999)]),
2190            ],
2191        );
2192
2193        check_assign_to_windows_with_overlapping(
2194            &[(0, 1), (0, 999), (100, 2999)],
2195            2,
2196            &[
2197                (0, true, vec![(0, 1), (0, 999)]),
2198                (2, true, vec![(100, 2999)]),
2199            ],
2200        );
2201
2202        check_assign_to_windows_with_overlapping(
2203            &[(0, 999), (1000, 1999), (2000, 2999), (3000, 3999)],
2204            2,
2205            &[
2206                (0, false, vec![(0, 999), (1000, 1999)]),
2207                (2, false, vec![(2000, 2999), (3000, 3999)]),
2208            ],
2209        );
2210
2211        check_assign_to_windows_with_overlapping(
2212            &[
2213                (0, 999),
2214                (1000, 1999),
2215                (2000, 2999),
2216                (3000, 3999),
2217                (0, 3999),
2218            ],
2219            2,
2220            &[
2221                (0, true, vec![(0, 999), (1000, 1999)]),
2222                (2, true, vec![(0, 3999), (2000, 2999), (3000, 3999)]),
2223            ],
2224        );
2225
2226        check_assign_to_windows_with_overlapping(
2227            &[
2228                (0, 999),
2229                (1000, 1999),
2230                (2000, 2999),
2231                (3000, 3999),
2232                (1999, 3999),
2233            ],
2234            2,
2235            &[
2236                (0, true, vec![(0, 999), (1000, 1999)]),
2237                (2, true, vec![(1999, 3999), (2000, 2999), (3000, 3999)]),
2238            ],
2239        );
2240
2241        check_assign_to_windows_with_overlapping(
2242            &[
2243                (0, 999),     // window 0
2244                (1000, 1999), // window 0
2245                (2000, 2999), // window 2
2246                (3000, 3999), // window 2
2247                (2999, 3999), // window 2
2248            ],
2249            2,
2250            &[
2251                // Overlap within a window does not imply cross-window overlap.
2252                (0, false, vec![(0, 999), (1000, 1999)]),
2253                (2, false, vec![(2000, 2999), (2999, 3999), (3000, 3999)]),
2254            ],
2255        );
2256
2257        check_assign_to_windows_with_overlapping(
2258            &[
2259                (0, 999),     // window 0
2260                (1000, 1999), // window 0
2261                (2000, 2999), // window 2
2262                (3000, 3999), // window 2
2263                (0, 2000),    // window 2
2264            ],
2265            2,
2266            &[
2267                (0, true, vec![(0, 999), (1000, 1999)]),
2268                (2, true, vec![(0, 2000), (2000, 2999), (3000, 3999)]),
2269            ],
2270        );
2271    }
2272
2273    #[test]
2274    fn test_assign_to_windows_not_overlapping_when_pk_disjoint() {
2275        let files = [
2276            new_file_handle_with_size_sequence_and_primary_key_range(
2277                FileId::random(),
2278                0,
2279                1000,
2280                0,
2281                1,
2282                10,
2283                pk_range(b"a", b"f"),
2284            ),
2285            new_file_handle_with_size_sequence_and_primary_key_range(
2286                FileId::random(),
2287                500,
2288                2999,
2289                0,
2290                2,
2291                10,
2292                pk_range(b"x", b"z"),
2293            ),
2294        ];
2295
2296        let windows = assign_to_windows(files.iter(), 2);
2297
2298        assert_eq!(2, windows.len());
2299        let overlapping = window_has_overlap(windows.get(&0).unwrap(), &windows);
2300        assert!(!overlapping);
2301    }
2302
2303    #[test]
2304    fn test_assign_to_windows_pk_unknown_in_earlier_window_does_not_poison_later_windows() {
2305        let files = [
2306            new_file_handle(FileId::random(), 0, 1999, 0),
2307            new_file_handle_with_size_sequence_and_primary_key_range(
2308                FileId::random(),
2309                2000,
2310                3999,
2311                0,
2312                1,
2313                10,
2314                pk_range(b"a", b"f"),
2315            ),
2316            new_file_handle_with_size_sequence_and_primary_key_range(
2317                FileId::random(),
2318                3000,
2319                4999,
2320                0,
2321                2,
2322                10,
2323                pk_range(b"x", b"z"),
2324            ),
2325        ];
2326
2327        let windows = assign_to_windows(files.iter(), 2);
2328
2329        let overlapping = window_has_overlap(windows.get(&4).unwrap(), &windows);
2330        assert!(!overlapping);
2331    }
2332
2333    struct CompactionPickerTestCase {
2334        window_size: i64,
2335        input_files: Vec<FileHandle>,
2336        expected_outputs: Vec<ExpectedOutput>,
2337    }
2338
2339    impl CompactionPickerTestCase {
2340        async fn check(&self) {
2341            let file_id_to_idx = self
2342                .input_files
2343                .iter()
2344                .enumerate()
2345                .map(|(idx, file)| (file.file_id(), idx))
2346                .collect::<HashMap<_, _>>();
2347            let windows = assign_to_windows(self.input_files.iter(), self.window_size);
2348            let active_window =
2349                find_active_window_by_sequence(self.input_files.iter(), self.window_size).or_else(
2350                    || find_latest_window_in_seconds(self.input_files.iter(), self.window_size),
2351                );
2352            let output = TwcsPicker {
2353                trigger_file_num: 2,
2354                active_window_l1_merge_trigger: 8,
2355                inactive_window_trigger_file_num: 2,
2356                inactive_window_l1_merge_trigger: 2,
2357                time_window_seconds: None,
2358                max_output_file_size: None,
2359                append_mode: false,
2360                merge_mode: MergeMode::LastRow,
2361                max_background_tasks: None,
2362                time_range: None,
2363                all_windows_inactive: false,
2364                metrics: Default::default(),
2365            }
2366            .build_output_with_time_range(RegionId::from_u64(0), windows, active_window, None)
2367            .await
2368            .unwrap();
2369
2370            let output = output
2371                .iter()
2372                .map(|o| {
2373                    let input_file_ids = o
2374                        .inputs
2375                        .iter()
2376                        .map(|f| file_id_to_idx.get(&f.file_id()).copied().unwrap())
2377                        .collect::<HashSet<_>>();
2378                    (input_file_ids, o.output_level)
2379                })
2380                .collect::<Vec<_>>();
2381
2382            let expected = self
2383                .expected_outputs
2384                .iter()
2385                .map(|o| {
2386                    let input_file_ids = o.input_files.iter().copied().collect::<HashSet<_>>();
2387                    (input_file_ids, o.output_level)
2388                })
2389                .collect::<Vec<_>>();
2390            assert_eq!(expected, output);
2391        }
2392    }
2393
2394    struct ExpectedOutput {
2395        input_files: Vec<usize>,
2396        output_level: Level,
2397    }
2398
2399    #[tokio::test]
2400    async fn test_newer_windows_are_placed_last_for_execution() {
2401        let file_ids = (0..4).map(|_| FileId::random()).collect::<Vec<_>>();
2402
2403        // Case 1: 2 runs found in each time window.
2404        CompactionPickerTestCase {
2405            window_size: 3,
2406            input_files: [
2407                new_file_handle_with_sequence(file_ids[0], -2000, -3, 0, 1),
2408                new_file_handle_with_sequence(file_ids[1], -3000, -100, 0, 2),
2409                new_file_handle_with_sequence(file_ids[2], 0, 2999, 0, 3), //active windows
2410                new_file_handle_with_sequence(file_ids[3], 50, 2998, 0, 4), //active windows
2411            ]
2412            .to_vec(),
2413            expected_outputs: vec![
2414                ExpectedOutput {
2415                    input_files: vec![0, 1],
2416                    output_level: 1,
2417                },
2418                ExpectedOutput {
2419                    input_files: vec![2, 3],
2420                    output_level: 1,
2421                },
2422            ],
2423        }
2424        .check()
2425        .await;
2426
2427        // Case 2:
2428        //    -2000........-3
2429        // -3000.....-100
2430        //                    0..............2999
2431        //                      50..........2998
2432        //                     11.........2990
2433        let file_ids = (0..6).map(|_| FileId::random()).collect::<Vec<_>>();
2434        CompactionPickerTestCase {
2435            window_size: 3,
2436            input_files: [
2437                new_file_handle_with_sequence(file_ids[0], -2000, -3, 0, 1),
2438                new_file_handle_with_sequence(file_ids[1], -3000, -100, 0, 2),
2439                new_file_handle_with_sequence(file_ids[2], 0, 2999, 0, 3),
2440                new_file_handle_with_sequence(file_ids[3], 50, 2998, 0, 4),
2441                new_file_handle_with_sequence(file_ids[4], 11, 2990, 0, 5),
2442            ]
2443            .to_vec(),
2444            expected_outputs: vec![
2445                ExpectedOutput {
2446                    input_files: vec![0, 1],
2447                    output_level: 1,
2448                },
2449                ExpectedOutput {
2450                    input_files: vec![2, 3, 4],
2451                    output_level: 1,
2452                },
2453            ],
2454        }
2455        .check()
2456        .await;
2457
2458        // Case 3:
2459        // A compaction may split output into several files that have overlapping time ranges and
2460        // the same sequence. They are ordinary compaction candidates now: the picker merges the
2461        // overlapping ones in the window that reaches the trigger.
2462        let file_ids = (0..6).map(|_| FileId::random()).collect::<Vec<_>>();
2463        CompactionPickerTestCase {
2464            window_size: 3,
2465            input_files: [
2466                new_file_handle_with_sequence(file_ids[0], 0, 2999, 1, 1),
2467                new_file_handle_with_sequence(file_ids[1], 0, 2998, 1, 1),
2468                new_file_handle_with_sequence(file_ids[2], 3000, 5999, 1, 2),
2469                new_file_handle_with_sequence(file_ids[3], 3000, 5000, 1, 2),
2470                new_file_handle_with_sequence(file_ids[4], 11, 2990, 0, 3),
2471            ]
2472            .to_vec(),
2473            expected_outputs: vec![ExpectedOutput {
2474                input_files: vec![2, 3],
2475                output_level: 1,
2476            }],
2477        }
2478        .check()
2479        .await;
2480    }
2481
2482    #[tokio::test]
2483    async fn test_build_output_skips_pk_disjoint_files() {
2484        let files = [
2485            new_file_handle_with_size_sequence_and_primary_key_range(
2486                FileId::random(),
2487                0,
2488                2999,
2489                0,
2490                1,
2491                10,
2492                pk_range(b"a", b"f"),
2493            ),
2494            new_file_handle_with_size_sequence_and_primary_key_range(
2495                FileId::random(),
2496                50,
2497                2998,
2498                0,
2499                2,
2500                10,
2501                pk_range(b"x", b"z"),
2502            ),
2503        ];
2504        let windows = assign_to_windows(files.iter(), 3);
2505        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2506        let output = TwcsPicker {
2507            trigger_file_num: 4,
2508            active_window_l1_merge_trigger: 8,
2509            inactive_window_trigger_file_num: 4,
2510            inactive_window_l1_merge_trigger: 8,
2511            time_window_seconds: None,
2512            max_output_file_size: None,
2513            append_mode: false,
2514            merge_mode: MergeMode::LastRow,
2515            max_background_tasks: None,
2516            time_range: None,
2517            all_windows_inactive: false,
2518            metrics: Default::default(),
2519        }
2520        .build_output_with_time_range(RegionId::from_u64(0), windows, active_window, None)
2521        .await
2522        .unwrap();
2523
2524        assert!(output.is_empty());
2525    }
2526
2527    #[test]
2528    fn test_append_mode_filter_large_files() {
2529        let file_ids = (0..4).map(|_| FileId::random()).collect::<Vec<_>>();
2530        let max_output_file_size = 1000u64;
2531
2532        // Create files with different sizes
2533        let small_file_1 = new_file_handle_with_size_and_sequence(file_ids[0], 0, 999, 0, 1, 500);
2534        let large_file_1 = new_file_handle_with_size_and_sequence(file_ids[1], 0, 999, 0, 2, 1500);
2535        let small_file_2 = new_file_handle_with_size_and_sequence(file_ids[2], 0, 999, 0, 3, 800);
2536        let large_file_2 = new_file_handle_with_size_and_sequence(file_ids[3], 0, 999, 0, 4, 2000);
2537
2538        let mut files_to_merge = vec![small_file_1, large_file_1, small_file_2, large_file_2];
2539
2540        // Test filtering logic directly
2541        let original_count = files_to_merge.len();
2542
2543        // Apply append mode filtering
2544        files_to_merge.retain(|file| file.size() <= max_output_file_size);
2545
2546        // Should have filtered out 2 large files, leaving 2 small files
2547        assert_eq!(files_to_merge.len(), 2);
2548        assert_eq!(original_count, 4);
2549
2550        // Verify the remaining files are the small ones
2551        for file in &files_to_merge {
2552            assert!(
2553                file.size() <= max_output_file_size,
2554                "File size {} should be <= {}",
2555                file.size(),
2556                max_output_file_size
2557            );
2558        }
2559    }
2560
2561    #[tokio::test]
2562    async fn test_build_output_multiple_windows_with_zero_runs() {
2563        let file_ids = (0..7).map(|_| FileId::random()).collect::<Vec<_>>();
2564
2565        let files = [
2566            // Window 0: Contains 3 files but not forming any runs (not enough files in sequence to reach trigger_file_num)
2567            new_file_handle_with_sequence(file_ids[0], 0, 999, 0, 1),
2568            new_file_handle_with_sequence(file_ids[1], 0, 999, 0, 2),
2569            new_file_handle_with_sequence(file_ids[2], 0, 999, 0, 3),
2570            // Window 3: Contains files that will form 2 runs
2571            new_file_handle_with_sequence(file_ids[3], 3000, 3999, 0, 4),
2572            new_file_handle_with_sequence(file_ids[4], 3000, 3999, 0, 5),
2573            new_file_handle_with_sequence(file_ids[5], 3000, 3999, 0, 6),
2574            new_file_handle_with_sequence(file_ids[6], 3000, 3999, 0, 7),
2575        ];
2576
2577        let windows = assign_to_windows(files.iter(), 3);
2578
2579        // Create picker with trigger_file_num of 4 so single files won't form runs in first window
2580        let picker = TwcsPicker {
2581            trigger_file_num: 4, // High enough to prevent runs in first window
2582            active_window_l1_merge_trigger: 8,
2583            inactive_window_trigger_file_num: 4,
2584            inactive_window_l1_merge_trigger: 8,
2585            time_window_seconds: Some(3),
2586            max_output_file_size: None,
2587            append_mode: false,
2588            merge_mode: MergeMode::LastRow,
2589            max_background_tasks: None,
2590            time_range: None,
2591            all_windows_inactive: false,
2592            metrics: Default::default(),
2593        };
2594
2595        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2596        let output = picker
2597            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2598            .await
2599            .unwrap();
2600
2601        assert!(
2602            !output.is_empty(),
2603            "Should have output from windows with runs, even when one window has 0 runs"
2604        );
2605
2606        let all_output_files: Vec<_> = output
2607            .iter()
2608            .flat_map(|o| o.inputs.iter())
2609            .map(|f| f.file_id().file_id())
2610            .collect();
2611
2612        assert!(
2613            all_output_files.contains(&file_ids[3])
2614                || all_output_files.contains(&file_ids[4])
2615                || all_output_files.contains(&file_ids[5]),
2616            "Output should contain files from the window with runs"
2617        );
2618    }
2619
2620    #[tokio::test]
2621    async fn test_build_output_single_window_zero_runs() {
2622        let file_ids = (0..2).map(|_| FileId::random()).collect::<Vec<_>>();
2623
2624        let large_file_1 = new_file_handle_with_size_and_sequence(file_ids[0], 0, 999, 0, 1, 2000); // 2000 bytes
2625        let large_file_2 = new_file_handle_with_size_and_sequence(file_ids[1], 0, 999, 0, 2, 2500); // 2500 bytes
2626
2627        let files = [large_file_1, large_file_2];
2628
2629        let windows = assign_to_windows(files.iter(), 3);
2630
2631        let picker = TwcsPicker {
2632            trigger_file_num: 2,
2633            active_window_l1_merge_trigger: 8,
2634            inactive_window_trigger_file_num: 2,
2635            inactive_window_l1_merge_trigger: 8,
2636            time_window_seconds: Some(3),
2637            max_output_file_size: Some(1000),
2638            append_mode: true,
2639            merge_mode: MergeMode::LastRow,
2640            max_background_tasks: None,
2641            time_range: None,
2642            all_windows_inactive: false,
2643            metrics: Default::default(),
2644        };
2645
2646        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2647        let output = picker
2648            .build_output_with_time_range(RegionId::from_u64(456), windows, active_window, None)
2649            .await
2650            .unwrap();
2651
2652        // Should return empty output (no compaction needed)
2653        assert!(
2654            output.is_empty(),
2655            "Should return empty output when no runs are found after filtering"
2656        );
2657    }
2658
2659    #[tokio::test]
2660    async fn test_append_mode_can_pick_remaining_single_level_files() {
2661        let files = [
2662            new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 100),
2663            new_file_handle_with_size_and_sequence(FileId::random(), 20, 29, 0, 2, 100),
2664            new_file_handle_with_size_and_sequence(FileId::random(), 40, 49, 0, 3, 100),
2665            new_file_handle_with_size_and_sequence(FileId::random(), 60, 69, 0, 4, 2_000),
2666        ];
2667        let windows = assign_to_windows(files.iter(), 1);
2668        let picker = TwcsPicker {
2669            trigger_file_num: 4,
2670            active_window_l1_merge_trigger: 8,
2671            inactive_window_trigger_file_num: 4,
2672            inactive_window_l1_merge_trigger: 8,
2673            time_window_seconds: Some(1),
2674            max_output_file_size: Some(1_000),
2675            append_mode: true,
2676            merge_mode: MergeMode::LastRow,
2677            max_background_tasks: None,
2678            time_range: None,
2679            all_windows_inactive: false,
2680            metrics: Default::default(),
2681        };
2682
2683        let output = picker
2684            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(1), None)
2685            .await
2686            .unwrap();
2687
2688        assert_eq!(1, output.len());
2689        assert_eq!(3, output[0].inputs.len());
2690    }
2691
2692    #[tokio::test]
2693    async fn test_max_background_tasks_truncation() {
2694        let file_ids = (0..10).map(|_| FileId::random()).collect::<Vec<_>>();
2695        let max_background_tasks = 3;
2696
2697        // Create files across multiple windows that will generate multiple compaction outputs
2698        let files = [
2699            // Window 0: 4 files that will form a run
2700            new_file_handle_with_sequence(file_ids[0], 0, 999, 0, 1),
2701            new_file_handle_with_sequence(file_ids[1], 0, 999, 0, 2),
2702            new_file_handle_with_sequence(file_ids[2], 0, 999, 0, 3),
2703            new_file_handle_with_sequence(file_ids[3], 0, 999, 0, 4),
2704            // Window 3: 4 files that will form another run
2705            new_file_handle_with_sequence(file_ids[4], 3000, 3999, 0, 5),
2706            new_file_handle_with_sequence(file_ids[5], 3000, 3999, 0, 6),
2707            new_file_handle_with_sequence(file_ids[6], 3000, 3999, 0, 7),
2708            new_file_handle_with_sequence(file_ids[7], 3000, 3999, 0, 8),
2709            // Window 6: 4 files that will form another run
2710            new_file_handle_with_sequence(file_ids[8], 6000, 6999, 0, 9),
2711            new_file_handle_with_sequence(file_ids[9], 6000, 6999, 0, 10),
2712        ];
2713
2714        let windows = assign_to_windows(files.iter(), 3);
2715
2716        let picker = TwcsPicker {
2717            trigger_file_num: 4,
2718            active_window_l1_merge_trigger: 8,
2719            inactive_window_trigger_file_num: 4,
2720            inactive_window_l1_merge_trigger: 8,
2721            time_window_seconds: Some(3),
2722            max_output_file_size: None,
2723            append_mode: false,
2724            merge_mode: MergeMode::LastRow,
2725            max_background_tasks: Some(max_background_tasks),
2726            time_range: None,
2727            all_windows_inactive: false,
2728            metrics: Default::default(),
2729        };
2730
2731        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2732        let output = picker
2733            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2734            .await
2735            .unwrap();
2736
2737        // Should have at most max_background_tasks outputs
2738        assert!(
2739            output.len() <= max_background_tasks,
2740            "Output should be truncated to max_background_tasks: expected <= {}, got {}",
2741            max_background_tasks,
2742            output.len()
2743        );
2744
2745        // Without max_background_tasks, should have more outputs
2746        let picker_no_limit = TwcsPicker {
2747            trigger_file_num: 4,
2748            active_window_l1_merge_trigger: 8,
2749            inactive_window_trigger_file_num: 4,
2750            inactive_window_l1_merge_trigger: 8,
2751            time_window_seconds: Some(3),
2752            max_output_file_size: None,
2753            append_mode: false,
2754            merge_mode: MergeMode::LastRow,
2755            max_background_tasks: None,
2756            time_range: None,
2757            all_windows_inactive: false,
2758            metrics: Default::default(),
2759        };
2760
2761        let windows_no_limit = assign_to_windows(files.iter(), 3);
2762        let output_no_limit = picker_no_limit
2763            .build_output_with_time_range(
2764                RegionId::from_u64(123),
2765                windows_no_limit,
2766                active_window,
2767                None,
2768            )
2769            .await
2770            .unwrap();
2771
2772        // Without limit, should have more outputs (if there are enough windows)
2773        if output_no_limit.len() > max_background_tasks {
2774            assert!(
2775                output_no_limit.len() > output.len(),
2776                "Without limit should have more outputs than with limit"
2777            );
2778        }
2779    }
2780
2781    #[tokio::test]
2782    async fn test_max_background_tasks_no_truncation_when_under_limit() {
2783        let file_ids = (0..4).map(|_| FileId::random()).collect::<Vec<_>>();
2784        let max_background_tasks = 10; // Larger than expected outputs
2785
2786        // Create files in one window that will generate one compaction output
2787        let files = [
2788            new_file_handle_with_sequence(file_ids[0], 0, 999, 0, 1),
2789            new_file_handle_with_sequence(file_ids[1], 0, 999, 0, 2),
2790            new_file_handle_with_sequence(file_ids[2], 0, 999, 0, 3),
2791            new_file_handle_with_sequence(file_ids[3], 0, 999, 0, 4),
2792        ];
2793
2794        let windows = assign_to_windows(files.iter(), 3);
2795
2796        let picker = TwcsPicker {
2797            trigger_file_num: 4,
2798            active_window_l1_merge_trigger: 8,
2799            inactive_window_trigger_file_num: 4,
2800            inactive_window_l1_merge_trigger: 8,
2801            time_window_seconds: Some(3),
2802            max_output_file_size: None,
2803            append_mode: false,
2804            merge_mode: MergeMode::LastRow,
2805            max_background_tasks: Some(max_background_tasks),
2806            time_range: None,
2807            all_windows_inactive: false,
2808            metrics: Default::default(),
2809        };
2810
2811        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2812        let output = picker
2813            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2814            .await
2815            .unwrap();
2816
2817        // Should have all outputs since we're under the limit
2818        assert!(
2819            output.len() <= max_background_tasks,
2820            "Output should be within limit"
2821        );
2822        // Should have at least one output
2823        assert!(!output.is_empty(), "Should have at least one output");
2824    }
2825
2826    #[tokio::test]
2827    async fn test_pick_multiple_runs() {
2828        common_telemetry::init_default_ut_logging();
2829
2830        let num_files = 8;
2831        let file_ids = (0..num_files).map(|_| FileId::random()).collect::<Vec<_>>();
2832
2833        // Create files with different sequences so they form multiple runs
2834        let files: Vec<_> = file_ids
2835            .iter()
2836            .enumerate()
2837            .map(|(idx, file_id)| {
2838                new_file_handle_with_size_and_sequence(
2839                    *file_id,
2840                    0,
2841                    999,
2842                    0,
2843                    (idx + 1) as u64,
2844                    1024 * 1024,
2845                )
2846            })
2847            .collect();
2848
2849        let windows = assign_to_windows(files.iter(), 3);
2850
2851        let picker = TwcsPicker {
2852            trigger_file_num: 4,
2853            active_window_l1_merge_trigger: 8,
2854            inactive_window_trigger_file_num: 4,
2855            inactive_window_l1_merge_trigger: 8,
2856            time_window_seconds: Some(3),
2857            max_output_file_size: None,
2858            append_mode: false,
2859            merge_mode: MergeMode::LastRow,
2860            max_background_tasks: None,
2861            time_range: None,
2862            all_windows_inactive: false,
2863            metrics: Default::default(),
2864        };
2865
2866        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2867        let output = picker
2868            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2869            .await
2870            .unwrap();
2871
2872        assert_eq!(1, output.len());
2873        assert_eq!(output[0].inputs.len(), num_files);
2874    }
2875
2876    #[tokio::test]
2877    async fn test_window_trigger_can_exceed_input_limit() {
2878        common_telemetry::init_default_ut_logging();
2879
2880        let num_files = 50;
2881        let file_ids = (0..num_files).map(|_| FileId::random()).collect::<Vec<_>>();
2882
2883        // Create files with different sequences so they form 2 runs
2884        let files: Vec<_> = file_ids
2885            .iter()
2886            .enumerate()
2887            .map(|(idx, file_id)| {
2888                new_file_handle_with_size_and_sequence(
2889                    *file_id,
2890                    (idx / 2 * 10) as i64,
2891                    (idx / 2 * 10 + 5) as i64,
2892                    0,
2893                    (idx + 1) as u64,
2894                    1024 * 1024,
2895                )
2896            })
2897            .collect();
2898
2899        let windows = assign_to_windows(files.iter(), 3);
2900
2901        let picker = TwcsPicker {
2902            trigger_file_num: num_files,
2903            active_window_l1_merge_trigger: 8,
2904            inactive_window_trigger_file_num: num_files,
2905            inactive_window_l1_merge_trigger: 8,
2906            time_window_seconds: Some(3),
2907            max_output_file_size: None,
2908            append_mode: false,
2909            merge_mode: MergeMode::LastRow,
2910            max_background_tasks: None,
2911            time_range: None,
2912            all_windows_inactive: false,
2913            metrics: Default::default(),
2914        };
2915
2916        let active_window = find_latest_window_in_seconds(files.iter(), 3);
2917        let output = picker
2918            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2919            .await
2920            .unwrap();
2921
2922        assert_eq!(1, output.len());
2923        assert_eq!(output[0].inputs.len(), num_files.min(*MAX_INPUT_FILES));
2924    }
2925
2926    #[tokio::test]
2927    async fn test_limit_max_input_files_keeps_deletion_markers() {
2928        common_telemetry::init_default_ut_logging();
2929
2930        // One large file group spanning the whole window plus enough small ones to fill the
2931        // input limit. That is exactly 2 runs, so the window allows filtering deletions.
2932        let mut files = vec![new_file_handle_with_size_and_sequence(
2933            FileId::random(),
2934            0,
2935            3_000_000,
2936            0,
2937            1,
2938            1024 * 1024 * 1024,
2939        )];
2940        files.extend((0..DEFAULT_MAX_INPUT_FILES as i64).map(|idx| {
2941            new_file_handle_with_size_and_sequence(
2942                FileId::random(),
2943                (idx + 1) * 10_000,
2944                (idx + 1) * 10_000 + 1_000,
2945                0,
2946                (idx + 2) as u64,
2947                1024,
2948            )
2949        }));
2950
2951        let windows = assign_to_windows(files.iter(), 3600);
2952
2953        let picker = TwcsPicker {
2954            trigger_file_num: 4,
2955            active_window_l1_merge_trigger: 8,
2956            inactive_window_trigger_file_num: 4,
2957            inactive_window_l1_merge_trigger: 8,
2958            time_window_seconds: Some(3600),
2959            max_output_file_size: None,
2960            append_mode: false,
2961            merge_mode: MergeMode::LastRow,
2962            max_background_tasks: None,
2963            time_range: None,
2964            all_windows_inactive: false,
2965            metrics: Default::default(),
2966        };
2967
2968        let active_window = find_latest_window_in_seconds(files.iter(), 3600);
2969        let output = picker
2970            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
2971            .await
2972            .unwrap();
2973
2974        assert_eq!(1, output.len());
2975        // The input file num limit picks the smallest groups first, so the large group is
2976        // left behind while the small groups that overlap it are compacted.
2977        assert_eq!(DEFAULT_MAX_INPUT_FILES, output[0].inputs.len());
2978        assert!(
2979            !output[0].filter_deleted,
2980            "deletion markers must be kept once the file num limit drops files they may mask"
2981        );
2982    }
2983
2984    #[tokio::test]
2985    async fn test_limit_max_input_files_still_filters_without_overlap() {
2986        common_telemetry::init_default_ut_logging();
2987
2988        // More disjoint file groups than the input limit, i.e. a single run. Nothing left
2989        // behind can hold a row masked by a deletion marker we compact.
2990        let files: Vec<_> = (0..DEFAULT_MAX_INPUT_FILES as i64 + 8)
2991            .map(|idx| {
2992                new_file_handle_with_size_and_sequence(
2993                    FileId::random(),
2994                    (idx + 1) * 10_000,
2995                    (idx + 1) * 10_000 + 1_000,
2996                    0,
2997                    (idx + 1) as u64,
2998                    1024,
2999                )
3000            })
3001            .collect();
3002
3003        let windows = assign_to_windows(files.iter(), 3600);
3004
3005        let picker = TwcsPicker {
3006            trigger_file_num: 4,
3007            active_window_l1_merge_trigger: 8,
3008            inactive_window_trigger_file_num: 4,
3009            inactive_window_l1_merge_trigger: 8,
3010            time_window_seconds: Some(3600),
3011            max_output_file_size: Some(1024 * 1024 * 1024),
3012            append_mode: false,
3013            merge_mode: MergeMode::LastRow,
3014            max_background_tasks: None,
3015            time_range: None,
3016            all_windows_inactive: false,
3017            metrics: Default::default(),
3018        };
3019
3020        let active_window = find_latest_window_in_seconds(files.iter(), 3600);
3021        let output = picker
3022            .build_output_with_time_range(RegionId::from_u64(123), windows, active_window, None)
3023            .await
3024            .unwrap();
3025
3026        assert_eq!(1, output.len());
3027        assert_eq!(DEFAULT_MAX_INPUT_FILES, output[0].inputs.len());
3028        assert!(output[0].filter_deleted);
3029    }
3030
3031    #[tokio::test]
3032    async fn test_newer_windows_have_priority() {
3033        let older_file_ids = [FileId::random(), FileId::random()];
3034        let newer_file_ids = [FileId::random(), FileId::random()];
3035        let files = [
3036            new_file_handle_with_sequence(older_file_ids[0], 1_000, 1_999, 0, 1),
3037            new_file_handle_with_sequence(older_file_ids[1], 1_000, 1_999, 0, 2),
3038            new_file_handle_with_sequence(newer_file_ids[0], 7_000, 7_999, 0, 3),
3039            new_file_handle_with_sequence(newer_file_ids[1], 7_000, 7_999, 0, 4),
3040        ];
3041        let windows = assign_to_windows(files.iter(), 3);
3042        let picker = TwcsPicker {
3043            trigger_file_num: 2,
3044            active_window_l1_merge_trigger: 8,
3045            inactive_window_trigger_file_num: 2,
3046            inactive_window_l1_merge_trigger: 8,
3047            time_window_seconds: Some(3),
3048            max_output_file_size: None,
3049            append_mode: false,
3050            merge_mode: MergeMode::LastRow,
3051            max_background_tasks: Some(1),
3052            time_range: None,
3053            all_windows_inactive: false,
3054            metrics: Default::default(),
3055        };
3056
3057        let output = picker
3058            .build_output_with_time_range(RegionId::from_u64(123), windows, Some(6), None)
3059            .await
3060            .unwrap();
3061
3062        assert_eq!(1, output.len());
3063        assert_eq!(
3064            newer_file_ids.into_iter().collect::<HashSet<_>>(),
3065            output[0]
3066                .inputs
3067                .iter()
3068                .map(|file| file.file_id().file_id())
3069                .collect::<HashSet<_>>()
3070        );
3071    }
3072
3073    #[test]
3074    fn test_filter_time_windows_by_time_range() {
3075        // Interior, exclusive boundary ends, fractional boundary ends, negative
3076        // timestamps, and empty ranges must all use the same half-open windows.
3077        for (start, end, expected_windows) in [
3078            (1_200, 1_800, vec![0]),
3079            (0, 3_000, vec![0]),
3080            (3_000, 6_000, vec![3]),
3081            (2_999, 3_000, vec![0]),
3082            (2_999, 3_001, vec![0, 3]),
3083            (3_000, 3_001, vec![3]),
3084            (3_001, 3_002, vec![3]),
3085            (-3_000, 0, vec![-3]),
3086            (-3_001, -2_999, vec![-6, -3]),
3087            (0, 0, vec![]),
3088            (1_500, 1_500, vec![]),
3089        ] {
3090            let time_range = TimestampRange::with_unit(start, end, TimeUnit::Millisecond).unwrap();
3091            let selected = [-6, -3, 0, 3, 6]
3092                .into_iter()
3093                .filter(|window| time_window_intersects_range(*window, 3, &time_range))
3094                .collect::<Vec<_>>();
3095            assert_eq!(expected_windows, selected, "{time_range}");
3096        }
3097    }
3098
3099    #[test]
3100    fn test_filter_time_windows_with_unbounded_and_extreme_ranges() {
3101        for (range, expected_windows) in [
3102            (TimestampRange::min_to_max(), vec![-3, 0, 3]),
3103            (
3104                TimestampRange::from_start(Timestamp::new_second(0)),
3105                vec![0, 3],
3106            ),
3107            (
3108                TimestampRange::until_end(Timestamp::new_second(0), false),
3109                vec![-3],
3110            ),
3111        ] {
3112            let selected = [-3, 0, 3]
3113                .into_iter()
3114                .filter(|window| time_window_intersects_range(*window, 3, &range))
3115                .collect::<Vec<_>>();
3116            assert_eq!(expected_windows, selected, "{range}");
3117        }
3118
3119        let upper_range = TimestampRange::new(
3120            Timestamp::new_second(i64::MAX - 1),
3121            Timestamp::new_second(i64::MAX),
3122        )
3123        .unwrap();
3124        assert!(!time_window_intersects_range(0, 4, &upper_range));
3125        assert!(time_window_intersects_range(i64::MAX - 3, 4, &upper_range));
3126
3127        let lower_range = TimestampRange::until_end(Timestamp::new_second(i64::MIN), false);
3128        assert!(!time_window_intersects_range(i64::MIN, 3, &lower_range));
3129    }
3130
3131    #[tokio::test]
3132    async fn test_time_range_filter_precedes_background_task_limit() {
3133        let early_file_ids = [FileId::random(), FileId::random()];
3134        let selected_file_ids = [FileId::random(), FileId::random()];
3135        let files = [
3136            new_file_handle_with_sequence(early_file_ids[0], 1_000, 1_999, 0, 1),
3137            new_file_handle_with_sequence(early_file_ids[1], 1_000, 1_999, 0, 2),
3138            new_file_handle_with_sequence(selected_file_ids[0], 7_000, 7_999, 0, 3),
3139            new_file_handle_with_sequence(selected_file_ids[1], 7_000, 7_999, 0, 4),
3140        ];
3141        let windows = assign_to_windows(files.iter(), 3);
3142        let picker = TwcsPicker {
3143            trigger_file_num: 2,
3144            active_window_l1_merge_trigger: 8,
3145            inactive_window_trigger_file_num: 2,
3146            inactive_window_l1_merge_trigger: 8,
3147            time_window_seconds: Some(3),
3148            max_output_file_size: None,
3149            append_mode: false,
3150            merge_mode: MergeMode::LastRow,
3151            max_background_tasks: Some(1),
3152            time_range: TimestampRange::new(
3153                Timestamp::new_millisecond(7_200),
3154                Timestamp::new_millisecond(7_800),
3155            ),
3156            all_windows_inactive: false,
3157            metrics: Default::default(),
3158        };
3159
3160        let output = picker
3161            .build_output_with_time_range(RegionId::from_u64(123), windows, Some(6), Some(3))
3162            .await
3163            .unwrap();
3164
3165        assert_eq!(1, output.len());
3166        assert_eq!(
3167            selected_file_ids.into_iter().collect::<HashSet<_>>(),
3168            output[0]
3169                .inputs
3170                .iter()
3171                .map(|file| file.file_id().file_id())
3172                .collect::<HashSet<_>>()
3173        );
3174    }
3175
3176    #[tokio::test]
3177    async fn test_inactive_window_uses_its_trigger_file_num() {
3178        let files = [
3179            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 0, 1, 10),
3180            new_file_handle_with_size_and_sequence(FileId::random(), 20, 30, 0, 2, 10),
3181        ];
3182        let windows = assign_to_windows(files.iter(), 100);
3183        let picker = TwcsPicker {
3184            trigger_file_num: 4,
3185            active_window_l1_merge_trigger: 8,
3186            inactive_window_trigger_file_num: 2,
3187            inactive_window_l1_merge_trigger: 8,
3188            time_window_seconds: Some(100),
3189            max_output_file_size: None,
3190            append_mode: false,
3191            merge_mode: MergeMode::LastRow,
3192            max_background_tasks: None,
3193            time_range: None,
3194            all_windows_inactive: false,
3195            metrics: Default::default(),
3196        };
3197
3198        let output = picker
3199            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
3200            .await
3201            .unwrap();
3202
3203        assert_eq!(1, output.len());
3204        assert_eq!(2, output[0].inputs.len());
3205    }
3206
3207    #[tokio::test]
3208    async fn test_inactive_window_requires_a_level_trigger_before_mixed_fallback() {
3209        let files = [
3210            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 0, 1, 10),
3211            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 1, 2, 10),
3212        ];
3213        let windows = assign_to_windows(files.iter(), 100);
3214        let picker = TwcsPicker {
3215            trigger_file_num: 4,
3216            active_window_l1_merge_trigger: 8,
3217            inactive_window_trigger_file_num: 8,
3218            inactive_window_l1_merge_trigger: 2,
3219            time_window_seconds: Some(100),
3220            max_output_file_size: Some(1_000),
3221            append_mode: false,
3222            merge_mode: MergeMode::LastRow,
3223            max_background_tasks: None,
3224            time_range: None,
3225            all_windows_inactive: false,
3226            metrics: Default::default(),
3227        };
3228
3229        let output = picker
3230            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
3231            .await
3232            .unwrap();
3233
3234        assert!(output.is_empty());
3235    }
3236
3237    #[tokio::test]
3238    async fn test_count_first_prefers_more_files_over_smaller_overlap() {
3239        let files = [
3240            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 0, 1, 10),
3241            new_file_handle_with_size_and_sequence(FileId::random(), 20, 30, 0, 2, 10),
3242            new_file_handle_with_size_and_sequence(FileId::random(), 40, 50, 0, 3, 10),
3243            new_file_handle_with_size_and_sequence(FileId::random(), 5, 15, 0, 4, 10),
3244        ];
3245        let windows = assign_to_windows(files.iter(), 100);
3246        let picker = TwcsPicker {
3247            trigger_file_num: 2,
3248            active_window_l1_merge_trigger: 8,
3249            inactive_window_trigger_file_num: 2,
3250            inactive_window_l1_merge_trigger: 8,
3251            time_window_seconds: Some(100),
3252            max_output_file_size: None,
3253            append_mode: false,
3254            merge_mode: MergeMode::LastRow,
3255            max_background_tasks: None,
3256            time_range: None,
3257            all_windows_inactive: false,
3258            metrics: Default::default(),
3259        };
3260
3261        let output = picker
3262            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(0), None)
3263            .await
3264            .unwrap();
3265
3266        assert_eq!(1, output.len());
3267        assert_eq!(4, output[0].inputs.len());
3268    }
3269
3270    #[tokio::test]
3271    async fn test_count_first_trigger_counts_physical_ssts() {
3272        let files = [
3273            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 0, 1, 10),
3274            new_file_handle_with_size_and_sequence(FileId::random(), 0, 10, 0, 1, 10),
3275            new_file_handle_with_size_and_sequence(FileId::random(), 20, 30, 0, 2, 10),
3276        ];
3277        let windows = assign_to_windows(files.iter(), 100);
3278        let picker = TwcsPicker {
3279            trigger_file_num: 3,
3280            active_window_l1_merge_trigger: 8,
3281            inactive_window_trigger_file_num: 3,
3282            inactive_window_l1_merge_trigger: 8,
3283            time_window_seconds: Some(100),
3284            max_output_file_size: None,
3285            append_mode: false,
3286            merge_mode: MergeMode::LastRow,
3287            max_background_tasks: None,
3288            time_range: None,
3289            all_windows_inactive: false,
3290            metrics: Default::default(),
3291        };
3292
3293        let output = picker
3294            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(0), None)
3295            .await
3296            .unwrap();
3297
3298        assert_eq!(1, output.len());
3299        assert_eq!(3, output[0].inputs.len());
3300    }
3301
3302    #[tokio::test]
3303    async fn test_count_first_does_not_compact_overlap_below_trigger() {
3304        let files = [
3305            new_file_handle_with_size_and_sequence(FileId::random(), 0, 20, 0, 1, 10),
3306            new_file_handle_with_size_and_sequence(FileId::random(), 10, 30, 0, 2, 10),
3307        ];
3308        let windows = assign_to_windows(files.iter(), 100);
3309        let picker = TwcsPicker {
3310            trigger_file_num: 3,
3311            active_window_l1_merge_trigger: 8,
3312            inactive_window_trigger_file_num: 3,
3313            inactive_window_l1_merge_trigger: 8,
3314            time_window_seconds: Some(100),
3315            max_output_file_size: None,
3316            append_mode: false,
3317            merge_mode: MergeMode::LastRow,
3318            max_background_tasks: None,
3319            time_range: None,
3320            all_windows_inactive: false,
3321            metrics: Default::default(),
3322        };
3323
3324        let output = picker
3325            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(0), None)
3326            .await
3327            .unwrap();
3328
3329        assert!(output.is_empty());
3330    }
3331
3332    #[tokio::test]
3333    async fn test_filter_deleted_is_false_when_selected_files_overlap_unselected_file() {
3334        let mut files = (0..32)
3335            .map(|idx| {
3336                new_file_handle_with_size_and_sequence(
3337                    FileId::random(),
3338                    idx * 10,
3339                    idx * 10 + 9,
3340                    0,
3341                    idx as u64 + 1,
3342                    10,
3343                )
3344            })
3345            .collect::<Vec<_>>();
3346        files.push(new_file_handle_with_size_and_sequence(
3347            FileId::random(),
3348            0,
3349            320,
3350            0,
3351            33,
3352            10,
3353        ));
3354        let windows = assign_to_windows(files.iter(), 1000);
3355        let picker = TwcsPicker {
3356            trigger_file_num: 2,
3357            active_window_l1_merge_trigger: 8,
3358            inactive_window_trigger_file_num: 2,
3359            inactive_window_l1_merge_trigger: 8,
3360            time_window_seconds: Some(1000),
3361            max_output_file_size: None,
3362            append_mode: false,
3363            merge_mode: MergeMode::LastRow,
3364            max_background_tasks: None,
3365            time_range: None,
3366            all_windows_inactive: false,
3367            metrics: Default::default(),
3368        };
3369
3370        let output = picker
3371            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(0), None)
3372            .await
3373            .unwrap();
3374
3375        assert_eq!(1, output.len());
3376        assert_eq!(DEFAULT_MAX_INPUT_FILES, output[0].inputs.len());
3377        assert!(!output[0].filter_deleted);
3378    }
3379
3380    #[rstest::rstest]
3381    #[case::historical_l1(0, PickClass::FileReduction, 1)]
3382    #[case::same_window_l1(10, PickClass::FileReduction, 1)]
3383    #[case::older_l0(0, PickClass::L0Merge, 0)]
3384    #[case::historical_overlap(0, PickClass::OverlapResolution, 1)]
3385    #[tokio::test]
3386    async fn test_fair_picker_promotes_waiting_work_with_one_slot(
3387        #[case] waiting_window: i64,
3388        #[case] class: PickClass,
3389        #[case] level: Level,
3390    ) {
3391        let overlap = class == PickClass::OverlapResolution;
3392        let files = priority_test_files(10, 0, 40, false)
3393            .into_iter()
3394            .chain(priority_test_files(
3395                waiting_window,
3396                level,
3397                if overlap { 100 } else { 40 },
3398                overlap,
3399            ))
3400            .collect::<Vec<_>>();
3401        let mut history = PickHistory::default();
3402        let picker = priority_test_picker(1);
3403        let first = picker
3404            .build_output_with_history(assign_to_windows(files.iter(), 1), Some(10), &mut history)
3405            .await
3406            .unwrap();
3407        assert_eq!(1, first.len());
3408        assert!(first[0].inputs.iter().all(|f| f.level() == 0));
3409        assert_eq!(10, output_window(&first[0]));
3410
3411        // Advance the waiting candidate's age without sleeping. Discovery must
3412        // preserve it even while the hot window keeps supplying eligible L0.
3413        let key = PickKey {
3414            window: waiting_window,
3415            class,
3416        };
3417        history = PickHistory::default();
3418        history.observe_for_test([key].into_iter(), Instant::now() - Duration::from_secs(120));
3419        let output = picker
3420            .build_output_with_history(assign_to_windows(files.iter(), 1), Some(10), &mut history)
3421            .await
3422            .unwrap();
3423        assert_eq!(1, output.len());
3424        assert_eq!(waiting_window, output_window(&output[0]));
3425        assert!(output[0].inputs.iter().all(|f| f.level() == level));
3426        let expected: HashSet<_> = files
3427            .iter()
3428            .filter(|f| f.level() == level && f.time_range().1.value() / 1000 == waiting_window)
3429            .map(FileHandle::file_id)
3430            .collect();
3431        assert_eq!(
3432            expected,
3433            output[0].inputs.iter().map(FileHandle::file_id).collect()
3434        );
3435    }
3436
3437    #[tokio::test]
3438    async fn test_overdue_candidates_alternate_without_completion() {
3439        // A plan that is accepted but never completes must still consume the
3440        // fairness turn. Otherwise an older candidate that keeps failing keeps
3441        // the first slot and starves every other eligible window.
3442        let files = priority_test_files(0, 0, 40, false)
3443            .into_iter()
3444            .chain(priority_test_files(10, 0, 40, false))
3445            .collect::<Vec<_>>();
3446        let mut region = compaction_region_with_ssts(
3447            files.iter().map(|file| file.meta_ref().clone()),
3448            Duration::from_secs(60),
3449        )
3450        .await;
3451        region.ttl = None;
3452        let crate::region::options::CompactionOptions::Twcs(options) =
3453            &mut region.region_options.compaction;
3454        options.time_window = Some(Duration::from_secs(1));
3455        options.active_window_trigger_file_num = 2;
3456        let mut history = PickHistory::default();
3457        let start = Instant::now();
3458        history.seed_for_test(
3459            PickKey {
3460                window: 0,
3461                class: PickClass::L0Merge,
3462            },
3463            start - Duration::from_secs(120),
3464        );
3465        let younger = PickKey {
3466            window: 10,
3467            class: PickClass::L0Merge,
3468        };
3469        let waiting_since = start - Duration::from_secs(90);
3470        history.seed_for_test(younger, waiting_since);
3471
3472        // Exercise the production orchestration, not the test helper's copy of
3473        // rank/truncate/acknowledge: only the selected key may consume a turn.
3474        let first = pick_automatic_for_test(&region, &mut history, Some(1))
3475            .await
3476            .unwrap()
3477            .unwrap();
3478        assert_eq!(1, first.outputs.len());
3479        assert_eq!(0, output_window(&first.outputs[0]));
3480        assert_eq!(
3481            Some(waiting_since),
3482            history.promoted_since_for_test(younger, start)
3483        );
3484
3485        // No completion acknowledgement: selecting the older window already
3486        // consumed its turn, so the younger overdue window must go next.
3487        let second = pick_automatic_for_test(&region, &mut history, Some(1))
3488            .await
3489            .unwrap()
3490            .unwrap();
3491        assert_eq!(1, second.outputs.len());
3492        assert_eq!(10, output_window(&second.outputs[0]));
3493    }
3494
3495    #[rstest::rstest]
3496    #[case::stateless_early_exit(false, false, true)]
3497    #[case::fair_full_scan(true, false, true)]
3498    #[case::promoted_selection(true, true, true)]
3499    #[case::empty_plan(true, false, false)]
3500    #[tokio::test]
3501    async fn test_pick_metrics_cover_scanned_windows_and_selected_seeds(
3502        #[case] fair: bool,
3503        #[case] promoted: bool,
3504        #[case] eligible: bool,
3505    ) {
3506        let mut files = priority_test_files(10, 0, 40, false).to_vec();
3507        files.extend(priority_test_files(10, 1, 40, false));
3508        files.extend(priority_test_files(0, 1, 40, false));
3509        if !eligible {
3510            files = vec![files[0].clone(), files[4].clone()];
3511        }
3512        // Unregistered instances cannot be changed by other libtest threads.
3513        let selected_metrics = IntCounterVec::new(
3514            prometheus::Opts::new("test_twcs_selected", "selected seeds"),
3515            &["class", "priority"],
3516        )
3517        .unwrap();
3518        let picker = TwcsPicker {
3519            metrics: TwcsPickMetrics {
3520                elapsed: HistogramVec::new(
3521                    prometheus::HistogramOpts::new("test_twcs_pick_elapsed", "pick elapsed"),
3522                    &["mode"],
3523                )
3524                .unwrap(),
3525                scanned_windows: IntCounterVec::new(
3526                    prometheus::Opts::new("test_twcs_scanned_windows", "scanned windows"),
3527                    &["mode"],
3528                )
3529                .unwrap(),
3530            },
3531            ..priority_test_picker(1)
3532        };
3533        let mut history = PickHistory::with_selected_metrics_for_test(selected_metrics.clone());
3534        if fair && promoted {
3535            history.observe_for_test(
3536                [PickKey {
3537                    window: 0,
3538                    class: PickClass::FileReduction,
3539                }]
3540                .into_iter(),
3541                Instant::now() - Duration::from_secs(120),
3542            );
3543        }
3544        let mode = if fair { "fair" } else { "stateless" };
3545        let elapsed = picker.metrics.elapsed.with_label_values(&[mode]);
3546        let windows = picker.metrics.scanned_windows.with_label_values(&[mode]);
3547        let elapsed_before = elapsed.get_sample_count();
3548        let windows_before = windows.get();
3549        let selected = [
3550            PickClass::L0Merge,
3551            PickClass::FileReduction,
3552            PickClass::OverlapResolution,
3553        ]
3554        .into_iter()
3555        .flat_map(|class| {
3556            let selected_metrics = &selected_metrics;
3557            ["normal", "promoted"].into_iter().map(move |priority| {
3558                let counter = selected_metrics.with_label_values(&[class.as_str(), priority]);
3559                let before = counter.get();
3560                (class, priority, counter, before)
3561            })
3562        })
3563        .collect::<Vec<_>>();
3564
3565        let output = if fair {
3566            picker
3567                .build_output_with_history(
3568                    assign_to_windows(files.iter(), 1),
3569                    Some(10),
3570                    &mut history,
3571                )
3572                .await
3573                .unwrap()
3574        } else {
3575            picker
3576                .build_output_with_time_range(
3577                    RegionId::from_u64(1),
3578                    assign_to_windows(files.iter(), 1),
3579                    Some(10),
3580                    None,
3581                )
3582                .await
3583                .unwrap()
3584        };
3585        assert_eq!(usize::from(eligible), output.len());
3586        if eligible {
3587            assert_eq!(if promoted { 0 } else { 10 }, output_window(&output[0]));
3588        }
3589        assert_eq!(elapsed_before + 1, elapsed.get_sample_count());
3590        assert_eq!(windows_before + if fair { 2 } else { 1 }, windows.get());
3591        // Count only the single selected seed, not the other discovered classes
3592        // or the older window discarded by the output limit. Stateless picks
3593        // never contribute to automatic selection/promotion metrics.
3594        for (class, priority, counter, before) in selected {
3595            let chosen = if promoted {
3596                (PickClass::FileReduction, "promoted")
3597            } else {
3598                (PickClass::L0Merge, "normal")
3599            };
3600            let expected = u64::from(fair && eligible && (class, priority) == chosen);
3601            assert_eq!(before + expected, counter.get(), "{class:?}/{priority}");
3602        }
3603    }
3604
3605    #[tokio::test]
3606    async fn test_fair_inactive_closed_merge_absorbs_stranded_l0() {
3607        // R2-C1: one L0 cannot merge alone, and the mixed L0 fallback exceeds
3608        // its one-output budget. A closed overlap merge must still see both levels.
3609        let files = [
3610            new_file_handle_with_size_and_sequence(FileId::random(), 0, 499, 0, 1, 100),
3611            new_file_handle_with_size_and_sequence(FileId::random(), 250, 749, 1, 1, 100),
3612        ];
3613        let picker = priority_test_picker(1);
3614        let mut history = PickHistory::default();
3615        let output = picker
3616            .build_output_with_history(assign_to_windows(files.iter(), 1), Some(10), &mut history)
3617            .await
3618            .unwrap();
3619        assert_eq!(1, output.len());
3620        assert_eq!(
3621            files
3622                .iter()
3623                .map(FileHandle::file_id)
3624                .collect::<HashSet<_>>(),
3625            output[0].inputs.iter().map(FileHandle::file_id).collect()
3626        );
3627    }
3628
3629    #[rstest::rstest]
3630    #[case::stranded_l0(1)]
3631    #[case::eligible_l0_merge(2)]
3632    #[tokio::test]
3633    async fn test_fair_closed_merge_does_not_add_conflicts_with_l0(#[case] l0_count: usize) {
3634        // R2-C1: merging the two L1 files alone encloses previously disjoint L0
3635        // peers. Even an aged FileReduction must not displace safe L0 work with
3636        // such a merge; without L0 work this snapshot must produce no plan.
3637        let mut files = vec![
3638            new_file_handle_with_size_and_sequence(FileId::random(), 0, 99, 1, 1, 40),
3639            new_file_handle_with_size_and_sequence(FileId::random(), 200, 299, 1, 1, 40),
3640        ];
3641        files.extend((0..l0_count).map(|_| {
3642            new_file_handle_with_size_and_sequence(FileId::random(), 100, 199, 0, 1, 1000)
3643        }));
3644        let mut history = PickHistory::default();
3645        history.observe_for_test(
3646            [PickKey {
3647                window: 0,
3648                class: PickClass::FileReduction,
3649            }]
3650            .into_iter(),
3651            Instant::now() - Duration::from_secs(120),
3652        );
3653        let picker = priority_test_picker(1);
3654        let output = picker
3655            .build_output_with_history(assign_to_windows(files.iter(), 1), Some(10), &mut history)
3656            .await
3657            .unwrap();
3658        if l0_count == 1 {
3659            assert!(output.is_empty());
3660        } else {
3661            assert_eq!(1, output.len());
3662            assert_eq!(
3663                files[2..]
3664                    .iter()
3665                    .map(FileHandle::file_id)
3666                    .collect::<HashSet<_>>(),
3667                output[0].inputs.iter().map(FileHandle::file_id).collect()
3668            );
3669        }
3670    }
3671
3672    #[rstest::rstest]
3673    #[case::active(0, MergeMode::LastRow, "active:pick_l1_file_reduction")]
3674    #[case::inactive(10, MergeMode::LastRow, "inactive:pick_l1_file_reduction")]
3675    #[case::settling_fallback(1, MergeMode::LastRow, "inactive:pick_small_l1")]
3676    #[case::settling_last_non_null(1, MergeMode::LastNonNull, "")]
3677    fn test_window_discovery_keeps_l1_alongside_l0(
3678        #[case] active_window: i64,
3679        #[case] merge_mode: MergeMode,
3680        #[case] l1_branch: &str,
3681    ) {
3682        let files = priority_test_files(0, 0, 40, false)
3683            .into_iter()
3684            .chain(priority_test_files(0, 1, 20, true))
3685            .collect::<Vec<_>>();
3686        let windows = assign_to_windows(files.iter(), 1);
3687        let mapper = primary_key_mapper_for_test();
3688        let mut context = WindowPickContext {
3689            all_candidates: false,
3690            region_id: RegionId::from_u64(1),
3691            active_window: Some(active_window),
3692            time_window_size: Some(1),
3693            region_sequence: 100,
3694            mapper: &mapper,
3695        };
3696        let mut picker = priority_test_picker(4);
3697        picker.merge_mode = merge_mode;
3698        let legacy = picker.pick_window(&windows[&0], &context);
3699        assert_eq!(1, legacy.len());
3700        assert_eq!(PickClass::L0Merge, legacy[0].class);
3701
3702        context.all_candidates = true;
3703        let picks = picker.pick_window(&windows[&0], &context);
3704        assert_eq!(if l1_branch.is_empty() { 1 } else { 2 }, picks.len());
3705        assert_eq!(PickClass::L0Merge, picks[0].class);
3706        if !l1_branch.is_empty() {
3707            assert_eq!(PickClass::FileReduction, picks[1].class);
3708            assert_eq!(l1_branch, picks[1].branch);
3709            assert_eq!(
3710                files
3711                    .iter()
3712                    // Inactive closed merges include overlapping L0 peers;
3713                    // active picks and the small-L1 fallback remain L1-only.
3714                    .filter(|file| active_window == 10 || file.level() == 1)
3715                    .map(FileHandle::file_id)
3716                    .collect::<HashSet<_>>(),
3717                picks[1]
3718                    .inputs
3719                    .iter()
3720                    .map(FileHandle::file_id)
3721                    .collect::<HashSet<_>>()
3722            );
3723        }
3724    }
3725
3726    #[tokio::test]
3727    async fn test_fair_picker_does_not_schedule_same_window_alternatives_together() {
3728        let files = priority_test_files(0, 0, 40, false)
3729            .into_iter()
3730            .chain(priority_test_files(0, 1, 40, false))
3731            .collect::<Vec<_>>();
3732        let picker = priority_test_picker(4);
3733        let mut history = PickHistory::default();
3734        let output = picker
3735            .build_output_with_history(assign_to_windows(files.iter(), 1), Some(0), &mut history)
3736            .await
3737            .unwrap();
3738        assert_eq!(1, output.len());
3739        assert!(output[0].inputs.iter().all(|f| f.level() == 0));
3740        assert!(
3741            !output[0].filter_deleted,
3742            "unselected overlapping L1 must retain tombstones"
3743        );
3744    }
3745
3746    fn new_file(start: i64, end: i64, sequence: u64, file_size: u64) -> FileHandle {
3747        new_file_handle_with_size_and_sequence(FileId::random(), start, end, 0, sequence, file_size)
3748    }
3749
3750    fn new_file_with_level_and_rows(
3751        start: i64,
3752        end: i64,
3753        level: Level,
3754        sequence: u64,
3755        file_size: u64,
3756        num_rows: u64,
3757    ) -> FileHandle {
3758        let file = new_file_handle_with_size_and_sequence(
3759            FileId::random(),
3760            start,
3761            end,
3762            level,
3763            sequence,
3764            file_size,
3765        );
3766        let mut meta = file.meta_ref().clone();
3767        meta.num_rows = num_rows;
3768        FileHandle::new(meta, crate::test_util::new_noop_file_purger())
3769    }
3770
3771    fn picked_ranges(files: &[FileHandle]) -> Vec<(i64, i64)> {
3772        files
3773            .iter()
3774            .map(|file| {
3775                let (start, end) = file.range();
3776                (start.value(), end.value())
3777            })
3778            .collect()
3779    }
3780
3781    #[test]
3782    fn test_count_first_rejects_dominant_historical_file() {
3783        let picked = pick_count_first(
3784            vec![SortedRun::from(vec![
3785                new_file(0, 9, 1, 400),
3786                new_file(20, 29, 2, 100),
3787            ])],
3788            None,
3789        );
3790
3791        assert!(picked.is_empty());
3792    }
3793
3794    #[test]
3795    fn test_count_first_accepts_balanced_historical_file() {
3796        let picked = pick_count_first(
3797            vec![SortedRun::from(vec![
3798                new_file(0, 9, 1, 400),
3799                new_file(20, 29, 2, 100),
3800                new_file(40, 49, 3, 100),
3801                new_file(60, 69, 4, 100),
3802                new_file(80, 89, 5, 100),
3803            ])],
3804            None,
3805        );
3806
3807        assert_eq!(
3808            vec![(0, 9), (20, 29), (40, 49), (60, 69), (80, 89)],
3809            picked_ranges(&picked)
3810        );
3811    }
3812
3813    #[test]
3814    fn test_count_first_finds_smaller_balanced_interval_when_larger_one_is_unbalanced() {
3815        let picked = pick_count_first(
3816            vec![SortedRun::from(vec![
3817                new_file(0, 9, 1, 1000),
3818                new_file(20, 29, 2, 100),
3819                new_file(40, 49, 3, 100),
3820                new_file(60, 69, 4, 100),
3821                new_file(80, 89, 5, 100),
3822            ])],
3823            None,
3824        );
3825
3826        assert_eq!(
3827            vec![(20, 29), (40, 49), (60, 69), (80, 89)],
3828            picked_ranges(&picked)
3829        );
3830    }
3831
3832    #[test]
3833    fn test_count_first_prefers_overlap_participants_when_file_counts_match() {
3834        let first_run = (0..DEFAULT_MAX_INPUT_FILES)
3835            .map(|idx| {
3836                let start = idx as i64 * 20;
3837                let end = if idx + 1 == DEFAULT_MAX_INPUT_FILES {
3838                    700
3839                } else {
3840                    start + 9
3841                };
3842                new_file(start, end, idx as u64 + 1, 10)
3843            })
3844            .collect::<Vec<_>>();
3845        let overlapping = new_file(690, 710, 100, 10);
3846
3847        let picked = pick_count_first(
3848            vec![
3849                SortedRun::from(first_run),
3850                SortedRun::from(vec![overlapping]),
3851            ],
3852            None,
3853        );
3854        let ranges = picked_ranges(&picked);
3855
3856        assert_eq!(DEFAULT_MAX_INPUT_FILES, ranges.len());
3857        assert!(!ranges.contains(&(0, 9)));
3858        assert!(ranges.contains(&(690, 710)));
3859    }
3860
3861    #[tokio::test]
3862    async fn test_picker_avoids_chained_l1_rewrites_by_compacting_levels_separately() {
3863        let mut enough_l0 = (0..DEFAULT_MAX_INPUT_FILES)
3864            .map(|idx| {
3865                let start = idx as i64 * 20;
3866                new_file_handle_with_size_and_sequence(
3867                    FileId::random(),
3868                    start,
3869                    start + 9,
3870                    0,
3871                    idx as u64 + 1,
3872                    10,
3873                )
3874            })
3875            .collect::<Vec<_>>();
3876        enough_l0.push(new_file_handle_with_size_and_sequence(
3877            FileId::random(),
3878            0,
3879            700,
3880            1,
3881            100,
3882            100,
3883        ));
3884        let mut enough_l1 = (0..4)
3885            .map(|idx| {
3886                new_file_handle_with_size_and_sequence(
3887                    FileId::random(),
3888                    idx * 100,
3889                    idx * 100 + 99,
3890                    1,
3891                    idx as u64 + 1,
3892                    100,
3893                )
3894            })
3895            .collect::<Vec<_>>();
3896        enough_l1.extend((0..3).map(|idx| {
3897            new_file_handle_with_size_and_sequence(
3898                FileId::random(),
3899                idx * 20,
3900                idx * 20 + 9,
3901                0,
3902                idx as u64 + 10,
3903                10,
3904            )
3905        }));
3906        let picker = TwcsPicker {
3907            trigger_file_num: 4,
3908            active_window_l1_merge_trigger: 8,
3909            inactive_window_trigger_file_num: 4,
3910            inactive_window_l1_merge_trigger: 4,
3911            time_window_seconds: Some(1),
3912            max_output_file_size: None,
3913            append_mode: false,
3914            merge_mode: MergeMode::LastRow,
3915            max_background_tasks: None,
3916            time_range: None,
3917            all_windows_inactive: false,
3918            metrics: Default::default(),
3919        };
3920
3921        for (case, files, expected_level, expected_len) in [
3922            ("L0 reaches trigger", enough_l0, 0, DEFAULT_MAX_INPUT_FILES),
3923            ("L0 fallback precedes triggered L1", enough_l1, 0, 3),
3924        ] {
3925            let windows = assign_to_windows(files.iter(), 1);
3926            let output = picker
3927                .build_output_with_time_range(RegionId::from_u64(1), windows, Some(1), None)
3928                .await
3929                .unwrap();
3930
3931            assert_eq!(1, output.len(), "{case}");
3932            assert_eq!(expected_len, output[0].inputs.len(), "{case}");
3933            assert!(
3934                output[0]
3935                    .inputs
3936                    .iter()
3937                    .all(|file| file.level() == expected_level),
3938                "{case}"
3939            );
3940        }
3941    }
3942
3943    #[tokio::test]
3944    async fn test_active_window_defers_l1_below_safety_trigger() {
3945        let files = (0..7)
3946            .map(|idx| {
3947                let start = idx * 100;
3948                new_file_handle_with_size_and_sequence(
3949                    FileId::random(),
3950                    start,
3951                    start + 99,
3952                    1,
3953                    idx as u64 + 1,
3954                    100,
3955                )
3956            })
3957            .collect::<Vec<_>>();
3958        let windows = assign_to_windows(files.iter(), 1);
3959        let active_window = windows.keys().next().copied();
3960        let picker = TwcsPicker {
3961            trigger_file_num: 4,
3962            active_window_l1_merge_trigger: 8,
3963            inactive_window_trigger_file_num: 2,
3964            inactive_window_l1_merge_trigger: 8,
3965            time_window_seconds: Some(1),
3966            max_output_file_size: None,
3967            append_mode: false,
3968            merge_mode: MergeMode::LastRow,
3969            max_background_tasks: None,
3970            time_range: None,
3971            all_windows_inactive: false,
3972            metrics: Default::default(),
3973        };
3974
3975        let output = picker
3976            .build_output_with_time_range(RegionId::from_u64(1), windows, active_window, None)
3977            .await
3978            .unwrap();
3979
3980        assert!(output.is_empty());
3981    }
3982
3983    #[tokio::test]
3984    async fn test_active_window_l1_safety_trigger_is_independent_of_l0_trigger() {
3985        let files = (0..8)
3986            .map(|idx| {
3987                let start = idx * 100;
3988                new_file_handle_with_size_and_sequence(
3989                    FileId::random(),
3990                    start,
3991                    start + 99,
3992                    1,
3993                    idx as u64 + 1,
3994                    100,
3995                )
3996            })
3997            .collect::<Vec<_>>();
3998        let windows = assign_to_windows(files.iter(), 1);
3999        let active_window = windows.keys().next().copied();
4000        let picker = TwcsPicker {
4001            trigger_file_num: 16,
4002            active_window_l1_merge_trigger: 8,
4003            inactive_window_trigger_file_num: 2,
4004            inactive_window_l1_merge_trigger: 8,
4005            time_window_seconds: Some(1),
4006            max_output_file_size: None,
4007            append_mode: false,
4008            merge_mode: MergeMode::LastRow,
4009            max_background_tasks: None,
4010            time_range: None,
4011            all_windows_inactive: false,
4012            metrics: Default::default(),
4013        };
4014
4015        let output = picker
4016            .build_output_with_time_range(RegionId::from_u64(1), windows, active_window, None)
4017            .await
4018            .unwrap();
4019
4020        assert_eq!(1, output.len());
4021        assert_eq!(8, output[0].inputs.len());
4022        assert!(output[0].inputs.iter().all(|file| file.level() == 1));
4023    }
4024
4025    #[tokio::test]
4026    async fn test_picker_falls_back_to_l1_when_triggered_l0_cannot_make_progress() {
4027        let mut files = (0..4)
4028            .map(|idx| {
4029                let start = idx * 20;
4030                new_file_handle_with_size_and_sequence(
4031                    FileId::random(),
4032                    start,
4033                    start + 9,
4034                    0,
4035                    idx as u64 + 1,
4036                    600,
4037                )
4038            })
4039            .collect::<Vec<_>>();
4040        files.extend((0..8).map(|idx| {
4041            let start = idx * 20 + 100;
4042            new_file_handle_with_size_and_sequence(
4043                FileId::random(),
4044                start,
4045                start + 9,
4046                1,
4047                idx as u64 + 10,
4048                50,
4049            )
4050        }));
4051        let windows = assign_to_windows(files.iter(), 1);
4052        let active_window = windows.keys().next().copied();
4053        let picker = TwcsPicker {
4054            trigger_file_num: 4,
4055            active_window_l1_merge_trigger: 8,
4056            inactive_window_trigger_file_num: 4,
4057            inactive_window_l1_merge_trigger: 8,
4058            time_window_seconds: Some(1),
4059            max_output_file_size: Some(512),
4060            append_mode: false,
4061            merge_mode: MergeMode::LastRow,
4062            max_background_tasks: None,
4063            time_range: None,
4064            all_windows_inactive: false,
4065            metrics: Default::default(),
4066        };
4067
4068        let output = picker
4069            .build_output_with_time_range(RegionId::from_u64(1), windows, active_window, None)
4070            .await
4071            .unwrap();
4072
4073        assert_eq!(1, output.len());
4074        assert_eq!(8, output[0].inputs.len());
4075        assert!(output[0].inputs.iter().all(|file| file.level() == 1));
4076    }
4077
4078    fn priority_test_files(
4079        window: i64,
4080        level: Level,
4081        file_size: u64,
4082        overlap: bool,
4083    ) -> [FileHandle; 2] {
4084        let start = window * 1_000;
4085        let ranges = if overlap {
4086            [(start, start + 499), (start + 250, start + 749)]
4087        } else {
4088            [(start, start + 99), (start + 200, start + 299)]
4089        };
4090        ranges.map(|(start, end)| {
4091            new_file_handle_with_size_and_sequence(
4092                FileId::random(),
4093                start,
4094                end,
4095                level,
4096                window as u64 + 1,
4097                file_size,
4098            )
4099        })
4100    }
4101
4102    fn priority_test_picker(max_background_tasks: usize) -> TwcsPicker {
4103        TwcsPicker {
4104            trigger_file_num: 2,
4105            active_window_l1_merge_trigger: 2,
4106            inactive_window_trigger_file_num: 2,
4107            inactive_window_l1_merge_trigger: 2,
4108            time_window_seconds: Some(1),
4109            max_output_file_size: Some(100),
4110            append_mode: false,
4111            merge_mode: MergeMode::LastRow,
4112            max_background_tasks: Some(max_background_tasks),
4113            time_range: None,
4114            all_windows_inactive: false,
4115            metrics: Default::default(),
4116        }
4117    }
4118
4119    fn output_window(output: &CompactionOutput) -> i64 {
4120        output.inputs[0]
4121            .time_range()
4122            .1
4123            .convert_to(TimeUnit::Second)
4124            .unwrap()
4125            .value()
4126    }
4127
4128    #[tokio::test]
4129    async fn test_manual_compaction_resolves_active_window_overlaps() {
4130        let files = priority_test_files(5, 1, 100, true);
4131        for (all_windows_inactive, expected) in [(false, 0), (true, 1)] {
4132            let picker = TwcsPicker {
4133                all_windows_inactive,
4134                ..priority_test_picker(1)
4135            };
4136            let output = picker
4137                .build_output_with_time_range(
4138                    RegionId::from_u64(1),
4139                    assign_to_windows(files.iter(), 1),
4140                    Some(5),
4141                    None,
4142                )
4143                .await
4144                .unwrap();
4145            assert_eq!(expected, output.len(), "manual: {all_windows_inactive}");
4146        }
4147    }
4148
4149    #[tokio::test]
4150    async fn test_shared_boundary_l1_files_resolve_in_inactive_and_manual_windows() {
4151        let files = [(b"a", b"m"), (b"m", b"z")].map(|(min, max)| {
4152            new_file_handle_with_size_sequence_and_primary_key_range(
4153                FileId::random(),
4154                0,
4155                100,
4156                1,
4157                1,
4158                100,
4159                pk_range(min, max),
4160            )
4161        });
4162        for (active_window, all_windows_inactive, expected) in
4163            [(0, false, 0), (0, true, 1), (3, false, 1)]
4164        {
4165            let picker = TwcsPicker {
4166                all_windows_inactive,
4167                ..priority_test_picker(1)
4168            };
4169            let output = picker
4170                .build_output_with_time_range(
4171                    RegionId::from_u64(1),
4172                    assign_to_windows(files.iter(), 1),
4173                    Some(active_window),
4174                    Some(1),
4175                )
4176                .await
4177                .unwrap();
4178            assert_eq!(
4179                expected,
4180                output.len(),
4181                "active: {active_window}, manual: {all_windows_inactive}"
4182            );
4183            if let Some(output) = output.first() {
4184                assert_eq!(2, output.inputs.len());
4185            }
4186        }
4187    }
4188
4189    #[tokio::test]
4190    async fn test_settling_window_defers_overlap_resolution() {
4191        let files = priority_test_files(3, 1, 100, true);
4192        for (active_window, all_windows_inactive, expected) in
4193            [(4, false, 0), (5, false, 1), (2, false, 1), (4, true, 1)]
4194        {
4195            let picker = TwcsPicker {
4196                all_windows_inactive,
4197                ..priority_test_picker(1)
4198            };
4199            let output = picker
4200                .build_output_with_time_range(
4201                    RegionId::from_u64(1),
4202                    assign_to_windows(files.iter(), 1),
4203                    Some(active_window),
4204                    Some(1),
4205                )
4206                .await
4207                .unwrap();
4208            assert_eq!(
4209                expected,
4210                output.len(),
4211                "active: {active_window}, manual: {all_windows_inactive}"
4212            );
4213        }
4214    }
4215
4216    #[tokio::test]
4217    async fn test_inactive_windows_merge_small_l1_without_large_peer() {
4218        let large =
4219            new_file_handle_with_size_and_sequence(FileId::random(), 3_000, 3_999, 1, 1, 1_000);
4220        let small = priority_test_files(3, 1, 20, true);
4221        let files = [vec![large.clone()], small.to_vec()].concat();
4222        // The immediate predecessor is settling; the older window is not quiet.
4223        for (active_window, merge_mode, trigger, expected) in [
4224            (4, MergeMode::LastRow, 2, 1),
4225            (5, MergeMode::LastRow, 2, 1),
4226            (4, MergeMode::LastNonNull, 2, 0),
4227            (5, MergeMode::LastNonNull, 2, 0),
4228            (4, MergeMode::LastRow, 4, 0),
4229        ] {
4230            let picker = TwcsPicker {
4231                merge_mode,
4232                inactive_window_l1_merge_trigger: trigger,
4233                ..priority_test_picker(1)
4234            };
4235            let output = picker
4236                .build_output_with_time_range(
4237                    RegionId::from_u64(1),
4238                    assign_to_windows(files.iter(), 1),
4239                    Some(active_window),
4240                    Some(1),
4241                )
4242                .await
4243                .unwrap();
4244            assert_eq!(
4245                expected,
4246                output.len(),
4247                "active: {active_window}, mode: {merge_mode:?}, trigger: {trigger}"
4248            );
4249            if expected == 0 {
4250                continue;
4251            }
4252            let inputs: HashSet<_> = output[0].inputs.iter().map(FileHandle::file_id).collect();
4253            assert_eq!(
4254                small
4255                    .iter()
4256                    .map(FileHandle::file_id)
4257                    .collect::<HashSet<_>>(),
4258                inputs
4259            );
4260            assert!(
4261                !output[0].filter_deleted,
4262                "the unselected large file still overlaps"
4263            );
4264        }
4265    }
4266
4267    #[tokio::test]
4268    async fn test_small_l1_fallback_checks_large_append_mode_peer() {
4269        // Two conflicting small files form a non-rectangular area. Their union
4270        // would introduce a conflict with the large file in the empty corner.
4271        let files = [
4272            (0, 20, b"a", b"m", 20),
4273            (10, 30, b"l", b"z", 20),
4274            (0, 5, b"y", b"z", 1_000),
4275        ]
4276        .map(|(start, end, min, max, size)| {
4277            new_file_handle_with_size_sequence_and_primary_key_range(
4278                FileId::random(),
4279                start,
4280                end,
4281                1,
4282                1,
4283                size,
4284                pk_range(min, max),
4285            )
4286        });
4287        for append_mode in [false, true] {
4288            let picker = TwcsPicker {
4289                append_mode,
4290                ..priority_test_picker(1)
4291            };
4292            let output = picker
4293                .build_output_with_time_range(
4294                    RegionId::from_u64(1),
4295                    assign_to_windows(files.iter(), 1),
4296                    Some(1),
4297                    Some(1),
4298                )
4299                .await
4300                .unwrap();
4301            assert!(output.is_empty(), "append mode: {append_mode}");
4302        }
4303    }
4304
4305    #[tokio::test]
4306    async fn test_settling_window_does_not_rewrite_l1_for_late_data() {
4307        // A late L0 file overlapping both L1 files, which a mixed merge absorbs.
4308        let mut files = priority_test_files(3, 1, 40, false).to_vec();
4309        files.push(new_file_handle_with_size_and_sequence(
4310            FileId::random(),
4311            3_000,
4312            3_299,
4313            0,
4314            10,
4315            10,
4316        ));
4317        for (active_window, expected) in [(4, 0), (5, 1)] {
4318            let output = priority_test_picker(1)
4319                .build_output_with_time_range(
4320                    RegionId::from_u64(1),
4321                    assign_to_windows(files.iter(), 1),
4322                    Some(active_window),
4323                    Some(1),
4324                )
4325                .await
4326                .unwrap();
4327            assert_eq!(expected, output.len(), "active: {active_window}");
4328        }
4329    }
4330
4331    #[tokio::test]
4332    async fn test_older_l0_candidate_has_priority_over_newer_pure_l1_candidate() {
4333        let files = priority_test_files(0, 0, 40, false)
4334            .into_iter()
4335            .chain(priority_test_files(1, 1, 40, false))
4336            .collect::<Vec<_>>();
4337        let windows = assign_to_windows(files.iter(), 1);
4338
4339        let output = priority_test_picker(1)
4340            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(1), None)
4341            .await
4342            .unwrap();
4343
4344        assert_eq!(1, output.len());
4345        assert_eq!(0, output_window(&output[0]));
4346        assert!(output[0].inputs.iter().all(|file| file.level() == 0));
4347    }
4348
4349    #[tokio::test]
4350    async fn test_older_l1_file_reduction_has_priority_over_newer_overlap_resolution() {
4351        let files = priority_test_files(0, 1, 40, false)
4352            .into_iter()
4353            .chain(priority_test_files(1, 1, 100, true))
4354            .collect::<Vec<_>>();
4355        let windows = assign_to_windows(files.iter(), 1);
4356
4357        let output = priority_test_picker(1)
4358            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(1), None)
4359            .await
4360            .unwrap();
4361
4362        assert_eq!(1, output.len());
4363        assert_eq!(0, output_window(&output[0]));
4364    }
4365
4366    #[tokio::test]
4367    async fn test_multiple_slots_follow_class_priority_and_newer_first_within_class() {
4368        let files = [
4369            priority_test_files(0, 0, 40, false),
4370            priority_test_files(1, 0, 40, false),
4371            priority_test_files(2, 1, 40, false),
4372            priority_test_files(3, 1, 40, false),
4373            priority_test_files(4, 1, 100, true),
4374            priority_test_files(5, 1, 100, true),
4375        ]
4376        .into_iter()
4377        .flatten()
4378        .collect::<Vec<_>>();
4379        let windows = assign_to_windows(files.iter(), 1);
4380
4381        let output = priority_test_picker(5)
4382            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(5), None)
4383            .await
4384            .unwrap();
4385        let pop_priority = output
4386            .iter()
4387            .rev()
4388            .map(|output| (output.inputs[0].level(), output_window(output)))
4389            .collect::<Vec<_>>();
4390
4391        // The active window 5 only reduces files, so the overlap slot goes to
4392        // the inactive window 4.
4393        assert_eq!(vec![(0, 1), (0, 0), (1, 3), (1, 2), (1, 4)], pop_priority);
4394        let units = crate::compaction::unit::CompactionUnit::from_picker(PickerOutput {
4395            outputs: output,
4396            time_window_size: 1,
4397            ..Default::default()
4398        })
4399        .unwrap();
4400        let unit_priority = units
4401            .iter()
4402            .map(|unit| {
4403                (
4404                    unit.outputs[0].inputs[0].level(),
4405                    output_window(&unit.outputs[0]),
4406                )
4407            })
4408            .collect::<Vec<_>>();
4409        assert_eq!(
4410            pop_priority, unit_priority,
4411            "local FIFO must follow the picker's execution priority"
4412        );
4413    }
4414
4415    #[tokio::test]
4416    async fn test_inactive_window_mixed_fallback_merges_within_rewrite_budget() {
4417        let files = [
4418            new_file_with_level_and_rows(0, 99, 1, 1, 1_000, 1_000_000),
4419            new_file_with_level_and_rows(0, 9, 0, 2, 10, 1),
4420        ];
4421        let windows = assign_to_windows(files.iter(), 100);
4422        let picker = TwcsPicker {
4423            trigger_file_num: 4,
4424            active_window_l1_merge_trigger: 8,
4425            inactive_window_trigger_file_num: 2,
4426            inactive_window_l1_merge_trigger: 8,
4427            time_window_seconds: Some(100),
4428            max_output_file_size: Some(2_000),
4429            append_mode: false,
4430            merge_mode: MergeMode::LastRow,
4431            max_background_tasks: None,
4432            time_range: None,
4433            all_windows_inactive: false,
4434            metrics: Default::default(),
4435        };
4436
4437        let output = picker
4438            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
4439            .await
4440            .unwrap();
4441
4442        assert_eq!(1, output.len());
4443        assert_eq!(2, output[0].inputs.len());
4444    }
4445
4446    #[tokio::test]
4447    async fn test_inactive_window_over_budget_merges_l0_only() {
4448        // L0 files are unbalanced among themselves, and merging in the huge L1 file
4449        // would exceed the rewrite budget: only the L0 files are compacted.
4450        let files = [
4451            new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 10_000),
4452            new_file_handle_with_size_and_sequence(FileId::random(), 20, 29, 0, 2, 10),
4453            new_file_handle_with_size_and_sequence(FileId::random(), 0, 99, 1, 3, 1_000_000),
4454        ];
4455        let windows = assign_to_windows(files.iter(), 100);
4456        let picker = TwcsPicker {
4457            trigger_file_num: 4,
4458            active_window_l1_merge_trigger: 8,
4459            inactive_window_trigger_file_num: 2,
4460            inactive_window_l1_merge_trigger: 8,
4461            time_window_seconds: Some(100),
4462            max_output_file_size: Some(100_000),
4463            append_mode: false,
4464            merge_mode: MergeMode::LastRow,
4465            max_background_tasks: None,
4466            time_range: None,
4467            all_windows_inactive: false,
4468            metrics: Default::default(),
4469        };
4470
4471        let output = picker
4472            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
4473            .await
4474            .unwrap();
4475
4476        assert_eq!(1, output.len());
4477        assert_eq!(2, output[0].inputs.len());
4478        assert!(output[0].inputs.iter().all(|file| file.level() == 0));
4479    }
4480
4481    #[tokio::test]
4482    async fn test_inactive_window_over_budget_without_l0_pair_does_not_merge() {
4483        // A single tiny L0 and a huge L1: merging is over budget and there is no
4484        // L0 pair to converge, so the window is left as-is.
4485        let files = [
4486            new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 10),
4487            new_file_handle_with_size_and_sequence(FileId::random(), 0, 99, 1, 2, 1_000_000),
4488        ];
4489        let windows = assign_to_windows(files.iter(), 100);
4490        let picker = TwcsPicker {
4491            trigger_file_num: 4,
4492            active_window_l1_merge_trigger: 8,
4493            inactive_window_trigger_file_num: 2,
4494            inactive_window_l1_merge_trigger: 8,
4495            time_window_seconds: Some(100),
4496            max_output_file_size: Some(100_000),
4497            append_mode: false,
4498            merge_mode: MergeMode::LastRow,
4499            max_background_tasks: None,
4500            time_range: None,
4501            all_windows_inactive: false,
4502            metrics: Default::default(),
4503        };
4504
4505        let output = picker
4506            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
4507            .await
4508            .unwrap();
4509
4510        assert!(output.is_empty());
4511    }
4512
4513    #[tokio::test]
4514    async fn test_inactive_window_falls_through_when_triggered_l0_pick_fails() {
4515        // L0 reaches the inactive trigger but is unbalanced; L1 is below the
4516        // trigger. The window must still converge through the budgeted mixed
4517        // fallback instead of being skipped.
4518        let files = [
4519            new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 100_000),
4520            new_file_handle_with_size_and_sequence(FileId::random(), 20, 29, 0, 2, 10),
4521            new_file_handle_with_size_and_sequence(FileId::random(), 0, 99, 1, 3, 50_000),
4522        ];
4523        let windows = assign_to_windows(files.iter(), 100);
4524        let picker = TwcsPicker {
4525            trigger_file_num: 4,
4526            active_window_l1_merge_trigger: 8,
4527            inactive_window_trigger_file_num: 2,
4528            inactive_window_l1_merge_trigger: 8,
4529            time_window_seconds: Some(100),
4530            max_output_file_size: Some(1_000_000),
4531            append_mode: false,
4532            merge_mode: MergeMode::LastRow,
4533            max_background_tasks: None,
4534            time_range: None,
4535            all_windows_inactive: false,
4536            metrics: Default::default(),
4537        };
4538
4539        let output = picker
4540            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(100), None)
4541            .await
4542            .unwrap();
4543
4544        assert_eq!(1, output.len());
4545        assert_eq!(3, output[0].inputs.len());
4546    }
4547
4548    #[test]
4549    fn test_mixed_candidate_row_balance() {
4550        for (case, l1_rows, l0_rows, expected_len) in [
4551            ("L1 rows dominate", 1_000_000, 10_000, 0),
4552            ("L1 rows meet ratio", 60_000, 10_000, 4),
4553            ("L0 rows are unknown", 1_000_000, 0, 4),
4554        ] {
4555            let files = vec![
4556                new_file_with_level_and_rows(0, 99, 1, 1, 100, l1_rows),
4557                new_file_with_level_and_rows(0, 9, 0, 2, 100, l0_rows),
4558                new_file_with_level_and_rows(20, 29, 0, 3, 100, l0_rows),
4559                new_file_with_level_and_rows(40, 49, 0, 4, 100, l0_rows),
4560            ];
4561
4562            let picked = pick_mixed_count_first(vec![SortedRun::from(files)], None);
4563
4564            assert_eq!(expected_len, picked.len(), "{case}");
4565        }
4566    }
4567
4568    #[test]
4569    fn test_count_first_prefers_smaller_bytes_when_file_counts_match() {
4570        let files = (0..=DEFAULT_MAX_INPUT_FILES)
4571            .map(|idx| {
4572                let start = idx as i64 * 20;
4573                let size = if idx == 0 {
4574                    100
4575                } else if idx == DEFAULT_MAX_INPUT_FILES {
4576                    1
4577                } else {
4578                    10
4579                };
4580                new_file(start, start + 9, idx as u64 + 1, size)
4581            })
4582            .collect::<Vec<_>>();
4583
4584        let picked = pick_count_first(vec![SortedRun::from(files)], None);
4585        let ranges = picked_ranges(&picked);
4586
4587        assert_eq!(DEFAULT_MAX_INPUT_FILES, ranges.len());
4588        assert_eq!(Some(&(20, 29)), ranges.first());
4589        let last_start = DEFAULT_MAX_INPUT_FILES as i64 * 20;
4590        assert_eq!(Some(&(last_start, last_start + 9)), ranges.last());
4591    }
4592
4593    #[test]
4594    fn test_count_first_skips_pure_rewrite_without_progress() {
4595        // Four non-overlapping files whose combined size splits back into at least
4596        // four outputs: compacting them reduces neither the file count nor any
4597        // overlap, so there is nothing worth picking.
4598        let picked = pick_count_first(
4599            vec![SortedRun::from(vec![
4600                new_file(0, 9, 1, 600),
4601                new_file(20, 29, 2, 600),
4602                new_file(40, 49, 3, 600),
4603                new_file(60, 69, 4, 600),
4604            ])],
4605            Some(512),
4606        );
4607
4608        assert!(picked.is_empty());
4609    }
4610
4611    #[test]
4612    fn test_count_first_allows_overlap_resolution_without_file_reduction() {
4613        // Two large overlapping files from different runs: compacting them cannot
4614        // reduce the file count (the output splits back into just as many files),
4615        // but it resolves the overlap and merges two sorted runs into one.
4616        let picked = pick_count_first(
4617            vec![
4618                SortedRun::from(vec![new_file(0, 19, 1, 600)]),
4619                SortedRun::from(vec![new_file(10, 29, 2, 600)]),
4620            ],
4621            Some(512),
4622        );
4623
4624        assert_eq!(vec![(0, 19), (10, 29)], picked_ranges(&picked));
4625    }
4626
4627    #[tokio::test]
4628    async fn test_l1_partial_pk_overlap_does_not_rewrite_unrelated_files() {
4629        // Region 1025's 2026-09-23 R2: A1..A8 are R1's outputs, plus one L1 E.
4630        // Keep the logged, rounded sizes (tenths of MiB) and normalize timestamps
4631        // while preserving the observed order: A3, A7, A6, A1, A4, A5, A2, A8, E.
4632        // The PK ranges are hypothetical: the logs only contain their lengths.
4633        let a_files = [
4634            (4, 5249), // A1
4635            (7, 5218), // A2
4636            (1, 5255), // A3
4637            (5, 5263), // A4
4638            (6, 5131), // A5
4639            (3, 5143), // A6
4640            (2, 5197), // A7
4641            (8, 4716), // A8
4642        ]
4643        .into_iter()
4644        .enumerate()
4645        .map(|(idx, (start, size))| {
4646            let key = b'a' + idx as u8;
4647            new_file_handle_with_size_sequence_and_primary_key_range(
4648                FileId::random(),
4649                start,
4650                10_000,
4651                1,
4652                100,
4653                size * 1024 * 1024 / 10,
4654                pk_range(&[key, b'0'], &[key, b'9']),
4655            )
4656        })
4657        .collect::<Vec<_>>();
4658        let mapper = primary_key_mapper_for_test();
4659        for (idx, file) in a_files.iter().enumerate() {
4660            for other in &a_files[idx + 1..] {
4661                assert!(file.overlap_inclusive(other)); // Their time ranges overlap.
4662                assert!(!files_overlap_inclusive(file, other, &mapper));
4663            }
4664        }
4665
4666        let picker = TwcsPicker {
4667            trigger_file_num: 4,
4668            active_window_l1_merge_trigger: 4,
4669            inactive_window_trigger_file_num: 2,
4670            inactive_window_l1_merge_trigger: 8,
4671            time_window_seconds: Some(60),
4672            max_output_file_size: Some(512 * 1024 * 1024),
4673            append_mode: false,
4674            merge_mode: MergeMode::LastRow,
4675            max_background_tasks: Some(1),
4676            time_range: None,
4677            all_windows_inactive: false,
4678            metrics: Default::default(),
4679        };
4680
4681        for (case, key_range, extra_size, overlapping_a, expected_inputs) in [
4682            (
4683                "A3 and E skip the unrelated A files",
4684                Some((b'c', b'c')),
4685                5155,
4686                &[2][..],
4687                &[2, 8][..],
4688            ),
4689            (
4690                "A8 and E must not pull in A2",
4691                Some((b'h', b'h')),
4692                5155,
4693                &[7][..],
4694                &[7, 8][..],
4695            ),
4696            (
4697                "E overlaps no A: no progress",
4698                Some((b'z', b'z')),
4699                5155,
4700                &[][..],
4701                &[] as &[usize],
4702            ),
4703            (
4704                "A3 and E may split into one extra tail file",
4705                Some((b'c', b'c')),
4706                5255,
4707                &[2][..],
4708                &[2, 8][..],
4709            ),
4710            (
4711                "two A files exceed E's run budget",
4712                Some((b'b', b'c')),
4713                5155,
4714                &[1, 2][..],
4715                &[][..],
4716            ),
4717            (
4718                "sufficient E bytes allow two A files separated in time order",
4719                Some((b'b', b'c')),
4720                6000,
4721                &[1, 2][..],
4722                &[1, 2, 8][..],
4723            ),
4724            (
4725                "unknown PK bounds include the whole dominant run in the budget",
4726                None,
4727                5155,
4728                &[0, 1, 2, 3, 4, 5, 6, 7][..],
4729                &[][..],
4730            ),
4731        ] {
4732            let extra = new_file_handle_with_size_sequence_and_primary_key_range(
4733                FileId::random(),
4734                1_000,
4735                9_000,
4736                1,
4737                100,
4738                extra_size * 1024 * 1024 / 10,
4739                key_range.and_then(|(min, max)| pk_range(&[min, b'0'], &[max, b'9'])),
4740            );
4741            for (idx, file) in a_files.iter().enumerate() {
4742                assert!(file.overlap_inclusive(&extra));
4743                assert_eq!(
4744                    overlapping_a.contains(&idx),
4745                    files_overlap_inclusive(file, &extra, &mapper),
4746                    "{case}: A{}",
4747                    idx + 1,
4748                );
4749            }
4750
4751            let mut files = a_files.clone();
4752            files.push(extra);
4753            for active_window in [Some(0), None] {
4754                // The active window leaves pure overlap resolution to the window
4755                // becoming inactive.
4756                let expected_inputs = if active_window.is_some() {
4757                    &[][..]
4758                } else {
4759                    expected_inputs
4760                };
4761                let expected = expected_inputs
4762                    .iter()
4763                    .map(|&idx| files[idx].file_id())
4764                    .collect::<HashSet<_>>();
4765                let windows = assign_to_windows(files.iter(), 60);
4766                let outputs = picker
4767                    .build_output_with_time_range(
4768                        RegionId::from_u64(0),
4769                        windows,
4770                        active_window,
4771                        Some(60),
4772                    )
4773                    .await
4774                    .unwrap();
4775
4776                assert_eq!(
4777                    usize::from(!expected_inputs.is_empty()),
4778                    outputs.len(),
4779                    "{case}, active window: {active_window:?}"
4780                );
4781                let actual = outputs
4782                    .iter()
4783                    .flat_map(|output| output.inputs.iter().map(FileHandle::file_id))
4784                    .collect::<HashSet<_>>();
4785                assert_eq!(expected, actual, "{case}, active window: {active_window:?}");
4786            }
4787        }
4788    }
4789
4790    #[rstest::rstest]
4791    #[case::active_filtered(Some(0), false, 1000, &[0, 2])]
4792    #[case::inactive_filtered(None, false, 1000, &[0, 2])]
4793    #[case::older_reduction_before_newer_overlap(Some(3), true, 1000, &[0, 2])]
4794    #[case::contiguous_has_more_reduction(Some(0), false, 90, &[0, 1, 2, 3])]
4795    #[case::filtered_has_equal_reduction_with_less_io(Some(0), false, 600, &[0, 2])]
4796    #[tokio::test]
4797    async fn test_l1_file_reduction_considers_filtered_candidates(
4798        #[case] active_window: Option<i64>,
4799        #[case] newer_overlap_window: bool,
4800        #[case] unrelated_size: u64,
4801        #[case] expected_indices: &[usize],
4802    ) {
4803        // Only A/B overlap. With 1000-byte unrelated files between/after them,
4804        // no contiguous interval reduces the file count, but A+B alone does.
4805        let mut files = [
4806            (b'a', 100),
4807            (b'b', unrelated_size),
4808            (b'a', 100),
4809            (b'c', unrelated_size),
4810        ]
4811        .into_iter()
4812        .enumerate()
4813        .map(|(idx, (key, size))| {
4814            new_file_handle_with_size_sequence_and_primary_key_range(
4815                FileId::random(),
4816                idx as i64 * 100,
4817                749,
4818                1,
4819                1,
4820                size,
4821                pk_range(&[key], &[key]),
4822            )
4823        })
4824        .collect::<Vec<_>>();
4825        let expected = expected_indices
4826            .iter()
4827            .map(|&idx| files[idx].file_id())
4828            .collect::<Vec<_>>();
4829        if newer_overlap_window {
4830            // One slot: a filtered file-reducing pick must beat a newer pure
4831            // rewrite, rather than being deferred behind overlap resolution.
4832            files.extend(priority_test_files(1, 1, 512, true));
4833        }
4834        let picker = TwcsPicker {
4835            max_output_file_size: Some(512),
4836            ..priority_test_picker(1)
4837        };
4838        let outputs = picker
4839            .build_output_with_time_range(
4840                RegionId::from_u64(0),
4841                assign_to_windows(files.iter(), 1),
4842                active_window,
4843                Some(1),
4844            )
4845            .await
4846            .unwrap();
4847
4848        assert_eq!(1, outputs.len());
4849        assert_eq!(
4850            expected,
4851            outputs[0]
4852                .inputs
4853                .iter()
4854                .map(FileHandle::file_id)
4855                .collect::<Vec<_>>()
4856        );
4857    }
4858
4859    #[tokio::test]
4860    async fn test_overlap_resolution_limits_dominant_run_rewrites() {
4861        let file_size = 512 * 1024 * 1024;
4862        // Peers are full-size files in one run, so a pure rewrite keeps the file count.
4863        for (case, peer_sizes, max_output_size, should_pick) in [
4864            (
4865                "small peer cannot rewrite any slice of the large run",
4866                vec![file_size],
4867                file_size,
4868                false,
4869            ),
4870            (
4871                "one byte below the run budget",
4872                [vec![file_size; 6], vec![file_size - 1]].concat(),
4873                file_size,
4874                false,
4875            ),
4876            (
4877                "exact run budget boundary",
4878                vec![file_size; 7],
4879                file_size,
4880                true,
4881            ),
4882            ("equal sized runs", vec![file_size; 8], file_size, true),
4883            (
4884                "file reduction keeps its own admission",
4885                vec![file_size],
4886                2 * file_size,
4887                true,
4888            ),
4889        ] {
4890            let mut files = (0..8)
4891                .map(|idx| {
4892                    let key = b'a' + idx as u8;
4893                    new_file_handle_with_size_sequence_and_primary_key_range(
4894                        FileId::random(),
4895                        idx,
4896                        10_000,
4897                        1,
4898                        100,
4899                        file_size,
4900                        pk_range(&[key, b'0'], &[key, b'9']),
4901                    )
4902                })
4903                .collect::<Vec<_>>();
4904            files.extend(peer_sizes.into_iter().enumerate().map(|(idx, size)| {
4905                let start = 1_000 * (idx as i64 + 1);
4906                new_file_handle_with_size_sequence_and_primary_key_range(
4907                    FileId::random(),
4908                    start,
4909                    start + 999,
4910                    1,
4911                    100,
4912                    size,
4913                    pk_range(b"a0", b"h9"),
4914                )
4915            }));
4916            // Only the last case removes files; the active window leaves pure
4917            // overlap resolution to the window becoming inactive.
4918            let reduces_files = max_output_size > file_size;
4919            let picker = TwcsPicker {
4920                trigger_file_num: 4,
4921                active_window_l1_merge_trigger: 4,
4922                inactive_window_trigger_file_num: 2,
4923                inactive_window_l1_merge_trigger: 8,
4924                time_window_seconds: Some(60),
4925                max_output_file_size: Some(max_output_size),
4926                append_mode: false,
4927                merge_mode: MergeMode::LastRow,
4928                max_background_tasks: Some(1),
4929                time_range: None,
4930                all_windows_inactive: false,
4931                metrics: Default::default(),
4932            };
4933
4934            for active_window in [Some(0), None] {
4935                let expected = if should_pick && (reduces_files || active_window.is_none()) {
4936                    files
4937                        .iter()
4938                        .map(FileHandle::file_id)
4939                        .collect::<HashSet<_>>()
4940                } else {
4941                    HashSet::new()
4942                };
4943                let outputs = picker
4944                    .build_output_with_time_range(
4945                        RegionId::from_u64(0),
4946                        assign_to_windows(files.iter(), 60),
4947                        active_window,
4948                        Some(60),
4949                    )
4950                    .await
4951                    .unwrap();
4952                let actual = outputs
4953                    .iter()
4954                    .flat_map(|output| output.inputs.iter().map(FileHandle::file_id))
4955                    .collect::<HashSet<_>>();
4956                assert_eq!(expected, actual, "{case}, active window: {active_window:?}");
4957            }
4958        }
4959    }
4960
4961    #[tokio::test]
4962    async fn test_quiet_or_manual_window_resolves_dominant_run_overlap() {
4963        let file_size = 512 * 1024 * 1024;
4964        let l1_file =
4965            |start, end, sequence, size, range: Option<(bytes::Bytes, bytes::Bytes)>, num_rows| {
4966                let file = new_file_handle_with_size_sequence_and_primary_key_range(
4967                    FileId::random(),
4968                    start,
4969                    end,
4970                    1,
4971                    sequence,
4972                    size,
4973                    range.clone(),
4974                );
4975                FileHandle::new_with_primary_key_range(
4976                    FileMeta {
4977                        num_rows,
4978                        ..file.meta_ref().clone()
4979                    },
4980                    crate::test_util::new_noop_file_purger(),
4981                    range,
4982                )
4983            };
4984
4985        // The window holds 9 rows. It is quiet once the region writes 9 more
4986        // rows after it, and only if its row counts are known. A manual
4987        // compaction does not wait, even for the active window.
4988        for (newer_sequence, num_rows, manual, resolves) in [
4989            (108, 1, false, false),
4990            (109, 1, false, true),
4991            (109, 0, false, false),
4992            (100, 1, true, true),
4993        ] {
4994            // A run of eight key-sliced files and one small file overlapping all
4995            // of them: resolving the overlap rewrites the run for its small peer.
4996            let mut window_files = (0..8)
4997                .map(|idx| {
4998                    let key = b'a' + idx as u8;
4999                    let range = pk_range(&[key, b'0'], &[key, b'9']);
5000                    l1_file(idx, 10_000, 100, file_size, range, num_rows)
5001                })
5002                .collect::<Vec<_>>();
5003            window_files.push(l1_file(
5004                1_000,
5005                1_999,
5006                100,
5007                file_size / 8,
5008                pk_range(b"a0", b"h9"),
5009                num_rows,
5010            ));
5011            let expected = window_files
5012                .iter()
5013                .map(FileHandle::file_id)
5014                .collect::<HashSet<_>>();
5015            let picker = TwcsPicker {
5016                trigger_file_num: 4,
5017                active_window_l1_merge_trigger: 4,
5018                inactive_window_trigger_file_num: 2,
5019                inactive_window_l1_merge_trigger: 16,
5020                time_window_seconds: Some(60),
5021                max_output_file_size: Some(file_size),
5022                append_mode: false,
5023                merge_mode: MergeMode::LastRow,
5024                max_background_tasks: Some(1),
5025                time_range: None,
5026                all_windows_inactive: manual,
5027                metrics: Default::default(),
5028            };
5029            let mut files = window_files;
5030            files.push(l1_file(
5031                120_000,
5032                120_999,
5033                newer_sequence,
5034                file_size,
5035                pk_range(b"a0", b"h9"),
5036                1,
5037            ));
5038            let outputs = picker
5039                .build_output_with_time_range(
5040                    RegionId::from_u64(0),
5041                    assign_to_windows(files.iter(), 60),
5042                    manual.then_some(0),
5043                    Some(60),
5044                )
5045                .await
5046                .unwrap();
5047            let actual = outputs
5048                .iter()
5049                .flat_map(|output| output.inputs.iter().map(FileHandle::file_id))
5050                .collect::<HashSet<_>>();
5051            let case = format!("sequence {newer_sequence}, rows {num_rows}, manual {manual}");
5052            if resolves {
5053                assert_eq!(expected, actual, "{case}");
5054            } else {
5055                assert!(actual.is_empty(), "{case}: {actual:?}");
5056            }
5057        }
5058    }
5059
5060    #[test]
5061    fn test_count_first_prefers_guaranteed_reduction_over_pure_rewrite() {
5062        // A window mixing large and small files: the large triple on its own is a
5063        // pure rewrite, and every interval containing large files rewrites more
5064        // bytes for the same predicted reduction, so the small triple wins.
5065        let picked = pick_count_first(
5066            vec![SortedRun::from(vec![
5067                new_file(0, 9, 1, 600),
5068                new_file(10, 19, 2, 600),
5069                new_file(20, 29, 3, 600),
5070                new_file(30, 39, 4, 10),
5071                new_file(40, 49, 5, 10),
5072                new_file(50, 59, 6, 10),
5073            ])],
5074            Some(512),
5075        );
5076
5077        assert_eq!(vec![(30, 39), (40, 49), (50, 59)], picked_ranges(&picked));
5078    }
5079
5080    #[test]
5081    fn test_count_first_prefers_earlier_time_on_exact_tie() {
5082        let files = (0..=DEFAULT_MAX_INPUT_FILES)
5083            .map(|idx| {
5084                let start = idx as i64 * 20;
5085                new_file(start, start + 9, idx as u64 + 1, 10)
5086            })
5087            .collect::<Vec<_>>();
5088
5089        let picked = pick_count_first(vec![SortedRun::from(files)], None);
5090        let ranges = picked_ranges(&picked);
5091
5092        assert_eq!(DEFAULT_MAX_INPUT_FILES, ranges.len());
5093        assert_eq!(Some(&(0, 9)), ranges.first());
5094        let last_start = (DEFAULT_MAX_INPUT_FILES as i64 - 1) * 20;
5095        assert_eq!(Some(&(last_start, last_start + 9)), ranges.last());
5096    }
5097
5098    #[test]
5099    fn test_count_first_keeps_each_interleaved_run_contiguous() {
5100        let picked = pick_count_first(
5101            vec![
5102                SortedRun::from(vec![
5103                    new_file(0, 9, 1, 1),
5104                    new_file(20, 29, 2, 1),
5105                    new_file(40, 49, 3, 1),
5106                ]),
5107                SortedRun::from(vec![new_file(10, 19, 4, 1), new_file(30, 39, 5, 1)]),
5108            ],
5109            None,
5110        );
5111
5112        assert_eq!(
5113            vec![(0, 9), (10, 19), (20, 29), (30, 39), (40, 49)],
5114            picked_ranges(&picked)
5115        );
5116    }
5117
5118    // TODO(hl): TTL tester that checks if get_expired_ssts function works as expected.
5119
5120    // Reproduces the leftover-small-files deadlock observed in the compaction bench:
5121    // an "EngineFull" flush emits several SSTs sharing one sequence. They must be ordinary
5122    // candidates so a contiguous candidate can span them instead of treating them as an
5123    // indivisible block that fragments the timeline.
5124    #[test]
5125    fn test_count_first_candidate_spans_same_sequence_files() {
5126        let picked = pick_count_first(
5127            vec![SortedRun::from(vec![
5128                new_file(0, 9, 1, 10),
5129                // One EngineFull flush output: three SSTs with the same sequence.
5130                new_file(10, 19, 2, 10),
5131                new_file(10, 19, 2, 10),
5132                new_file(10, 19, 2, 10),
5133                new_file(20, 29, 3, 10),
5134            ])],
5135            None,
5136        );
5137
5138        assert_eq!(
5139            vec![(0, 9), (10, 19), (10, 19), (10, 19), (20, 29)],
5140            picked_ranges(&picked)
5141        );
5142    }
5143
5144    // End-to-end repro of the compaction-bench leftover files: a window where
5145    // EngineFull flush groups (multiple SSTs sharing a sequence) sit between
5146    // singleton flushes. The picker must be able to merge the whole contiguous
5147    // range; otherwise these files can never be compacted once the active window
5148    // moves on.
5149    #[tokio::test]
5150    async fn test_count_first_merges_window_with_interleaved_flush_groups() {
5151        let files = [
5152            // Singleton flush.
5153            new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 10),
5154            // EngineFull flush: three SSTs sharing sequence 2.
5155            new_file_handle_with_size_and_sequence(FileId::random(), 10, 19, 0, 2, 10),
5156            new_file_handle_with_size_and_sequence(FileId::random(), 10, 19, 0, 2, 10),
5157            new_file_handle_with_size_and_sequence(FileId::random(), 10, 19, 0, 2, 10),
5158            // Singleton flush.
5159            new_file_handle_with_size_and_sequence(FileId::random(), 20, 29, 0, 3, 10),
5160        ];
5161        let windows = assign_to_windows(files.iter(), 100);
5162        let picker = TwcsPicker {
5163            trigger_file_num: 3,
5164            active_window_l1_merge_trigger: 8,
5165            inactive_window_trigger_file_num: 3,
5166            inactive_window_l1_merge_trigger: 8,
5167            time_window_seconds: Some(100),
5168            max_output_file_size: None,
5169            append_mode: false,
5170            merge_mode: MergeMode::LastRow,
5171            max_background_tasks: None,
5172            time_range: None,
5173            all_windows_inactive: false,
5174            metrics: Default::default(),
5175        };
5176
5177        let output = picker
5178            .build_output_with_time_range(RegionId::from_u64(1), windows, Some(0), None)
5179            .await
5180            .unwrap();
5181
5182        assert_eq!(1, output.len());
5183        // All five SSTs of the window are merged in one compaction.
5184        assert_eq!(5, output[0].inputs.len());
5185    }
5186}