Parallel merge sort method and apparatus

A method of sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising:

• reading blocks of records from an input device and writing the blocks to memory;
• sorting the records within each block simultaneously to create a run therein;
• constructing a merge tree for merging the runs into a larger run that is output by the tree, the merge tree having nodes where two runs are merged;
• simultaneously merging the runs throughout the merge tree to form the larger run by having more than two processes reserve portions of the two runs for merging at each node and having the processes simultaneously merge their portions of the runs at each node;
• and
• writing the larger run to an output device.

A method of merging records stored in shorter runs into a larger run, the method comprising the following steps:

• providing a forecast structure, the structure having entries containing a key of a predetermined record in each run block of each run and a run block address;
• sorting the entries in the forecast structure by the key of the predetermined record of each run block;
• reading a number of the sorted run blocks from secondary storage into memory;
• and
• merging the run blocks in memory through a merge tree having a root node to produce a longer run.

Apparatus for sorting records with a multiprocessor computer system having memory and a set of processes running in parallel, comprising:

• means for reading blocks of records from an input device and writing the blocks to memory;
• means for sorting the records within each block simultaneously to create a run therein;
• means for constructing a merge tree for merging the runs into an intermediate run that is output by the tree, the merge tree having nodes where two runs are merged to form another run;
• means for simultaneously merging the runs throughout the merge tree to form the intermediate run;
• means for writing intermediate runs to secondary storage;
• means for determining an order in which run blocks of the intermediate runs will be read from secondary storage;
• means for constructing a merge tree for merging the run blocks into a complete run that is output by the tree, the merge tree having nodes where two runs are merged to form another run;
• means for reading the run blocks from the secondary storage and writing the run blocks to memory in the determined order for merging in the merge tree;
• means for simultaneously merging runs throughout the merge tree to form the complete run;
• and
• means for writing the complete run to an output device.

A multiprocessor computer system for sorting records comprising:

• memory;
• multiple processors programmed to run merge processes in parallel in memory, at least several of the merge processes performing each of the following tasks as needed:
• constructing a merge tree in memory;
• and
• merging of records at a tree node into runs.