index/inverted_index/create/
sort.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15pub mod external_sort;
16mod intermediate_rw;
17mod merge_stream;
18
19use async_trait::async_trait;
20use futures::Stream;
21
22use crate::bitmap::Bitmap;
23use crate::inverted_index::error::Result;
24use crate::inverted_index::format::writer::ValueStream;
25use crate::{Bytes, BytesRef};
26
27/// A stream of sorted values along with their associated bitmap
28pub type SortedStream = Box<dyn Stream<Item = Result<(Bytes, Bitmap)>> + Send + Unpin>;
29
30/// Output of a sorting operation, encapsulating a bitmap for null values and a stream of sorted items
31pub struct SortOutput {
32    /// Bitmap indicating which segments have null values
33    pub segment_null_bitmap: Bitmap,
34
35    /// Stream of sorted items
36    pub sorted_stream: ValueStream,
37
38    /// Total number of rows in the sorted data
39    pub total_row_count: usize,
40}
41
42/// Handles data sorting, supporting incremental input and retrieval of sorted output
43#[async_trait]
44pub trait Sorter: Send {
45    /// Buffers `n` identical non-null or null values in memory.
46    ///
47    /// Returns true when the buffer should be spilled with [`Sorter::spill`] before more
48    /// values are pushed. Kept synchronous so the per-row path does not allocate a future.
49    #[must_use = "a true result requires calling `spill` before pushing more"]
50    fn push_n(&mut self, value: Option<BytesRef<'_>>, n: usize) -> bool;
51
52    /// Moves the in-memory buffer to external storage.
53    async fn spill(&mut self) -> Result<()>;
54
55    /// Completes the sorting process and returns the sorted data
56    async fn output(&mut self) -> Result<SortOutput>;
57}
index/inverted_index/create/sort.rs

index/inverted_index/create/
sort.rs
