External sorting using virtual storage

Claim 1

A data processing system comprising a CPU having LRU-managed virtual storage supported by fast internal (real) memory and a slower higher capacity backing store and sort logic for performing an external sort operation on key-based records by: (a) during a sort phase, reading subsets of record keys into a fully internal memory-backed virtual storage, arranging the records into ordered strings, and mapping the ordered strings into other selectively internal memory-backed portions of virtual storage; and (b) during a merge phase, mapping back preselected elements of the sorted strings into fully internal memory-backed virtual storage and performing a multiple- way merge operation on said mapped preselected string elements, whereby the virtual storage is used as a work device during the sort and merge phases of the external sort operation.

Claim 9

A method of performing an external sort operation on key-based records in a data processing system comprising a CPU having LRU-managed virtual storage supported by fast internal (real) memory and a slower higher capacity backing store, the method comprising the steps of: (a) during a sort phase, reading subsets of record keys into a fully internal memory-backed virtual storage, arranging the records into ordered strings, and mapping the ordered strings into other selectively internal memory-backed portions of virtual storage; and (b) during a merge phase, mapping back preselected elements of the sorted strings into fully internal memory-backed virtual storage and performing a multiple- way merge operation on said mapped preselected string elements, whereby the virtual storage is used as a work device during the sort and merge phases of the external sort operation.

Claim 10

A method of performing an external sort operation on key-based records in a data processing system comprising a CPU having LRU-managed virtual storage supported by fast internal (real) memory and a slower higher capacity backing store, the method comprising the steps of: (a) during a sort phase, reading subsets of record keys into a fully internal memory-backed virtual storage, arranging the records into ordered strings, and mapping the ordered strings into other selectively internal memory-backed portions of virtual storage; and (b) during a merge phase, mapping back preselected elements of the sorted strings into fully internal memory-backed virtual storage and performing a multiple- way merge operation on said mapped preselected string elements, whereby the virtual storage is used as a work device during the sort and merge phases of the external sort operation.

Claim 13

A method of generating a sort string of m records in a data processing system comprising a central processing unit having LRU-managed virtual storage, said CPU including internal (real) memory for storing programs and data, and means for accessing the real memory for executing sort and management operations, said real memory and accessing means being managed as virtual storage, the method of generating the sort string being manifest as a nested ordering of keys of the records and comprising the steps of: (a) during a first pass, calling one of m/s subsets of s keys (s < m) of the records from an extrinsic source into a portion of virtual storage fully backed by internal (real) memory, and arranging the called subset into a partial nested ordering thereof, moving the nested ordering to another portion of virtual storage selectively backed by internal (real) memory and updating a table with the virtual storage address of the nested ordering, the step being repeated until the m/s subsets are exhausted; and (b) during a second pass, executing a t-way replacement selection merge (t < s) in virtual storage selectively backed by internal (real) memory from among at least one key selected from each of t partial nested orderings of the subsets resident in the virtual storage according to their table virtual storage addresses until the m/s such orderings become exhausted.

Claim 14

A method of generating a sort string of m records in a data processing system comprising a central processing unit having LRU-managed virtual storage, said CPU including internal (real) memory for storing programs and data, and means for accessing the real memory for executing sort and management operations, said real memory and accessing means being managed as virtual storage, the method of generating the sort string being manifest as a nested ordering of keys of the records and comprising the steps of: (a) during a first pass, calling one of m/s subsets of s keys (s < m) of the records from an extrinsic source into a portion of virtual storage fully backed by internal (real) memory, and arranging the called subset into a partial nested ordering thereof, moving the nested ordering to another portion of virtual storage selectively backed by internal (real) memory and updating a table with the virtual storage address of the nested ordering, the step being repeated until the m/s subsets are exhausted; and (b) during a second pass, executing a t-way replacement selection merge (t < s) in virtual storage selectively backed by internal (real) memory from among at least one key selected from each of t partial nested orderings of the subsets resident in the virtual storage according to their table virtual storage addresses until the m/s such orderings become exhausted.

Claim 15

A method as claimed in any one of claims 7 to 10 wherein said internal memory includes a byte-oriented, randomly addressable portion and a block-oriented and LRU-managed portion.

Claim 16

A method as claimed in any one of claims 7 to 11 wherein wherein the ratio of internal (real) memory backing to virtual storage lies in the range substantially between 30-80 percent.