External sorting using key value distribution and range formation

• US 4,575,798 A
• Filed: 06/03/1983
• Issued: 03/11/1986
• Est. Priority Date: 06/03/1983
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vitter, Jeffrey S., Lindstrom, Eugene E.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/500,741
• Time in Patent Office: 1,012 Days
• Field of Search: 364/200, 364/300, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 2207/222 Binary data tree
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method for executing an external distribution sort in which the data to be rearranged includes keyed stored records that can be accessed on associative secondary storage. The method steps include random sampling of a certain number of keys and internally sorting the sampled keys; forming equal sized partitions of records in a single pass, each partition of which can fit within internal CPU memory and constitute a range of key values; and associatively retrieving all of the records whose keys lie within a range and internally sorting said records.

Claims

1. A method for executing an external distribution sort, the data to be rearranged including N keyed records accessed by a CPU from associative secondary storage, the CPU having predetermined available internal memory of F records capacity, comprising the steps of:

random sampling of S keys, internally sorting the sampled keys within the CPU, and representing the sorted order by a sequential pointer list;

forming equal sized partitions averaging N/S<

F records in a single pass by obtaining a histogram of keys and ranges of key values including for each key the step of performing a binary search on the pointer list to ascertain the range associated with the key, and forming S+1 ranges and denoting the sorted key values by X₁, X₂, . . . . , X_S for each value i from one to S+1, the ith range including the set of records whose key value lies in the semi-closed interval X_i-1 to X_i, and combining contiguous lesser populated ranges to form larger ranges such that each partition fits within the CPU internal memory; and

associatively retrieving all of the records whose keys lie within a range of a partition and internally sorting said records.

2. A method according to claim 1, wherein said method further includes the modification steps of marking selective records and associatively retrieving only marked records.

3. A new use of a data processor having a central processing unit, an internal memory of capacity M, an associative storage device, and means coupling the memory and the device to the CPU, said new use comprising a method for executing a distribution sort on data including keyed records accessible on the associative device, the method steps include:

random sampling S record keys and sorting the sampled keys;

counting how many records belong to each range defined by the sorted sample, and combining lesser populated contiguous ranges to form larger ranges, each range of which containing roughly the number of records that can fit within the internal memory, in order to estimate the distribution of key values of the records constituting a file in a single pass; and

associatively retrieving all of the records whose keys lie within a range and internally sorting the retrieved records.

4. A new use of a data processor according to claim 3, wherein each record has a fixed length of R bytes and each key field consists of K less than R bytes, and further wherein any arbitrary file to be sorted consists of N records, and still further wherein the minimum amount of internal memory is proportional to ##EQU3##

5. A method for executing an external distribution sort, the data to be rearranged including keyed records accessed by a CPU from associative secondary storage, the CPU having predetermined available internal memory M, the method steps include:

random sampling of S keys and internal sorting of the sampled keys including the step of representing the sorted order by a sequential pointer list;

forming equal sized partitions of records in a single pass by obtaining a histogram of keys and ranges of key values and combining contiguous lesser populated ranges to form larger ranges such that each partition fits within the CPU internal memory, said partition forming step includes the step of performing a binary search on the pointer list in order to ascertain the range associated with the key for each key in the histogram; and

associatively retrieving all of the records whose keys lie within a range of a partition and internally sorting said records.

6. A method according to claim 5, wherein the partition forming step further includes the steps of forming S+1 ranges and denoting the sorted key values by X₁, X₂, . . . , X_s for each value i from 1 to S+1, the ith range including the set of records whose key value lies in the semi-closed interval X_i-1 to X_i.

7. A method according to claim 5, wherein the step of forming of partitions of records includes the steps of processing each key on the associative device and performing a binary search on the pointer list in order to ascertain which small range contains the key, incrementing the count for that range by unity and storing the count for the range in the pointer fields of the key defining the upper limit of the range;

the step of combining contiguous lesser populated ranges to form larger ranges includes the steps of combining small ranges so that the resulting combined range contains at most M/R records, in the event such combined range exceeds M/R, associating a special marker with the key that defines the upper limit of the range designating it as an overflow range.