JPH04213111A - Data sort system - Google Patents

Abstract

PURPOSE:To improve a sort speed and a sort performance at the time of a sort intermediate processing and sort final processing, when the sort processing of a great amount of data is operated by using a work fine. CONSTITUTION:This system is controlled by a string link means 7, so that after there is only one string in which a record remains at the time of the merge processing of the string, during the sort intermediate processing, this string can be linked to the tail of the newest string whose marge processing is completed on a work file 1. And also, when the above mentioned state is generated at the time of the sort final processing, this remining record is successively transmitted from the work file 1 to an output file 2.

Description

[Detailed description of the invention]

0001

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data sorting method, and more particularly to a data sorting method that uses a work file to sort data in an amount that cannot be read once into a main memory device.

0002

[Background Art] In a sorting process that uses a work file to sort the amount of data that cannot be read into the main memory at once, records are read into the main memory one by one while the intermediate results of sorting are processed. It creates multiple ordered sequences of records, called strings, and then merges some of these strings together to create a new string. Then, the above process is repeated to finally merge the strings into one string.

More specifically, when merging strings together to create a new string, first input records one by one into the sort memory area in the main storage, starting from the first record of each string in the work file. , these records are sorted, and if a record becomes the winner, this record is output to the work file. Then, the next record from the string to which this record belonged is input into the sort memory area, and the records in the sort memory area are sorted again to determine the winner. Write this winning record after the previous winning record in the work file to create a new string.

[0004] Merge processing work is to combine a plurality of strings into one string by repeating the above processing.

During this merge process, even after all string records except one string have been processed, the records are sorted from the strings whose records remain in the sort memory area in the main storage. The winning record is determined and output to the work file by inputting dummy data having an infinite key in place of the string with no records and competing against the records in the sort memory area.

[0006] Also, even in sort termination processing that merges all strings in a work file at once and outputs the sorted results, even after all string records except for one string have been processed, the sort cannot be completed. The winning record is determined by inputting a record from a slit string that has a record remaining in the memory area, and using dummy data with an infinite key to compete against the record in memory in place of the data of the string that has no record. , is outputting to the output file.

[0007] When sorting is performed using the conventional technique described above, when merging strings,
Even if only one string of records remains, sorting is performed by matching this record against dummy data, which has the drawback of requiring extra processing time.

[0008] Furthermore, when merging strings to create a new string, even if only one string of records remains, the remaining records are input to main memory and then output to the work file. This has the disadvantage that the number of input/output operations to the work file increases, reducing performance.

[0009]

OBJECTS OF THE INVENTION An object of the present invention is to provide a data sorting method using a work file that can shorten sorting processing time and improve sorting performance.

0010

[Structure of the Invention] The data sorting method according to the present invention reads records one by one into the main memory and creates a plurality of ordered record strings called strings, which are intermediate results of sorting. A data sorting method that includes sorting intermediate processing to create a new string by merging the strings, and includes a randomly accessible work file to store the strings and a temporary record to be sorted. A sort memory area provided in a main memory for storing, a string means for linking strings to each other on the work file, and a sort main processing means for performing sort processing, and the sort main processing means: During the merge work of the sort intermediate processing, when the merging of records for all strings except one string is completed, the records remaining in the sort memory area are output to the work file, and then the remaining records are The present invention is characterized in that the string ring means is controlled so that the one string that is being created is linked on the work file after the string that is being created.

Another data sorting method according to the present invention reads records one by one into the main memory, creates a plurality of ordered record strings called strings, which are intermediate results of sorting, and selects how many of them. A data sorting method that includes a final sorting process in which the strings are merged to create a new string, and the above operations are repeated to finally create one string, and a random string is used to store the string. An accessible work file, a sort memory area provided in the main memory to temporarily store records to be sorted, an output file to which merged records are written one by one, and a sorter to perform the sorting process. a main processing means, and when the merging of records of all strings except one string is completed during the merging operation, the sort main processing means transfers the records remaining in the sort memory area to the output file. The remaining strings of records in the work file are sequentially written to the sort memory area, and the written records are sequentially output to the output file for final sort processing. It is characterized by the following.

0012

DESCRIPTION OF THE PREFERRED EMBODIMENTS Examples of the present invention will be described below with reference to the drawings.

FIG. 1 is a functional block diagram of an embodiment of the present invention. 1 is a randomly accessible work file on an auxiliary storage device for storing an ordered sequence of records called a string, which is an intermediate result of sorting;
, 12 and 13 are each string output to the work file 1, 2 is an output file for outputting the sort results, 3 is a sort main processing means, 4 is a main storage device, and 41 is a main memory for reading records to be sorted. A sort memory area on the storage device 4, 5 a work file input means for reading one record from a string in the work file 1 into the sort memory area 41, and 6 a work file input means for writing one record from the sort memory area 41 into the work file 1 as a string. 7 is a string linking means for linking strings in the work file 1; 8 is a string linking means for linking strings in the work file 1;
is 1 record output file 2 from sort memory area 41
This is an output means for outputting to.

First, using FIG. 1, sort main processing means 3
An overview of the processing procedure is explained below. The sort main processing means 3 sequentially reads records to be sorted into the sort memory area 41 while sorting them, outputs a plurality of strings to the work file 1, and uses the work file input means 5 to input records from these strings into the sort memory again. Sorting is performed by reading into the area 41 and merging.

At this time, if there is no sort memory area 41 that can merge all the strings created in the work file 1 at once, some of these strings are merged and output to the work file output means. 6, new strings are output to work file 1 and the number of strings is reduced.

