Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Data sorting method and system

This is a continuation of U.S. patent application Ser. No. 10/983,745, filed on Nov. 8, 2004, the entirety of which is incorporated herein by reference.

The technology described in this patent document relates generally to data sorting. More specifically, this document describes systems and methods for sorting data using a multi-block floating buffer.

Sorting is the process of ordering items based on specified criteria. In data processing, sorting indicates the sequencing of records using a key value determined for each record. If a group of records is too large to be sorted within available random access memory, then a two-phase process, referred to as external sorting, may be used. In the first phase of the external sorting process, a portion of the records is typically sorted and the partial result, referred to as a sorted run, is stored to temporary external storage. Sorted runs are generated until the entire group of records is exhausted. Then, in the second phase of the external sorting process, the sorted runs are merged, typically to a final output record group. If all of the sorted runs cannot be merged in one pass, then the second phase may be executed multiple times in a process commonly referred to as a multi-pass or multi-phase merge. In a multi-phase merge, existing runs are merged to create a new, smaller replacement set of runs.

The records within a sorted run are typically written to external storage in sequential blocks of data, such that each block includes an integral number of records. The performance of typical merging and forecasting algorithms can be greatly affected by the size of the record block. For example, when sorting randomly ordered records, poor merge performance may result from the selection of small block size because disk latency, which may be orders of magnitude larger than any other delay (e.g., memory access latency) encountered during merging, can dominate processing time. One method of increasing merge performance is to establish a large block size so that access costs (i.e., time spent locating the blocks) are insignificant compared to transfer costs (i.e., time spent reading the blocks.) However, a large block size may also decrease performance by resulting in a multi-pass merge and, consequently, increased processing time and increased temporary storage requirements.

Another method for increasing performance during the merge phase is to eliminate time spent stalled on input (i.e., waiting for a record block to be retrieved from external storage) by reading blocks from storage in advance of their need while the merge is in progress. One algorithm used to achieve such parallelism is referred to as forecasting with floating buffers. This forecasting algorithm, designed to execute concurrently with the merge algorithm, reads blocks in the same sequence that the merge algorithm requires them. A typical forecasting algorithm determines which run to read next by comparing the largest key value of the last block read from each run being merged. The run associated with the smallest such key is the run from which the next block is read. The buffers, into which blocks are read, may be used to read data from any run, and are thus said to float among the runs.

In accordance with the teachings described herein, systems and methods are provided for data sorting. A method for use with one or more processing devices in order to merge sorted runs of data may include the steps of: defining a plurality of floating buffers; calculating a number of data blocks for each floating buffer; configuring the floating buffers to store the number of data blocks; and using the floating buffers to perform an external data sorting operation. A data sorting system may include one or more programs, and may be used with a plurality of floating buffers and a data storage device for storing a plurality of sorted runs of data blocks, each data block including a plurality of data records. The one or more programs in a data sorting system may be operable to calculate a number of data blocks for each floating buffer and configure the plurality of floating buffers to store the number of data blocks. In addition, the one or more programs in a data sorting system may be further operable to sort the plurality of data records into a single sorted output run using the plurality of floating buffers. In other examples, the number of data blocks in the plurality of floating buffers may be pre-determined or may be calculated by a different system using the techniques described herein.

FIG. 1 is a block diagram of an example data sorting system for performing an external sorting operation.

FIG. 2 is a block diagram of an example data sorting system showing sorted runs.

FIGS. 3A-3C illustrate an example operation of a data sorting system.

FIG. 4 is a flow diagram illustrating an example operational scenario for merging sorted runs.

FIG. 5 is a flow diagram illustrating an example operational scenario involving forecasting.

FIG. 6 is a block diagram illustrating an example data structure for a multi-block floating buffer.