Method for performing an external (disk-based) sort of a large data file which takes advantage of “presorted” data already present in the input
View Patent ↗A method of externally sorting large files in a computer system is presented. The contents of the input file to be sorted are investigated in order to identify presorted portions thereof. The presorted portions of the input file as thus identified are incorporated as sorted strings into an external sortwork file, by rearranging directory information rather than physically transferring data. If merging is necessary, the data may then be merged by a procedure wherein blocks of sorted data to be merged are incorporated into an output (sortout) file, by rearranging directory information rather than physically transferring sorted blocks to the sortout file. As a result of the process, portions of sorted data incorporated into the sortout file may physically remain in external storage space allocated to the input file, and/or in external space allocated to sortwork, thereby eliminating or reducing reading and writing from disk during sort-merge processing.
1. A method for performing the string generation phase of a sort merge process in a computer, upon data in a first file comprising data blocks in a sortin file residing in persistent machine-readable storage, wherein said data may contain presorted portions, said method comprising:
(a) reading a portion of the sortin file into a first machine-readable memory area and noting in a second machine-readable memory area the locations on said persistent machine-readable storage from which the blocks of said portion were read;
(b) determining the location of any presorted runs existing in said read portion;
(c) marking as free the memory locations in said first memory area that are occupied by said presorted runs and noting in said second machine-readable memory area the locations in said persistent machine-readable storage from which the blocks of said presorted portions had been read;
(d) repeating the preceding three steps until either all data in the sortin file has been read or until said first memory area is full, and then sorting any data remaining in said first memory area, writing said sorted data to said persistent machine-readable storage, and noting in said second machine-readable memory area the locations in said persistent machine-readable storage area of said sorted data that was so written; and
(e) writing a file directory structure for a second file in persistent machine-readable storage, incorporating therein said locations of the blocks of said presorted runs and the locations of the blocks of said sorted data.
2. The method of claim 1 , wherein said second file is a sortwork file.
3. The method of claim 2 , further comprising:
(a) during said string generation phase, noting in said second machine-readable memory area the high and low keys of each data block read from said machine-readable persistent storage;
(b) performing a merge phase of the data in said sortwork file into a sortout file; and
(c) during said merge phase reading each block of each sorted string from said sortwork file if comparison of said keys for said block reflects that said block is not part of a run, and otherwise including said block into said sortout file by writing its block locations into the directory structure of said sortout file without physically reading or moving the data in said block.
4. The method of claim 1 , wherein said second machine-readable memory area comprises a directory structure maintained by an operating system of said computer for said persistent machine-readable storage.
5. The method of claim 3 , wherein said sortin file is deleted, by an operating system of said computer, after said merge phase.
6. The method of claim 3 , wherein said sortin file is replaced by said sortout file, by an operating system of said computer, after said merge phase.
7. The method of claim 1 , wherein said sortin file is comprised in its entirety by one fully sorted presorted portion, and wherein no data from said sortin file is sorted and no data from said sortin file is physically moved from said sortin file to said second file.