1mod 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#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
53pub(crate) enum PickClass {
54 L0Merge,
56 FileReduction,
58 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#[derive(Debug)]
74pub(crate) struct WindowPick {
75 pub(crate) class: PickClass,
76 branch: &'static str,
78 pub(crate) inputs: Vec<FileHandle>,
79 found_runs: usize,
81}
82
83#[derive(Debug)]
85pub(crate) struct WindowCandidate {
86 pub(crate) window: i64,
87 pub(crate) pick: WindowPick,
88}
89
90pub(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 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 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
158struct 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
177const MAX_L1_L0_ROW_RATIO: usize = 2;
179
180const DEFAULT_MAX_INPUT_FILES: usize = 16;
182
183const MAX_INPUT_FILES_ENV: &str = "GREPTIME_TWCS_MAX_INPUT_FILES";
184
185static 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
192const 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#[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#[derive(Clone, Debug)]
223pub struct TwcsPicker {
224 pub(crate) metrics: TwcsPickMetrics,
226 pub trigger_file_num: usize,
228 pub active_window_l1_merge_trigger: usize,
230 pub inactive_window_trigger_file_num: usize,
232 pub inactive_window_l1_merge_trigger: usize,
234 pub time_window_seconds: Option<i64>,
236 pub max_output_file_size: Option<u64>,
239 pub append_mode: bool,
241 pub(crate) merge_mode: MergeMode,
244 pub max_background_tasks: Option<usize>,
246 pub(crate) time_range: Option<TimestampRange>,
248 pub(crate) all_windows_inactive: bool,
252}
253
254impl TwcsPicker {
255 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 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 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 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 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 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 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 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 && 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 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 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 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 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
625fn 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: Option<(bytes::Bytes, bytes::Bytes)>,
700}
701
702impl OrderedFile<'_> {
703 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#[derive(Debug, Default)]
715struct Candidate {
716 num_files: usize,
718 total_size: usize,
720 largest_file_size: usize,
722 overlap_participants: usize,
725 l0_rows: usize,
727 l1_rows: usize,
729 has_l0: bool,
730 has_l1: bool,
731 has_unknown_rows: bool,
733}
734
735impl Candidate {
736 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 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 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 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 fn is_balanced(&self) -> bool {
806 self.largest_file_size <= self.total_size - self.largest_file_size
807 }
808
809 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 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 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#[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
870fn 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
909fn 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
921fn 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
974fn 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 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 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 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 time_window: i64,
1206 primary_key_range: Option<(bytes::Bytes, bytes::Bytes)>,
1207}
1208
1209impl Window {
1210 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 fn range(&self) -> (Timestamp, Timestamp) {
1225 (self.start, self.end)
1226 }
1227
1228 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
1245fn 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 active
1257 .checked_sub(window)
1258 .is_some_and(|distance| (1..=size).contains(&distance))
1259 })
1260}
1261
1262fn 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
1283fn 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 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
1312fn time_window_start(timestamp: Timestamp, time_window_size: i64) -> i64 {
1315 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 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
1363fn 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
1383fn 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); 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 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 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 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 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 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 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 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 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 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 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 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), (1000, 1999), (2000, 2999), (3000, 3999), (2999, 3999), ],
2249 2,
2250 &[
2251 (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), (1000, 1999), (2000, 2999), (3000, 3999), (0, 2000), ],
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 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), new_file_handle_with_sequence(file_ids[3], 50, 2998, 0, 4), ]
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 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 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 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 let original_count = files_to_merge.len();
2542
2543 files_to_merge.retain(|file| file.size() <= max_output_file_size);
2545
2546 assert_eq!(files_to_merge.len(), 2);
2548 assert_eq!(original_count, 4);
2549
2550 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 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 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 let picker = TwcsPicker {
2581 trigger_file_num: 4, 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); let large_file_2 = new_file_handle_with_size_and_sequence(file_ids[1], 0, 999, 0, 2, 2500); 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 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 let files = [
2699 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 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 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 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 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 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; 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 assert!(
2819 output.len() <= max_background_tasks,
2820 "Output should be within limit"
2821 );
2822 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 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 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 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 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 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 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 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 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 let first = pick_automatic_for_test(®ion, &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 let second = pick_automatic_for_test(®ion, &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 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 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 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 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 .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 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 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 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 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 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 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 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 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 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 let a_files = [
4634 (4, 5249), (7, 5218), (1, 5255), (5, 5263), (6, 5131), (3, 5143), (2, 5197), (8, 4716), ]
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)); 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 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 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 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 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 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 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 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 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 #[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 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 #[tokio::test]
5150 async fn test_count_first_merges_window_with_interleaved_flush_groups() {
5151 let files = [
5152 new_file_handle_with_size_and_sequence(FileId::random(), 0, 9, 0, 1, 10),
5154 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 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 assert_eq!(5, output[0].inputs.len());
5185 }
5186}