JPH0554082A - Data base system - Google Patents

Abstract

PURPOSE:To accelerate the retrieval processing of a data base. CONSTITUTION:A retrieval designation edit part 3 decides a retrieval method from a retrieval equation described on inquiry from a user and statistical information in accordance with a table and sequence in the retrieval equation. A squeeze rate calculation part 4 calculates a squeeze rate representing to what degree a retrieval instruction designated by a user can be squeezed at every retrieval method from the retrieval designation edit part 3. A retrieval cost calculation part 7 calculates a retrieval cost at every retrieval method based on the squeeze rate from the squeeze rate calculation part 4 and the statistical information read out from a statistical information storage file 6 by a statistical information input part 5. An access route decision part 8 compares the retrieval costs at every retrieval method calculated at the retrieval cost calculation part 7 with each other, and generates the retrieval method with the minimum retrieval cost as the information of access route.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a database system, and more particularly to a database system capable of searching and updating by designating only a part of columns in a table in which columns, which are the minimum unit of data, are assembled.

[0002]

2. Description of the Related Art Conventionally, a database system of this type has a storage structure in which a minimum unit of data input by a user is managed as a column and a concatenation of a plurality of columns is stored as a record in a storage device. There is. A set of columns stored in this storage device is provided to the user as a table, and the user can search and update by designating only a part of columns in the table. The search process is performed in the order specified by the user.

In such a conventional database system, since the retrieval processing for the columns stored in the storage device is performed in the order designated by the user, there is an order having a short retrieval time other than the order designated by the user. However, there is a problem that it cannot be used and the search time is wasted.

[0004]

SUMMARY OF THE INVENTION The present invention has been made in order to eliminate the above-mentioned problems of the prior art, and an object of the present invention is to provide a database system capable of accelerating a search process for a database.

[0005]

The database system according to the present invention comprises:
A database system for storing a plurality of data input by a user in units of columns as a record and performing a search and update by designating only a part of columns in a table composed of the set of records, wherein the user A narrowing-down rate calculating unit that calculates a narrowing-down rate that indicates how much the search instruction requested from can be expected to be narrowed down,
A search cost calculating means for calculating a search cost based on the narrowing rate calculated by the narrowing rate calculating means, and an access route for the search instruction based on the search cost calculated by the search cost calculating means And determining means.

[0006]

An embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. In the figure, when the database system 1 receives a database search instruction input from the user via the input / output device 9, it transfers control to the optimization level determination unit 2. The optimization level determination unit 2 determines to which level the user has set the optimization level, and the determination result is used as a search designation editing unit 3, a narrowing rate calculation unit 4, a search cost calculation unit 7, and an access route determination unit 8. And output them respectively and call them.

Here, the user can set any of FULL optimization, HALF optimization, and NONE optimization for the optimization level determining unit 2. When FULL optimization is set, the search method is determined using all of the statistical information and knowledge base. When HALF optimization is set, the search method is determined using the statistical information and part of the knowledge base. When NONE optimization is set, the search method is decided without using the statistical information and knowledge base.

The search designation editing unit 3 determines a search method from the search formula described in the inquiry from the user and the statistical information corresponding to the tables and columns in the search formula, and the search method is narrowed down to a narrowing rate calculation unit. Send to 4. In this case, since there is no case where there is only one search method for one search request from the user, a plurality of search methods are determined.

For example, "column 1> = 10 AND column 1 <
= 50 ”is described, if
A method of taking a logical product of the search result of “column 1> = 10” and the search result of “column 1 <= 50”, and “column 1> = 10 A
ND column 1 <= 50 "in the BETWEEN predicate" column 1 "
There will be two types of search methods, the method of searching with "BETWEEN 10 AND 50".

If the search expression "column 1 IN (1,2,3)" is written, "column 1 IN (1,2,3)" is written.
(1,2,3) "search method," Column 1 IN
A method of taking the logical sum of the search result of (1, 2) and the search result of “column 1 = 3”, and the search result of “column 1 = 1” and “column 1 =”
There are three types of search methods, namely, a method of taking the logical sum of the search result of "2" and the search result of "column 1 = 3".

When the optimization level determination unit 2 calls the narrowing-down rate calculating unit 4, the narrowing-down rate indicating the rate at which the search instruction designated by the user can be expected to be narrowed down is designated by the search designation editing unit 3. Calculate for each search method from.

