The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Dec. 22, 1998
Filed:
Jan. 26, 1996
Gary Graunke, Beaverton, OR (US);
Leonard D Shapiro, Portland, OR (US);
Sujata Ramamoorthy, Beaverton, OR (US);
Sequent Computer Systems, Inc., Beaverton, OR (US);
Abstract
A parallel sorting technique for external and internal sorting which maximizes the use of multiple processes to sort records from an input data set. Performance of the sort linearly scales with the number of processors because multiple processors can perform every step of the technique. To begin, the records of a data set to be sorted are read from an input file and written into multiple buffers in memory so long as memory is available. The records within each buffer are then simultaneously sorted to create runs therein. A merge tree is constructed with the runs as stream elements into leaf nodes of the tree, where the stream elements are merged. The stream elements at each node are then merged by multiple processes working simultaneously at the node, thereby generating an output stream of elements for merging at a higher node. For an internal sort, the run that results from all of the merging is immediately written to an output device. For an external sort, the run is an intermediate run, written to secondary storage along with other intermediate runs. A forecast structure provides a forecast of the order of the run blocks from the multiple intermediate runs. These blocks are read in the forecasted order from secondary storage, written into memory and merged through a merge tree to form an ordered record stream that is a complete run for the data set. The ordered record stream is then written to the output device.