JPH06314299A - Data base control method - Google Patents

Abstract

(57) [Summary] [Configuration] In an environment in which processors and external storage devices are hierarchically configured on a network, a table in a database is arranged by a data division method suitable for an arbitrary hierarchy. A means for selecting an access procedure corresponding to each storage means in which the table is divided and stored is provided by a user's inquiry. [Effect] Since the table data in the database is divided in consideration of the hierarchy of the hardware, uniform distribution of data can be facilitated and a data parallel search processing method suitable for each division method can be selected.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a database management method using a plurality of processors and a plurality of storage devices.

[0002]

2. Description of the Related Art A database management system is a computer system that records and holds data.

Of the database management systems,
In a relational database management system, a database is composed of a table (or a relation) which is viewed by a user in a two-dimensional tabular form, and this table is composed of a plurality of rows (records or tuples). A row is composed of a plurality of columns (attributes or fields), and each column is defined with a data type, a data length, etc. indicating the characteristics of the column.

When using such a relational database system, a user or application program processes data by issuing a request or command to the database (called a query).
(Select, update, insert or delete) In data queries and processing languages of relational database management systems such as SQL, queries are atypical. That is, the user or the application program only specifies what is necessary, and does not need to specify the processing procedure for executing it. Further, the user and the application program do not need to be aware of the place where the table accessed by the inquiry is stored.

However, while the user and the application program are not aware of the processing procedure, the load on the relational database management system (the process of optimizing the access plan of the database by the inquiry) tends to increase. In particular, input / output processing with an external storage device such as a magnetic disk in which a database is stored becomes a burden.

Therefore, in recent years, an increasing number of systems have reduced the load of input / output processing by dividing one table into a plurality of external storage devices and storing the same and parallelizing the input / output processing.

Further, in order to parallelize the arithmetic processing of the database, there is also a system in which table data is divided and stored in each external storage device under the control of a plurality of processors connected by a network. According to this system,
One table can be stored in different external storage devices, and different processors can read them in parallel. This data distribution technology is playing an increasingly important role in relational database management systems.

By the way, as a form of storing data in a distributed manner, there are forms such as round robin, hash partitioning, user-specified key range partitioning, and uniform partitioning.

The first form of division, round robin, is
Data is stored in a plurality of storage devices so that the data amount is uniform. The next hash partition determines the corresponding storage device by applying a hash function to a column of the table.

Next, the key range division is a storage device which satisfies a condition by a given value of data by designating a range of data to be stored in each storage device as a condition for a certain column of a table. Select and store.
When such key range division is performed based on the user's designated condition, the acceptance of the designation of the storage location of the divided table does not directly receive the designation of the storage device to store, but at least one storage unit. There is known a system that accepts a designation of a logical database area formed of devices. In this way, the specification of the storage location of the table divided by the logical database area is accepted so that the user (the person who defines the database) does not have to be aware of the physical system configuration as much as possible. is there.

In the final uniform division, when a table is initially loaded, the data is divided into a plurality of storage devices in a round robin form. Then, the entire specific column (item) is sorted, and the sorted items are again divided into a plurality of storage devices so that the data amount becomes even. Then, the minimum value and the maximum value of the sorted items are obtained for each storage device, and the range between the minimum value and the maximum value is set as the key range of the storage device.