That is, the narrowing-down rate calculating unit 4 first determines whether the search expression described in the inquiry from the user is a logical condition,
Alternatively, it is determined whether it is a scalar operation. Narrowing rate calculation unit 4
Determines that the search expression is a scalar operation, the statistical information input unit 5
To read the statistical information corresponding to the table or column from the statistical information storage file 6. After that, the narrowing-down rate calculating unit 4 calculates the narrowing-down rate for each search method based on the statistical information read from the statistical information storage file 6, and sends the narrowing-down rate to the search cost calculating unit 7.

Here, for example, in order to search the table A composed of columns 1 to 4, the search formula "column 1> = 10 AND column 1"
<= 50 ”is given,“ Column 1 has no duplicate data,
The total number of records in column 1 is 200, the average value between the values in column 1 is 2.0, and the number of records in one work area when reading the records in table A is 50 records. " If it is obtained, it is shown in the BETWEEN predicate "column 1 BETWEE
In the case of the method of searching by "N 10 AND 50", the narrowing rate = [(50-10) / 2] /200=0.1. On the other hand, in the case of the method of taking the logical product of the search result of “column 1> = 10” and the search result of “column 1 <= 50”, the narrowing rate = [(10/1) / 200] + [( 50 /
1) / 200] + α 2 = 0.05 + 0.25 + α 2 = 0.3 + α. Note that [(10/1) / 200] is “column 1> = 1”
It is the narrowing down ratio when searching for "0", which is [(50 /
1) / 200] is a narrowing down ratio when searching for “column 1 <= 50”, and α is a narrowing down ratio when performing a logical product of those search results.

Therefore, "column 1 BE" shown in the BETWEEN predicate
The narrowing-down rate of the search method using "TWEEN 10 AND 50" is "column 1> = 10" and "column 1 <= 50".
This is smaller than the narrowing rate of the method of taking the logical product with the search result of.

The search cost calculation section 7 is a narrowing rate calculation section 4
The search cost is calculated for each search method on the basis of the narrowing-down rate and the statistical information read by the statistical information input unit 5 from the statistical information storage file 6, and the search cost for each search method is sent to the access route determination unit 8. Send out. Here, the search cost is the input / output cost associated with the file input / output by one search request from the user, and the larger the search cost value, the longer it takes to access the database (not shown). It will be.

For example, assuming that the number of records handled in one file input / output is 10, the search cost = (total number of records) in the method of searching by "column 1 BETWEEN 10 AND 50" shown in the BETWEEN predicate described above. × Narrowing down rate) / the number of records of one file input / output = (200 × 0.1) / 10 10 = 2.0. On the other hand, in the case of the method of taking the logical product of the search result of “column 1> = 10” and the search result of “column 1 <= 50”, search cost = [200 × (0.3 + α)] / 10 = It becomes 6.0 + 20α. Therefore, "column 1 BETWEE" shown in the BETWEEN predicate
The search cost of the method of searching with "N 10 AND 50" is smaller than the search cost of the method of logically ANDing the search result of "column 1> = 10" and the search result of "column 1 <= 50". ..

The access route determining unit 8 compares the search costs for each search method calculated by the search cost calculating unit 7 and uses the search method with the smallest search cost as access route information via the optimization level determining unit 2. To the database system 1.

For example, as described above, "column 1> = 10 AN"
When the search expression "D column 1 <= 50" is described, "column 1" shown in the BETWEEN predicate with a low search cost
BETWEEN 10 AND 50 ”will be used as the access route information.

FIG. 2 is a flow chart showing the operation of the optimization level determining unit 2 in FIG. 1, FIG. 3 is a flow chart showing the operation of the search designation editing unit 3 in FIG. 1, and FIG.
6 is a flowchart showing the operation of the narrowing-down rate calculation unit 4, FIG. 5 is a flowchart showing the operation of the statistical information input unit 5 of FIG. 1, and FIG. 6 is a flowchart showing the operation of the search cost calculation unit 7 of FIG. Yes, FIG. 7 is a flowchart showing the operation of the access route determination unit 8 of FIG. The operation of the embodiment of the present invention will be described with reference to FIGS.

When the database search instruction is input from the user via the input / output device 9, the database system 1 transfers control to the optimization level determining unit 2. The optimization level determination unit 2 first determines to which level the user has set the optimization level, that is, whether to use the statistical information (step 11 in FIG. 2). When the optimization level determining unit 2 determines to use the statistical information, it calls the narrowing rate calculating unit 4, the search cost calculating unit 7, the search designation editing unit 3, and the access route determining unit 8 in order (steps 11 to 11 in FIG. 2). 1
5).

