Skip to main content

risingwave_storage/hummock/compactor/
shared_buffer_compact.rs

1// Copyright 2022 RisingWave Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
16use std::ops::Bound;
17use std::sync::atomic::AtomicUsize;
18use std::sync::atomic::Ordering::Relaxed;
19use std::sync::{Arc, LazyLock};
20
21use await_tree::InstrumentAwait;
22use bytes::Bytes;
23use foyer::Hint;
24use futures::future::try_join;
25use futures::{FutureExt, StreamExt, stream};
26use itertools::Itertools;
27use risingwave_common::catalog::TableId;
28use risingwave_hummock_sdk::key::{EPOCH_LEN, FullKey};
29use risingwave_hummock_sdk::key_range::KeyRange;
30use risingwave_hummock_sdk::{EpochWithGap, KeyComparator, LocalSstableInfo};
31use risingwave_pb::hummock::{PbSstableFilterLayout, PbSstableFilterType};
32use thiserror_ext::AsReport;
33use tracing::error;
34
35use crate::compaction_catalog_manager::{CompactionCatalogAgentRef, CompactionCatalogManagerRef};
36use crate::hummock::compactor::compaction_filter::DummyCompactionFilter;
37use crate::hummock::compactor::compaction_utils::{
38    blocked_xor_filter_key_count_threshold, estimate_output_key_count_by_size,
39};
40use crate::hummock::compactor::context::{CompactorContext, await_tree_key};
41use crate::hummock::compactor::{CompactOutput, Compactor, check_flush_result};
42use crate::hummock::event_handler::uploader::UploadTaskOutput;
43use crate::hummock::iterator::{Forward, HummockIterator, MergeIterator, UserIterator};
44use crate::hummock::{
45    CachePolicy, GetObjectId, HummockError, HummockResult, ObjectIdManagerRef,
46    SstableBuilderOptions,
47};
48use crate::mem_table::ImmutableMemtable;
49use crate::opts::StorageOpts;
50
51const GC_DELETE_KEYS_FOR_FLUSH: bool = false;
52
53/// Flush shared buffer to level0. Resulted SSTs are grouped by compaction group.
54pub async fn compact(
55    context: CompactorContext,
56    object_id_manager: ObjectIdManagerRef,
57    payload: Vec<ImmutableMemtable>,
58    compaction_catalog_manager_ref: CompactionCatalogManagerRef,
59) -> HummockResult<UploadTaskOutput> {
60    let table_ids_with_old_value: HashSet<TableId> = payload
61        .iter()
62        .filter(|imm| imm.has_old_value())
63        .map(|imm| imm.table_id)
64        .collect();
65    let mut non_log_store_new_value_payload = Vec::with_capacity(payload.len());
66    let mut log_store_new_value_payload = Vec::with_capacity(payload.len());
67    let mut old_value_payload = Vec::with_capacity(payload.len());
68    for imm in payload {
69        if table_ids_with_old_value.contains(&imm.table_id) {
70            if imm.has_old_value() {
71                old_value_payload.push(imm.clone());
72            }
73            log_store_new_value_payload.push(imm);
74        } else {
75            assert!(!imm.has_old_value());
76            non_log_store_new_value_payload.push(imm);
77        }
78    }
79    let non_log_store_new_value_future = async {
80        if non_log_store_new_value_payload.is_empty() {
81            Ok(vec![])
82        } else {
83            compact_shared_buffer::<true>(
84                context.clone(),
85                object_id_manager.clone(),
86                compaction_catalog_manager_ref.clone(),
87                non_log_store_new_value_payload,
88            )
89            .instrument_await("shared_buffer_compact_non_log_store_new_value")
90            .await
91        }
92    };
93
94    let log_store_new_value_future = async {
95        if log_store_new_value_payload.is_empty() {
96            Ok(vec![])
97        } else {
98            compact_shared_buffer::<true>(
99                context.clone(),
100                object_id_manager.clone(),
101                compaction_catalog_manager_ref.clone(),
102                log_store_new_value_payload,
103            )
104            .instrument_await("shared_buffer_compact_log_store_new_value")
105            .await
106        }
107    };
108
109    let old_value_future = async {
110        if old_value_payload.is_empty() {
111            Ok(vec![])
112        } else {
113            compact_shared_buffer::<false>(
114                context.clone(),
115                object_id_manager.clone(),
116                compaction_catalog_manager_ref.clone(),
117                old_value_payload,
118            )
119            .instrument_await("shared_buffer_compact_log_store_old_value")
120            .await
121        }
122    };
123
124    // Note that the output is reordered compared with input `payload`.
125    let ((non_log_store_new_value_ssts, log_store_new_value_ssts), old_value_ssts) = try_join(
126        try_join(non_log_store_new_value_future, log_store_new_value_future),
127        old_value_future,
128    )
129    .await?;
130
131    let mut new_value_ssts = non_log_store_new_value_ssts;
132    new_value_ssts.extend(log_store_new_value_ssts);
133
134    Ok(UploadTaskOutput {
135        new_value_ssts,
136        old_value_ssts,
137        wait_poll_timer: None,
138    })
139}
140
141/// For compaction from shared buffer to level 0, this is the only function gets called.
142///
143/// The `IS_NEW_VALUE` flag means for the given payload, we are doing compaction using its new value or old value.
144/// When `IS_NEW_VALUE` is false, we are compacting with old value, and the payload imms should have `old_values` not `None`
145async fn compact_shared_buffer<const IS_NEW_VALUE: bool>(
146    context: CompactorContext,
147    object_id_manager: ObjectIdManagerRef,
148    compaction_catalog_manager_ref: CompactionCatalogManagerRef,
149    mut payload: Vec<ImmutableMemtable>,
150) -> HummockResult<Vec<LocalSstableInfo>> {
151    if !IS_NEW_VALUE {
152        assert!(payload.iter().all(|imm| imm.has_old_value()));
153    }
154    // Local memory compaction looks at all key ranges.
155    let existing_table_ids: HashSet<TableId> =
156        payload.iter().map(|imm| imm.table_id).dedup().collect();
157    assert!(!existing_table_ids.is_empty());
158
159    let compaction_catalog_agent_ref = compaction_catalog_manager_ref
160        .acquire(existing_table_ids.iter().copied().collect())
161        .await?;
162    let existing_table_ids = compaction_catalog_agent_ref
163        .table_ids()
164        .collect::<HashSet<_>>();
165    payload.retain(|imm| {
166        let ret = existing_table_ids.contains(&imm.table_id);
167        if !ret {
168            error!(
169                "cannot find table {:?}; it may have been removed by the meta service",
170                imm.table_id
171            );
172        }
173        ret
174    });
175
176    let total_key_count = payload.iter().map(|imm| imm.key_count()).sum::<usize>();
177    let (splits, sub_compaction_sstable_size, table_vnode_partition, compact_data_size) =
178        generate_splits(&payload, &existing_table_ids, context.storage_opts.as_ref());
179    let parallelism = splits.len();
180    let mut compact_success = true;
181    let mut output_ssts = Vec::with_capacity(parallelism);
182    let mut compaction_futures = vec![];
183    // Shared buffer compaction always goes to L0. Use a blocked filter when kv_count is large.
184    // Use None to apply the default threshold since shared buffer flush doesn't have a CompactTask.
185    let estimated_output_key_count = estimate_output_key_count_by_size(
186        total_key_count as u64,
187        compact_data_size,
188        sub_compaction_sstable_size as usize,
189    );
190    let sstable_filter_layout =
191        if risingwave_hummock_sdk::filter_utils::should_use_blocked_xor_filter_by_kv_count(
192            estimated_output_key_count as u64,
193            None,
194        ) {
195            PbSstableFilterLayout::Blocked
196        } else {
197            PbSstableFilterLayout::Plain
198        };
199    let sstable_filter_type = if IS_NEW_VALUE {
200        // L0 flush writes overlapping SSTs, so keep a conservative filter type here.
201        PbSstableFilterType::SstableFilterXor16
202    } else {
203        // Changelog readers scan old-value SSTs without probing the filter.
204        PbSstableFilterType::SstableFilterNone
205    };
206
207    for (split_index, key_range) in splits.into_iter().enumerate() {
208        let compactor = SharedBufferCompactRunner::new(
209            split_index,
210            key_range,
211            context.clone(),
212            sub_compaction_sstable_size as usize,
213            estimated_output_key_count,
214            table_vnode_partition.clone(),
215            sstable_filter_layout,
216            sstable_filter_type,
217            object_id_manager.clone(),
218        );
219        let mut forward_iters = Vec::with_capacity(payload.len());
220        for imm in &payload {
221            forward_iters.push(imm.clone().into_directed_iter::<Forward, IS_NEW_VALUE>());
222        }
223        let compaction_executor = context.compaction_executor.clone();
224        let compaction_catalog_agent_ref = compaction_catalog_agent_ref.clone();
225        let handle = compaction_executor.spawn({
226            static NEXT_SHARED_BUFFER_COMPACT_ID: LazyLock<AtomicUsize> =
227                LazyLock::new(|| AtomicUsize::new(0));
228            let tree_root = context.await_tree_reg.as_ref().map(|reg| {
229                let id = NEXT_SHARED_BUFFER_COMPACT_ID.fetch_add(1, Relaxed);
230                reg.register(
231                    await_tree_key::CompactSharedBuffer { id },
232                    format!(
233                        "Compact Shared Buffer: {:?}",
234                        payload
235                            .iter()
236                            .map(|imm| imm.epoch())
237                            .collect::<BTreeSet<_>>()
238                    ),
239                )
240            });
241            let future = compactor.run(
242                MergeIterator::new(forward_iters),
243                compaction_catalog_agent_ref,
244            );
245            if let Some(root) = tree_root {
246                root.instrument(future).left_future()
247            } else {
248                future.right_future()
249            }
250        });
251        compaction_futures.push(handle);
252    }
253
254    let mut buffered = stream::iter(compaction_futures).buffer_unordered(parallelism);
255    let mut err = None;
256    while let Some(future_result) = buffered.next().await {
257        match future_result {
258            Ok(Ok((split_index, ssts, table_stats_map))) => {
259                output_ssts.push((split_index, ssts, table_stats_map));
260            }
261            Ok(Err(e)) => {
262                compact_success = false;
263                tracing::warn!(error = %e.as_report(), "Shared Buffer Compaction failed with error");
264                err = Some(e);
265            }
266            Err(e) => {
267                compact_success = false;
268                tracing::warn!(
269                    error = %e.as_report(),
270                    "Shared Buffer Compaction failed with future error",
271                );
272                err = Some(HummockError::compaction_executor(
273                    "failed while execute in tokio",
274                ));
275            }
276        }
277    }
278
279    // Sort by split/key range index.
280    output_ssts.sort_by_key(|(split_index, ..)| *split_index);
281
282    if compact_success {
283        let mut level0 = Vec::with_capacity(parallelism);
284        let mut sst_infos = vec![];
285        for (_, ssts, _) in output_ssts {
286            for sst_info in &ssts {
287                context
288                    .compactor_metrics
289                    .write_build_l0_bytes
290                    .inc_by(sst_info.file_size());
291
292                sst_infos.push(sst_info.sst_info.clone());
293            }
294            level0.extend(ssts);
295        }
296        if context.storage_opts.check_compaction_result {
297            let compaction_executor = context.compaction_executor.clone();
298            let mut forward_iters = Vec::with_capacity(payload.len());
299            for imm in &payload {
300                if !existing_table_ids.contains(&imm.table_id) {
301                    continue;
302                }
303                forward_iters.push(imm.clone().into_forward_iter());
304            }
305            let iter = MergeIterator::new(forward_iters);
306            let left_iter = UserIterator::new(
307                iter,
308                (Bound::Unbounded, Bound::Unbounded),
309                u64::MAX,
310                0,
311                None,
312            );
313            compaction_executor.spawn(async move {
314                match check_flush_result(left_iter, sst_infos, context).await {
315                    Err(e) => {
316                        tracing::warn!(
317                            error = %e.as_report(),
318                            "failed to check the memtable flush result",
319                        );
320                    }
321                    Ok(true) => (),
322                    Ok(false) => {
323                        panic!(
324                            "failed to check flush result consistency of state-table {:?}",
325                            existing_table_ids
326                        );
327                    }
328                }
329            });
330        }
331        Ok(level0)
332    } else {
333        Err(err.unwrap())
334    }
335}
336
337///  Based on the incoming payload and opts, calculate the sharding method and sstable size of shared buffer compaction.
338fn generate_splits(
339    payload: &Vec<ImmutableMemtable>,
340    existing_table_ids: &HashSet<TableId>,
341    storage_opts: &StorageOpts,
342) -> (Vec<KeyRange>, u64, BTreeMap<TableId, u32>, u64) {
343    let mut size_and_start_user_keys = vec![];
344    let mut compact_data_size = 0;
345    let mut table_size_infos: HashMap<TableId, u64> = HashMap::default();
346    let mut table_vnode_partition = BTreeMap::default();
347    for imm in payload {
348        let data_size = {
349            // calculate encoded bytes of key var length
350            (imm.value_count() * EPOCH_LEN + imm.size()) as u64
351        };
352        compact_data_size += data_size;
353        size_and_start_user_keys.push((
354            data_size,
355            FullKey {
356                user_key: imm.start_user_key(),
357                epoch_with_gap: EpochWithGap::new_max_epoch(),
358            }
359            .encode(),
360        ));
361        let v = table_size_infos.entry(imm.table_id).or_insert(0);
362        *v += data_size;
363    }
364
365    size_and_start_user_keys
366        .sort_by(|a, b| KeyComparator::compare_encoded_full_key(a.1.as_ref(), b.1.as_ref()));
367    let mut splits = Vec::with_capacity(size_and_start_user_keys.len());
368    splits.push(KeyRange::new(Bytes::new(), Bytes::new()));
369    let sstable_size = (storage_opts.sstable_size_mb as u64) << 20;
370    let min_sstable_size = (storage_opts.min_sstable_size_mb as u64) << 20;
371    let parallel_compact_size = (storage_opts.parallel_compact_size_mb as u64) << 20;
372    let parallelism = std::cmp::min(
373        storage_opts.share_buffers_sync_parallelism as u64,
374        size_and_start_user_keys.len() as u64,
375    );
376    let sub_compaction_data_size = if compact_data_size > parallel_compact_size && parallelism > 1 {
377        compact_data_size / parallelism
378    } else {
379        compact_data_size
380    };
381
382    if parallelism > 1 && compact_data_size > sstable_size {
383        let mut last_buffer_size = 0;
384        let mut last_key: Vec<u8> = vec![];
385        for (data_size, key) in size_and_start_user_keys {
386            if last_buffer_size >= sub_compaction_data_size && !last_key.eq(&key) {
387                splits.last_mut().unwrap().right = Bytes::from(key.clone());
388                splits.push(KeyRange::new(Bytes::from(key.clone()), Bytes::default()));
389                last_buffer_size = data_size;
390            } else {
391                last_buffer_size += data_size;
392            }
393
394            last_key = key;
395        }
396    }
397
398    if compact_data_size > sstable_size {
399        // Meta node will calculate size of each state-table in one task in `risingwave_meta::hummock::manager::compaction::calculate_vnode_partition`.
400        // To make the calculate result more accurately we shall split the large state-table from other small ones.
401        for table_id in existing_table_ids {
402            if let Some(table_size) = table_size_infos.get(table_id)
403                && *table_size > min_sstable_size
404            {
405                table_vnode_partition.insert(*table_id, 1);
406            }
407        }
408    }
409
410    // mul 1.2 for other extra memory usage.
411    // Ensure that the size of each sstable is still less than `sstable_size` after optimization to avoid generating a huge size sstable which will affect the object store
412    let sub_compaction_sstable_size = std::cmp::min(sstable_size, sub_compaction_data_size * 6 / 5);
413    (
414        splits,
415        sub_compaction_sstable_size,
416        table_vnode_partition,
417        compact_data_size,
418    )
419}
420
421pub struct SharedBufferCompactRunner {
422    compactor: Compactor,
423    split_index: usize,
424}
425
426impl SharedBufferCompactRunner {
427    pub fn new(
428        split_index: usize,
429        key_range: KeyRange,
430        context: CompactorContext,
431        sub_compaction_sstable_size: usize,
432        estimated_output_key_count: usize,
433        table_vnode_partition: BTreeMap<TableId, u32>,
434        sstable_filter_layout: PbSstableFilterLayout,
435        sstable_filter_type: PbSstableFilterType,
436        object_id_getter: Arc<dyn GetObjectId>,
437    ) -> Self {
438        let mut options: SstableBuilderOptions = context.storage_opts.as_ref().into();
439        options.capacity = sub_compaction_sstable_size;
440        options.estimated_output_key_count = Some(estimated_output_key_count);
441        options.filter_hash_prealloc_key_count_cap = blocked_xor_filter_key_count_threshold(None);
442        let compactor = Compactor::new(
443            context,
444            options,
445            super::TaskConfig {
446                key_range,
447                cache_policy: CachePolicy::Fill(Hint::Normal),
448                gc_delete_keys: GC_DELETE_KEYS_FOR_FLUSH,
449                retain_multiple_version: true,
450                table_vnode_partition,
451                sstable_filter_layout,
452                sstable_filter_type,
453                table_schemas: Default::default(),
454                disable_drop_column_optimization: false,
455            },
456            object_id_getter,
457        );
458        Self {
459            compactor,
460            split_index,
461        }
462    }
463
464    pub async fn run(
465        self,
466        iter: impl HummockIterator<Direction = Forward>,
467        compaction_catalog_agent_ref: CompactionCatalogAgentRef,
468    ) -> HummockResult<CompactOutput> {
469        let dummy_compaction_filter = DummyCompactionFilter {};
470        let (ssts, table_stats_map) = self
471            .compactor
472            .compact_key_range(
473                iter,
474                dummy_compaction_filter,
475                compaction_catalog_agent_ref,
476                None,
477                None,
478                None,
479            )
480            .await?;
481        Ok((self.split_index, ssts, table_stats_map))
482    }
483}
484
485#[cfg(test)]
486mod tests {
487    use std::collections::HashSet;
488
489    use bytes::Bytes;
490    use risingwave_common::catalog::TableId;
491    use risingwave_common::hash::VirtualNode;
492    use risingwave_common::util::epoch::test_epoch;
493    use risingwave_hummock_sdk::key::{TableKey, prefix_slice_with_vnode};
494
495    use crate::hummock::compactor::shared_buffer_compact::generate_splits;
496    use crate::hummock::shared_buffer::shared_buffer_batch::SharedBufferValue;
497    use crate::mem_table::ImmutableMemtable;
498    use crate::opts::StorageOpts;
499
500    fn generate_key(key: &str) -> TableKey<Bytes> {
501        TableKey(prefix_slice_with_vnode(
502            VirtualNode::from_index(1),
503            key.as_bytes(),
504        ))
505    }
506
507    #[tokio::test]
508    async fn test_generate_splits_in_order() {
509        let imm1 = ImmutableMemtable::build_shared_buffer_batch_for_test(
510            test_epoch(3),
511            0,
512            vec![(
513                generate_key("dddd"),
514                SharedBufferValue::Insert(Bytes::from_static(b"v3")),
515            )],
516            1024 * 1024,
517            TableId::new(1),
518        );
519        let imm2 = ImmutableMemtable::build_shared_buffer_batch_for_test(
520            test_epoch(3),
521            0,
522            vec![(
523                generate_key("abb"),
524                SharedBufferValue::Insert(Bytes::from_static(b"v3")),
525            )],
526            (1024 + 256) * 1024,
527            TableId::new(1),
528        );
529
530        let imm3 = ImmutableMemtable::build_shared_buffer_batch_for_test(
531            test_epoch(2),
532            0,
533            vec![(
534                generate_key("abc"),
535                SharedBufferValue::Insert(Bytes::from_static(b"v2")),
536            )],
537            (1024 + 512) * 1024,
538            TableId::new(1),
539        );
540        let imm4 = ImmutableMemtable::build_shared_buffer_batch_for_test(
541            test_epoch(3),
542            0,
543            vec![(
544                generate_key("aaa"),
545                SharedBufferValue::Insert(Bytes::from_static(b"v3")),
546            )],
547            (1024 + 512) * 1024,
548            TableId::new(1),
549        );
550
551        let imm5 = ImmutableMemtable::build_shared_buffer_batch_for_test(
552            test_epoch(3),
553            0,
554            vec![(
555                generate_key("aaa"),
556                SharedBufferValue::Insert(Bytes::from_static(b"v3")),
557            )],
558            (1024 + 256) * 1024,
559            TableId::new(2),
560        );
561
562        let storage_opts = StorageOpts {
563            share_buffers_sync_parallelism: 3,
564            parallel_compact_size_mb: 1,
565            sstable_size_mb: 1,
566            ..Default::default()
567        };
568        let payload = vec![imm1, imm2, imm3, imm4, imm5];
569        let (splits, _sstable_capacity, vnodes, _) = generate_splits(
570            &payload,
571            &HashSet::from_iter([1.into(), 2.into()]),
572            &storage_opts,
573        );
574        assert_eq!(
575            splits.len(),
576            storage_opts.share_buffers_sync_parallelism as usize
577        );
578        assert!(vnodes.is_empty());
579
580        // Basic validation: splits should be continuous and monotonic
581        for i in 1..splits.len() {
582            assert_eq!(splits[i].left, splits[i - 1].right);
583            assert!(splits[i].left > splits[i - 1].left);
584            assert!(splits[i].right.is_empty() || splits[i].left < splits[i].right);
585        }
586    }
587
588    #[tokio::test]
589    async fn test_generate_splits_no_duplicate_keys() {
590        // Create test data with specific ordering to detect sorting issues
591        // Make data sizes large enough to trigger splitting
592        let imm1 = ImmutableMemtable::build_shared_buffer_batch_for_test(
593            test_epoch(1),
594            0,
595            vec![(
596                generate_key("zzz"), // This should be last after sorting
597                SharedBufferValue::Insert(Bytes::from_static(b"v1")),
598            )],
599            2 * 1024 * 1024, // 2MB to ensure compact_data_size > sstable_size
600            TableId::new(1),
601        );
602
603        let imm2 = ImmutableMemtable::build_shared_buffer_batch_for_test(
604            test_epoch(1),
605            0,
606            vec![(
607                generate_key("aaa"), // This should be first after sorting
608                SharedBufferValue::Insert(Bytes::from_static(b"v1")),
609            )],
610            2 * 1024 * 1024, // 2MB
611            TableId::new(1),
612        );
613
614        let imm3 = ImmutableMemtable::build_shared_buffer_batch_for_test(
615            test_epoch(1),
616            0,
617            vec![(
618                generate_key("mmm"), // This should be middle after sorting
619                SharedBufferValue::Insert(Bytes::from_static(b"v1")),
620            )],
621            2 * 1024 * 1024, // 2MB
622            TableId::new(1),
623        );
624
625        let storage_opts = StorageOpts {
626            share_buffers_sync_parallelism: 3, // Enable parallelism
627            parallel_compact_size_mb: 2,       // Small threshold to trigger splitting
628            sstable_size_mb: 1,                // Small SSTable size to trigger condition
629            ..Default::default()
630        };
631
632        // Test with payload in wrong order (zzz, aaa, mmm) instead of sorted order (aaa, mmm, zzz)
633        let payload = vec![imm1, imm2, imm3];
634        let (splits, _sstable_capacity, _vnodes, _) =
635            generate_splits(&payload, &HashSet::from_iter([1.into()]), &storage_opts);
636
637        // Should have multiple splits due to large data size
638        assert!(
639            splits.len() > 1,
640            "Expected multiple splits, got {}",
641            splits.len()
642        );
643
644        // Verify no key range overlaps between splits
645        for i in 0..splits.len() {
646            for j in (i + 1)..splits.len() {
647                let split_i = &splits[i];
648                let split_j = &splits[j];
649
650                // Check that splits don't overlap
651                if !split_i.right.is_empty() && !split_j.left.is_empty() {
652                    assert!(
653                        split_i.right <= split_j.left || split_j.right <= split_i.left,
654                        "Split {} and {} overlap: [{:?}, {:?}) vs [{:?}, {:?})",
655                        i,
656                        j,
657                        split_i.left,
658                        split_i.right,
659                        split_j.left,
660                        split_j.right
661                    );
662                }
663            }
664        }
665
666        // Additional verification: ensure splits are sorted
667        for i in 1..splits.len() {
668            if !splits[i - 1].right.is_empty() && !splits[i].left.is_empty() {
669                assert!(
670                    splits[i - 1].right <= splits[i].left,
671                    "Splits are not in sorted order at index {}: {:?} > {:?}",
672                    i,
673                    splits[i - 1].right,
674                    splits[i].left
675                );
676            }
677        }
678    }
679}