Method for executing aggregate queries, and computer system

• US 6,182,061 B1
• Filed: 04/09/1998
• Issued: 01/30/2001
• Est. Priority Date: 04/09/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fukuda, Takeshi, Matsuzawa, Hirofumi
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/057,520
• Time in Patent Office: 1,027 Days
• Field of Search: 707/1, 707/3, 707/2, 707/7, 707/101
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

To provide a method for performing a plurality of aggregations in parallel and at a high speed, in a computer system so constructed that each of a plurality of processors connected across a network can use a memory area for itself and a part of the database for itself that includes data categorized into one or a plurality of groups, a method comprising the steps of: (a) ensuring space for storing results of M aggregate queries of the N aggregate queries (M is an integer equal to or less than N) in the memory area for itself in each processor; (b) executing all of the M aggregate queries for the part of the database for itself in each processor; (c) transmitting the results of the M aggregate queries executed by each processor to another processor for counting up and calculating of a final result for counting up; and (d) repeating the steps (a) to (c) until execution of the N aggregate queries is completed by each processor.

Claims

1. A method for executing N aggregate queries for a database in a computer system, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said method comprising the steps of:

(a) ensuring space for storing results of M aggregate queries of said N aggregate queries (M being an integer less than N) in the memory area for itself in each said processor;

(b) executing said M aggregate queries together for said part of said database for itself in each said processor in parallel;

(c) transmitting the results of said M aggregate queries executed by each said processor to a processor for counting up and calculating a final result; and

(d) iterating said steps (a) to (c) until execution of said N aggregate queries is completed.

2. The method according to claim 1, wherein said step (b) includes the steps of:

(b1) in each said processor, reading a part of a partial database into a work space of said memory area for itself, said partial database being said part of said database for itself;

(b2) in each said processor, executing said M aggregate queries for results of calculations that were performed at previous steps and stored in the memory area for itself and the read part of said partial database; and

(b3) iterating said steps (b1) and (b2) until execution of said M aggregate queries is completed for all of said database.

3. The method according to claim 1, wherein M is determined from an amount of space which can be acquired in said memory area for itself for storage of results obtained by execution of aggregate queries.

4. A method for executing P aggregate queries for a database in a computer system, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said method comprising the steps of:

(a) in each said processor, ensuring space for storing results of Q aggregate queries (Q being an integer less than P) to be executed in that processor of said P aggregate queries in the memory area for itself;

(b) executing said Q aggregate queries for data in the entire database in each said processor by iterating a step of reading a part of said partial database into the memory area for itself in each said processor and a step of broadcasting said read part of said partial database via said network in each said processor; and

(c) iterating said steps (a) and (b) until execution of said P aggregate queries is completed.

5. The method according to claim 4, wherein said step (a) includes the steps of:

(a1) checking whether space in which a result of an execution of one aggregate query is stored is present in the memory area for one processor;

(a2) acquiring said space for said result of said execution of said one aggregate query when said space is present;

(a3) when said space is not present, checking whether said space in which said result of said execution of said one aggregate query is stored is present in the memory area for another processor; and

(a4) acquiring said space for said result of said execution of said one aggregate query when said space is present in said another processor; and

wherein, when said space is not present in the memory area for said another processor, said one aggregate query is executed in a succeeding iteration process.

6. The method according to claim 4, wherein Q is determined from an amount of space which can be acquired in said memory area for itself for storage for results obtained by execution of aggregate queries.

7. The method according to claim 4, wherein said step (b) includes the steps of:

(b1) in each said processor, reading a part of said partial database to a work space of said memory area for itself;

(b2) broadcasting the read part of said partial database via said network;

(b3) executing said Q aggregate queries for results of calculations that were performed at previous steps and stored in the memory area for itself and the read part of said partial database and data transmitted from other processors; and

(b4) iterating said steps (b1) to (b3) until each said processor completes execution of said Q aggregate queries for all data in said database.

8. A method for executing S aggregate queries for a database in a computer system, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of a database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of the groups, said method comprising the steps of:

(a) determining T aggregate queries to be executed of said S aggregate queries;

(b) determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed;

(c) in each said processor, reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries;

(d) iterating said step (c) until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries; and

(e) iterating said steps (a) to (d) until the execution of said S aggregate queries is completed.

9. The method according to the claim 8, wherein the step (c) includes the steps of:

(c1) in each said processor, reading a part of said partial database into a work area in the memory area for itself;

(c2) in each said processor, determining which processor needs each portion of read data, transmitting said portion with an ID of an aggregate query associated with said portion to the needing processor via said network; and