On the other hand, when it is determined that the statistical information is not used, the optimization level determining unit 2 determines whether to use a knowledge base (not shown) (step 16 in FIG. 2). Here, the knowledge base stores the experience and knowledge accumulated in the development of a relational database over many years.

When the optimization level determining unit 2 determines to use the knowledge base, it calls the search designation editing unit 3 and the access route determining unit 8 in order (steps 14 and 1 in FIG. 2).
5). If the optimization level determining unit 2 determines not to use the knowledge base, it calls the access route determining unit 8 (step 15 in FIG. 2).

The search designation editing unit 3 is an optimization level determining unit 2
Is called from, it is determined whether all the scalar conditions in the search expression described in the inquiry from the user are connected by equal signs (step 21 in FIG. 3). When the search specification editing unit 3 determines that all scalar conditions are connected by equal signs in the search expression, it determines whether all logical conditions are connected by AND (logical product) (step 22 in FIG. 3).

When the search specification editing unit 3 determines that all logical conditions are connected by AND in the search expression, it determines whether the type of the table described in the search expression is single (FIG. 3).
Step 23). When the search specification editing unit 3 determines that the type of the table described in the search expression is single, it determines whether or not an index (index) applicable to evaluate the search expression is added (step 24 in FIG. 3). ). Search specification editorial department 3
When it is determined that the index is added, the search method of the search formula is set to index search, and the search method is sent to the narrowing rate calculation unit 4 (step 25 in FIG. 3).

On the other hand, when the search designation editing unit 3 determines in step 21 that all the scalar conditions are not connected by equal signs, or in step 22 that all the logical conditions are not connected by AND, the search expression It is determined whether there are a plurality of types of tables described in (2) (step 26 in FIG. 3).
When the search designation editing unit 3 determines that there are a plurality of types of tables described in the search formula, or when it determines that the type of table described in the search formula is not single in step 23, the search of the search formula is performed. The method is a nested loop connection search, and the search method is sent to the narrowing rate calculation unit 4 (step 27 in FIG. 3).

Here, the nested loop join search is performed by sequentially determining search conditions in the first record of the join source and the records from the first record to the last record of the join destination, and after the decision is completed, the join source The search condition is sequentially determined for the next record and the records from the first record to the last record to be combined. This is a method of performing a search by repeatedly making such a determination.

Further, when the search designation editing unit 3 determines in step 24 that the index is not added, or in step 26 that the number of types of tables described in the search formula is not plural, the search formula is searched. The method is a sequential search, and the search method is sent to the narrowing rate calculation unit 4 (step 28 in FIG. 3).

When called by the optimization level determining unit 2, the narrowing rate calculating unit 4 sequentially extracts the search formulas described in the inquiry from the user (step 31 in FIG. 4).
It is determined whether the extracted search expression is a logical condition (step 32 in FIG. 4).

When the narrowing-down rate calculating unit 4 determines that the search expression is a logical condition, the narrowing-down rate is calculated by designating the search expressions on both sides described in the search expression (step 33 in FIG. 4).
After that, the narrowing-down rate calculating unit 4 determines whether or not the search formula still remains (step 34 in FIG. 4). If the search formula still remains, the process returns to step 33 to calculate the narrowing rate, and if the search formula does not remain, the control is returned to the optimization level determination unit 2.

On the other hand, when the narrowing-down rate calculating unit 4 determines that the search expression is not a logical condition, it determines whether the search expression is a scalar operation (step 35 in FIG. 4). Narrowing rate calculation unit 4
Determines that the search expression is a scalar operation, calls the statistical information input unit 5 by specifying the tables and columns described on both sides of the scalar operation, and reads the statistical information corresponding to the table or column from the statistical information storage file 6. (FIG. 4, step 36).

After that, the narrowing-down rate calculating unit 4 calculates the narrowing-down rate for each search method based on the statistical information read from the statistical information storage file 6, and then determines whether or not tables and columns still remain (FIG. 4 step 37). If the table or column still remains, the process returns to step 36 and the narrowing rate is calculated for each search method based on the statistical information read from the statistical information storage file 6, and if the table or column does not remain, the optimization level is determined. Return control to part 2. Here, the narrowing rate and the statistical information calculated by the above processing are sent to the search cost calculation unit 7.

