System and method for implementing hash-based load-balancing query processing in a multiprocessor database system

• US 6,567,806 B1
• Filed: 09/20/2000
• Issued: 05/20/2003
• Est. Priority Date: 01/20/1993
• Status: Expired due to Fees

• 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/666,884
• Time in Patent Office: 972 Days
• Field of Search: 707/1-2, 707/100-102, 709/201, 714/11, 714/12, 714/20, 714/21
• 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 query operation method for a query processor in a database management system including a plurality of processors, the method comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

generating a plurality of database operation requests based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key of said retrieval request, by a second one of said processing functions;

distributing said database operation requests to said processors, by said second processing function, each of said database operation requests corresponding to at least one of said processors;

inputting database operation results by execution of the generated plurality of database operation requests, by a third one of said processing functions; and

outputting a set of said database operation results as a retrieval request result, by said third processing function.

3. A query operation method according to claim 1, further comprising:

a step of dividing the database operation key to obtain a plurality of keys, based upon the list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said database operation key, by said second processing function;

wherein said designating step designates said database operation to said plurality of database processors, assigning each of said plurality of keys respectively.

4. A query operation method according to claim 1, further comprising:

a step of generating a plurality of database operation requests based upon said list of key value ranges, with a set of upper and lower bounds, of said hash code, by said second processing function;

wherein said designating step designates the database operation by distributing each of the generated plurality of database operation requests to said database processors respectively.

6. A query operation method according to claim 1, wherein said database operation is a join operation, and said database operation key is a join operation key.

2. A query operation method in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database processors, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

inputting results of said database operation from the database processors to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

5. A query operation method in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database operation programs, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

inputting results of said database operation from the database operation programs to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

7. A query operation method according to claim 5, wherein said database operation is a join operation, and said database operation key is a join operation key.

8. A query operation method in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database processors by assigning one of s aid plurality of keys respectively;

inputting results of said join operation from the database processors to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.

9. A query operation method in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database operation programs, by assigning one of said plurality of keys respectively;

inputting results of said join operation from the database operation programs to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.

10. A query operation system in a database management system including a plurality of processors, comprising:

means for determining a plurality of processing functions, based upon load balancing among said processors;

means for analyzing an input retrieval request by a first one of said processing functions;

means for generating a plurality of database operation requests based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key of said retrieval request, by a second one of said processing functions;

means for distributing said database operation requests to said processors, by said second processing function, each of said database operation requests corresponding to at least one of said processors;

means for receiving database operation results by execution of the generated plurality of database operation requests, by a third one of said processing functions; and

means for outputting a set of the database operation results as a retrieval request result, by said third processing function.

11. A query operation system in a database management apparatus including a plurality of processors, comprising:

means for determining a plurality of processing functions, based upon load balancing among said processors;

means for analyzing an input retrieval request by a first one of said processing functions;

means for designating a database operation to a plurality of database processors, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

means for inputting results of said database operation from the database processors to which the database operation is designated, by a third one of said processing functions; and

means for outputting a set of the database operation results as a retrieval request result, by said third processing function.

13. A query operation system according to claim 11, wherein said database operation is a join operation, and wherein said database operation key is a join operation key.

12. A query operation system including a plurality of processors, comprising:

means for determining a plurality of processing functions, based upon load balancing among said processors;

means for analyzing an input retrieval request by a first one of said processing functions;

means for designating a database operation to a plurality of database operation programs, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

means for inputting results of said database operation from the database operation programs to which the database operation is designated, by a third one of said processing functions; and

means for outputting a set of the database operation results as a retrieval request result, by said third processing function.

14. A query operation system according to claim 12, wherein said database operation is a join operation, and wherein said database operation key is a join operation key.

15. A query operation system including a plurality of processors, comprising:

means for determining a plurality of processing functions, based upon load balancing among said processors;

means for analyzing an input retrieval request by a first one of said processing functions;

means for dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

means for designating by said second processing function, a join operation to each of a plurality of database processors, by assigning one of said plurality of keys respectively;

