JP3732655B2 - Database management system, database management apparatus, and query processing method - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to database processing technology, and in particular,Parallel database processing technologyAbout.
[0002]
[Prior art]
A database management system (hereinafter abbreviated as DBMS), in particular, a relational DBMS processes a query expressed in a non-procedural language, determines an internal processing procedure, and executes it according to the internal processing procedure. SQL is used as this database language (Database Language SQL ISO 9075: 1989). The main methods of conventional query processing include determining a single internal processing procedure based on preset rules and a plurality of candidate processing procedures selected using various statistical information, by cost evaluation, Some determine what seems to be optimal. In the former case, although the load for creating the processing procedure is small, there is a problem in the validity of the uniformly set rule, and there is also a problem in the optimality of the selected internal processing procedure. The latter manages various statistical information, creates a plurality of candidate processing procedures, calculates a load for cost evaluation thereof, and gives an optimal processing procedure. As a combination technique of the above, there is, for example, Satoh, K., et.al. “Local and Global Optimization Mechanisms for Relational Database”, Proc. VLDB, 1985. In the prior art, the processing procedure is determined by estimating the amount of data from the inquiry conditions.
[0003]
In addition, in many DBMSs, query processing is realized through two-phase processing of query analysis processing and query execution processing. When a query language is incorporated into a host language (COBOL, PL / I, etc.), the query is subjected to query analysis processing in advance before executing the application program, and one internal processing procedure that is an execution format is created. In this query expression, a host language variable is often described in the search condition expression. A constant is assigned to this variable when an internal processing procedure that has already been subjected to a query analysis process is executed, that is, when a query is executed. The problem in this case is that a plurality of optimum processing procedures can be considered according to the value substituted for the variable. In order to solve this problem, there is a method in which a plurality of processing procedures are created at the time of query execution processing, and processing procedures are selected according to values assigned to variables at the time of query execution. As for the code technology, there are technologies described in Japanese Patent Application Laid-Open No. 1-194028 and Graefe, G., et.al. “Dynamic Query Evaluation Plans”, Proc. ACM-SIGMOD, 1989. .
[0004]
Furthermore, it is desired by users to provide a scalable parallel database system in response to an increase in transaction volume and an increase in database volume that exceed the increase in CPU performance and disk capacity. User performance requirements for a database system include support for tens of thousands of concurrent users, the appearance of terabyte-based search transactions, and guaranteed response times that are not proportional to the table size. Parallel database systems are attracting attention, coupled with recent reductions in hardware costs. Regarding the parallel database system, there is a technique described in DeWitt, D., et.al .: “Parallel Database Systems: The Future of High Performance Database Systems”, CACM, Vol. 35, No. 6, 1992. In such a system, it is necessary to connect a processor in a tightly coupled or loosely coupled manner, and to allocate and schedule database processing to a plurality of processors statically / dynamically. If the degree of parallelism is increased, the response performance is improved. However, an excessive degree of parallelism is adversely affected by an increase in overhead and an increase in the response time of other transactions. Therefore, setting an appropriate degree of parallelism is important.
[0005]
In the database processing, the data to be processed exists on the secondary storage device, and it is necessary to read and transfer a large amount of data for each database operation. Even in a parallel database system, when a large amount of data is transferred, the data transfer time becomes a performance bottleneck of the database system. Therefore, a method of effectively utilizing the time for transferring data from the secondary storage device can be considered. This overlaps the data transfer time and the time required for the database processing for the data, and is well known in the prior art. This method can also be applied to data transfer between processor groups connected by an interconnection network.
[0006]
[Problems to be solved by the invention]
In the above prior art, the query optimization process is one in which the DBMS automatically determines the most efficient processing procedure based on various statistical information of the database system from the query input by the user. Furthermore, when a variable is embedded in the query selection conditional expression, multiple processing steps are expanded at the time of query analysis, and by selecting the processing procedure according to the value assigned to this variable at the time of query execution, The optimal processing procedure is selected.
[0007]
In the prior art, a technique for distributing a query request to a database to each processor and performing parallel processing is disclosed, but means for improving an imbalance in processing load in each processor is not specifically disclosed.
[0011]
The purpose of the present invention is toThe inquiry request processing is sent to each processor so that the imbalance of the inquiry request processing load in each processor is improved.There is.
[0012]
[Means for Solving the Problems]
In order to solve the above-mentioned problems, the present invention comprises a storage means for storing data constituting a database, and according to a read request, a storage means for reading out and outputting the stored data, and an input database operation request , Executing a database operation process on the data input from the storage unit, outputting a result of the database operation process, analyzing the input inquiry request, and obtaining the inquiry requestData distribution information is generated based on the evaluation value of the hash function for the database calculation key, and the data to be subjected to the database calculation request is sent from the storage unit to the plurality of calculation units based on the data distribution information,Control means for receiving the database operation processing result of the database operation request from the operation means that has sent the database operation request, and outputting the processing result of the inquiry request.
[0036]
[Action]
The principle of the present invention will be described below. The control means analyzes the input inquiry request and obtains it from the inquiry request.Data distribution information is generated based on the evaluation value of the hash function with respect to the database operation key, and data to be subjected to the database operation request is sent from the storage unit to the plurality of operation units based on the data distribution information.The storage means includes storage means for storing data constituting the database, and reads and outputs the stored data in accordance with a read request. The calculation means executes database calculation processing on the data input from the storage means in accordance with the input database calculation request, and outputs the database calculation processing result. The control means receives the database operation processing result of the database operation request from the operation means that sent the database operation request, and outputs the processing result of the inquiry request.
[0048]
【Example】
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0049]
FIG. 2 shows a conceptual diagram of the database system of this embodiment. In FIG. 2, the database system includes a plurality of application programs (hereinafter abbreviated as AP) 10 and 11 created by the user, and a database such as query processing and resource management. The DBMS 20 that manages the entire system and the operating system (hereinafter referred to as the operating system) that reads and writes the data to be input / output processed in the database processing and is responsible for the management of the entire computer system. (The operating system is abbreviated as OS) 30, a database 40 for storing data to be subjected to database processing, and a dictionary 50 for managing database definition information. The DBMS 20 is connected to another database management system. The dictionary 50 also stores optimization information related to the join columns used in this embodiment.
[0050]
The DBMS 20 includes a system control unit 21 that performs input / output management in addition to management and control of the entire system, a logical processing unit 22 that performs logical processing related to an inquiry, and a physical processing unit 23 that executes physical processing of a database. And a database buffer 24 for storing data to be processed by the DBMS 20. The logic processing unit 22 also includes a query analysis 220 that performs query syntax analysis and semantic analysis, a static optimization process 221 that generates an appropriate processing procedure, and a code generation 222 that generates code corresponding to the processing procedure. A dynamic optimization process 223 for selecting an optimal process procedure candidate generated in the static optimization process 221 and a code interpretation execution unit 224 for interpreting and executing the code. In addition, the physical processing unit 23 includes a data access process 230 that realizes condition determination, editing, and record addition of the accessed data, a database buffer control 231 that controls reading and writing of database records, an input A mapping process 232 for managing the storage location of data to be output and an exclusive control 233 for realizing exclusive control of resources shared by the system are provided.
[0051]
FIG. 3 shows an example of a hardware configuration to which the present invention is applied. Specifically, FIG. 3 shows an application configuration example of a parallel processor system in which a processor and a disk device constitute one node and a plurality of nodes. In FIG. 3, processors 60 to 65 and disk devices 70 to 75 are connected by an interconnection network 80. The hardware configuration shown in FIG. 3 is a configuration for parallel processing of the database system shown in FIG. 2 by a plurality of processors, and the processing is distributed to each node.
[0052]
FIG. 1 shows a configuration when the functions are distributed for each of the above nodes. FIG. 1 shows a schematic diagram of a database system to which this embodiment is applied. Hereinafter, a processing example of the parallel database system will be described with reference to FIG. In this example, parallel processing is applied to a search request for a database. In FIG. 1, each node is assigned to each node a sorting function for extracting and distributing data and a merging function for combining data sorted by a plurality of nodes. Some nodes have only a sort function, and others have a sort function and a merge function. The database consists of a table that can be viewed by the user in a two-dimensional table format, and the table has data for each row or row. A row is composed of one or more attributes (this is referred to as “column”). In FIG. 1, there are T1 and T2 as database tables. Table T1 is stored from node 1 (90) to node 4 (91), and table T2 is stored from node 5 (92) to node 8 (93). Each of these nodes is a distribution node, and data extraction processing and data distribution processing are executed based on a table stored in the distribution node. Nodes 9 (94) to 11 (96) are combined nodes, receive data output from nodes 1 to 4 and 5 to 8, and perform partial column sort processing and merge processing to complete columns. Execute creation. Further, the node 12 (97) is a decision node that receives an inquiry, analyzes the inquiry, and determines the number of distribution nodes and combination nodes that execute processing for the inquiry. The node 12 (97) receives and outputs the data output from the nodes 9-11. These node groups are connected by an interconnection network 80. Nodes 1 to 4 and nodes 5 to 8 and nodes 9 to 11 operate in parallel and are processed by nodes 1 to 4 and nodes 5 to 8, respectively. The result is a pipeline operation in which processing is immediately performed in the nodes 9 to 11 (hereinafter referred to as a parallel pipeline operation). Similarly, the nodes 9 to 11 and the node 12 perform the pipeline operation. Hereinafter, the partial column sorting process in the nodes 9 to 11 is referred to as a slot sort process, and the complete column creation process is referred to as an N-way merge process. The slot sort process refers to a sort process within a page that targets a page in which data is stored. If reading is performed in the slot order, rows can be accessed in ascending order. The N-way merge process uses an N-way buffer to input N sort sequences at each merge stage and finally create one sort sequence.
[0053]
A query for database search processing is, for example, as follows.
[0054]
SELECT T1. C3, T2. C3
FROM T1, T2
WHERE T1. C1 = T2. C1
AND T1. C2 =?
When such an inquiry is received at the node 12, the optimal distribution processing method is selected at the node 12, and each node is instructed via the network. In the above inquiry, the table T1 is stored from the node 1 (90) to the node 4 (91), and the table T2 is stored from the node 5 (92) to the node 8 (93). And data distribution processing is executed. Further, the nodes 9 (94) to 11 (96) sequentially receive the data output from the nodes 1 to 4 and the nodes 5 to 8, and execute the sort process and the join process. The node 12 (97) receives and outputs the data output from the nodes 9-11. This completes the database search.
[0055]
Next, the relationship between the processing times of the respective nodes will be described with reference to FIG. FIG. 4 shows a schematic diagram for explaining the parallel pipeline operation. In FIG. 4, reference numerals 100 and 101 correspond to the processes in node 1 (90) to node 4 (91) and node 5 (92) to node 8 (93) in FIG. Execute. 110 and 111 correspond to the processing from the node 9 (94) to the node 11 (96), and the slot sort processing, N-way merge processing, and matching processing are executed. 120 corresponds to the processing in the node 12 (97), and the requested data output processing is executed. Along the time axis, the data processed in the data extraction processing and data distribution processing 100 and 101 is sequentially transferred to slot sorting processing 110 and 111 and executed in a pipeline manner. The process from the data extraction process to the slot sort process is called an extraction phase. Further, the N-way merge processing 110 and 111 is simply executed in parallel at each node. This N-way merge processing period is called a merge phase. Further, the result of the matching process is sequentially transferred to the request data output process 120 and executed in a pipeline manner. This process from matching to request data output is called a combination phase. The time chart shown in FIG. 4 shows the processing contents when the query example shown in FIG. 1 is applied. In the retrieval phase, the processing time from node 1 (90) to node 4 (91) is shown as T1 data retrieval / data distribution processing time 130. Also, the processing time from the node 5 (92) to the node 8 (93) is indicated by the T2 data fetch / data distribution processing time 131, the transfer time in the interconnection network 80 is indicated by the data distribution transfer time 140, and the node 9 (94 ) To node 11 (96) are executed as indicated by T1 / T2 slot sort processing time 150, respectively. In FIG. 4, the take-out phase ends until the slot sort process completion wait 180. In the merge phase, the processing time from the node 9 (94) to the node 11 (96) is executed at the time indicated by the T1 / T2N way merge processing time 151. This merge phase ends with the T1 / T2N way merge process waiting 181. In the joining phase, the processing time in the node 9 (94) to the node 11 (96) is indicated by the matching processing time 152, the processing time in the mutual connection network 80 is indicated by the joining result transfer time 160, and in the node 12 (97). The processing time is indicated by a request data output processing time 170, and each is executed within that time.
[0056]
Next, a method for distributing processing to each node group of the node 12 in FIG. 1 will be described with reference to FIG. FIG. 5 is an explanatory diagram showing a distribution method to each node group in the data distribution processing. As a premise, a node group that performs data extraction / data distribution processing includes ten nodes 1 to 10 including processors 200 to 230 and disk devices 201 to 231. In addition, it is assumed that the node group that performs the combining process includes five nodes 11 to 15 including processors 240 to 250 and disk devices 241 to 251. The dictionary 50 stores optimization information 51 related to the joined columns. The optimization information 51 is information for equally dividing the data in the database. For example, since the number of data for the combined column is not usually uniform, the data is divided by the combined column so that the number of data is uniform. To do. As shown in FIG. 5, it is shown that the data stored in the nodes 1 to 10 can be equally divided in the divided ranges from v1 to v10. In this case, in order to equally divide the data into the nodes 11 to 15, the node numbers 11, 12, 13, 14, and 5 are divided into five sections of v1 to v2, v3 to v4, v5 to v6, v7 to v8, and v9 to v10, respectively. Distribution processing means for associating 15 may be provided. If the optimization information does not exist, data distribution may be performed by setting an appropriate hash function. In this manner, the node 12 in FIG. 1 includes the distribution processing means, and distributes the processing to each node group when performing the N-way merge processing. Thereby, in the above case, data can be equally divided into the nodes 11 to 15, and the processing time becomes equal.
[0057]
Next, a method for determining the number of coupled nodes when performing N-way merge processing will be described with reference to FIG. FIG. 6 is a schematic diagram for explaining a method for determining the number of coupled nodes.
[0058]
Each phase of parallel connection processing in FIG. 1 and the processing time of each processing are graphed and laid out according to the outline of the parallel pipeline operation shown in FIG. In FIG. 6, it is assumed that data extraction / data distribution processing is executed in the nodes 1 to 8 and processing times of 300 to 305 are required. Here, it is assumed that the processing time 304 of the node 5 is the maximum processing time. The slot sort processing time can be derived from the number N of coupled processing nodes, predetermined system characteristics (CPU performance, disk device performance, etc.), and a database calculation method. It can be obtained by the following formula.
[0059]
[Expression 1]
E = a / N + b * N + c
In order to maximize the effect at the time of performing pipeline processing, the combined node allocation number 350 that is the intersection of the performance characteristics of the slot sort processing and the maximum processing time 304 can be obtained as the number of nodes. When the combined node allocation number 350 is determined, the N-way merge processing time 320 and the matching processing time 330 can be similarly estimated from the performance characteristics of the N-way merge processing and the performance characteristics of the matching process. The total of these processing times is the total processing time for the inquiry. By determining the number of coupled nodes in this way, and sequentially merging the data distributed in the data extraction / data distribution processing and processing them simultaneously, the overall processing time (response time from inquiry to output) Can be shortened.
[0060]
Specific examples of performance characteristics used when determining the number of coupled nodes are shown below. For example, the number of rows is 10,000,000 in both Table T1 and Table T2, the number of conditions is T1-1 (the total number of rows is narrowed down to 1%), and the number of distribution nodes for data retrieval / data distribution processing is Both Table T1 and Table T2 are equally divided into 16 nodes, the number of coupled nodes is 8, the processor performance is 50 MIPS (50 million instructions executed per second), and the network transfer rate is 20 Mbytes / second. . The result of processing by the actual database management system under such conditions or the result calculated from the performance model is as follows.
[0061]
The processing time of the distribution nodes in Table T1 and Table T2 is 180 seconds, T1 / T2 slot sort processing time is 80 seconds, N-way merge processing time is 380 seconds, matching processing time is 110 seconds, and request data output time is 10 seconds. It becomes. Based on the processing performance of these results, the processing time for the query is estimated.
[0062]
Next, a processing time adjustment method (tuning method) for further shortening the response time based on the method for determining the number of coupled nodes shown in FIG. 6 will be described with reference to FIG. 7, FIG. 8, and FIG. . The method described below is calculated in advance when the distribution processing means of the node 12 determines the distribution of processing to each node group, and the distribution is determined from the result.
[0063]
FIG. 7 shows a schematic diagram of slot sorting pre-processing. It is assumed that data extraction / data distribution processing is executed in the nodes 1 to 8 and processing times of 300 to 305 are required. The processing time for each node varies depending on the number of data in each table. Further, the slot sort process is set to be executed by the combination process node group. If there is a variation in processing time for each node, consider a processing procedure for transferring the slot sort processing to the data extraction / data distribution processing node group. As shown in FIG. 7 as pre-processing of slot sorting, slot sorting processing is performed at a node where data extraction / data distribution processing is completed earlier. According to this processing, the slot sort processing time in the node having the combined node allocation number 350 can be reduced from 310 to 312. The N-way merge processing is shifted in the processing time difference 311. This is nothing but extending the length of the slot sort process. Thereby, the N-way merge processing time can be reduced, and as a result, the response time can be reduced.
[0064]
FIG. 8 shows a slot sort sequence length tuning outline diagram. For example, when multiple processing is performed within the time, such as when there is a restriction on processing time, each database operation executed at each node is parameterized and time adjustment (tuning) based on the expected processing time The method of doing will be described. The number of join processing nodes is increased as much as possible from the join node allocation number 350 obtained in FIG. 6 to shorten the response time. In this case, the number of combined node assignments is 351. Assuming that the combined node allocation number is 351, the slot sort processing time is reduced from 310 to 312. In order to maximize the pipeline effect, the N-way merge process is shifted to the slot sort process at the processing time 311. As a result, the number of merges in the N-way merge process is reduced, the processing time can be reduced to 320, and as a result, the response time can be reduced.
[0065]
FIG. 9 shows a schematic diagram of N-way merge frequency tuning. When the matching processing time 330 determined by the combined node allocation number 350 is shorter than the request data output processing time 340, the merge processing at the final stage of the N-way merge processing can be shifted to the matching processing. If the sum of the merge processing time 331 at the final stage of the N-way merge process and the matching process time 330 does not exceed the requested data output processing time 340, the merge process at the final stage is shifted to the matching process. Thereby, the response time can be reduced.
[0066]
Next, the operation flow of the database management system in the present embodiment will be described. 10, FIG. 11, FIG. 12, FIG. 13, FIG. 14 and FIG. 15 show a flowchart of DBMS processing in this embodiment. In FIG. 10, the DBMS includes a query analysis process 400 that performs query analysis by query analysis processing (step 220), static optimization processing (step 221), and code generation (step 222) performed before query execution, A constant optimization is performed, and a dynamic optimization process (step 223) for selecting a processing procedure and a query execution process 410 for performing an execution process on the query by code interpretation execution (step 224) of the query are performed.
[0067]
The outline of each processing unit will be described below.
[0068]
(A) Query analysis processing 400
10A and 10C, in the query analysis (step 220), syntax analysis and semantic analysis of the query sentence input by the application program in the node 12 are executed (step 2200). In FIG. 10A, in the static optimization process (step 221), the ratio of data satisfying the condition is estimated from the conditional expression appearing in the query in the node 12, and based on the preset rule. Create valid access path candidates (especially, select an index) and create processing procedure candidates. In the code generation (step 222), the processing procedure candidates are expanded into an execution format in the node 12.
[0069]
(B) Query execution processing 410
In FIG. 10B, in the dynamic runtime optimization (step 223), the processing procedure to be executed in each node group is determined based on the constant substituted in the node 12. In the code interpretation execution (step 224), the processing procedure is interpreted and executed in each node.
[0070]
Next, a detailed processing flow of each processing unit will be described.
[0071]
In FIG. 10D, in the dynamic optimization process (step 221), the predicate selection rate of the conditional expression appearing in the query is estimated (step 2210), the access path consisting of an index or the like is pruned (step 2211), A processing procedure candidate is generated by combining these access paths (step 2212).
[0072]
In FIG. 10E, in the predicate selection rate estimation (step 2210), it is checked whether or not a variable appears in the query conditional expression (step 22101). If a variable appears, it is checked whether there is column value distribution information in the conditional expression (step 22104). Exit if it exists. If it does not exist, a default value is set according to the type of conditional expression (step 22105), and the process ends. If no variable appears, it is checked whether the conditional expression includes column value distribution information (step 22104). If it does not exist, a default value is set according to the type of conditional expression (step 22105), and the process ends. If it exists, the selectivity is calculated using the column value distribution information (step 22103).
[0073]
In FIG. 11, in the access path pruning 2212, the index of the column appearing in the query conditional expression is registered as an access path candidate (step 22120). Next, it is checked whether the table to be accessed by the query is divided and stored in a plurality of nodes (step 22121). If stored separately, the parallel table scan is registered as an access path candidate (step 22123). If not stored separately, the table scan is registered as an access path candidate (step 22123). It is checked whether the selection rate of each conditional expression has already been set (step 22124). If already set, the index of the conditional expression that minimizes the selection rate for each table is set as the highest priority of the access path (step 22125). If not set, the maximum value / minimum value of the selection rate of each conditional expression is acquired (step 22126). Finally, the selection criteria for each access path is calculated from the system characteristics such as CPU performance and IO performance (step 22127), and the selection rate in the access path combining a single index or a plurality of indexes is less than the above selection criteria. Registration as an access path candidate (step 22128).
[0074]
In FIG. 12, the processing procedure candidate generation 2213 checks whether the table to be accessed in the query is divided and stored in a plurality of nodes (step 22130). If it is stored separately, the process proceeds to step 22135. If it is not stored separately, it is checked whether or not sort processing is included in the processing procedure candidate (step 22131). If it is included, the process proceeds to step 22135. If not included, it is checked whether the access path of the table to be accessed by the query is unique (step 22132). If it is unique, a single processing procedure is created (step 22133). Is created (step 22134), and the process ends. In step 22135, the query is broken down into two-way joins that can be joined. Corresponding to the storage node group of the table to be divided and stored, the data reading / data distribution processing procedure is registered as a candidate. Further, the slot sort processing procedure is registered as a candidate (step 22136). Corresponding to the combination processing node group, the slot sort processing procedure, the N-way merge processing procedure and the matching processing procedure are registered as candidates, and the slot sort continuous length and the number of merge processing are parameterized (step 22137). The request data output processing procedure is registered in the request data output node (step 22138). Finally, when all the evaluations on the decomposition result are completed (step 22139), the process ends.
[0075]
In FIG. 13, the code generation 222 checks whether or not the processing procedure candidate is unique (step 2220). If it is unique, the process proceeds to step 2223. If not unique, optimization information consisting of column value distribution information or the like is embedded in the processing procedure (step 2221), and a data structure for selecting the processing procedure is created based on the constants assigned during query execution (step 2222). Finally, the processing procedure is expanded into an execution format (step 2223).
[0076]
In FIG. 14, the dynamic optimization process 223 checks whether or not the created processing procedure is single (step 22300). If it is single, it ends. If not single, the selectivity is calculated based on the assigned constant (step 22301). It is checked whether or not parallel processing procedures are included in the processing procedure candidates (step 22302). If not included, a processing procedure is selected according to the access path selection criteria (step 22313), and the process ends. If included, the optimization information (column value distribution information of the join column, the number of rows in the table to be accessed, the number of pages, etc.) is input from the dictionary (step 22303), and processing for data retrieval / data distribution The time is calculated as described above in consideration of each system characteristic (step 22304). From this processing time, the number p of nodes to be allocated to the joining process is determined, and this processing procedure a1 is determined (step 22305). It is checked whether or not there is a variation in the data extraction / data distribution processing time (step 22306). If there is variation, a processing procedure a2 for executing slot sorting processing in the data fetch / data distribution processing node group is set (step 22307). Next, a processing procedure a3 is set in which the number of combined nodes allocated p is increased by α (step 22308). If the requested data processing time is longer than the sum of the matching processing time and one N-way merge processing time (step 22309), a processing procedure a4 is set in which one N-way merge processing is transferred to the matching processing ( Step 22310). In the processing procedures a1 to a4, the optimum processing procedure is selected from the viewpoints of minimum response time, minimum load on each node, and small influence on other transaction response performance (step 2211). Data distribution information is created based on the optimization information (step 22312). If there is no optimization information, data distribution information is created according to the combined column evaluation value of the hash function. A processing procedure is selected according to the access path selection criteria (step 22313), and the process ends.
[0077]
In FIG. 15, in the code interpretation execution processing 224, processing is performed in accordance with the corresponding processing procedure in each set node.
[0078]
First, each node determines whether or not data extraction / data distribution processing is set (step 22400). If the data retrieval / data distribution process is set, the database stored in the storage device of each node is accessed and the conditional expression is evaluated (step 22401). Data is extracted based on the data distribution information created based on the optimization information, and the data is sequentially distributed to the buffers of the respective joining nodes (step 22402). It is determined whether or not the buffer of each joining node is full. If the buffer is full, it is transferred to the corresponding joining node in page format. When all the data corresponding to the inquiry is extracted and distributed, the process ends (step 22404).
[0079]
Each node determines whether slot sort processing is set (step 22405). If slot sort processing is set, page format data from the data fetch / data distribution processing node is received (step 22406), and slot sort processing is sequentially performed on the received data (step 22407). The processed slot sort result is temporarily stored, and the slot sort process is terminated (step 22408).
[0080]
Also, it is determined whether or not N-way merge processing is set (step 22409). If the N-way merge process is set, the N-way merge process is executed based on the slot sort result (step 22410), the N-way merge process result is temporarily stored in a buffer or the like (step 22411), and the N-way merge process is executed. Exit.
[0081]
Further, it is determined whether or not the matching process is set (step 22412). If the matching process is set, the sort list of the N-way merge process result is matched, and data is set in the output buffer (step 22413). If the output buffer is full, it is transferred to the request data output node in page format (step 22415).
[0082]
Further, it is determined whether or not the request data output process is set (step 22416). If the requested data output process is set, it is determined whether or not there is a page format data transfer from the joining node (step 22417). If there is a page format data transfer, the page format data is received (step 22418), and the query processing result is output to the application program. If there is no page format data transfer, the query processing result is output as it is. It outputs (step 22419).
[0083]
Further, in the above-described code interpretation execution process, when the slot sorting process is executed in the data extraction / data distribution processing node group when the processing time varies, the code interpretation is performed after the data extraction / data distribution process is completed. The execution process 224 is executed again to perform the slot sort process.
[0084]
Furthermore, if the N-way merge process result is not a complete sort column in step 22413, the final stage merge and matching process are performed.
[0085]
By processing as described above, the inquiry response time of the database management system can be shortened.
[0086]
The joining node assignment method shown in FIG. 6 and the tuning methods shown in FIGS. 7, 8, and 9 may be applied independently or in any combination. That is, the dynamic optimization process 223 assumes a case where all combinations can be applied. Further, in the data fetching process, the application of a parallel input / output access method comprising a plurality of disk devices, the application of a batch input / output method / prefetch input / output method, and a data distribution method using optimized information or a hash function for data distribution processing Application, application of a parallel sorting method to N-way merge processing, application of a matching processing method between nodes to matching processing, application of a parallel reception processing method by assigning a plurality of nodes to request data output processing, and the like are also conceivable. In step 22309 and step 22310, one way N-way merge processing is assumed, but it may be generally n times (n ≧ 1).
[0087]
With respect to the parallel pipeline operation shown in FIG. 4, when the joining node allocation method shown in FIG. 6 and the tuning method shown in FIGS. 7, 8, and 9 are applied, among the extraction phase, merge phase, and joining phase, There are cases where the merge phase can be omitted. That is, it is possible by extending the slot sort sequence length and moving the N-way merge process. In this case, the merge phase process is omitted even in the query execution process.
[0088]
The query processing method of the present invention is not limited to the combined use of the rule using statistical information and cost evaluation, but can be applied as long as a processing procedure for providing appropriate database reference characteristic information can be obtained. For example, the present invention can also be applied to a DBMS that performs optimization processing such as cost evaluation only, rule usage only, or cost evaluation and rule usage combined.
[0089]
The present invention can be realized through a tightly coupled / loosely coupled multiprocessor system software system of a large computer, or through a tightly coupled / loosely coupled complex processor system in which a dedicated processor is prepared for each processing unit. It can also be realized. Further, even a single processor system is applicable if a parallel process is assigned for each processing procedure.
[0090]
According to the present embodiment, the number of nodes is determined corresponding to the database operation executed at each node, and if there is a variation in the data division, the data is divided equally into each node, Since each database operation to be executed is parameterized and the expected processing time is equalized, there is no bias in processing time between the nodes, and a pipeline operation can be performed smoothly, and high-speed query processing can be realized.
[0091]
【The invention's effect】
According to the invention, obtained from an inquiry requestBy generating data distribution information based on the evaluation value of the hash function for the database calculation key, and sending the data subject to the database calculation request from the storage unit to the plurality of calculation units based on the data distribution information,The load imbalance in the processor can be reduced.
[Brief description of the drawings]
[Fig. 1] Outline of parallel join processing
[Figure 2] Configuration diagram of the database system
FIG. 3 Hardware configuration diagram
[Figure 4] Outline of parallel pipeline operation
[Figure 5] Outline of data distribution process
[Fig. 6] Outline of node allocation
[Fig. 7] Overview of pre-slot sorting
[Figure 8] Overview of slot sort run length tuning
[Fig. 9] N-way merge count tuning overview diagram
FIG. 10 is a flowchart of the database management system.
FIG. 11 is a flowchart of the database management system.
FIG. 12 is a flowchart of the database management system.
FIG. 13 is a flowchart of the database management system.
FIG. 14 is a flowchart of the database management system.
FIG. 15 is a flowchart of the database management system.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 10, 11 ... Application program, 20 ... Database management system, 22 ... Logic processing part, 220 ... Query analysis, 221 ... Static optimization processing, 222 ... Code generation, 223 ... Dynamic optimization processing, 224 ... Code interpretation execution , 30 ... operating system, 40 ... database, 50 ... dictionary, 80 ... interconnection network, 90, 91, 92, 93, 94, 95, 96, 97 ... node.

