Hash table and radix sort based aggregation

摘要

Aggregation of an in-memory database includes receiving, by at least one processor having a plurality of threads, input having records stored in random access memory, distributing, by the at least one processor, the input into portions, one of the plurality of threads having an assigned portion, aggregating, by the at least one processor, the records in the assigned portion based on locality of keys in the records and outputting, by the at least one processor, the aggregated records into a global hash table.

主权项

1. A method, comprising:
receiving, by at least one processor having a plurality of threads, a query comprising an aggregation operation that aggregates a plurality of records across a plurality of columns stored in random access memory; distributing, by the at least one processor, a portion of the records to each of the plurality of threads for aggregation; determining an aggregation threshold based on a ratio of a number of records stored in an intermediate private hash table to a size of the intermediate private hash table; aggregating in accordance with the aggregation operation, by a first thread of the plurality of threads, the portion of records distributed to the first thread into a result stored in one or more hash tables associated with the first thread, wherein if a locality of keys is greater than the aggregation threshold, the aggregating uses multiple private hash tables, and wherein if the locality of keys is less than or equal to the aggregation threshold, the aggregating uses a radix-sort based aggregation; and outputting, by the first thread, the result into a global hash table asynchronously with respect to any other threads of the plurality of threads.