These techniques are described in 1986 VLDB by David J. DeWitt and others.
“(Gamma A High Performance Data Flow Database Machine (GAMMA A High
Performance Dataflow Database Machine) ”. It also describes the realization of parallel database processing by multiple processors.

By thus dividing the data and arranging the data in a plurality of different storage devices, parallel processing of database access becomes possible. As a data division method, particularly when data is evenly divided into a plurality of storage devices such as round robin, the same processing can be requested for each inquiry request, so that the parallel processing improves response time. be able to. In addition, when key range division is performed, if the condition is specified for the column (item) for which key range division is performed among the search conditions specified in the inquiry request for the table, the condition is satisfied in advance. The database processing may be performed only by the processing device in which the data to be stored is stored. As a result, the load on the other processing device is proposed, and the throughput of the entire system can be improved.

Now, as another important technique for speeding up database processing, statistical information is used in addition to the above.
There is a technique for optimizing a database access method.
Statistical information is information that the system uses on behalf of a user to determine the optimal database access procedure. Information typified as one piece of statistical information is section frequency distribution information in which, for each section, the frequency of a row having a value included in the section is obtained in a specific column.

As a result, when a condition is set for a column having section frequency distribution information by an inquiry, the number of rows (selectivity) satisfying the condition is referred to by referring to the section frequency distribution information for the column. Since it can be calculated, the optimum procedure can be selected as the inquiry access processing procedure (whether or not the index is used). This section frequency distribution information is acquired by Gregory Piate Tetsky Shapiro (Gregory
Piratetsky Shapiro) et al., “ACCURATE ESTIMATION OF THE NUMBER OF TUP
LES SATISFYING A CONDITION) ”.

Generally, in a database management system,
When designing a database, it provides a means for the database user to obtain the best performance. In particular, when the tables that make up the database are stored in an external storage device, if they are stored in one external storage device, inquiries to the tables will concentrate access to the external storage device that stores the tables, resulting in bottlenecks in input / output processing. Is likely to occur, leading to a reduction in the throughput of the entire system. Therefore, it is well known that a plurality of external storage devices are prepared as a place for storing the table to disperse the access of the input / output processing and prevent the throughput from decreasing. In this case, the plurality of external storage devices can be used by simply storing data in the next external storage device when the storage capacity of one external storage device becomes insufficient, or by the storage condition (described above). A method of dividing data into a plurality of external storage devices using key range division, hash division, round robin division) is well known.

However, in the latter case of partitioning a table in which a storage condition is specified, only a query that exhibits an effect suitable for the specified storage condition produces a valid result.
The processing performance of queries that did not meet the storage conditions was not guaranteed.

[0018]

As described above, in the conventional technology, in the database management system such as the relational database, the inquiry from the user is atypical, and the storage condition that produces only a specific effect is set. Satisfactory system performance cannot be demanded simply by providing it to users. Furthermore, when changing the applied partitioning condition to another partitioning condition once, all the data of the table must be reorganized and the definition of the partitioning condition of the table must be redefined. ) Is a heavy burden.

It is also necessary to consider not only the balance of access to the external storage device that stores the table data, but also the load on the processor that processes the data. Another problem in dividing a table is a key range dividing condition specified by the user. Today, with the improvement of parallel computer technology, the number of processors is expanded from a few to a few thousand. The number of storage devices (such as magnetic disks) connected to the processor is similarly expanded. When you build a database system with such a system, in the definition of the table that divides the key range,
If the number of division conditions specified by the user exceeds several tens, the burden is heavy and the definition is likely to make a mistake. For example, if the user specifies at most several partitioning conditions, the amount of data stored in the storage device increases in proportion to the amount of data in the table, the load on one storage device increases, and I / O It easily becomes a bottleneck. Further, depending on the domain of the column designated as the division condition, an imbalance may occur in which data is concentrated in a specific storage device.

In this case, the user is forced to prepare a new storage device and redefine the table. To redefine a table, the user needs to back up the data that has already been stored, delete the table, redefine the division conditions, and then download the backed up data. However, there was a problem that the time that interferes with the operation of was prolonged.

Regarding this, a uniform parti
According to the option), the user does not specify the division condition when performing the key range division, but only specifies the items that are the target of the division condition so that the system can evenly distribute the data amount to the plurality of storage devices. The load on the user is reduced by determining the key range of each storage device according to the minimum value and the maximum value of the items to be stored that are specified and divided in each storage device. However, even in this case, adding or deleting data causes an imbalance in the amount of data in each storage device, and there is no need to redefine the table. Since it is necessary to equalize the data amount of each storage device and recalculate the key range of each storage device, the operation time of the system may be hindered. Furthermore, even if the amount of data in each storage device is constant, depending on the query to the table, the access may be concentrated only in a specific key range. Get access status information to
The table division conditions must be readjusted by the user.

An object of the present invention is to manage a database capable of optimally dividing data of a table constituting a relational database in an information processing device including a plurality of processing devices and a storage device connected to the processing devices. To provide a system.