(c3) in each said processor, executing said T aggregate queries for data associated with groups to be aggregated in that processor in the read data and data transmitted from other processors and results of calculations which were performed at the previous steps and stored in the memory area for itself.

10. A method for executing N aggregate queries for a database in a computer system, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data that is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said method comprising the steps of:

determining which method in a plurality of aggregate query execution methods which includes first and second and third methods is the speediest by using parameters of said computer system that includes the number of said processors, the size of said database and a communication speed of said network, and parameters associated with properties of said aggregate queries that include the number of aggregate queries to be executed and a capacity of memory in which the results of said execution of said aggregate queries are stored,

wherein said first method comprises the steps of;

(a) ensuring space for storing results of M aggregate queries of said N aggregate queries (M is an integer equal to or less than N) in the memory area for itself in each processor;

(b) executing said M aggregate queries together for said part of database for itself in each said processor;

(c) transmitting the results of said M aggregate queries executed by each processor to a processor for counting up in each said processor, and calculating a final result in said processor for counting up; and

(d) iterating said steps (a) to (c) until execution of said N aggregate queries is completed,

wherein said second method comprises the steps of;

(e) in each said processor, ensuring space for storing results of Q aggregate queries to be executed in that processor of said N aggregate queries in the memory area for itself;

(f) executing said Q aggregate queries for data in the entire database in each said processor by iterating a step of reading a part of said partial database into the memory area for itself in each said processor and a step of broadcasting said read part of said partial database via said network in each said processor; and

(g) iterating said steps (e) and (f) until execution of said N aggregate queries is completed,

wherein said third method comprising the steps of;

(h) determining T aggregate queries to be executed of said N aggregate queries;

(i) determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed;

(j) in each said processor, reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries;

(k) iterating said step (j) until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries; and

(l) iterating said steps (h) to (k) until the execution of said N aggregate queries is completed; and

executing said N aggregate queries by the determined method.

11. A computer system for executing N aggregate queries for a database, said computer system being so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a part of said database for itself, said database including data that is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, each said processor comprising:

(a) a memory processor for ensuring space for storing results of M aggregate queries of said N aggregate queries (M being an integer less than N) in the memory area for itself;

(b) a database processor for executing said M aggregate queries together for said part of said database for itself;

(c) a transmitter for transmitting results obtained by said M aggregate queries to a processor for counting up; and

wherein each said processor operates said memory processor and said database processor and said transmitter until the execution of the N aggregate queries is completed, and said processor for counting up receives and counts up execution results to be counted up in that processor from other processors.

12. A computer system for executing N aggregate queries for a database, said computer system being so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data that is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, each said processor comprising:

(a) a memory processor for ensuring space for storing results of Q aggregate queries (Q being an integer less than N) to be executed in that processor of said N aggregate queries in the memory area for itself;

(b) a database processor for executing said Q aggregate queries for data in the entire database by iterating a step of reading a part of said partial database into a work space in the memory area for itself and a step of broadcasting via said network the read part of said partial database; and

wherein each said processor operates said memory processor and said database processor until execution of said P aggregate queries is completed.

13. A computer system for executing S aggregate queries for a database, said computer system being so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data that is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said computer system comprising:

a controller for determining T aggregate queries to be executed of said S aggregate queries and determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed,

each said processor comprising;

a database processor for reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries,

wherein said database processor operates until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries, and said controller and each said processor operate until the execution of said S aggregate queries is completed.

14. A computer system for executing N aggregate queries for a database, said computer system being so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data that is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said computer system comprising:

a selector for determining which method in a plurality of aggregate query execution methods which includes first and second and third methods is the speediest by using parameters of said computer system that includes the number of said processors, the size of said database and a communication speed of said network, and parameters associated with properties of said aggregate queries that include the number of aggregate queries to be executed and a capacity of memory in which the results of said execution of said aggregate queries are stored,

wherein said first method comprises the steps of;

(a) ensuring space for storing results of M aggregate queries of said N aggregate queries (M is an integer equal to or less than N) in the memory area for itself in each processor;

(b) executing said M aggregate queries together for said part of database for itself in each said processor;

(c) transmitting the results of said M aggregate queries executed by each processor to a processor for counting up in each said processor, and calculating a final result in said processor for counting up; and

(d) iterating said steps (a) to (c) until execution of said N aggregate queries is completed,

wherein said second method comprises the steps of;

(e) in each said processor, ensuring space for storing results of Q aggregate queries to be executed in that processor of said N aggregate queries in the memory area for itself;

