JPH0776935B2 - Record storage method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Object of the Invention (Field of Industrial Application) The present invention relates to a record storage system in a secondary storage device in a parallel processing device having a secondary storage device and a plurality of processors.

(Prior Art) In many information processing systems including a database, various kinds of information are generally stored as records in a secondary storage device. Then, the secondary storage device is configured to input and output the data in units of data of a certain fixed length. Therefore, it is not possible to individually store records of various sizes in the secondary storage device.

Therefore, conventionally, when storing records of various sizes in the secondary storage device, a record area of a certain fixed length called a page is defined, and information (records) of various sizes is defined with this page as a unit. Are stored in a secondary storage device.

That is, as shown in FIG. 5, for example, one or a plurality of records are set so that the record having the maximum size among various records to be stored in the secondary storage device is contained in one page. Records are stored together as long as they do not exceed the page length. At this time, information such as the number of records stored on the page and the number of pages is stored in the management area set at the beginning of the page, for example. In the example shown in FIG. 5, [n] records are stored in that page, and information indicating that the number of pages is [1] is stored.

However, due to the data input / output characteristics of the secondary storage device, there is a limit in setting the page length in accordance with the maximum record length. That is, the size of the page (page length) set in the secondary storage device is naturally limited. Therefore, it is undeniable that records exceeding the page length often appear.

In such a case, conventionally, a plurality of continuous pages are generally used, for example, as shown in FIG. 6, and it is possible to store records having a page length longer than the page length by continuously distributing the records. Be seen. In the example shown in FIG. 6, m
One continuous record is sequentially stored from the first page using the continuous pages. In this case, [1] records are stored in the management area set at the beginning of the first page, and information indicating that the number of used pages is [m] is stored.

A page as shown in FIG. 6 in which one record is stored over a plurality of continuous pages in this way is called an "incomplete page". On the other hand, as shown in FIG. 5 described above, a page packed with one or more records within a range that can be stored in one page is called a “complete page”.

By the way, in the technical field of information processing, various developments of a parallel processing device including a plurality of processors have been advanced, and the information processing is executed efficiently and at high speed by parallel processing in which functions are distributed. . In the technical field of database processing, the introduction of this kind of parallel processing has been tried, and various methods have been proposed.

Now, the most basic processing in database processing is "2.
Of the plurality of records stored in the next storage device, a record satisfying a certain search condition is selectively taken out. "

When such a search process is realized by a parallel processing device having a plurality of processors, basically, for example, "each processor synchronizes with another processor using some means, For each page to be processed in the secondary storage device, a processor that processes the page is determined.
The processor selected and determined then reads the corresponding page from the secondary storage device to the main storage device of the processor, and checks whether the given search condition is satisfied for the records packed therein. The processing procedure "" will be performed.

Such a processing procedure is realized by causing each of a plurality of processors to execute a program as shown in FIG. 7, for example. However, wait (S) and signal (S) in the program shown in FIG. 7 are means for ensuring that at most one processor executes the processing between them. That is, in this program, for example, when a certain processor A executes wait (S), if there is another processor B executing the part from wait (S) to signal (S), the above processor A Is processor B sign
Until al (S) is executed, wait (S) cannot proceed.

Incidentally, such an exclusive processing function will be introduced in detail in the following documents and the like.

"Blink Hansen, translated by Hozumi Tanaka, et al.," Operating System Principles, "published by Modern Science Co., Ltd. However, in the case of an ordinary parallel processing device, the processing from wait (S) to signal (S) of the program shown in FIG. 7 is required. The time is [the number of times required for reading the P-th page [read (P)] from the secondary storage device to the main storage device and the time required for the search condition determination process for the P-th page read to the main storage device. 100 to several tens of thousands]. Therefore, regarding the processing time from the wait (S) to the signal (S) of the above-mentioned program, even if only one processor at most can execute the processing during that time, it does not cause much problem.

However, if the page read from the secondary storage device to the main storage device includes the above-mentioned incomplete page, the program shown in FIG. 7 has a problem. That is, although it is necessary for a single processor to process continuous pages (non-completed pages) that store records exceeding the page size, the program shown in FIG. 7 takes this into consideration. Absent. For this reason, the records stored in the continuous pages (non-completed pages) may be read into the main storage devices of different processors for each page.

Therefore, if there are two records containing such a non-completed page,
When reading from the next storage device, a program as shown in FIG. 8 is executed in each processor.

Between this program wait (S) and signal (S), 2
The P-th page is read [read (P)] from the next storage device to the main storage device, the number of linked pages is obtained from the information described in the management area for the read page, and the read page is read. It is configured to advance P by that number (the number of connected pages). Then, after this processing is completed, the above-mentioned signal (S) is executed.

Therefore, in the program shown in FIG. 8 in which such measures are taken, the time required for the processing between wait (S) and signal (S) may be approximately the same as the time required for other processing. can not deny. As a result, even if the number of processors is increased and parallel processing is executed, there arises a problem that the overall processing time cannot be shortened so much.

