JP2525947B2 - Global index processing method - Google Patents

Description

DETAILED DESCRIPTION [Outline] A function of storing a table of logical structure representation or a set of data units consisting of a part thereof in association with a plurality of structured data storage units having independent data organizations is stored. Concerning the global index processing method in the database management system that it has, it aims to provide a means that enables high-speed retrieval of data that has been divided and stored. A dictionary that manages information about spanned subsidiary indexes as global index information, and for queries, evaluates the cost of access using the global index based on the dictionary registration information and other access, and the access by the global index When cost is low In this case, an optimization processing unit that generates an access procedure that uses the global index is configured.

[Industrial applications]

The present invention relates to a global in a database management system having a function of storing a set of data units consisting of a table of logical structure representation or a part thereof in association with a plurality of storage units of structured data having independent data organizations. Regarding the index processing method.

From the viewpoint of performance and operation, it is necessary for the data in the database to be able to set the optimal storage structure for the user in consideration of the processing form and access frequency. Therefore, it is considered that divided storage can be flexibly performed with respect to a logical structure and a data organization suitable for a data processing form can be designated for each storage unit. For example, even if the data has the same logical structure, some data rarely undergoes random processing. Therefore, it is necessary to select Hash organization or Btree organization because random processing and forward processing are mixed. , This method is possible for a data unit consisting of a logical structure representation table or a part thereof.

In a database management system that can have such various storage structures, a means that can generate a more efficient access procedure is desired.

[Conventional technology]

FIG. 7 shows an example of divided storage of a database according to the prior art.

In a conventional relational database management system, redundant storage with independent data organization is realized by redundantly defining tables with the same logical structure. In the example of FIG. 7, tables T1, T2, T3 having the same logical structure
Is defined redundantly, and the table to which the record is to be allocated is determined according to the value of column A. Data D1, D2,
It realizes divided storage called D3.

At this time, the divided data can have independent data organization, but since the data organization information of the target data (base data) was not managed as an index, the secondary index is the individual data Can only be set for. That is, for the data D1, D2, D3 each having an independent data organization, for example, the secondary indexes IX-1, IX-2, IX-3 of column C can be set individually.

Note that, for example, the following references describe the basic data organization used in the database management system.

1) “The Ubiqutous B-Tree”, DOUGLAS COMER, ACM Com
puting Surveys Vol.11, NO.2.

2) “Dynamic Hashing Schemes”, RJENBODYPACM Comp
uting Surveys Vol.20, No.2.

[Problems to be Solved by the Invention]

Therefore, in the secondary key search process for the entire data, it is necessary to search by using the secondary index for each divided data. In particular, the sequential search by the secondary key has a problem that the search efficiency is poor. was there.

In the example of FIG. 7, when searching all the data of the tables T1, T2, T3 by the value of column C, the divided data
Secondary indexes IX-1, IX- provided for D1, D2, D3
2, IX-3 must be searched respectively.

By the way, the present inventors have realized a storage structure that is highly independent of the logical structure, and take an optimum data organization for a certain data unit in the logical structure representation from the relationship of the processing form and access frequency. The storage structure to be obtained can be set, and even if it is necessary to change the storage structure due to performance or operational reasons, the logical structure and application programs closely related to it should not be affected as much as possible. We are considering a mechanism for defining the storage structure that takes this into consideration.

With this storage structure definition method, data can be divided and stored without duplicate definition of tables with the same logical structure, and independent data organization can be defined for each divided data. However, when it is desired to perform a secondary key search for the entire divided data, the secondary index provided for each divided data must be searched for as in the example of FIG. 7 described above. Therefore, there remains a problem that the search efficiency deteriorates.

It is an object of the present invention to solve the above problems and to provide a means for enabling high-speed retrieval of data that is divided and stored.

[Means for solving the problem]

 FIG. 1 is an explanatory view of the principle of the present invention.

In FIG. 1, 10 is a database processing method equipped with a CPU and memory, 11 is a database inquiry,
12 is an optimization processing unit that determines the optimal access route to the database for the inquiry 11, 13 is an access procedure for obtaining the answer to the query 11, 14 is a dictionary that stores the definition information about the database, and 15 is a global index. Information, 16 is an access component library that stores information obtained by dividing access means for each data organization, 17 is an access component, 18 is a database, and 19 is a storage unit having an independent structure on a physical medium (CS: Composit Stru
cture), 20 is a global index that spans multiple storage units 19, 21 is the data unit of the logical structure representation and storage unit 1
A storage structure definition for defining correspondence information with 9, and 22 denotes a table which is one form of a data unit of a logical structure expression.

For example, as shown in FIG. 1 (b), a set of data units consisting of a table 22 which is a representation of a logical structure or a part thereof is defined by a storage structure definition 21 and an arbitrary number of storage units 19
Can be associated with. Each storage unit 19 that constitutes the database 18 has a data organization, and records are stored on the physical medium based on the storage logic.

