Struct LinearSearch 

pub struct LinearSearch {
    input_buffer_hashes: VecDeque<u64>,
    random_state: RandomState,
    ordered_partition_by_indices: Vec<usize>,
    row_map_batch: HashTable<(u64, usize)>,
    row_map_out: HashTable<(u64, usize, usize)>,
    input_schema: SchemaRef,
}

This object encapsulates the algorithm state for a simple linear scan algorithm for computing partitions.

Fields

input_buffer_hashes: VecDeque<u64>

Keeps the hash of input buffer calculated from PARTITION BY columns. Its length is equal to the input_buffer length.

random_state: RandomState

Used during hash value calculation.

ordered_partition_by_indices: Vec<usize>

Input ordering and partition by key ordering need not be the same, so this vector stores the mapping between them. For instance, if the input is ordered by a, b and the window expression contains a PARTITION BY b, a clause, this attribute stores [1, 0].

row_map_batch: HashTable<(u64, usize)>

We use this [HashTable] to calculate unique partitions for each new RecordBatch. First entry in the tuple is the hash value, the second entry is the unique ID for each partition (increments from 0 to n).

row_map_out: HashTable<(u64, usize, usize)>

We use this [HashTable] to calculate the output columns that we can produce at each cycle. First entry in the tuple is the hash value, the second entry is the unique ID for each partition (increments from 0 to n). The third entry stores how many new outputs are calculated for the corresponding partition.

input_schema: SchemaRef

Implementations

impl LinearSearch

fn new( ordered_partition_by_indices: Vec<usize>, input_schema: SchemaRef, ) -> Self

Initialize a new LinearSearch partition searcher.

fn get_per_partition_indices( &mut self, columns: &[ArrayRef], batch: &RecordBatch, ) -> Result<Vec<(PartitionKey, Vec<u32>)>>

Calculate indices of each partition (according to PARTITION BY expression) columns contain partition by expression results.

fn calc_partition_output_indices( &mut self, input_buffer: &RecordBatch, window_agg_states: &[PartitionWindowAggStates], window_expr: &[Arc<dyn WindowExpr>], ) -> Result<Vec<(PartitionKey, Vec<u32>)>>

Calculates partition keys and result indices for each partition. The return value is a vector of tuples where the first entry stores the partition key (unique for each partition) and the second entry stores indices of the rows for which the partition is constructed.

Trait Implementations

impl PartitionSearcher for LinearSearch

fn calculate_out_columns( &mut self, input_buffer: &RecordBatch, window_agg_states: &[PartitionWindowAggStates], partition_buffers: &mut PartitionBatches, window_expr: &[Arc<dyn WindowExpr>], ) -> Result<Option<Vec<ArrayRef>>>

This method constructs output columns using the result of each window expression.

fn evaluate_partition_batches( &mut self, record_batch: &RecordBatch, window_expr: &[Arc<dyn WindowExpr>], ) -> Result<Vec<(PartitionKey, RecordBatch)>>

fn prune(&mut self, n_out: usize)

Prunes the state.

fn mark_partition_end(&self, partition_buffers: &mut PartitionBatches)

Marks the partition as done if we are sure that corresponding partition cannot receive any more values.

fn is_mode_linear(&self) -> bool

Determine whether [InputOrderMode] is [InputOrderMode::Linear] or not.

fn input_schema(&self) -> &SchemaRef

fn update_partition_batch( &mut self, input_buffer: &mut RecordBatch, record_batch: RecordBatch, window_expr: &[Arc<dyn WindowExpr>], partition_buffers: &mut PartitionBatches, ) -> Result<()>

Updates input_buffer and partition_buffers with the new record_batch.