Back to results
US 2016/0098481 A1Published application
Parallel data sorting
AssigneeOracle International Corporation
InventorsHaowei Zhang, Xiaoying Shen
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeOracle International Corporation
InventorsHaowei Zhang, Xiaoying Shen
Estimating the term…
A method, apparatus, and system for improved high-performance parallel data sorting is provided. In a first phase, a plurality of unordered data elements to be sorted is divided into K unordered lists each preferably having approximately M elements. Each of these K unordered lists can be independently sorted in parallel using any algorithm, such as quicksort, to generate K ordered lists. In a second phase, N balanced workloads are determined from the K ordered lists by using an iterative converging process capped by a maximum number of iterations. Thus, any non-uniform or skewed data distribution can be load balanced with minimal processing time. Once the N balanced workloads are determined, they can be independently sorted in parallel, for example by using a merge sort, and then combined with a fast concatenation to provide the final sorted result. Thus, sorting operations are fully parallelized while avoiding any expensive data scanning steps.
A method comprising:
A non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, cause performing of:
A system comprising:
Dependencies are inferred from the claim text.