System and method for implementing parallel operations in a database management system

• US 6,026,394 A
• Filed: 09/04/1998
• Issued: 02/15/2000
• Est. Priority Date: 01/20/1993
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kawamura, Nobuo, Tsuchida, Masashi, Torii, Shunichi, Nakano, Yukio, Negishi, Kazuyoshi
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/148,648
• Time in Patent Office: 529 Days
• Field of Search: 707/2, 707/3, 707/7, 707/10, 395/200.31, 709/200, 709/201, 709/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• 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 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 plurality of first nodes each having a storage unit for storing data constituting a database, and a controller for retrieving data from said storage unit in accordance with a retrieval request and for sending the retrieved data;

a plurality of second nodes each having a processor for executing a database operation on the data sent from at least one of said first nodes, in accordance with an inputted request for the database operation, and for outputting the result of said database operation; and

a third node having a processor for analyzing an inputted retrieval request, generating a plurality of database operation requests based upon a key range of a hash code obtained by a hash function which is assigned in advance to a database operation key, and distributing the generated database operation requests to each of said second nodes, and further generating a plurality of data retrieval requests for retrieving the data to be retrieved by said data retrieval request, said third node further having a controller for sending the generated data retrieval requests to each of said first nodes, receiving the result of said database operation operated in accordance with said database operation request from each of said second nodes, and outputting the result of said retrieval conducted in accordance with said retrieval requests;

wherein said nodes execute operations in parallel with each other.

2. A database management system according to claim 1, wherein said nodes further comprise functions of:

in said second nodes, inputting the data sent from said first nodes, and executing a database operation per each of said inputted data.

3. A database management system according to claim 1, wherein each of said first nodes further comprises:

a function of sorting the data retrieved from said first nodes, and sending the sorted data.

4. A database management system according to claim 1, wherein said third node further comprises:

when there is a first node whose operation is not finished within a calculated expected operation time in said first nodes, generating a sorting request for sorting data to be distributed to said first nodes, in a first node whose operation finishes earlier, and sending the generated sorting request to said first node whose operation finishes earlier.

5. A database management system according to claim 1, wherein each of said second nodes further comprises:

a function of executing a join operation after completion of sorting the data in said first nodes.

6. A query processing method performed in a database management system having a plurality of first nodes, a plurality of second nodes and a third node, said method comprising:

a process performed by said first nodes of retrieving data from a storage unit in said first nodes in accordance with a retrieval request, and sending the retrieved data;

a process performed by said second nodes of executing a database operation on the data sent from at least one of said first nodes, in accordance with an inputted request for the database operation, and outputting the result of said database operation; and

a process performed by said third node of analyzing an inputted retrieval request, generating a plurality of database operation requests based upon a key range of a hash code obtained by a hash function which is assigned in advance to a database operation key, and distributing the generated database operation requests to each of said second nodes, and further generating a plurality of data retrieval requests for retrieving the data to be retrieved by said database retrieval request, sending the generated data retrieval requests to each of said first nodes, receiving the result of said database operation operated in accordance with said database operation request from each of said second nodes, and outputting the result of said retrieval conducted in accordance with said retrieval requests;

wherein said nodes execute operations independently of each other.

7. A query processing method according to claim 6, further comprising:

a process performed by said second nodes, of inputting the data sent from said first nodes, and executing a database operation per each of said inputted data.

8. A query processing method according to claim 6, wherein the process performed by said first nodes further comprises:

a process of sorting the data retrieved from said first nodes, and sending the sorted data.

9. A query processing method according to claim 6, wherein the process performed by said third node further comprises:

when there is a first node whose operation is not finished within a calculated expected operation time in said first nodes, a process of generating a sorting request for sorting data to be distributed to said first nodes, in a first node whose operation finishes earlier, and sending the generated sorting request to said first node whose operation finishes earlier.

10. A query processing method according to claim 6, wherein the process performed by said second node further comprises:

a process of executing a join operation after completion of sorting of the data in said first nodes.

11. A database management apparatus for indicating a database operation request to a plurality of database processors in a parallel processor system wherein nodes execute independently, comprising:

a query processor having functions of;

analyzing an inputted retrieval request;

generating a plurality of database operation requests based upon a key range of a hash code obtained by a hash function which is assigned in advance to a database operation key of said retrieval request;

a distributing processor for distributing the generated database operation requests to each of said database processors;

a result correcting processor for receiving the result of said database operation, outputted from each of said database processors; and

outputting the result of the processes to said retrieval requests.

12. A database management apparatus according to claim 11, wherein said distributing processor further performs:

a function of outputting a data retrieval request to said database processors.

13. A database management apparatus according to claim 12, wherein said distributing processor further performs:

a function of outputting a sorting request for sorting data further to the retrieved data to said database processors to which said data retrieval request was sent.

14. A query operation method, in a database management apparatus for indicating a database operation request to a plurality of database processors in a parallel processor system wherein nodes execute independently, and having a query processor, comprising processes performed by said query processor of:

analyzing an inputting retrieval request;

generating a plurality of database operation requests based upon a key range of a hash code obtained by a hash function which is assigned in advance to a database operation key of said retrieval request;

receiving the result of said database operation executed to the generated plurality of database operation request; and

