Struct WindowedSortExec

pub struct WindowedSortExec {
    expression: PhysicalSortExpr,
    fetch: Option<usize>,
    ranges: Vec<Vec<PartitionRange>>,
    all_avail_working_range: Vec<Vec<(TimeRange, BTreeSet<usize>)>>,
    input: Arc<dyn ExecutionPlan>,
    metrics: ExecutionPlanMetricsSet,
    properties: PlanProperties,
}

A complex stream sort execution plan which accepts a list of PartitionRange and merge sort them whenever possible, and emit the sorted result as soon as possible. This sorting plan only accept sort by ts and will not sort by other fields.

internally, it call [StreamingMergeBuilder] multiple times to merge multiple sorted “working ranges”

Invariant Promise on Input Stream

1. The input stream must be sorted by timestamp and
2. in the order of PartitionRange in ranges
3. Each PartitionRange is sorted within itself(ascending or descending) but no need to be sorted across ranges
4. There can’t be any RecordBatch that is cross multiple PartitionRange in the input stream

TODO(discord9): fix item 4, but since only use PartSort as input, this might not be a problem

Fields

expression: PhysicalSortExpr

Physical sort expressions(that is, sort by timestamp)

fetch: Option<usize>

Optional number of rows to fetch. Stops producing rows after this fetch

ranges: Vec<Vec<PartitionRange>>

The input ranges indicate input stream will be composed of those ranges in given order.

Each partition has one vector of PartitionRange.

all_avail_working_range: Vec<Vec<(TimeRange, BTreeSet<usize>)>>

All available working ranges and their corresponding working set

working ranges promise once input stream get a value out of current range, future values will never be in this range. Each partition has one vector of ranges.

input: Arc<dyn ExecutionPlan>

metrics: ExecutionPlanMetricsSet

Execution metrics

properties: PlanProperties

Implementations

impl WindowedSortExec

pub fn try_new( expression: PhysicalSortExpr, fetch: Option<usize>, ranges: Vec<Vec<PartitionRange>>, input: Arc<dyn ExecutionPlan>, ) -> Result<Self>

pub fn to_stream( &self, context: Arc<TaskContext>, partition: usize, ) -> Result<DfSendableRecordBatchStream>

During receiving partial-sorted RecordBatch, we need to update the working set which is the PartitionRange we think those RecordBatch belongs to. And when we receive something outside of working set, we can merge results before whenever possible.

Trait Implementations

impl Clone for WindowedSortExec

fn clone(&self) -> WindowedSortExec

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for WindowedSortExec

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DisplayAs for WindowedSortExec

fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter<'_>) -> Result

Format according to DisplayFormatType, used when verbose representation looks different from the default one

impl ExecutionPlan for WindowedSortExec

fn benefits_from_input_partitioning(&self) -> Vec<bool>

Explain

This plan needs to be executed on each partition independently, and is expected to run directly on storage engine’s output distribution / partition.

fn as_any(&self) -> &dyn Any

Returns the execution plan as Any so that it can be downcast to a specific implementation.

fn schema(&self) -> SchemaRef

Get the schema for this execution plan

fn properties(&self) -> &PlanProperties

Return properties of the output of the ExecutionPlan, such as output ordering(s), partitioning information etc.

fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>>

Get a list of children ExecutionPlans that act as inputs to this plan. The returned list will be empty for leaf nodes such as scans, will contain a single value for unary nodes, or two values for binary nodes (such as joins).

fn with_new_children( self: Arc<Self>, children: Vec<Arc<dyn ExecutionPlan>>, ) -> Result<Arc<dyn ExecutionPlan>>

Returns a new ExecutionPlan where all existing children were replaced by the children, in order

fn execute( &self, partition: usize, context: Arc<TaskContext>, ) -> Result<DfSendableRecordBatchStream>

Begin execution of partition, returning a Stream of [RecordBatch]es.

fn metrics(&self) -> Option<MetricsSet>

Return a snapshot of the set of [Metric]s for this [ExecutionPlan]. If no Metrics are available, return None.