When the statistical information input unit 5 is called by the narrowing-down rate calculating unit 4, it determines whether or not the data read from the statistical information storage file 6 is a table (FIG. 5, step 4).
1). When the statistical information input unit 5 determines that the data to be read is a table, it prepares to read the table data (step 42 in FIG. 5) and then reads the statistical information of the specified table from the statistical information storage file 6. (FIG. 5, step 43). The statistical information input unit 5 sends the read statistical information to the narrowing-down rate calculating unit 4, and then returns control to the narrowing-down rate calculating unit 4.

On the other hand, when the statistical information input unit 5 determines that the data to be read is not a table, it prepares to read the column data (step 44 in FIG. 5), and then the statistical information storage file 6
The statistical information of the designated column is read from (step 4 in FIG. 5).
5). The statistical information input unit 5 sends the read statistical information to the narrowing-down rate calculating unit 4, and then returns control to the narrowing-down rate calculating unit 4.

When the search cost calculation unit 7 is called by the optimization level determination unit 2, the search cost calculation unit 7 determines whether or not a table is used to calculate the search cost (step 51 in FIG. 6). When it is determined that the search cost is calculated for the table, the search cost calculation unit 7 calculates the search cost for the table for each search method based on the narrowing rate and the statistical information sent from the narrowing rate calculating unit 4 (FIG. 6). Step 52). When it is determined that the search cost is not calculated for the table, the search cost calculation unit 7 calculates the search cost for the column for each search method based on the narrowing rate and the statistical information sent from the narrowing rate calculating unit 4 ( 6 step 53). After the calculated search cost for the table or column for each search method is sent to the access route determination unit 8, the control is passed to the access route determination unit 8.

When the search cost calculation unit 7 receives the control, the access route determination unit 8 compares the search costs calculated by the search cost calculation unit 7 for each search method. That is, the search cost of the first search method is set as the search cost mi of the comparison source, and the search cost of the next search method is set as the search cost m (i + 1) of the comparison target. It is compared with m (i + 1) (step 61 in FIG. 7). As a result, the comparison source search cost mi is larger than the comparison target search cost m (i + 1) [m
i> m (i + 1)] is determined (step 6 in FIG. 7).
2).

If the comparison source search cost mi is larger than the comparison destination search cost m (i + 1), the comparison source search cost mi is set as the comparison source search cost mi. The search cost of the comparison destination is m (i + 1). That is, the search cost mi of the comparison source when 1 is added to i and the search cost m (i + 1) of the comparison target are compared (steps 62 and 63 in FIG. 7).

At this time, it is determined whether i exceeds the number n of search costs calculated by the search cost calculation unit 7 (step 65 in FIG. 7). If i exceeds the number n of search costs calculated by the search cost calculation unit 7, the search cost mi of the comparison source at that time is set to the search cost of the shortest access route, that is, the smallest search cost is set to the shortest access. The route search cost is determined (step 66 in FIG. 7). i
Does not exceed the number n of search costs calculated by the search cost calculation unit 7, the process returns to step 61 and the above processing is repeated.

Access route information is created from the search method corresponding to the search cost mi of the comparison source determined as the search cost of the shortest access route (step 67 in FIG. 7).
Information on the access route is sent to the database system 1 via the optimization level determination unit 2.

Next, for example, "exp.SELECT column 1, column 2, column 3 FROM table 1 WHERE (column 1> = 3) AND
When the search expression "(column 1 <= 55)" is input to the database system 1 via the input / output device 9, the WHERE
A search expression “(column 1> = 3) AND (column 1 <= 55)” described below is extracted. At this time,
If the user has set "FULL optimization", the statistical information and knowledge base are all used to determine the access route.

The search specification editing unit 3 calculates the logical product of the search result of "column 1> = 3" and the search result of "column 1 <= 55" from the above search formula, and "column 1> = 3". AND column 1 <
= 55 ”in the BETWEEN predicate,“ Column 1 BETWEEN 3
AND 55 ”and two types of search methods are determined and sent to the narrowing rate calculation unit 4.

The narrowing-down rate calculating unit 4 uses the statistical information input unit 5 to read from the statistical information storage file 6 that "column 1 has no duplicate data, the total number of cases in column 1 is 200, and the average value between the values in column 1 is the average value. Is 2.0 and the number of records in one work area when reading the records in Table A is 50 records ", the search method from the search designation editing unit 3 is based on these statistical information. The narrowing rate is calculated for each.

