THIS IS A TEST INSTANCE. ALL YOUR CHANGES WILL BE LOST!!!!
1. Motivation
To efficiently support the sort-dependent operators based on the Hyracks running framework, a multiple stages-based subdivision is used to dynamically construct the rangemap, cache the frames as well as parallelize the operations. Since the down-streaming operator could be connected with the sort-dependent operators in one stage, which means both those down-streaming operators and the sort-dependent operators can execute in pipeline. We should cache the frames from the down-streaming operators to the sort-dependent operators until the target rangemap is completely figured out. Based on a range partitioner, the caching frames can be forwarded onto their targets correspondingly.
2. RangeMap Generation Based on Aggregation
Combining a replicate operator, the aggregation-based RangeMap is generated based on a streaming algorithm to dynamically construct the histogram.
use dataverse tpch let $rg := rg( for $d in dataset Lineitem return $d.l_extendedprice ) return $rg |
|---|
3. Parallel Sort
In general, the parallel sort is divided into five stages, i.e., replicate, local aggregation, global aggregation, forward, sort and merge, to scale up the sort based on Hyracks.
A parallel sort template can be given as:
use dataverse tpch for $d in dataset Lineitem order by $d.l_extendedprice /*+ psort */ return $d |
|---|
3.1 Five stages of parallel sort
4. Binary In-Equal Join