[0023]

In order to achieve the above object, the present invention provides M (M ≧ 1) M (M ≧ 1) input / outputs between N (N ≧ 1) storage means and the storage means. And a processing device including the processor
An information processing apparatus in which a hierarchy is configured with (O> 1) sets as clusters and the cluster P (P> 1) sets as cluster groups, and all of these processing devices are connected by a network. In, a table that constitutes a relational database is divided and stored in a certain arbitrary layer in correspondence with the user's specification of the division method, and the division definition information specified for the arbitrary layer is associated with the layer. By storing the information as the stored information, the data is processed based on the division definition information in response to the inquiry from the user.

[0024]

[Function] A table constituting a relational database is divided and stored in a certain arbitrary hierarchy in accordance with the user's specification of the division method, and the division definition information specified for the arbitrary hierarchy is associated with the hierarchy. According to the relational database management system of the present invention, which stores the stored information, in response to an inquiry from the user,
Since it is possible to limit the processing device that processes the data based on the division definition information and the storage device that stores the data, it is possible to prevent the throughput of the entire system from decreasing and not to increase the processing load. it can.

[0025]

EXAMPLE A database management system according to the present invention is
A plurality of processors connected to the network divides the table data into an external storage device connected to each processor.

The hardware of the database management system according to this embodiment is shown in FIGS.

In FIG. 2, the minimum structural unit of the database management system according to the present invention comprises a processor 12 and an external storage device 14 connected to the processor 12, which is called a node 15. The number of processors that make up a node is not limited to one, but may be a plurality of closely coupled processors. Also, a plurality of external storage devices 14 connected to the processor 12 may be connected. The node is connected to the network 10. A cluster 16 is a collection of a plurality of nodes, each of which has a node as a minimum unit. Further, in FIG. 3 and FIG. 4, a cluster group 18 is a group of a plurality of clusters 16. The cluster 16 and the cluster group 18 are logical system configuration units and do not indicate special hardware. The database management system according to the present invention makes it possible to change the system configuration in units of the node 15, the cluster 16, and the cluster group.

Next, FIG. 5 shows the system configuration of the database management system according to the present invention, which has the hardware configuration shown in FIGS.

FIG. 5 shows the configuration of each processing unit (hereinafter referred to as a server) of the database management system according to the present invention, the correspondence relation between the server and the resource, the node configuration, and the position of the communication path (network). The front-end server 103 (hereinafter abbreviated as FES) receives an inquiry from the application program 104 (hereinafter abbreviated as AP) and generates a processing procedure. Back-end server 1
01 (hereinafter abbreviated as BES) receives a processing procedure from the FES, accesses the database 102 (hereinafter abbreviated as DB), acquires data, and passes the data to the FES. A journal server 107 (hereinafter abbreviated as JS) records change history information of a database where FES and BES occur and transaction status information. Data dictionary server 10
5 (hereinafter abbreviated as DDS) is FES or BES (or J
The meta information used by S), for example, table definition information in the relational database and column information of each table is held in the data dictionary (hereinafter abbreviated as DD). Item number 15 in FIG. 5 is the node shown in FIG. Item No. 10 is the network shown in FIG. 2, which is a communication backbone for communication between nodes. A node address unique to the node is given to the node.
The node address is a physical node identifier, and communication is performed by designating this node address on the network.

The network absorbs the difference in protocol and network interface in the communication system, and it is possible to perform transmission / reception by designating an identifier for identifying the partner server with respect to all the servers existing on the network. And

Next, FIG. 1 shows an embodiment of table division of the database according to the present invention.

In FIG. 1, a table T120 is defined by a CREATE TABLE statement which is a SQL data definition language in a relational database. The table T120 is stored in the cluster group 1 including the cluster group 18 shown in FIG. Further, table T1
(20) is divided and stored in a plurality of clusters 16 (Cluster1 to ClusterO) included in the cluster group 1. Further, in each cluster, the data is divided and stored in a plurality of nodes 15 included in the cluster, and finally divided and stored in a plurality of external storage devices 14 included in each node.

