Multi stage aggregation using digest order after a first stage of aggregation

• US 10,140,334 B2
• Filed: 03/04/2015
• Issued: 11/27/2018
• 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.
• Primary Examiner(s): Tran, Loc
• Application Number:
  US14/638,783
• Publication Number:
  US 20150288691A1
• Time in Patent Office: 1,364 Days
• 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. A method of processing a database query including an aggregation operation and table grouping columns by a plurality of processing nodes each including a processor, comprising:

generating, at each processing node, a digest for each of a plurality of database object elements of that processing node based on a first mathematical hash function applied to the table grouping columns that provides unordered digests across the database object elements, wherein generating a digest includes;

generating a hash value for a first column of the table grouping columns of a database object element; and

utilizing the generated hash value in the first mathematical hash function and applying the first mathematical hash function to a second column of the table grouping columns of the database object element to produce the digest value for that database object element;

mapping, at each processing node, the plurality of database object elements of that processing node into a plurality of groups within a hash table based on a second mathematical hash function applied to a corresponding digest, wherein the second mathematical hash function produces a value different than the digest to identify a group location and preserve order of the digests within the hash table, and wherein locations within the hash table for the groups are ordered based on the order of corresponding digests to arrange the database object elements in the hash table in digest order;

extracting, at each processing node, the database object elements of that processing node sequentially from the plurality of groups in the hash table in digest order;

performing, at each processing node, the aggregation operation on the database object elements of that processing node in digest order to produce aggregation information;

transferring the database object elements and aggregation information in digest order between the plurality of processing nodes, wherein the database object elements within a same group and including a same digest are transferred to a same processing node;

applying, at each processing node, a merge sort to the transferred database object elements in digest order and aggregating the sorted database object elements with a same digest; and

producing resulting data for the database query grouped by the database table grouping columns based on the aggregated sorted database object elements.

2. The method of claim 1, wherein the query specifies an arrangement for resulting data.

3. The method of claim 2, wherein mapping the plurality of database object elements at each of the plurality of processing nodes includes:

applying data of the database table grouping columns from the plurality of database object elements of that processing node to the first mathematical hash function to determine the digest; and

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

4. The method of claim 1, further comprising:

applying, at each processing node, data of the database object elements of that processing node to the hash table to determine database object elements within a same aggregation bucket.

5. The method of claim 1, further comprising:

applying, at each processing node, data of additional database object elements of that processing node to the hash table to determine database object elements within a same aggregation bucket, wherein the hash table is in an approximate digest order based on the additional database object elements; and

extracting, at each processing node, the database object elements of that processing node from the hash table and placing the extracted database object elements in a fully-sorted digest order.

6. The method of claim 1, wherein the generated hash value is utilized as a seed for the first mathematical hash function.