fn name(&self) -> &str

Short name for the ExecutionPlan, such as ‘DataSourceExec’.

fn static_name() -> &'static str

where Self: Sized,

Short name for the ExecutionPlan, such as ‘DataSourceExec’. Like name but can be called without an instance.

fn check_invariants(&self, check: InvariantLevel) -> Result<(), DataFusionError>

Returns an error if this individual node does not conform to its invariants. These invariants are typically only checked in debug mode.

fn required_input_distribution(&self) -> Vec<Distribution>

Specifies the data distribution requirements for all the children for this ExecutionPlan, By default it’s [[Distribution::UnspecifiedDistribution]] for each child,

fn required_input_ordering(&self) -> Vec<Option<OrderingRequirements>>

Specifies the ordering required for all of the children of this ExecutionPlan.

fn maintains_input_order(&self) -> Vec<bool>

Returns false if this ExecutionPlan’s implementation may reorder rows within or between partitions.

fn reset_state( self: Arc<Self>, ) -> Result<Arc<dyn ExecutionPlan>, DataFusionError>

Reset any internal state within this [ExecutionPlan].

fn repartitioned( &self, _target_partitions: usize, _config: &ConfigOptions, ) -> Result<Option<Arc<dyn ExecutionPlan>>, DataFusionError>

If supported, attempt to increase the partitioning of this ExecutionPlan to produce target_partitions partitions.

fn statistics(&self) -> Result<Statistics, DataFusionError>

👎Deprecated since 48.0.0: Use partition_statistics method instead

Returns statistics for this ExecutionPlan node. If statistics are not available, should return [Statistics::new_unknown] (the default), not an error.

fn partition_statistics( &self, partition: Option<usize>, ) -> Result<Statistics, DataFusionError>

Returns statistics for a specific partition of this ExecutionPlan node. If statistics are not available, should return [Statistics::new_unknown] (the default), not an error. If partition is None, it returns statistics for the entire plan.

fn supports_limit_pushdown(&self) -> bool

Returns true if a limit can be safely pushed down through this ExecutionPlan node.

fn with_fetch(&self, _limit: Option<usize>) -> Option<Arc<dyn ExecutionPlan>>

Returns a fetching variant of this ExecutionPlan node, if it supports fetch limits. Returns None otherwise.

fn fetch(&self) -> Option<usize>

Gets the fetch count for the operator, None means there is no fetch.

fn cardinality_effect(&self) -> CardinalityEffect

Gets the effect on cardinality, if known

fn try_swapping_with_projection( &self, _projection: &ProjectionExec, ) -> Result<Option<Arc<dyn ExecutionPlan>>, DataFusionError>

Attempts to push down the given projection into the input of this ExecutionPlan.

fn gather_filters_for_pushdown( &self, _phase: FilterPushdownPhase, parent_filters: Vec<Arc<dyn PhysicalExpr>>, _config: &ConfigOptions, ) -> Result<FilterDescription, DataFusionError>

Collect filters that this node can push down to its children. Filters that are being pushed down from parents are passed in, and the node may generate additional filters to push down. For example, given the plan FilterExec -> HashJoinExec -> DataSourceExec, what will happen is that we recurse down the plan calling ExecutionPlan::gather_filters_for_pushdown:

fn handle_child_pushdown_result( &self, _phase: FilterPushdownPhase, child_pushdown_result: ChildPushdownResult, _config: &ConfigOptions, ) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>, DataFusionError>

Handle the result of a child pushdown. This method is called as we recurse back up the plan tree after pushing filters down to child nodes via [ExecutionPlan::gather_filters_for_pushdown]. It allows the current node to process the results of filter pushdown from its children, deciding whether to absorb filters, modify the plan, or pass filters back up to its parent.

fn with_new_state( &self, _state: Arc<dyn Any + Sync + Send>, ) -> Option<Arc<dyn ExecutionPlan>>

Injects arbitrary run-time state into this execution plan, returning a new plan instance that incorporates that state if it is relevant to the concrete node implementation.