Data Sorting Method And System

Abstract

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 using the plurality of floating buffers.

1 . A computer-implemented method for merging sorted runs of data, comprising:
 comparing data records in a first set of floating buffers to generate a sorted output;   storing the sorted output in a computer readable medium;   copying additional data blocks from a plurality of sorted runs into a second set of floating buffers before the additional data blocks are needed by the comparing step; and   replacing depleted floating buffers from the first set with floating buffers from the second set containing the additional data blocks.   
   
   
       2 . The computer-implemented method of  claim 1 , further comprising:
 prior to the comparing step, configuring the first and second sets of floating buffers to store a predetermined number of data blocks, wherein the predetermined number of data blocks is calculated to achieve an optimal number of data blocks for each floating buffer.   
   
   
       3 . The computer-implemented method of  claim 2 , wherein the optimal number of data blocks is the number for achieving a selected reduction in disk latency costs. 
   
   
       4 . A data sorting system, comprising:
 a data store for storing a plurality of sorted runs of data blocks, each data block including a plurality of data records;   a computing device configured with a plurality of floating buffers, the plurality of floating buffers including a first set of floating buffers and a second set of floating buffers; and   one or more programs stored in a memory location on the computing device and configured to compare data records in the first set of floating buffers to generate a sorted output, copy additional data blocks from the plurality of sorted runs into the second set of floating buffers before the additional data blocks are needed in the first set of floating buffers, and replace depleted floating buffers from the first set of floating buffers with floating buffers from the second set of floating buffers containing the additional data blocks.   
   
   
       5 . The data sorting system of  claim 4 , wherein the one or more programs are further configured to define the first and second sets of floating buffers to store a predetermined number of data blocks, wherein the predetermined number of data blocks is calculated to achieve an optimal number of data blocks for each floating buffer. 
   
   
       6 . The data sorting system of  claim 5 , wherein the optimal number of data blocks is the number needed to achieve a desired reduction in disk latency costs. 
   
   
       7 . A floating buffer for use with a data sorting system having a computing device and one or more programs stored in a memory location on the computing device, the one or more programs when executed by the computing device being operable to sort data records from a plurality of sorted runs of data blocks into a single sorted output, the floating buffer comprising:
 a record memory location configured to store a plurality of data blocks;   wherein the one or more programs calculate a number of data blocks stored in the record memory location and configure the record memory location to store the number of data blocks.   
   
   
       8 . The floating buffer of  claim 7 , further comprising:
 a key memory location configured to store record key values for associating the data blocks stored in the record memory location with a location of the data blocks in the sorted runs of data blocks.   
   
   
       9 . The floating buffer of  claim 8 , further comprising:
 a buffer data structure configured to identify the data blocks stored in the record memory location.   
   
   
       10 . The floating buffer of  claim 9 , wherein the buffer data structure includes a current key pointer for identifying a smallest record key value stored in the key memory location. 
   
   
       11 . The floating buffer of  claim 9 , wherein the buffer data structure includes a start block identifier for identifying a first data block loaded into the record memory location. 
   
   
       12 . The floating buffer of  claim 9 , wherein the buffer data structure includes a total block identifier for indicating a total number of data blocks stored in the record memory location. 
   
   
       13 . The floating buffer of  claim 9 , wherein the buffer data structure includes a total records identifier for indicating a total number of data records stored in the record memory location. 
   
   
       14 . The floating buffer of  claim 9 , wherein a plurality of run descriptor data structures are stored in a memory location on the computing device, each run descriptor data structure identifying the data blocks included in one of the sorted runs of data blocks, and wherein the buffer data structure includes a disk run pointer for identifying one or the run descriptor data structures associated with the data blocks stored in the record memory location.