×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×