(f) executing said Q aggregate queries for data in the entire database in each said processor by iterating a step of reading a part of said partial database into the memory area for itself in each said processor and a step of broadcasting said read part of said partial database via said network in each said processor; and

(g) iterating said steps (e) and (f) until execution of said N aggregate queries is completed,

wherein said third method comprising the steps of;

(h) determining T aggregate queries to be executed of said N aggregate queries;

(i) determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed;

(j) in each said processor, reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries;

(k) iterating said step (j) until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries; and

(l) iterating said steps (h) to (k) until the execution of said N aggregate queries is completed; and

means for instructing each said processor to execute said N aggregate queries by the determined method.

15. A storage medium for storing a program for causing a computer system to execute N aggregate queries for a database, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said program comprising the steps of:

(a) ensuring space for storing results of M aggregate queries of said N aggregate queries (M being an integer less than N) in the memory area for itself in each processor;

(b) executing said M aggregate queries together for said part of database for itself in each said processor;

(c) transmitting the results of said M aggregate queries executed by each processor to a processor for counting up in each said processor, and calculating a final result in said processor for counting up; and

(d) iterating said steps (a) to (c) until execution of said N aggregate queries is completed.

16. A storage medium for storing a program for causing a computer system to execute P aggregate queries for a database, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said program comprising the steps of:

(a) in each said processor, ensuring space for storing results of Q aggregate queries (Q being an integer less than P) to be executed in that processor of said P aggregate queries in the memory area for itself;

(b) executing said Q aggregate queries for data in the entire database in each said processor by iterating a step of reading a part of said partial database into the memory area for itself in each said processor and a step of broadcasting said read part of said partial database via said network in each said processor; and

(c) iterating said steps (a) and (b) until execution of said P aggregate queries is completed.

17. A storage medium for storing a program for causing a computer system to execute S aggregate queries for a database, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said program comprising the steps of:

(a) determining T aggregate queries to be executed of said S aggregate queries;

(b) determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed;

(c) in each said processor, reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries;

(d) iterating said step (c) until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries; and

(e) iterating said steps (a) to (d) until the execution of said S aggregate queries is completed.

18. A storage medium for storing a program for causing a computer system to execute N aggregate queries for a database, wherein said computer system is so constructed that each of a plurality of processors connected by a network can use a memory area for itself and a partial database which is a part of said database for itself, said database including data which is categorized into a plurality of groups, said aggregate query including a query of an aggregation for each of said groups, said program comprising the steps of:

determining which method in a plurality of aggregate query execution methods which includes first and second and third methods is the speediest by using parameters of said computer system that includes the number of said processors, the size of said database and a communication speed of said network, and parameters associated with properties of said aggregate queries that include the number of aggregate queries to be executed and a capacity of memory in which the results of said execution of said aggregate queries are stored,

wherein said first method comprises the steps of;

(a) ensuring space for storing results of M aggregate queries of said N aggregate queries (M is an integer equal to or less than N) in the memory area for itself in each processor;

(b) executing said M aggregate queries together for said part of database for itself in each said processor;

(c) transmitting the results of said M aggregate queries executed by each processor to a processor for counting up in each said processor, and calculating a final result in said processor for counting up; and

(d) iterating said steps (a) to (c) until execution of said N aggregate queries is completed,

wherein said second method comprises the steps of;

(e) in each said processor, ensuring space for storing results of Q aggregate queries to be executed in that processor of said N aggregate queries in the memory area for itself;

(f) executing said Q aggregate queries for data in the entire database in each said processor by iterating a step of reading a part of said partial database into the memory area for itself in each said processor and a step of broadcasting said read part of said partial database via said network in each said processor; and

(g) iterating said steps (e) and (f) until execution of said N aggregate queries is completed,

wherein said third method comprising the steps of;

(h) determining T aggregate queries to be executed of said N aggregate queries;

(i) determining which processor aggregates each group of each of said T aggregate queries, wherein each said group is to be aggregated when said T aggregate queries are executed;

(j) in each said processor, reading out a part of said partial database into said memory area for itself, and transmitting data associated with a group to be aggregated in another processor of an aggregate query in the read data to said another processor via said network with the aggregate query'"'"'s ID, and executing said aggregate queries for data associated with groups to be aggregated in that processor of said T aggregate queries;

(k) iterating said step (j) until each said processor completes the execution of said T aggregate queries for all data associated with groups to be aggregated in that processor of said T aggregate queries; and

(l) iterating said steps (h) to (k) until the execution of said N aggregate queries is completed; and

executing said N aggregate queries by the determined method.