(Problems to be Solved by the Invention) As described above, the conventional record storage method is basically developed with a single processor in mind, and stores a code including an incomplete page in the secondary storage device. If you do
The number of connected pages is recorded and managed in, for example, a management area set at the head of the page.
However, in the method of storing records in this way, in order to know the number of connected pages, it is necessary to read the pages from the secondary storage device to the main storage device one by one. Therefore,
In order to perform parallel processing, it is necessary to check the number of linked pages and continuously read the records of uncompleted pages as in the program shown in FIG. 8 described above. Even if the number of processors is increased, the processing time can be shortened considerably. There was a problem that I could not anticipate. In other words, there is a problem that the multiplicity of parallel processing cannot be increased because it takes time to process the number of linked pages.

The present invention has been made in consideration of such circumstances, and an object thereof is to selectively read a record including a non-concatenated page from a secondary storage device to a main storage device of a plurality of processors. A highly practical record storage method that can speed up the processing for checking the number of concatenated pages for each page and increase the multiplicity of parallel processing using multiple processors to reduce the overall processing time To provide.

[Structure of the Invention] (Means for Solving the Problems) A record storage system according to the present invention includes a secondary storage device and a plurality of processors each having a main storage device, and is fixed in the secondary storage device. In a record storage system of a parallel processing device that selectively reads records of various sizes stored in units of long pages into the processor and processes them in parallel, one or a plurality of records that do not exceed the page length is the page. Collectively within the range of 1
Records that exceed the page length are divided into a plurality of consecutive pages, and the record storage means for storing the records in the secondary storage device, and each page when the record storage means stores the record Connected page number information storage means for storing information on the number of linked pages in a storage area set separately from the storage area for each page in the secondary storage device, and a record stored in the secondary storage device. When each of the plurality of processors reads out, each processor exclusively reads out the concatenated page number information stored by the concatenated page number information storing means into the main storage device of the processor, and the reading means reads And a read page determining means for determining the page to be read by the processor by referring to the linked page number information. It is characterized in that it has.

(Operation) According to the present invention, information on the number of linked pages for each page is stored in a storage area different from the storage area of the page, for example, in a secondary storage device or a main storage device of another processor. Therefore, when the records of various sizes stored in the secondary storage device in units of a fixed length page are selectively read out to one of the plurality of processors, another area in which the information about the number of linked pages is stored. To read the concatenated page number information exclusively to the main memory of the processor, determine the page to be read by the processor, for example, a plurality of pages in record units, and read the information. This eliminates the need to read the page from the secondary storage device to the main storage device each time in order to check the number of linked pages for each page as in the conventional case.

As a result, the processing for checking the number of linked pages is greatly simplified, and the processing speed can be increased.
It is possible to reduce the overall processing time.

(Embodiment) Hereinafter, a record storage method according to an embodiment of the present invention will be described with reference to the drawings.

This embodiment system includes a secondary storage device and a plurality of processors, and records of various sizes stored in the secondary storage device in units of pages of a certain length are stored in one of the plurality of processors. The present invention is applied to a parallel processing device configured to perform parallel processing by a plurality of processors while selectively reading.

In this embodiment, a page of a fixed length is used as a unit, and one or more records that do not exceed the page length are collectively stored in one page within the range that does not exceed the page length (complete page), and the page length is Store the records that exceed the limit by dividing them into multiple consecutive pages (incomplete page)
In this case, for example, as shown in the concept of FIG. 1, the information of the number of linked pages c for each page (completed page a and non-completed page b) is set in a file d set in another area in the secondary storage device. It is characterized in that it is stored in.

In FIG. 1, the first page is the completed page a and the second page is
Three consecutive pages from the fourth page to the fourth page are uncompleted pages b, and the fifth page is completed pages a. The shaded areas of each of the pages a and b indicate the unused areas on that page. Then, in the separate file d that stores the information of the number of linked pages for each page, in this example, the number of linked pages of [1,3,0,0,1, ...] Information is stored respectively. However, information on the number of linked pages [0]
Indicates that the page is linked to the previous page.

Thus, referring to the information on the number of linked pages stored in the separate file d in this way, the number of linked pages for each page is checked, and the record of each page a, b is selected as one of the processors. In order to read the data in parallel and perform parallel processing, it is necessary to read the contents of the separate file d into the main memory of each processor so that each processor can refer to the contents. That is, it is necessary to read the contents of the separate file d into the main storage device of each processor independently of reading the record in page units from the secondary storage device so that the information on the number of linked pages can be checked. Becomes

FIG. 3 shows an example of a program configured to include such a processing function, and each processor executes the program to read a record of a required page from the secondary storage device. .

Explaining the program shown in FIG. 3, here, a process is performed between wait (S) and signal (s) to check the number of linked pages to be processed.