Claims (9)

A plurality of arithmetic processing units for performing arithmetic processing of data;
A distribution processing unit for distributing data extracted from the database to the plurality of arithmetic processing units;
A determination processing unit that determines an arithmetic processing unit that performs arithmetic processing on the input query,
The determination processing unit
Using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the arithmetic processing unit of the specified number of arithmetic processing units that executes the arithmetic processing for the query A decision means to decide;
According to calculation key optimization information for equally dividing the number of data in the database, the division range of the calculation key to be assigned to each of the calculation processing units of the specified number of calculation processing units executing the calculation processing for the query is described Setting means for setting data distribution information in the distribution processing unit;
Query result output means for outputting data received from each of the arithmetic processing units of the specified number of arithmetic processing units for executing arithmetic processing for the query,
The distribution processing unit includes:
Distributing means for distributing the data extracted from the database to the operation processing unit assigned to the division range to which the operation key of the data belongs in the data distribution information set in itself,
The arithmetic processing unit includes:
Computation result output means for computing the data distributed from the distribution processing unit and outputting the result to the decision processing unit
A database management system characterized by A plurality of arithmetic processing units for performing arithmetic processing of data;
A distribution processing unit for distributing data extracted from the database to the plurality of arithmetic processing units;
A determination processing unit that determines an arithmetic processing unit that performs arithmetic processing on the input query,
The determination processing unit
Using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the arithmetic processing unit of the specified number of arithmetic processing units that executes the arithmetic processing for the query A decision means to decide;
Setting means for setting, in the distribution processing unit, data distribution information in which hash values for the calculation keys of the data in the database are evenly assigned to the respective arithmetic processing units of the number of arithmetic processing units;
Query result output means for outputting data received from each of the arithmetic processing units of the specified number of arithmetic processing units for executing arithmetic processing for the query,
The distribution processing unit includes:
Distributing means for distributing the data extracted from the database to an operation processing unit to which a hash value for the operation key of the data is assigned in the data distribution information set in itself,
The arithmetic processing unit includes:
Computation processing means for computing the data distributed from the distribution processing unit and outputting the result to the decision processing unit
A database management system characterized by The database management system according to claim 1 or 2, wherein
The determination processing unit
When there are a plurality of distribution processing units and the processing time in each of the distribution processing units varies, a request for rearranging the data extracted in each of the distribution processing units is generated, and the request is sent to the distribution unit with the slowest processing time. A reordering request setting means for setting in at least one distribution processing unit of the distribution processing units other than the processing unit;
The distribution means of the distribution processing unit to which the rearrangement request is set,
According to the rearrangement request, after the retrieved data is rearranged, it is distributed to the assigned arithmetic processing unit.
A database management system characterized by Decision to determine a plurality of arithmetic processing units that perform arithmetic processing of data, a distribution processing unit that distributes the data extracted from the database to the plurality of arithmetic processing units, and an arithmetic processing unit that performs arithmetic processing on the input query A query processing method in a database management system having a processing unit,
In the determination processing unit, using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the specified arithmetic processing for executing the arithmetic processing for the query Determining an arithmetic processing unit for the number of copies;
In the determination processing unit, according to optimization information of an operation key for equally dividing the number of data in the database, an operation key assigned to each operation processing unit of the specified number of operation processing units for executing the operation processing for the query Setting data distribution information in which a division range is described in the distribution processing unit;
In the distribution processing unit, distributing the data extracted from the database to the calculation processing unit assigned to the division range to which the calculation key of the data belongs in the data distribution information set in itself;
The arithmetic processing unit performs arithmetic processing on the data distributed from the distribution processing unit, and outputs the result to the determination processing unit;
The decision processing unit includes a step of outputting data received from each of the specified number of arithmetic processing units for performing arithmetic processing on the query.
A query processing method characterized by Decision to determine a plurality of arithmetic processing units that perform arithmetic processing of data, a distribution processing unit that distributes the data extracted from the database to the plurality of arithmetic processing units, and an arithmetic processing unit that performs arithmetic processing on the input query A query processing method in a database management system having a processing unit,
In the determination processing unit, using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the specified arithmetic processing for executing the arithmetic processing for the query Determining an arithmetic processing unit for the number of copies;
A distribution information setting step for setting, in the distribution processing unit, data distribution information in which hash values for the calculation keys of the data in the database are evenly allocated to the calculation processing units of the number of calculation processing units;
In the distribution processing unit, distributing the data extracted from the database to a calculation processing unit to which a hash value for the calculation key of the data is assigned in the data distribution information set to itself;
The arithmetic processing unit performs arithmetic processing on the data distributed from the distribution processing unit, and outputs the result to the determination processing unit;
The decision processing unit includes a step of outputting data received from each of the specified number of arithmetic processing units for performing arithmetic processing on the query.
A query processing method characterized by The inquiry processing method according to claim 4 or 5, wherein
In the determination processing unit, the next of the distribution information setting step, the there are a plurality of distribution processing unit, if there are variations in the processing time in each said distribution processing unit, sorting data to which the taken out Te respective distribution processor odor Generating a request and setting the request to at least one distribution processing unit other than the distribution processing unit other than the distribution processing unit having the slowest processing time,
In the step of distributing the rearrangement request to the arithmetic processing unit of the set distribution processing unit, the retrieved data is rearranged according to the rearrangement request and then distributed to the arithmetic processing unit.
A query processing method characterized by A plurality of arithmetic processing units that perform arithmetic processing of data, and a plurality of distribution processing units that distribute the data extracted from the database to the arithmetic processing unit according to the operation key of the data and the data distribution information set in itself A database management apparatus that is used in a database management system and determines an arithmetic processing unit that performs arithmetic processing on an input query,
Using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the arithmetic processing unit of the specified number of arithmetic processing units that executes the arithmetic processing for the query Means to determine,
Data describing division ranges of calculation keys to be assigned to the respective calculation processing units of the specified number of calculation processing units for executing calculation processing for the query in accordance with calculation key optimization information for equally dividing the data of the database Means for setting distribution information in the distribution processing unit.
A database management device characterized by the above . A plurality of arithmetic processing units that perform arithmetic processing of data, and a plurality of distribution processing units that distribute the data extracted from the database to the arithmetic processing unit according to the operation key of the data and the data distribution information set in itself A query processing method in a database management device used in a database management system to determine an arithmetic processing unit that performs arithmetic processing on an input query,
Using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the arithmetic processing unit of the specified number of arithmetic processing units that executes the arithmetic processing for the query A step to determine;
According to calculation key optimization information for equally dividing the number of data in the database, the division range of the calculation key to be assigned to each of the calculation processing units of the specified number of calculation processing units for executing the calculation processing for the query is described Setting data distribution information in the distribution processing unit.
A query processing method characterized by A plurality of arithmetic processing units for performing data arithmetic processing, and a plurality of distribution processes for distributing the data extracted from the database to the arithmetic processing units according to the hash value for the operation key of the data and the data distribution information set in the processing unit A query processing method in a database management apparatus for determining an arithmetic processing unit that executes arithmetic processing on an input query, and is used in a database management system having
Using the correspondence relationship between the processing time and the number of arithmetic processing units, the number of arithmetic processing units corresponding to the processing time in the distribution processing unit is specified, and the arithmetic processing unit of the specified number of arithmetic processing units that executes the arithmetic processing for the query A step to determine;
Setting, in the distribution processing unit, data distribution information in which hash values for the operation keys of the data in the database are evenly assigned to the respective arithmetic processing units of the number of arithmetic processing units.
A query processing method characterized by

Images