Database management system and method for query process for the same

• US 20010014888A1
• Filed: 03/16/2001
• Published: 08/16/2001
• Est. Priority Date: 01/20/1993
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kawamura, Nobuo, Tsuchida, Masashi, Torii, Shunichi, Nakano, Yukio, Negishi, Kazuyoshi
• Granted Patent: US 6,556,988 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A database management system for executing database operations in parallel by a plurality of nodes and a query processing method for it are described. The database management system contains a decision management node for deciding a distribution node for retrieving information so as to analyze a query received from an application program, generate a processing procedure for processing the query, and execute the process and a join node for sorting, merging, and joining the information retrieved by the distribution node. When the query process is executed, the distribution node decided by the decision management node retrieves the information to be processed and the join node decided by the decision management node also obtains the result for the query from the retrieved information. The query result is outputted from an output node and transferred to the application program.

Claims

1. A database management system comprising:

a decision management node having analysis means of receiving a query, analyzing said query, and generating the query processing procedure and decision means of deciding the distribution nodes and join nodes for performing the execution process on the basis of the query analysis result by said analysis means;

at least one distribution node having storage means of distributing and storing the database to be queried and distribution means of retrieving information from said storage means and distributing the retrieved information to other nodes;

at least one join node having sorting means of sorting information distributed from said distribution node, merge means of merging said plurality of sorted information, if any, and join means of joining a query on the basis of said merged information;

an output node having output means of outputting the result for the query obtained from said join node; and

a network for transferring data between said nodes.

2. A database management system according to

claim 1

, wherein said decision means decides said distribution node on the basis of the query analysis result of said analysis means, calculates the expected processing time in said decided distribution node, and decides the join node on the basis of said processing time.

3. A database management system according to

claim 2

, wherein said decision means distributes said retrieval information equally to said join nodes on the basis of the expected retrieval information amount in said decided distribution node.

4. A database management system according to

claim 2

, wherein to assign the retrieval information equally to said join nodes by said decision means, said decision management node has storage means of storing column value frequency information relating to the information stored in the storage means of said each node.

5. A database management system according to

claim 3

, wherein said decision means uses the hash function which is decided beforehand so as to assign the retrieval information equally to said join nodes.

6. A database management system according to

claim 2

, wherein said plurality of nodes process independently and said join node inputs the information distributed from said distribution node successively and processes each inputted information.

7. A database management system according to

claim 6

, wherein said distribution node further comprises sorting means for sorting information distributed by said distribution node.

8. A database management system according to

claim 7

, wherein from the calculation result of the expected processing time in said distribution node, said decision means decides so that the sorting means of said distribution node sorts information after the distribution process is executed for the distribution node which finishes the process earlier.

9. A database management system according to

claim 6

, wherein said decision means decides join nodes whose number is larger than the number of said join nodes which are decided on the basis of said processing time by a predetermined number.

10. A database management system according to

claim 9

, wherein the sorting means of said join node has a function for executing the merge process after the sorting process is finished.

11. A database management system according to

claim 6

, wherein said join means has a function for executing said merge process.

12. A database management system according to

claim 11

, wherein said decision means calculates the expected processing times of said join means and said output means and when the processing time of said output means is greater than the processing time of said join means on the basis of said calculation results, decides so that said join means executes said merge process.

13. A query processing method of a database management system which has distribution nodes having storage means of storing information for retrieving information from said storage means and for distributing and sorting the retrieved information to other nodes, join nodes for sorting information distributed from said distribution nodes, merging said plurality of sorted information, if any, and merging and joining a query on the basis of said merged information, and at least one decision management node for receiving said query, analyzing said query, and generating the query processing procedure, and for deciding the distribution nodes and join nodes for performing the execution process on the basis of the query analysis result of said analysis means, comprising the steps of:

deciding said distribution nodes on the basis of the query analysis result of said analysis means in said decision management node, calculating the expected processing times in said distribution nodes, and deciding the join nodes on the basis of said processing times;

retrieving information from said storage means on the basis of said query analysis result in each of said decided distribution nodes and distributing and sorting said retrieved information to other nodes;

sorting information distributed from said distribution nodes in each of said decided join nodes, merging said plurality of sorted information, if any, and merging and joining a query on the basis of said merged information; and

outputting the results for the query obtained from said join nodes.

14. A query processing method of a database management system having a plurality of processing nodes which are connected via a network, wherein at least one of said processing nodes has a storage unit wherein a database is stored, comprising the steps of:

analyzing a query having a condition expression containing a variable in one of said plurality of nodes;

generating a plurality of processing procedure candidates to be executed in said plurality of nodes so as to process said query on the basis of said analysis result;

retrieving the database information to be processed for said query from said plurality of nodes on the basis of the value which is substituted for said variable and the information indicating the data storage status of said database which is given beforehand and selecting the distribution node for distributing said database information to other nodes and the join node for executing a database operation for the database information distributed by said distribution node;

deciding the processing procedure to be executed by said selected distribution node and join node among said plurality of processing procedure candidates;

assigning the process to be executed in each of said distribution node and said join node to said distribution node and said join node according to said decided processing procedure; and

obtaining the process result for said query by executing said assigned process in said distribution node and said join node.

15. A query processing method according to

claim 14

, wherein said selection step comprises the steps of:

selecting said distribution node on the basis of the information indicating the storing destination of the database information to be processed for said query;

calculating the expected processing time in said distribution node;

deciding the number of nodes to be selected as said join node on the basis of said expected processing time; and

selecting said join nodes on the basis of said decided number.

16. A query processing method according to

claim 15

, wherein said step for deciding the number of nodes decides said number of nodes so that the time required for the process which is to be executed in said join node in parallel with the process to be executed in said distribution node is equal to said expected processing time.

17. A query processing method according to

claim 16

, wherein said step for selecting join nodes selects nodes more than said decided number of nodes as said join nodes.

18. A query processing method according to

claim 14

, wherein said step for deciding the processing procedure contains a step for generating data distribution information for distributing data equally to said join nodes on the basis of said information indicating the data storage status.

19. A query processing method according to

claim 14

, wherein said step for assigning the process comprises the steps of:

judging whether there is a scattering in the expected processing time in said distribution node; and

assigning a part of the process of said database operation to a distribution node in which said expected processing time is short on the basis of said judgment result.