In the present invention, it is possible to provide an index that spans a plurality of storage units 19 that may have different data organizations. The index described here is a secondary index that allows data to be accessed using a key (called a secondary key) that is independent of the storage logic based on the data organization in order to improve access efficiency. The index that spans the plurality of storage units 19 is the global index 20.

The dictionary 14 manages global index information 15 regarding definition information of the global index 20.

The optimization processing unit 12 responds to the inquiry 11 by using the global index 20 based on the registration information in the dictionary 14.
The cost evaluation of the access using and the other access is performed, and when the access by the global index 20 is low cost, the access procedure 13 using the global index 20 is generated.

In addition, in FIG. 1A, the access component library 16
An access component 17 for each data organization is prepared in advance, and an access procedure 13 can be generated by combining the access components 17. However, the access component 17 is not essential for implementing the present invention.

[Action]

In the present invention, a database structured by a plurality of data having different independent data organizations is equipped with an index function that spans the plurality of data. Therefore, the access route is diversified, and the efficiency of the secondary search is improved as compared with the case where there is only a secondary index (hereinafter referred to as a local index) individually prepared for each of these data. Depending on the nature of the data and the access status, the local index is unnecessary.

The storage structure definition 21 is, for example, (a) one table 22 or a part thereof is associated with one storage unit 19, (b) a plurality of sets of the table 22 or a part thereof is associated with one storage unit 19. , (C) One table 22 or a part thereof is associated with a plurality of storage units 19, or is defined by a combination of these (a) to (c).

〔Example〕

FIG. 2 is an explanatory diagram of an access procedure by the global index according to the embodiment of the present invention.

The global index 20 manages pointer information 31 corresponding to a corresponding key 33 of a storage unit 32 (which is referred to as a base CS) in a database corresponding to a secondary key 30. By adding information that can identify the data organization of the base CS32 to this pointer information 31, an index that spans different data organizations is realized.

The optimization processing unit 12 for the inquiry 11 shown in FIG. 1 generates an access procedure 13 considering different data organization. The access procedure 13 is a global index.
When using 20, the record 33 is accessed based on the secondary key 30 by the processing procedure as shown in FIG.

The processing by the access procedure 13 for accessing the base CS32 by the global index 20 is as shown in (a) to (c) below.

(A) The data organization of the base CS32 is detected from the pointer information 31 managed by the subsidiary key 30.

(B) Schedule the access component 17 of the data organization. The access component 17 is, for example, Btree, heap,
It is prepared in advance as a component to be incorporated into the access module according to the data organization such as hash.

(C) All pointer information 31 managed by the secondary key 30
With respect to the above, the processes (a) and (b) are performed, and the corresponding record 33 is accessed by using the access components 17 according to the data organization in combination.

In this embodiment, the global index 20 is also managed as one storage unit (CS), and as its metadata, the data organization and the identification information (CSi) of the base CS32 to be managed.
d) is managed by dictionary 14.
Regarding the actual data base CS32, the dictionary 14 manages information such as data organization as its metadata. The storage structure definition 21 registers these metadata in the dictionary 14.

The access procedure 13 using the global index 20 is
As described above, the optimization processing unit 12 generates using the metadata of the global index 20 managed as CS and the metadata of the base CS32.

When the search by the global index 20 is executed, for each base CS32 managed by the sub key 30, the access component 17 that constitutes the access procedure of each CS is scheduled based on the base CS information and the storage key, The corresponding record 33 is retrieved.

FIG. 3 shows the structure of the lowest record of the global index 20 according to the embodiment of the present invention.

At the beginning of this global index record 40,
A record header exists, and record management information such as the number of base CS pointers managed by the secondary key is set in the record header. Same base
There may be multiple storage keys for CS.

Fig. 4 (a) shows an example of global index 20 for CS in the table, and Fig. 4 (b) shows CS between tables.
Here is an example of a global index 20 for.

In the example shown in FIG. 4A, the storage unit is divided as follows according to the value of the column A in the table T.

(A) When the value of A is 0 or more and less than 100 The storage unit is CS1 and its data organization is Btree organization with the value of column B as a key.

(B) When the value of A is 100 or more and less than 1000 The storage unit is CS2, and its data organization is Hash organization with the value of column B as a key.

(C) When the value of A is 1000 or more The storage unit is CS3, and its data organization is Btree organization with the value of column B as a key.

The global index (GX-1) 20 is prepared across the storage units CS1, CS2, CS3 that use the column C as a key and that have a plurality of different data organizations.

In the example shown in FIG. 4B, the storage unit CS1 is associated with the table T1 and the storage unit C is associated with the table T2.
S2 is associated. The data organization of storage unit CS1 is Btree organization that uses the value of column A as a key, and the data organization of storage unit CS2 is Btr that uses the value of column X as a key.
ee organization. Global Index (GIX-2) 20
Manages the storage keys of storage units CS1 and CS2 with column B as the key.

Below, based on the example of Figure 4 (a), the storage structure definition,
A specific example of the access procedure generation logic by the optimization process and the process at the time of execution by the record contents of the global index will be described with reference to FIGS. 5 and 6.

