JPH0516608B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field The present invention relates to an information retrieval device that extracts a plurality of pieces of corresponding information for one access to an external storage device or the like in a limit value extraction control method for electronic equipment.

Prior Art Conventionally, in an information retrieval device using a magnetic disk or the like that stores a large amount of information, when an operator obtains requested information, the control device of the magnetic disk device is asked to identify the characteristics (or "KEY") of the desired information. Generally, the information in the magnetic disk device is transferred to the main storage device in the control device, and after access to the magnetic disk device is completed, the information in the magnetic disk device is accessed. The information in the main memory is searched based on the characteristics described above. Therefore, it is necessary to once store unnecessary information in the main memory to obtain the requested information, and it is necessary to access the magnetic disk device and search for information in the main memory.
There is a drawback that a large capacity of the main storage device is required.

Another method is to perform processing within the access time to the magnetic disk device and obtain the relevant information in real time. This method compares the information read from the magnetic disk drive with the characteristics of the information described above in real time while the magnetic disk drive is being accessed, so that the comparison result is synchronized with the data read from the magnetic disk. However, in local minimum value and local maximum value searches, it is difficult to extract multiple items from the information obtained in one access to the magnetic disk device, and it is difficult to realize this. This required a complex hardware configuration and space.

Purpose The present invention was created in view of the drawbacks of the information retrieval method that processes in real time as described above, and is an information retrieval method that has a simple hardware configuration, is fast, and is extremely effective for local minimum and maximum value searches (sorting). The purpose is to provide equipment.

Embodiment An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram of an information retrieval device implementing the present invention.

1 is an external storage device under the control of this information retrieval device. Reference numeral 2 denotes an interface A for controlling, transmitting and receiving data and clocks of the external storage device 1 mentioned above. 3 is an interface B for transmitting and receiving the address of the external storage device 1 and return information from the external storage device 1; 4 is a control unit that controls the above-mentioned 1, 2, 3 and the entire information retrieval device of the present invention.
M.C.T. 5 switches the internal bus line, which will be described later.
A three-state gate that also controls the direction of data according to instructions from the control unit MCT4. 6 is a memory JM that temporarily stores information instructing how to search for search information.
Reference numeral 7 denotes a memory Q1 that stores initial values of search information. Memory Q2 (8) and memory Q3 (9) are memory JM
6. According to the contents of memory Q1 (7), the searched data extracted from the external storage device 1 is temporarily stored, or the temporarily stored searched data is stored in the second or third
This is a search register that also serves as a buffer memory and serves as a search data storage memory for searching extracted data. 10 is from external storage device 1 to interface A
2 and memory Q1
(7) A comparator that compares the data read from
CM1.11 and 12 are read data and memory Q2 (8) or memory Q3 like CM1 (10) above.
(9) Comparator to compare data read from
CM2 or CM3.13 is memory JM6, memory Q1
(7) A length counter (L/C) for controlling the address of memory Q2 (8) and memory Q3 (9) and the length of the searched data. 14 is CM1 (10), CM2 (1
1), manages the logic control of each comparator output of CM3 (12), controls the operation of LC13, and sends predetermined control information to the corresponding record and address storage memory ADM16 and the corresponding record status storage memory STM17, which will be described later. Search logic circuit control section
I.R.C.T. 15 is a record address counter RADC which counts the break of searched data according to the output information of the MCT 4, holds it as an address for each set of data (record), and sends it to the ADM 16 according to instructions from the IRCT 14; 16, as mentioned above, the contents of RADC16, IRCT14
A memory ADM that temporarily stores record addresses according to instructions from the ADM. 17 is a memory that stores the state of the searched data (presence or absence of a match, information on the presence or absence of multiple matches indicating that the same data previously existed, etc.);
STM. 18 is a bus interface BIF for connecting the information retrieval device of the present invention and higher-level devices, etc.; 19
MBUS is a high-speed bus line through which raw information from the external storage device 1 mentioned above is exchanged. 20 is an SBUS through which the status of each memory, counter values, and information to the BIF 18 are exchanged under the control of the MCT4. 21 is a communication means LBUS between this information retrieval device and a host device, and an arbitrary communication means can be constructed using the BIF 18.