Finally, when all the strings in the work file 1 have reached the number that can be merged at one time, the output means 8 sequentially outputs the records of this merge result to the output file 2.

Next, among the processing of the sort main processing means 3,
Refer to FIG. 2 for the process of merging several strings to create a new string, and the operations of the work file input means 5, work file output means 6, and string link means 7 used in this process. This will be explained in detail.

Here, as the string link means 7,
It is assumed that a string information table 210 having the position of a string in the work file 1 and a pointer to a linked string is prepared, and string linking processing is performed by manipulating this table.

As shown in FIG. 2(A), when proceeding to the string merging process, the string 2 created so far
Each position a, b, in the work file 01 to 203
Suppose that c is stored in the string information table 210.

First, work file 1 to be merged currently
Addresses a, b, and c of each string are taken out from the string information table 210, and the first record of each string is input to the sort memory area 41 using the work file input means 4, and these records are pitted against each other for sorting. do.

As a result of the sorting, the strongest record (in this example, the record of string 210) is output to the work file 1 using the work file output means 6, as shown in FIG. 2(B). The position d of the newly created string 204 in the work file 1 is stored in the string information table 210. Furthermore, the string 201 to which this record belonged
Enter the next record from.

[0022] Thereafter, the winning records are sequentially output to the work file 1, records are input from the string to which the records belonged, and the records are pitted against the records in the sort memory area 41, thereby performing string merging processing. .

As shown in FIG. 2(C), the string 201
, 202 are all input into the sort memory area 41, and only string 203 remains in the record (the hatched record is the processed record), all the records remaining in the sort memory area 41 are input. Sort and connect to string 204 in work file 1.

Next, the string linking means 7 is called, and the position e in the work file 1 of the record remaining in the string 203 is stored in the string information table 210, and the string information table 210 is further transferred to this area.
A pointer is attached as a continuation of the string 204 within. This allows the remaining records of string 203 to be linked to string 204.

[0025] Now, the strings 201, 202,
The merging work of 203 is completed. From now on, when merging the string 204 created above with another string, records are sequentially input from string 204 to the sort memory area 41 and sorted, and when the records for string 204 are completed, they are merged into the string information table 210.
The string 203 is retrieved using the pointer in the string 203, and records are input from the string 203.

Next, among the sort main processing means 3, there is a final sorting process of merging all the strings in the work file 1 and outputting the sort results to the output file 2, and a work file input means 5 used in this process. , the operation of the output means 8 will be explained in detail with reference to FIG.

First, as shown in FIG. 3(A), the first record of each string 301 to 303 in the work file 1 is input to the sort memory area 41 using the work file input means 4, and the main sort processing is performed. By means of means 3, these records are pitted against each other and sorted.

As a result of the sorting, the strongest record (in this example, the record of string 301) is output to the output file 2 using the output means 8, as shown in FIG. 3(B). Furthermore, the next record is input from the string 301 to which this record belonged.

[0029] From then on, the winning records are sequentially output to file 2.
By inputting a record from the string to which the record belonged and competing against the records in the sorting memory area 41, the sorting result is output.

When all the records of strings 301 and 302 are input into the memory area 41 and only string 303 remains as shown in FIG. 3(C), all the records remaining in the sort memory area 41 are input. Sort and output to output file 2.

Thereafter, as shown in FIG. 3(D), the remaining records from the string 303 are sequentially input into the sort memory area 41 using the work file input means 5.
The record is output as it is to an output file 2 using an output means 8 without being played.

[0032]

[Effects of the Invention] As described above, according to the present invention, after there is only one string with a record remaining during string merging processing, the record of this string can be processed without having to compete with dummy data. Therefore, the sort processing time can be shortened, and there is no need to input/output the remaining records to the work file.
This has the effect of improving sorting performance.

[Brief explanation of the drawing]

FIG. 1 is a functional block diagram showing an embodiment of the present invention.

FIG. 2 is a diagram illustrating a sorting intermediate processing procedure according to an embodiment of the present invention.

FIG. 3 is a diagram illustrating a sort final processing procedure according to an embodiment of the present invention.

Claims (2)

[Claims] Claim 1: While reading records one by one into the main memory, multiple ordered record columns called strings, which are intermediate results of sorting, are created, and some of these strings are merged to create a new record string. A data sorting method including intermediate sorting processing to create a string,
A randomly accessible work file for storing the strings; a sort memory area provided in main memory for temporarily storing records to be sorted; A linking string means and a sort main processing means for performing sort processing are provided, and the sort main processing means is configured to merge records of all strings except for one string during the merging operation of the sort intermediate processing. When finished, after outputting the records remaining in the sort memory area to the work file, the string ring is linked so that the one string in which records remain is linked on the work file after the string being created. A data sorting method characterized by controlling means. [Claim 2] While reading records one by one into the main memory, multiple ordered record columns called strings, which are intermediate results of sorting, are created, and some of these strings are merged to create a new record string. This data sorting method includes a final sorting process in which a string is created and the above operations are repeated to finally form one string, and the data sorting method includes a randomly accessible work file for storing the string, and a sorting process. A sort memory area provided in the main storage device for temporarily storing target records, an output file for writing merged records one by one, and a sort main processing means for performing sort processing, When the merging of records of all strings except one string is completed during the merging operation, the sort main processing means outputs the records remaining in the sort memory area to the output file and performs the merging operation. The remaining strings of records in the work file are sequentially written into the sort memory area, and the written records are sequentially output to the output file to perform final sort processing. Data sorting method.