FIG. 6 shows a definition example of the table T1 at this time.
The cluster group, the cluster, the node, and the external storage device that store the table T1 are specified hierarchically, and the method of dividing the table in each hierarchy is specified. In this case, the table T1 is stored in the cluster group 1 and the clusters included in the cluster group 1
Column C1 of table T1 is divided by the key range and divided into clusters 1 to 8. Next, in each cluster, hash division is performed on the nodes in the cluster by the column C2 of the table T1,
Further, each node specifies that the external storage device in the node should be equally divided.

As shown in FIG. 7, the configuration information of these cluster groups, clusters, nodes and external storage devices is managed by the system configuration information 30 and stored in the DDS in FIG. Further, the division definition information of the defined table is managed by three tables shown in FIG. 8, and these tables are also stored in the DDS in FIG. The cluster group management information table 32 stores information about cluster groups that divide the table, the cluster management information table 34 stores information about clusters that divide the table, and the node management information table 36 stores nodes that divide the table. And information about an external storage device (disk) included in the node.

FIG. 9 shows how the process of inserting data into a table is carried out based on the table division information according to the present invention. In FIG. 9, the insertion processing analysis processing 40 is the same as the database management system configuration in FIG.
A request is passed from the AP 104 to the FES 103 by the SQL INSERT statement, and the processing is started. The three tables shown in FIG. 8 are referred to in order to determine the division storage location of the table into which data is to be inserted. When referring to the three tables, use FE
From S103, a table information acquisition request is transmitted to the DDS 105, and the received DDS 105 returns the result of searching the partition information of the requested table to the requesting FES 103. First, referring to the cluster group management table 32, the division information of the table is acquired (step 410). Therefore, if there is division information in the cluster group (step 412), the cluster group and the cluster into which the data should be inserted are determined.
(Step 414). Next, the cluster management table 34 is referred to based on the previously determined cluster information to see if there is partition information in the cluster group, and the partition information for the cluster in the table is acquired (step 416).

Therefore, if there is partition information in the cluster (step 418), the cluster and the node into which the data should be inserted are determined (step 420). Next, the node management table 36 is referred to based on the previously determined node information whether there is any partition information in the cluster, and the partition information for the nodes in the table is acquired (step 422).

Therefore, if there is division information in the node (step 424), the node into which the data should be inserted is determined (step 426). Further, when the node is determined, the disk division information in the node is referred to and the disk to be inserted is determined (step 428). A data insertion request is transmitted to the corresponding server (BES 101 in FIG. 5) based on the data insertion location (which disk of which cluster of which cluster of which cluster) determined in this way (step 430).

Next, FIG. 10 and FIG. 11 show how the data retrieval process for the table is performed based on the table division information according to the present invention.

In FIG. 10, the optimizing process 50 is the AP 104 in the configuration of the database management system in FIG.
Request is passed to FES103 by SQL SELECT statement from
After the parsing process is performed, the process is started. The three tables shown in FIG. 8 are referred to in order to determine the divided storage location of the table for which data is to be searched. When referring to the three tables, the FES 103 transmits a table information acquisition request to the DDS 105, and the received DDS 105 returns the result of searching for the requested partition information of the table to the requesting FES 103.

The optimization process 50 is divided into three phases. First, the divided storage conditions of the table are referred to by the three tables, and the search target range is evaluated from the specified search condition in the inquiry (step 510). Next, a process of determining an access procedure is performed based on the determined search range of the table (step 520). Then, a processing procedure to be executed by the server (BES) for processing is generated based on the determined access procedure (step 30). The generated procedure is
It is sent from FES103 to BES101 which is the target of processing,
BES101 is a database based on the processing procedure sent.
Access processing is performed and the result is returned to FES103.

FIG. 11 shows the process flow of the table division storage condition evaluation process of step 510 of FIG.