Next, the principle of operation of an information retrieval device according to a preferred embodiment of the present invention will be explained in detail with reference to the drawings.

FIG. 2 is an operational flowchart of the present invention.
Via the LBUS 21 in FIG. 1, instructions are sent to the information processing apparatus in a predetermined format, and the address of the external storage device 1 storing the searched data to be searched or the file name of each file is stored in the host device. The sent information is decoded by the control unit (MCT) 4, and control, etc. to the external storage device 1 is executed via each search register and interface B3, and the search process is started. When predetermined initial values are set in search registers JM and Q1 (steps 100 and 101), external storage device 1
enters a data read cycle (step
102). There is a waiting time until the external storage device 1 reaches the address to be searched, and when the search instruction address is reached (step 103-Y), the MCT
4, a search start command is sent to LC13 and RADC15 (step 104), and in synchronization with the read speed of external storage device 1, according to the contents of JM6, Q1 (7) is sent.
A comparison is performed between the read data of the external storage device 1 and the read data of the external storage device 1 outputted on the MBUS 19 via the interface A2 (step 105). This comparison uses the first and second half of one clock cycle to compare the upper limit value (or lower limit value) and binary information, which is the initial value of the lower limit value (or upper limit value), with respect to the searched data.
It is determined whether the searched data is included in the initially set values. Next, if it is determined that "Q1 is applicable", it is selected whether the data is the first priority data (step 106). If the data is not in the first priority order, then it is selected whether the data is in the second priority order (step 107).

The conditions to be selected as the first priority are: (1) When the first match is found within the specified search range.

(2) From the corresponding data stored in Q2 and Q3,
If it is closer to the limit value.

The conditions to be selected as the second priority are as follows: (1) Within the specified search range, the second position is found and the corresponding data is further from the limit value than the first position, or If it is equal to the corresponding data of the eye.

(2) When the first priority and second priority data stored in Q2 and Q3 are closer to the extreme value than the existing first priority data and closer to the extreme value than the existing second priority data (this If the data is determined to be the first priority data (step 106-Y), Q2 (8) and Q3 (9) A flag indicating whether the data stored in the FSDB has the same content;
If ≠1 (if not the same content), it is the first applicable data from the start of the search, or Q2 (8) and Q3
Data with a higher priority than any of the data stored in (9) is input as the searched data, and the new data with the second priority does not have the same data. Therefore, it is determined whether the FDBL flag indicating that there was searched data that is the same as the second priority data in the past has been set (step 113), and if it has been set, it is reset (step 113). 114). After that, in order to make the searched data stored in the work area the first priority data, the value of the record address counter where the searched data was recorded is stored in memory.
In addition to setting ADM (step 111), Q2
(8), the work area where the searched data in Q3(9) is stored is the search data area, and Q2(8),
Data that is farther than the limit value in Q3 (9) is deleted, and the data storage location becomes a new work area (step 112).

Also, if FSDB = 1, the already applicable data stored in Q2 (8) and Q3 (9) are equally searched data, that is, the first priority data, which is closer to the limit value than the already applicable data, so one of the already applicable data must be deleted, but the FDBL flag is set to indicate that data equal to the existing applicable data existed in the past (step 109), and the FSDB flag is then reset to indicate that the existing applicable data is the same (step 109). Step 110).

Then, in the same way as when FSDB=1 mentioned above, the value of the record address counter is set in the memory ADM, and the previous applicable data that is later in time (referring to the existing applicable data that is near the end of the address within the search instruction range) is deleted ( Step 111), Q2 or Q3 mentioned above
The deleted data area is secured as a work area for the next record (step 112).