outputting the results of the processes to said retrieval request.

15. A query operation method according to claim 14, further comprising:

a process of outputting a data retrieval request to said database processors.

16. A query operation method according to claim 14, further comprising:

a process of outputting a sorting request for sorting data further to the retrieved data to said database processors to which said data retrieval request was sent.

17. A database management system comprising:

a plurality of first nodes each having a storage unit for storing data constituting a database, and a controller for retrieving data from said storage unit in accordance with a retrieval request and for sending the retrieved data;

a plurality of second nodes each having a processor for executing a join operation on the data sent from at least one of said first nodes, in accordance with an inputted request for the join operation, and for outputting the result of said join operation; and

a third node having a processor for analyzing an inputted join operation request, distributing a join operation key to a plurality of second nodes based upon a key range of join operation key, generating a plurality of join operation requests corresponding to the distributed join operation keys, and distributing the generated plurality of join operation requests to each of said second nodes, and further generating a plurality of data retrieval requests to be operated in said join operation request, said third node further having a controller for sending the generated data retrieval requests to each of said first nodes, receiving the result of said join operation operated in accordance with said join operation request from each of said second nodes, and outputting the result of said operation conducted in accordance with said join operation request;

Wherein said nodes execute operations independently of each other.

18. A database management system according to claim 17, wherein said nodes further comprise functions of:

in said second nodes, inputting the data sent from said first nodes, and executing a join operation per each of said inputted data.

19. A database management system according to claim 17, wherein each of said first nodes further comprises:

a function of sorting the data retrieved from said first nodes, and sending the sorted data.

20. A database management system according to claim 17, wherein said third node further comprises:

when there is a first node whose operation is not finished within a calculated expected operation time in said first nodes, generating a sorting request for sorting data to be distributed to said first nodes, in a first node whose operation finishes earlier, and sending the generated sorting request to said first node whose operation finishes earlier.

21. A database management system according to claim 17, wherein each of said second nodes further comprises:

a function of executing a join operation after completion of sorting of the data in said first nodes.

22. A query processing method in a database management system having a plurality of first nodes, a plurality of second nodes, and a plurality of third nodes, said method comprising:

a step performed in at least one of said first nodes, of retrieving data from a storage unit in accordance with a retrieval request and sending the retrieved data, each of said first nodes having said storage unit for storing data constituting a database;

a step performed in at least one of said second nodes, of executing a join operation on the data sent from at least one of said first nodes, in accordance with an inputted request for the join operation, and outputting the result of said join operation; and

a step performed in at least one of said third nodes of analyzing an inputted join operation request, distributing a join operation key to a plurality of second nodes based upon a key range of a join operation key, generating a plurality of join operation requests corresponding to the distributed join operation keys, and distributing the generated plurality of join operation requests to each of said second nodes, and further generating a plurality of data retrieval requests to be operated in said join operation request, sending the generated data retrieval requests to each of said first nodes, receiving from each of said second nodes the result of said join operation in accordance with said join operation request, and outputting the result of said operation conducted in accordance with said join operation request;

wherein said plurality of nodes execute operations independently of each other.

23. A query processing method according to claim 22, further comprising:

a process performed by said second nodes, of inputting the data sent from said first nodes, and executing a database operation per each of said inputted data.

24. A query processing method according to claim 22, wherein the step performed by each of said first node further comprises:

a process of sorting the data retrieved from said first nodes, and sending the sorted data.

25. A query processing method according to claim 22, wherein the step performed in at least one of said second nodes further comprises:

a process of executing a join operation after completion of sorting of the data in said first nodes.

26. A database management apparatus for indicating a database operation request to a plurality of database processors in a parallel processor system wherein nodes execute independently, comprising:

a join processor having a function of analyzing an inputted join request;

a distributing processor for distributing a join operation key to a plurality of database processors based upon a key range of a join operation key, generating a plurality of join operation requests corresponding to the distributed join operation keys, and distributing the generated plurality of join operation requests to each of said database processors; and

a result correcting processor for receiving the result of said join operation processes of said join operation request, from each of said database processors, and outputting the result of said join operation processes.

27. A database management apparatus according to claim 26, wherein said distributing processor further has a function of outputting a data retrieval request to said database processors.

28. A database management apparatus according to claim 27, wherein said distributing processor further has a function of outputting a sorting request for storing data further to the retrieved data to said database processors to which said data retrieval request was sent.

29. A query operation method, in a database management apparatus for indicating a database operation request to a plurality of database processors in a parallel processor system wherein nodes execute independently, and having a query processor, comprising processes performed by said query processor of:

analyzing an inputted query request;

distributing a join operation key to a plurality of database processors based upon a key range of a join operation key, generating a plurality of join operation requests corresponding to the distributed join operation keys, distributing the generated plurality of join operation requests to each of said database processors, receiving the result of said join operation processes of said join operation request, from each of said database processors, and outputting the result of said join operation processes.

30. A query operation method according to claim 29, further comprising:

a process of outputting a data retrieval request to said database processors.

31. A query operation method according to claim 30, further comprising:

a process of outputting a sorting request for sorting data further to the retrieved data to said database processors to which said data retrieval request was sent.