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 /// Inputs a non-null or null value into the sorter.
46 /// Should be equivalent to calling `push_n` with n = 1
47 async fn push(&mut self, value: Option<BytesRef<'_>>) -> Result<()> {
48 self.push_n(value, 1).await
49 }
50
51 /// Pushing n identical non-null or null values into the sorter.
52 /// Should be equivalent to calling `push` n times
53 async fn push_n(&mut self, value: Option<BytesRef<'_>>, n: usize) -> Result<()>;
54
55 /// Completes the sorting process and returns the sorted data
56 async fn output(&mut self) -> Result<SortOutput>;
57}