(1) Storage structure definition phase In the storage structure definition shown in FIG.
Is divided into three base CSs by the range value of column A, each CS identifier (CSid) is defined, and the data organization of storage units CS1 and CS3 is Btree and storage unit C.
The data organization of S2 is defined as Hash.

Next, the global index 20 for the storage units CS1, CS2, CS3 is defined. This Global Index 20
The data organization of is a Btree index organization with column C as a key. These are the dictionary as metadata of each base CS and global index 20.
Registered in 14.

(2) Optimization processing phase For queries 11 that use a secondary key, it is checked whether there is a local index of the same secondary key, that is, an individual secondary index for each storage unit, and if there is, Evaluate whether the global index 20 or the local index is the best path. If the bus according to the global index 20 is judged to be optimal and its selection is decided, the access procedure shown in FIG.
Generate various access procedures and run-time schedule procedures such as 13.

That is, the optimization processing unit 12 performs the following processing according to the definition information of the dictionary 14.

(A) When there is a local index with the same secondary key, the cost of the local index is evaluated, and the cost when the global index is used is evaluated.

(B) Decide to use the global index if access by the global index is low cost.

(C) The global index CS is registered by the metadata of the global index registered in the dictionary 14.
Generate access procedures for. Here access parts 17
Of these, the Btree index access component is used.

(D) Storage unit CS targeted by the global index
It detects 1, CS2, CS3 and generates a schedule procedure for them.

(E) The CS1 access procedure using the Btree access component is generated from the metadata of the storage unit CS1.

(F) The CS2 access procedure using the Hash access component is generated from the metadata of the storage unit CS2.

(G) A CS3 access procedure using the Btree access component is generated from the metadata of the storage unit CS3.

(3) Runtime processing phase When the access procedure 13 generated by the optimization processing unit 12 is executed, it is based on the content (pointer information) of the lowest record of the global index indicated by the secondary key specified at execution time. Determines the schedule procedure for base CSn.

The lowest record of the global index in this example is assumed to be as shown in FIG. 6, for example.

In this case, the number of pointers of the record header information in the global index record 40 is 4. For the value “aaa” in column C, which is a secondary key, there are two corresponding records in storage unit CS1, one in storage unit CS2, and storage unit CS3.
There is one in.

At the time of execution, the access procedure according to the data organization of each CS is scheduled for the secondary key value "aaa" based on the base CS information and the storage key of the pointers P1 to P4 in the global index record 40, and the corresponding Access records.

〔The invention's effect〕

As described above, according to the present invention, search processing can be executed for divided storage from the viewpoint of database design without lowering processing efficiency. Specifically, for example, there are the following effects.

(A) The uniqueness of a certain column attribute can be guaranteed for all the divided data efficiently by setting a global index using that column as a secondary key.

(B) The search efficiency is generally improved by using the global index as compared with the search by the local index which is a secondary index for each divided data.

[Brief description of drawings]

FIG. 1 is a diagram for explaining the principle of the present invention, FIG. 2 is a diagram for explaining an access procedure by the global index according to the embodiment of the present invention, FIG. 3 is a structure of the lowest record of the global index according to the embodiment of the present invention, and FIG. FIG. 5 is an example of a global index according to the embodiment of the present invention, FIG. 5 is an example of access procedure generation processing according to the embodiment of the present invention, FIG. 6 is an example of the lowest record of the global index in the embodiment of the present invention, FIG. 7 shows an example of divided storage of a database according to the prior art. In the figure, 10 is a database processor, 11 is an inquiry, 12 is an optimization processor, 13 is an access procedure, 14 is a dictionary, 1
5 is global index information, 16 is access component library, 17 is access component, 18 is database, 19 is storage unit, 20 is global index, 21 is storage structure definition, 2
2 represents a table.

Front page continued (72) Inventor Masaaki Mitani 1015 Kamiodanaka, Nakahara-ku, Kawasaki, Kanagawa, Fujitsu Limited (72) Inventor Tomohiro Hayashi 1015, Uedota, Nakahara-ku, Kawasaki, Kanagawa Prefecture, Fujitsu Limited (72) Inventor Koji Obata 1015 Kamiodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture, Fujitsu Limited (72) Inventor, Hiroshi Sekine 1015, Kamikodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture, Fujitsu Limited (72) Inventor, Mitsuhiro Ura, Kawasaki City, Kanagawa Prefecture 1015 Kamiodanaka, Nakahara-ku, Fujitsu Limited (72) Inventor Takuji Ishii 1015, Kamikodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Within Fujitsu Limited

Claims (1)

(57) [Claims] 1. A function of storing a table (22) of a logical structure representation or a set of data units consisting of a part thereof in association with a plurality of structured data storage units (19) having independent data organizations. (14) which is a global index processing method in a database management system having, and which manages, as global index information (15), definition information of a secondary index that spans multiple storage units that may have different data organizations And for the inquiry, the cost of the access using the global index (20) based on the registered information of the dictionary and other accesses is evaluated, and the global index is used when the access by the global index is low cost. Generated access procedure (13) Global indexing scheme, characterized in that a processing unit (12).