That is, "column 1" shown in the BETWEEN predicate
In the case of the method of searching with "BETWEEN 3 AND 55", the narrowing rate is [(55-3) / 2] /200=0.13.

On the other hand, in the case of the method of taking the logical product of the search result of “column 1> = 3” and the search result of “column 1 <= 55”, the narrowing rate = [(3/1) / 200] + [(55/1)
/ 200] + α = 0.015 + 0.275 + α = 0.29 + α.

The search cost calculation unit 7 is the narrowing rate calculation unit 4
The search cost is calculated for each search method on the basis of the narrowing-down rate and the statistical information read from the statistical information storage file 6, and the search cost for each search method is sent to the access route determination unit 8.

For example, assuming that the number of records handled in one file input / output is 10, the search cost = (200 × 0) in the case of the method of searching by “column 1 BETWEEN 3 AND 55” shown in the above BETWEEN predicate. .13) ÷ 10 = 2.6. On the other hand, in the case of the method of taking the logical product of the search result of “column 1> = 3” and the search result of “column 1 <= 55”, search cost = [200 × (0.29 + α)] / 10 =
It becomes 5.8 + 20α.

The access route determination unit 8 compares the search costs calculated by the search cost calculation unit 7 for each search method, and creates the search method with the smallest search cost as access route information. In this case, the search cost of the method of searching by "column 1 BETWEEN 3 AND 55" indicated by the BETWEEN predicate is "column 1> = 3" and "column 1 <
= 55 ”, the access cost is less than the search cost of the method of taking the logical product with the search result.
The method of searching with "column 1 BETWEEN 3 AND 55" shown in the predicate is created as access route information.

As described above, the narrowing-down rate calculating section 4 calculates the narrowing-down rate for each searching method determined by the search-designating and editing section 3, and the searching method calculated by the search-cost calculating section 7 based on the narrowing-down rate. In the search request from the user to the database, the access route determination unit 8 detects the search method with the smallest search cost among the search costs for each and creates the search method as the information of the access route. Since the access route having a high processing speed can be determined without changing the execution result, the search processing for the database can be speeded up.

Further, by enabling the user to set the optimization level, even if the user does not have knowledge of the search method, the fastest search method can be used by using the knowledge base and the statistical information. Therefore, the search processing can be speeded up.

[0050]

As described above, according to the present invention, it is possible to determine at what rate the search instructions calculated for each search method determined from the search formula and requested by the user can be narrowed down. An effect that the search process for the database can be sped up by calculating the search cost based on the narrowing-down ratio shown and determining the search method corresponding to the smallest search cost as the access route for the search instruction. There is.

[Brief description of drawings]

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

FIG. 2 is a flowchart showing an operation of an optimization level determining unit in FIG.

FIG. 3 is a flowchart showing an operation of a search designation editing unit in FIG.

FIG. 4 is a flowchart showing an operation of a narrowing-down rate calculating unit in FIG.

5 is a flowchart showing the operation of the statistical information input unit of FIG.

FIG. 6 is a flowchart showing an operation of a search cost calculation unit in FIG.

FIG. 7 is a flowchart showing the operation of the access route determination unit of FIG.

[Explanation of symbols]

 1 database system 2 optimization level determination unit 3 search specification editing unit 4 narrowing rate calculation unit 5 statistical information input unit 7 search cost calculation unit 8 access route determination unit

Claims (3)

[Claims] 1. A database system in which a plurality of data input by a user in units of columns are stored as records, and only a part of columns is specified in a table composed of a set of the records to perform search and update. Based on the narrowing-down rate calculated by the narrowing-down rate calculating means and a narrowing-down rate calculating means for calculating a narrowing-down rate indicating how much the search instruction requested by the user can be expected to be narrowed down. A database system comprising: a search cost calculating means for calculating a search cost according to the above; and a determining means for determining an access route for the search instruction based on the search cost calculated by the search cost calculating means. 2. A knowledge base for storing expertise of a search method in the table, an extracting means for extracting a search method for a search instruction requested by the user based on the knowledge base, and the extracting means. The database system according to claim 1, further comprising means for controlling to calculate the narrowing-down rate and the search cost of each of the extracted search methods. 3. A selection means for selecting a method for determining the access route based on the user's instruction content, and the narrowing-down rate calculation means and the search cost calculation based on the determination method selected by the selection means. 3. The database system according to claim 1, further comprising means for controlling the means and the determining means, respectively.