Fast OLAP Query Execution in Main Memory on Large Data in a Cluster

A computer-implemented method comprising:

• approximating a plurality of partial aggregation function results for data distributed across a cluster of processing nodes, the cluster of processing nodes comprising a plurality of computing systems, each storing a subset of data in a database;
• the approximating comprising determining a partial aggregation function result of the partial aggregation function results at each processing node based on an offset shared by a group of keys for data records in the database;
• computing a maximal and a minimal error for each partial aggregation function result;
• distributing a range of keys of the group of keys to each processing node, the distributing comprising each processing node receiving all encoded sums for its respective range of keys and being responsible for that respective range of keys;
• computing a lower and an upper bound for each decoded partial aggregation function result;
• generating an upper bound and a lower bound for a total sum per key of the group of keys, the generating comprising summing the lower bounds and upper bounds per key in the group of keys;
• performing a collective reduce operation at each node based on a determined a global k-th highest lower bound;
• and
• returning a result, the result comprising determined k-th highest total sums across the processing nodes.

A system comprising:

• computer hardware configured to perform operations comprising:
• approximating a plurality of partial aggregation function results for data distributed across a cluster of processing nodes, the cluster of processing nodes comprising a plurality of computing systems, each storing a subset of data in a database;
• the approximating comprising determining a partial aggregation function result of the partial aggregation function results at each processing node based on an offset shared by a group of keys for data records in the database;
• computing a maximal and a minimal error for each partial aggregation function result;
• distributing a range of keys of the group of keys to each processing node, the distributing comprising each processing node receiving all encoded sums for its respective range of keys and being responsible for that respective range of keys;
• computing a lower and an upper bound for each decoded partial aggregation function result;
• generating an upper bound and a lower bound for a total sum per key of the group of keys, the generating comprising summing the lower bounds and upper bounds per key in the group of keys;
• performing a collective reduce operation at each node based on a determined a global k-th highest lower bound;
• and
• returning a result, the result comprising determined k-th highest total sums across the processing nodes.