MULTI STAGE AGGREGATION USING DIGEST ORDER AFTER A FIRST STAGE OF AGGREGATION

• US 20150286676A1
• Filed: 04/07/2014
• Published: 10/08/2015
• Est. Priority Date: 04/07/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dickie, Garth A.
• Granted Patent: US 10,157,202 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

According to embodiments of the present invention, methods, systems and computer readable media are presented for processing a database query. The query may specify an arrangement for resulting data. A digest is generated for each of a plurality of database object elements. The plurality of database object elements are grouped or mapped into one or more groups based on the digest to arrange the database object elements in digest order. The database object elements from the one or more groups are extracted and/or processed in order of the digest, in accordance with the specified arrangement.

Claims

1-7. -7. (canceled)

8. A system for processing a database query comprising:

a memory; and

a processor configured to;

generate a digest for each of a plurality of database object elements;

map the plurality of database object elements into one or more groups based on the digest to arrange the database object elements in digest order; and

process the database object elements from the one or more groups in digest order.

9. The system of claim 8, wherein the query specifies an arrangement for resulting data and includes a parameter, the parameter including database table grouping columns.

10. The system of claim 9, wherein the processor is configured to;

apply data of the database table grouping columns from the plurality of database object elements to a hash function to determine the digest; and

determine groups for the database object elements based on the digest.

11. The system of claim 8, wherein the processor is configured to:

transfer the database object elements in digest order between the processing nodes, wherein the query is processed by a plurality of processing nodes each processing a respective plurality of database object elements and providing the database object elements in digest order; and

process at each node the transferred database object elements in accordance with the specified arrangement.

12. The system of claim 11, wherein the processor is configured to process data using a merge sort of the transferred database object elements.

13. The system of claim 8, wherein the processor is configured to apply data of the database object elements to a hash table to determine database object elements within a same aggregation bucket, wherein the hash table is in digest order.

14. The system of claim 8, wherein the processor is configured to:

apply data of the database object elements to a hash table to determine database object elements within a same aggregation bucket, wherein the hash table is in an approximate digest order; and

extract the database object elements from the hash table and place the extracted database object elements in a fully-sorted digest order.

15. A computer program product for processing a database query, comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code, when executed by a processor, causes the processor to:

generate a digest for each of a plurality of database object elements;

map the plurality of database object elements into one or more groups based on the digest to arrange the database object elements in digest order; and

process the database object elements from the one or more groups in digest order.

16. The computer program product of claim 15, wherein the query specifies an arrangement for resulting data and includes a parameter, the parameter including database table grouping columns.

17. The computer program product of claim 16, the computer readable program code further configured to:

apply data of the database table grouping columns from the plurality of database object elements to a hash function to determine the digest; and

determine groups for the database object elements based on the digest.

18. The computer program product of claim 15, wherein the query is processed by a plurality of processing nodes each processing a respective plurality of database object elements and providing the database object elements in digest order, the computer readable code further configured to:

transfer the database object elements in digest order between the processing nodes; and

process at each node the transferred database object elements including a merge sort of the transferred database object elements in accordance with the specified arrangement.

19. The computer program product of claim 15, the computer readable code further configured to:

apply data of the database object elements to a hash table to determine database object elements within a same aggregation bucket, wherein the hash table is in digest order.

20. The computer program product of claim 15, the computer readable code further configured to:

apply data of the database object elements to a hash table to determine database object elements within a same aggregation bucket, wherein the hash table is in an approximate digest order; and

extract the database object elements from the hash table and place the extracted database object elements in a fully-sorted digest order.