Parallel database query processing for non-uniform data sources via buffered access

• US 20030229640A1
• Filed: 06/07/2002
• Published: 12/11/2003
• Est. Priority Date: 06/07/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mahmood Choudhry, Tariq, James Kathmann, Kevin, Carlson, David Glenn
• Granted Patent: US 6,910,032 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An apparatus, program product and method utilize a dynamically-populated query buffer to facilitate the handling of at least a portion of a database query in parallel. A query is implemented using at least first and second portions, where the second portion of the query is executed in parallel using a plurality of threads. The first portion of the query is executed to dynamically populate a query buffer with records from a data source, and the plurality of threads that execute the second portion of the query are specified to the query buffer so that the effective data source for the second portion of the query comprises the records that are dynamically populated into the query buffer.

Claims

1. A method of executing a database query, the method comprising:

(a) executing a first portion of a query to dynamically populate a query buffer with records from a data source; and

(b) executing a second portion of the query in parallel using a plurality of threads specified to the query buffer.

2. The method of claim 1, wherein executing the first portion of the query dynamically populates the query buffer with records from the data source that match a first query criterion, and wherein executing the second portion of the query includes selecting those records among those populated in the query buffer that match a second query criterion.

3. The method of claim 1, wherein executing the first portion of the query is performed serially.

4. The method of claim 1, wherein executing the first portion of the query is performed by a thread that is separate from the plurality of threads that execute the second portion of the query.

5. The method of claim 1, wherein executing the first portion of the query is performed by a thread among the plurality of threads.

6. The method of claim 5, wherein executing the first portion of the query is performed by different threads among the plurality of threads at different times.

7. The method of claim 6, wherein executing the first portion of the query includes determining whether a thread among the plurality of threads has been drafted as a producer, and if so, serially executing the first portion of the query in the producer thread.

8. The method of claim 1, wherein executing the second portion of the query consumes records from the query buffer in parallel with dynamically populating the query buffer.

9. The method of claim 1, wherein the query buffer includes a plurality of entries, wherein executing the first portion of the query includes storing a record in an entry in the query buffer, and wherein executing the second portion of the database query includes, in each thread:

(a) retrieving an entry from the query buffer; and

(b) executing the second portion of the query on a record on the retrieved entry.

10. The method of claim 9, wherein each entry is configured to store a plurality of records.

11. The method of claim 9, wherein executing the first portion of the query includes populating at least one entry with a uniform set of records.

12. The method of claim 9, wherein executing the first portion of the query includes populating at least one entry with a nonuniform set of records.

13. The method of claim 1, wherein executing the first and second portion s of the query each include executing an attribute operation list associated with a node defined in a query object, the attribute operation list configured to manipulate at least one attribute described in an attribute descriptor array.

14. An apparatus, comprising:

(a) a memory within which is resident at least a portion of a database; and

(b) program code configured to execute a query on the database, the program code configured to execute a first portion of the query to dynamically populate a query buffer with records from the database, and to execute a second portion of the query in parallel using a plurality of threads specified to the query buffer.

15. The apparatus of claim 14, wherein the program code is configured to execute the first portion of the query to dynamically populate the query buffer with records from the database that match a first query criterion, and wherein the program code is configured to execute the second portion of the query by selecting those records among those populated in the query buffer that match a second query criterion.

16. The apparatus of claim 14, wherein the program code is configured to serially execute the first portion of the query.

17. The apparatus of claim 14, wherein the program code is configured to execute the first portion of the query in a thread that is separate from the plurality of threads that execute the second portion of the query.

18. The apparatus of claim 14, wherein the program code is configured to execute the first portion of the query in a thread among the plurality of threads.

19. The apparatus of claim 18, wherein the program code is configured to execute the first portion of the query in different threads among the plurality of threads at different times.

20. The apparatus of claim 19, wherein the program code is configured to execute the first portion of the query by determining whether a thread among the plurality of threads has been drafted as a producer, and if so, serially executing the first portion of the query in the producer thread.

21. The apparatus of claim 14, wherein the program code is configured to execute the second portion of the query to consume records from the query buffer in parallel with dynamically populating the query buffer.

22. The apparatus of claim 14, wherein the query buffer includes a plurality of entries, wherein the program code is configured to execute the first portion of the query by storing a record in an entry in the query buffer, and wherein the program code is configured to execute the second portion of the database query by, in each thread:

(a) retrieving an entry from the query buffer; and

(b) executing the second portion of the query on a record on the retrieved entry.

23. The apparatus of claim 22, wherein each entry is configured to store a plurality of records.

24. The apparatus of claim 22, wherein the program code is configured to execute the first portion of the query by populating at least one entry with a uniform set of records.

25. The apparatus of claim 22, wherein the program code is configured to execute the first portion of the query by populating at least one entry with a non-uniform set of records.

26. The apparatus of claim 14, wherein the program code is configured to execute the first and second portions of the query each by executing an attribute operation list associated with a node defined in a query object, the attribute operation list configured to manipulate at least one attribute described in an attribute descriptor array.

27. A program product, comprising:

(a) program code configured to execute a database query, the program code configured to execute a first portion of the query to dynamically populate a query buffer with records from a data source, and to execute a second portion of the query in parallel using a plurality of threads specified to the query buffer; and

(b) a signal bearing medium bearing the program code.

28. The program product of claim 27, wherein the signal bearing medium includes at least one of a transmission medium and a recordable medium.