If the page corresponding to another file d storing the information of the number of linked pages has already been read out to the main storage device, it is sufficient to refer to it. If not, a process of reading a page corresponding to another file d, which stores information on the number of linked pages related to the page, into the main storage device is performed.

However, in a normal case, the size of the page forming the recording unit of the record is generally set to about 4096 bytes. On the other hand, the area required to store the value of the number of linked pages for each page is generally about 2 bytes per page. When the information on the number of linked pages from the separate file d is read once for each page, the information on the number of linked pages for 2048 pages is obtained. Then, as long as the information on the number of linked pages within the range indicated by the read page is referenced, it is not necessary to newly read the information on the number of linked pages from the separate file d.

From the above, in the case of the program shown in FIG. 3 in this embodiment, information on the number of linked pages is sent from the secondary storage device to the main storage device between wait (S) and signal (s). The frequency of processing for reading is stochastic.
Once every 2048 times, in other cases, the number of linked pages for the page to be read is checked using the information of the number of linked pages shown in the already read file.

This is because in the program of FIG. 8 showing the conventional processing method, reading from the secondary storage device to the main storage device is required every time between wait (S) and signal (s). This means that the frequency of the read processing is greatly reduced, and the processing performance is greatly improved. And
The processing speed between wait (S) and signal (s) can be increased, and the overall processing time can be shortened.

In the above-described embodiment, the number of linked pages for each page is stored in another file d, but it may be stored in another location.

For example, the file for storing the original record is formed into a tree shape as illustrated in FIG. 2, and the actual record is stored in the page x at the right end in the figure. Then, information on the storage location in the secondary storage device and the number of linked pages for each rightmost page x may be stored in the page y on the left of the first row. In this case, when checking the number of linked pages for each page, it is not necessary to read the data for each page x from the secondary storage device to the main storage device, and the data stored for the page y is stored. Since it is only necessary to refer to, it is possible to achieve significant performance improvement.

As another example, it is possible to store the information on the number of linked pages in the main storage devices of a plurality of processors separately from the secondary storage device. That is,
The area required to store the value of the normal number of linked pages is 2
The size of the original page is about 4096 bytes as described above. Therefore, the information on the number of connected pages is about [1/2048] of the original file size,
There is almost no problem even if the information on the number of linked pages is stored in the main storage device.

If most of the pages are complete pages and only a very small number of pages are non-complete pages, instead of storing the number of linked pages for each page, each page is a complete page. It is also possible to retain only the information of whether or not it is separate from the original page. By doing so, the storage area can be made extremely small. In such a case, for example, a program as shown in FIG. 4 may be executed. According to such a program, the average value of the time required for the processing between wait (S) and signal (S) can be made significantly smaller than that of the conventional method, and the processing performance can be sufficiently improved. It is possible to raise it. In addition, the present invention can be variously modified and implemented without departing from the scope of the invention.

[Effects of the Invention] As described above, according to the present invention, in a parallel processing device including a secondary storage device and a plurality of processors, information on the number of linked pages for each page is stored in an area different from that of the original page. Since the reading of the record is controlled by storing it in the database, the process of "fetching the record stored in the secondary storage device satisfying a certain search condition" which is the most basic process in the database is executed. In doing so, even when a record exceeding the page length is included, it is possible to achieve a great practical effect such as improvement in processing performance commensurate with the number of processors.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a diagram schematically showing the concept of a record storage system according to an embodiment of the present invention, and FIG. 2 is a tree-like record storage form showing another embodiment of the present invention. The figure which shows typically, 3rd
FIG. 4 and FIG. 4 are diagrams showing an example of a processing program in the processor for realizing the embodiment system. Further, FIG. 5 is a diagram showing an example of a completed page stored in the secondary storage device, FIG. 6 is a diagram showing an example of a non-completed page stored in the secondary storage device, and FIG. 7 is a parallel to the completed page. FIG. 8 is a diagram showing an example of a program, and FIG. 8 is a diagram showing an example of a parallel program including a non-completed page. a: Completed page, b: Non-completed page, c: Number of linked pages, d: Separate file.

Claims (1)

[Claims] 1. A processor, comprising: a secondary storage device; and a plurality of processors each having a main storage device, wherein the secondary storage device stores records of various sizes stored in units of pages of a certain length. In a record storage method of a parallel processing device that selectively reads and parallel-processes data, one or more records that do not exceed the page length are grouped as one page within the range that does not exceed the page length. Is divided into a plurality of continuous pages and stores the record in the secondary storage device, and when the record storage stores the record, information on the number of linked pages for each page A concatenated page number information storage unit for storing in a storage area set separately from the storage area for each page in the secondary storage device; When each of the plurality of processors reads a record stored in the storage device, each processor exclusively reads the concatenated page number information stored by the concatenated page number information storage device into the main storage device of the processor. And a read page determining unit that determines a page to be read by the processor with reference to the number of linked pages read by the reading unit.