Data restructuring in multi-level memory hierarchies

摘要

A method, executed on a suitably programmed processor, provides for ordering records using a memory hierarchy. The memory hierarchy includes and two or more lower levels of the memory hierarchy. The method includes the steps of (a) receiving unsorted input records; (b) reading the input records in pages and writing one or more pages of the input records to the primary memory; (c) sorting the pages of input records to create a run; (d) if a size of the run exceeds primary memory capacity, moving data that just exceeds the primary memory capacity to a secondary level of the memory hierarchy; (e) repeating steps (a)-(d) until either (i) all unsorted input records have been read into primary memory and sorted, or (ii) a capacity of the secondary level of the memory hierarchy is exceeded; (f) following step (e)(ii), moving data that just exceeds the secondary memory capacity from the secondary level to a tertiary level of the memory hierarchy until the capacity of the secondary level no longer is exceeded; and (g) following either of steps (c), (e)(i), or (f), merging runs to create a merge output.

主权项

1. A method, executed on a processor, for ordering records using a memory hierarchy, comprising:
(a) receiving unsorted input records; (b) reading the input records and holding the input records in a primary memory; (c) sorting pages of input records to create a run; (d) moving data that just exceeds a capacity of the primary memory to a secondary level of the memory hierarchy; (e) repeating (a)-(d) until a capacity of the secondary level of the memory hierarchy is exceeded; (f) following (e), moving data that just exceeds the secondary memory capacity from the secondary level to a tertiary level of the memory hierarchy until the capacity of the secondary level no longer is exceeded; and (g) following (f), merging runs from the primary memory, the secondary level of the memory hierarchy, and the tertiary level of the memory hierarchy, to create a final sorted output, wherein the final sorted output is stored at the tertiary level of the memory hierarchy.