Next, if it is determined that it is not the first priority (step 106-N), it is determined whether the above-mentioned conditions for the second priority are satisfied (step 107), and the
When it is determined that the second priority data is equal to the first priority data (step 115), if they are equal, Q2 (8) and Q3 (9) are performed.
This means that the data stored in the registers are equal, and when the corresponding data interrupts as the first priority data as described above, the flag for setting the FDBL, FSDB (already present in Q2 and Q3) is set. ) (indicates that the corresponding data are equal) (step 116), and stores the value of the record address counter in memory.
ADM (step 111), the area where second-priority data was previously stored is set as a new work area, and the area where the searched data was stored is used to search for new second-priority data. data (step 112).

In addition, if the second priority data is different from the first priority data, for example in a descending sort process, if the first priority data < the second priority data, it is processed as normal matching data,
Does not involve setting or resetting special flags. That is, the record address is set in the memory ADM (step 111), and the deleted data area is secured as a new work area (step 111).
112).

If it is determined in step 107 that the data is not the second priority data, it is determined whether the data is equal to the second priority data (step 117), and if they are equal, Q2 (8) and Q3 (9) are determined. ) indicates that the same data as the corresponding data stored in ) exists.
Set the FDBL flag (step 118). After that, it will be treated as “not applicable” (step
119).

Next, using FIG. 3, the actual data storage state and comparison state will be explained along the flow of time. Third
The figure shows the flow of data when arbitrary numerical information is sorted in descending order from 50 to 125, and Q1 (7), Q2
(8), represents the data storage state and record address storage state of Q3 (9). In the figure, time flows from T0 to T1, T2...Tn, the data to be searched is read output from the external storage device of the disk device, and records N0, R0, and R0 are distinguished from each other.
There is R1...Rn. Q1 (7) stores the limit value, lower limit and upper limit for sorting, and the comparator 7 in FIG. 1 checks whether the data to be searched is included in the desired values. In other words, it is step 105 of the flowchart, and since 50<123<125 at T0, R0=123 is determined to be "applicable", and Q2 (8)
is stored in the work area W of. 50 in Q1 in T1
<99<125 and similarly R1=99 is "applicable"
It is determined that 99<123 holds true in Q2(8), so
R1=99 is the first priority data and R0=123
becomes the second priority data. Each corresponding record address is shown in the storage state of record addresses in FIG. 3, with the top one representing the first priority and the bottom one representing the second priority. In T2, 50 < 105 < 125 in Q1, so it is "applicable", but in Q2 and Q3, 99 < 105 <
Since 123 holds true, R0=123, which has been the second priority, is deleted. The record address also stores R1 and R2. In T3, the condition of Q1 is T
2 is similar, but in Q2 and Q3, 99=99<105, R2=105 is deleted, and the first and second priority data are equal, so FSDB is set. In T4
Conditions in Q1 are satisfied, but conditions in Q2 and Q3 are 99
=99<102, and the data in R4 has a low priority, so it is determined as "not applicable". In T5, Q1 is "applicable" in Q2, and in Q3, 91<99=99 holds, so it becomes the first priority data, and R3=99 is deleted. Since R3=99 and R1=99 are equal, as mentioned above
Since FSDB=1 and first priority data has newly appeared, FDBL is set, FSDB is reset, and it is possible to know the existence of equivalent data other than the data stored in the register. Q1 at T6
The condition is satisfied, but in Q2 and Q3, 91<R6≦=99 does not hold because R6=100, so it is "not applicable".In T7, the condition of Q1 is satisfied, but in Q2 and Q3, R7
(85) Since <91<99 holds true, the first priority data is R7=85, the second priority is R5=91, and R1=99 is deleted. Yotsute Q2,
Since (99) disappears in Q3, FDBL is reset.

