Struct TopKHeap 

struct TopKHeap {
    k: usize,
    batch_size: usize,
    inner: BinaryHeap<TopKRow>,
    store: RecordBatchStore,
    owned_bytes: usize,
}

This structure keeps at most the smallest k items, using the [arrow::row] format for sort keys. While it is called “topK” for values like 1, 2, 3, 4, 5 the “top 3” really means the smallest 3 , 1, 2, 3, not the largest 3 3, 4, 5.

Using the Row format handles things such as ascending vs descending and nulls first vs nulls last.

Fields

k: usize

The maximum number of elements to store in this heap.

batch_size: usize

The target number of rows for output batches

inner: BinaryHeap<TopKRow>

Storage for up at most k items using a BinaryHeap. Reversed so that the smallest k so far is on the top

store: RecordBatchStore

Storage the original row values (TopKRow only has the sort key)

owned_bytes: usize

The size of all owned data held by this heap

Implementations

impl TopKHeap

fn new(k: usize, batch_size: usize) -> Self

pub fn register_batch(&mut self, batch: RecordBatch) -> RecordBatchEntry

Register a [RecordBatch] with the heap, returning the appropriate entry

pub fn insert_batch_entry(&mut self, entry: RecordBatchEntry)

Insert a RecordBatchEntry created by a previous call to Self::register_batch into storage.

fn max(&self) -> Option<&TopKRow>

Returns the largest value stored by the heap if there are k items, otherwise returns None. Remember this structure is keeping the “smallest” k values

fn add( &mut self, batch_entry: &mut RecordBatchEntry, row: impl AsRef<[u8]>, index: usize, )

Adds row to this heap. If inserting this new item would increase the size past k, removes the previously smallest item.

pub fn emit(&mut self) -> Result<Option<RecordBatch>>

Returns the values stored in this heap, from values low to high, as a single [RecordBatch], resetting the inner heap

pub fn emit_with_state(&mut self) -> Result<(Option<RecordBatch>, Vec<TopKRow>)>

Returns the values stored in this heap, from values low to high, as a single [RecordBatch], and a sorted vec of the current heap’s contents

pub fn maybe_compact(&mut self) -> Result<()>

Compact this heap, rewriting all stored batches into a single input batch

fn size(&self) -> usize

return the size of memory used by this heap, in bytes

fn get_threshold_values( &self, sort_exprs: &[PhysicalSortExpr], ) -> Result<Option<Vec<ScalarValue>>>