First, the cluster group management table 32
To obtain the division information of the table (step 51).
10). Therefore, if there is division information in the cluster group (step 5112), the cluster group and the cluster for which data is to be searched are determined (step 5).
114). In the case of the table T1 (20) in FIG. 1, the cluster group 1 is the search target. In the cluster group, the partitioning condition for partitioning into clusters is key range partitioning. Therefore, if a search condition for the column C1 that is the target of key range partitioning is specified, it is specified as the search condition. The cluster to be searched is determined based on the comparison value. Next, the cluster management table 34 is referred to based on the previously determined cluster information to determine whether there is partition information in the cluster group, and the partition information for the cluster in the table is acquired (step 5116).

Therefore, if there is partition information in the cluster (step 5118), the cluster and node for which data is to be searched are determined (step 5120). Figure 1
In the case of the table T1 in the above, it is assumed that the cluster 11 is the search target. In this cluster, the partitioning condition for partitioning into nodes is hash partitioning. Therefore, if the search condition for the column C2 that is the target of hash partitioning is specified, the comparison value specified in that search condition is used. Determine the node to search based on. Next, the node management table 36 is referred to based on the previously determined node information whether there is any partition information in the cluster, and the partition information for the nodes in the table is acquired (step 5122).

Therefore, if there is division information in the node (step 5124), the node for which data is to be retrieved is determined (step 5126). In the case of the table T1 in FIG. 1, it is assumed that the cluster Node 111 is the search target.
When the node is determined, the disk division information in the node is referred to and the disk to be inserted is determined (step 5128).
In the node, since the division condition when dividing into disks is equal division, in the case of equal division, all the disks included in the node are targets of search. In this way, the search processing request range that is the target of the inquiry processing is determined (step 5130).

While a particular embodiment of the database management method of the present invention has been described, other examples can be implemented without departing from the purpose and spirit of the present invention. In another embodiment, even in a single system including a processor and a plurality of external storage devices connected to the processor, the external storage device is managed by being divided into logical hierarchies, and an arbitrary dividing method can be set according to the hierarchy of the external storage devices. There are ways to realize it.

[0046]

According to the present invention, the data of a table in the database is divided in consideration of the hierarchy of the hardware constituting the system, so that uniform distribution of data can be facilitated.

Further, by adopting such a data division method, it is possible to select a data parallel retrieval processing method which is good for each division method.

Further, since the table is divided hierarchically, even when the data is reorganized, the reorganization can be performed in an arbitrary hierarchy and the range of the reorganization processing can be localized.

[Brief description of drawings]

FIG. 1 is an explanatory diagram showing an example of dividing a table according to the present embodiment.

FIG. 2 is a block diagram showing a configuration from a cluster to a node of the hardware configuration of the present embodiment.

FIG. 3 is a block diagram showing a configuration from a cluster group to a node of the hardware configuration of this embodiment.

FIG. 4 is a block diagram showing the maximum configuration of the hardware configuration of this embodiment.

FIG. 5 is a block diagram showing the configuration of a database management system of this embodiment.

FIG. 6 is an explanatory diagram showing an example of table division definition according to the embodiment.

FIG. 7 is an explanatory diagram showing system configuration information of the hardware configuration of the present embodiment.

FIG. 8 is an explanatory diagram showing division information of a table according to the present embodiment.

FIG. 9 is a processing flowchart of a data insertion processing analysis processing of a table according to the present embodiment.

FIG. 10 is a processing flowchart of optimization processing in the table search processing according to the present embodiment.

FIG. 11 is a processing flowchart of table division storage condition evaluation processing in table search processing according to the present embodiment.

[Explanation of symbols]

10 ... Network, 12 ... Processor, 14 ... Storage device, 15 ... Node, 16 ... Cluster, 18 ... Cluster group.

Claims (1)

[Claims] 1. A processing device comprising N (N ≧ 1) storage means and M (M ≧ 1) processors for performing input / output between the storage means is a minimum unit, and the processing device O (O
In an information processing apparatus in which a hierarchy is formed by setting> 1) sets as clusters and P (P> 1) sets of the clusters as cluster groups, and connecting all of these processing devices by a network. , A table constituting a relational database is divided and stored in a certain arbitrary layer in accordance with the user's specification of the division method, and the division definition information specified for the arbitrary layer is made to correspond to the hierarchical layer. Stored as the information, the data is processed based on the division definition information in response to an inquiry from the user.