Record address is stored in each record memory ADM
However, if it is determined that it is applicable,
The ADM that is stored in the ADM by adding matching information to the beginning of the record address has an n-stage stack structure.
As mentioned above, by checking the data of
It is possible to extract multiple records (searched data) with one sorting process and also know the addresses of the records. By physically bringing the size of Q2 and Q3 closer to the size of the external storage device, more data can be extracted at one time. In other words, information stored randomly in a disk device or the like (representing random order when numerically representing a magnitude relationship) can be rearranged in ascending order or ascending order by searching the disk once. The structure of the record address is shown in FIG. Further, FIG. 5 shows the relationship between each register and the data to be searched. I ₁ , I ₂
... _I5 represents an item within each record (RN, RN+1...). Each item is a unit of information that can be used as a key reference at the time of searching, and can be searched by conjunction of each item such as I ₁ , I ₂ , I ₃ , and logical OR search starting from I ₁ + I ₂ + I ₃ . It is.

Effects As described above, according to the present invention, a plurality of pieces of relevant information can be obtained with one access to a large-capacity external storage device such as a magnetic disk device, thereby improving the performance of an information retrieval device using a magnetic disk device or the like. An information retrieval device that also functions as a disk cache, can be expected to perform high-speed processing, and contributes to improving the throughput of a processing system is realized. Furthermore, the present invention can be applied to various uses as hardware for database machines, which have been attracting attention in recent years.

Further, according to the present invention, the data is sequentially read out one by one from the storage means of the younger brother 1 which is addressed to store the data to be searched, and is stored in the designated position of the second storage means, and this readout data is The read data is compared with each of the previously stored ranked data, and as a result of this comparison, if there is one or more data with a lower rank than the read data, the Specify the storage location of the lowest ranked data as the storage location of the search target data to be read next,
By changing the ranking and also having a configuration in which the addresses of the stored data in the first storage means are stored in the address storage means, when the process goes through all the data to be searched, the data is sorted in the order of the highest ranking. It is possible to provide an information search device that can rank and search a plurality of pieces of data (n pieces).

Therefore, for example, when all data is sorted using this method, the processing time is reduced to 1/n compared to the conventional method in which only one piece of data can be retrieved every time all data are passed around.

In addition, storage processing is performed in the same way regardless of whether the read data has a higher rank than the previously stored data. Since it can be used for subsequent comparison processing without moving the storage location, high-speed processing can be achieved.

Furthermore, since the address in the memory that stores all the data obtained by the search is also obtained, further information is stored in each address of this memory using the search target data as a key, and the order of this key is An information retrieval device capable of sorting this information according to the following can be provided.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of this embodiment, FIG. 2 is an operation flowchart, FIG. 3 is a diagram showing the flow of data when performing sorting in ascending order, FIG. 4 is a diagram showing the structure of record addresses, and FIG. The figure is a diagram showing the correspondence between searched data and each register. In the figure, 1...external storage device, 2...interface A, 3...interface B, 4...
Control unit, 6...Memory JM, 7...Memory Q1, 8
...Memory Q2, 9...Memory Q3, 10...Comparator CM1, 11...Comparator CM2, 12...Comparator
CM3, 13...Length counter, 14...Search logic circuit control section, 15...Record address counter, 16...Memory ADM, 17...Memory
STM, 18... bus interface.

Claims (1)

[Claims] 1. A first storage means with an address for storing search target data; and for storing a plurality of predetermined pieces of data read from the first storage means and ranked. a second storage means having the predetermined number of storage locations; an address storage means for storing addresses of a plurality of data stored in the second storage means in accordance with the ranking according to the ranking; a reading means for sequentially reading out data one by one from the first storage means; and a reading means for reading data one by one from the first storage means;
storage control means for storing the data in a designated position among the predetermined storage positions of the second storage means; and storage control means for storing the data read by the reading means and a storage position other than the designated position in the second storage means. a comparison means for comparing the ranking with each of the data stored in the second storage means; If there is data with a lower rank than the read data, the storage position of the data with the lowest rank according to the ranking is set as a new specified position, the ranking is changed, and the data is stored according to the changed ranking. An information retrieval device comprising: control means for updating the contents of address storage means.