means for inputting results of said join operation from the database processors to which the corresponding join operation is designated, by a third one of said processing functions; and

means for outputting a set of the join operation results as a retrieval request result, by said third processing function.

16. A query operation system including a plurality of processors, comprising:

means for determining a plurality of processing functions, based upon load balancing among said processors;

means for analyzing an input retrieval request by a first one of said processing functions;

means for dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

means for designating by said second processing function, a join operation to each of a plurality of database operation programs, by assigning one of said plurality of keys respectively;

means for inputting results of said join operation from the database operation programs to which the corresponding join operation is designated, by a third one of said processing functions; and

means for outputting the join operation results as a retrieval request result, by said third processing function.

17. A computer readable storage medium storing a query operation program executed in a database management system including a plurality of processors, said program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

generating a plurality of database operation requests based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key of said retrieval request, by a second one of said processing functions;

distributing said database operation requests to said processors, by said second processing function, each of said database operation requests corresponding to at least one of said processors;

receiving database operation results by execution of the generated plurality of database operation requests, by a third one of said processing functions; and

outputting a set of said database operation results as a retrieval request result, by said third processing function.

18. A computer readable storage medium storing a query operation program executed in a database management system including a plurality of processors, said program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database processors, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied key range of a hash code obtained by a hash function which is assigned to a database operation key, by a second one of said processing functions;

inputting result s of said database operation from the database processors to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

20. A computer readable storage medium according to claim 18,

wherein said database operation is a join operation, and wherein said database operation key is a join operation key.

19. A computer readable storage medium storing a query operation program executed in a database management system including a plurality of processors, said program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database operation programs, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

inputting results of said database operation from the database operation programs to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

21. A computer readable storage medium according to claim 19,

wherein said database operation is a join operation, and wherein said database operation key is a join operation key.

22. A computer readable storage medium storing a query operation program executed in a database management system including a plurality of processors, said program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database processors, by assigning one of said plurality of keys respectively;

inputting results of said join operation from the database processors to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.

23. A computer readable storage medium storing a query operation program executed in a database management system including a plurality of processors, said program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database operation programs, by assigning one of said plurality of keys respectively;

inputting results of said join operation from the database operation programs to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.

24. A query operation program for a query processor in a database management system including a plurality of processors, the program comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

generating a plurality of database operation requests based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key of said retrieval request, by a second one of said processing functions;

distributing said database operation requests to said processors, by said second processing function, each of said database operation requests corresponding to at least one of said processors;

receiving database operation results by execution of the generated plurality of database operation requests, by a third one of said processing functions; and

outputting a set of said database operation results as a retrieval request result, by said third processing function.

25. A query operation program in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database processors, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

inputting results of said database operation from the database processors to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

27. A query operation program according to claim 25,

wherein said database operation is a join operation, and wherein said database operation key is a join operation key.

26. A query operation program in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

designating a database operation to a plurality of database operation programs, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to a database operation key, by a second one of said processing functions;

inputting results of said database operation from the database operation programs to which the database operation is designated, by a third one of said processing functions; and

outputting a set of the database operation results as a retrieval request result, by said third processing function.

28. A query operation program according to claim 26,

wherein said database operation is a join operation key.

29. A query operation program in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database processors, by assigning one of said plurality of keys respectively;

inputting results of said join operation from the database processors to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.

30. A query operation program in a database management apparatus including a plurality of processors, comprising the steps of:

determining a plurality of processing functions, based upon load balancing among said processors;

analyzing an input retrieval request by a first one of said processing functions;

dividing a join operation key to a plurality of keys, based upon a list of key value ranges, with a set of upper and lower bounds, of a hash code evaluated by a hash function which is applied to said join operation key, by a second one of said processing functions;

designating by said second processing function, a join operation to each of a plurality of database operation programs, by assigning one of said plurality of keys respectively;

inputting results of said join operation from the database operation programs to which the corresponding join operation is designated, by a third one of said processing functions; and

outputting a set of the join operation results as a retrieval request result, by said third processing function.