Hardware implementation of the aggregation/group by operation: hash-table method

• US 9,563,658 B2
• Filed: 08/20/2012
• Issued: 02/07/2017
• Est. Priority Date: 08/20/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Amberg, Philip, Schauer, Justin, Hopkins, Robert David
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US13/590,057
• Publication Number:
  US 20140052726A1
• Time in Patent Office: 1,632 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation

Abstract

Techniques are described for performing grouping and aggregation operations. In one embodiment, a request is received to aggregate data grouped by a first column. In response to receiving the request, a group value in a row of a first column is mapped to an address. A pointer is stored for a first group at a first location identified by the address. The pointer identifies a second location of a set of aggregation data for the first group. An aggregate value included in the set of aggregation data is updated based on a value in the row of a second column.

Claims

1. A method comprising:

receiving a request to aggregate data grouped by a first column;

in response to receiving the request, performing, for each row of a plurality of rows;

retrieving, using hardware of a group column access unit, a value from the first column of the row;

wherein the value from the first column of the row is a group value for the row;

mapping, using hardware of a hash table access unit, the group value for the row to an address;

retrieving from memory associated with the address, using hardware of an aggregation state access unit, a set of aggregation data for a group associated with the group value; and

updating, using hardware of a value column access unit, an aggregate value included in the set of aggregation data based on a value in a second column of the row;

wherein the group column access unit, the hash table access unit, the aggregation state access unit and the value column access unit are separate and distinct hardware units;

wherein the group column access unit, the hash table access unit, the aggregation state access unit, and the value column access unit each have a separate and distinct local memory;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

for a particular row of the plurality of rows, determining that aggregation data for the group value associated with the particular row has not yet been generated;

in response to determining that the aggregation data for the group value associated with the particular row has not yet been generated, allocating memory to store aggregation data for the group value associated with the particular row.

3. The method of claim 1, wherein for at least two rows of the plurality of rows, different group values map to a same address, the method further comprising:

for a particular group value, from a particular row of the plurality of rows, that maps to the same address;

using the same address to locate a particular set of aggregation data that includes a stored group value;

comparing the stored group value to the particular group value;

in response to determining that the stored group value and the particular group value match, updating an aggregate value included in the set of aggregation data based on a second value from the particular row of the second column.

4. The method of claim 3, further comprising:

in response to determining that the stored group value and the particular group value do not match;

allocating memory to store aggregation data for a new group;

generating a pointer that identifies an address of the allocated memory;

storing the pointer in the particular set of aggregation data.

5. The method of claim 1 wherein mapping the group value to an address comprises applying a hash function to the group value.

6. The method of claim 1, wherein the set of aggregation data for the group includes the group value, the aggregate value, and a pointer to a second set of aggregation data for a colliding group.

7. The method of claim 1, wherein the address is stored in a hash-table;

wherein the size of the hash-table is selected based on an estimate of a number of groups associated with the request to aggregate data.

8. The method of claim 1, wherein collisions are detected by precomputing all group names in the first column that map to a same address before the request is received.

9. One or more non-transitory computer-readable media storing instructions, which, when executed by one or more processors, cause one or more computing devices to perform:

receiving a request to aggregate data grouped by a first column;

in response to receiving the request, performing, for each row of a plurality of rows;

retrieving, using hardware of a group column access unit, a value from the first column of the row;

wherein the value from the first column of the row is a group value for the row;

mapping, using hardware of a hash table access unit, the group value for the row to an address;

retrieving from memory associated with the address, using hardware of an aggregation state access unit, a set of aggregation data for a group associated with the group value; and

updating, using hardware of a value column access unit, an aggregate value included in the set of aggregation data based on a value in a second column of the row;

wherein the group column access unit, the hash table access unit, the aggregation state access unit and the value column access unit are separate and distinct hardware units;

wherein the group column access unit, the hash table access unit, the aggregation state access unit, and the value column access unit each have a separate and distinct local memory.

10. The non-transitory computer-readable media of claim 9, further storing instructions causing the one or more computing devices to perform:

for a particular row of the plurality of rows, determining that aggregation data for the group value associated with the particular row has not yet been generated;

in response to determining that the aggregation data for the group value associated with the particular row has not yet been generated, allocating memory to store aggregation data for the group value associated with the particular row.

11. The non-transitory computer-readable media of claim 9, wherein for at least two rows of the plurality of rows, different group values map to a same address, the non-transitory computer-readable media further storing instructions causing the one or more computing devices to perform:

for a particular group value, from a particular row of the plurality of rows, that maps to the same address;

using the same address to locate a particular set of aggregation data that includes a stored group value;

comparing the stored group value to the particular group value;

in response to determining that the stored group value and the particular group value match, updating an aggregate value included in the set of aggregation data based on a second value from the particular row of the second column.

12. The non-transitory computer-readable media of claim 11, further storing instructions causing the one or more computing devices to perform, for a second row of the first column:

allocating memory to store aggregation data for a new group;

generating a pointer that identifies an address of the allocated memory;

storing the pointer in the particular set of aggregation data.

13. The non-transitory computer-readable media of claim 9, wherein instructions for mapping the group value to an address comprise instructions for applying a hash function to the group value.

14. The non-transitory computer-readable media of claim 9, wherein the set of aggregation data for the group includes the group value, the aggregate value, and a pointer to a second set of aggregation data for a colliding group.

15. The non-transitory computer-readable media of claim 9, wherein the address is stored in a hash-table;

wherein the size of the hash-table is selected based on an estimate of a number of groups associated with the request to aggregate data.

16. The non-transitory computer-readable media of claim 9, wherein collisions are detected by precomputing all group names in the first column that map to a same address before the request is received.

17. A system for performing grouping and aggregation operations comprising:

one or more processors;

one or more non-transitory computer-readable media storing instructions, which, when executed by the one or more processors cause;

hardware of a group column access unit to retrieve a group value for a first group from a row of a first column;

hardware of a hash table access unit to map the group value to an address;

hardware of an aggregation state access unit to retrieve aggregation data identified by a pointer stored at the address for the first group;

hardware of a value column access unit to update an aggregate value included in the aggregation data based on a value in the row of a second column;

wherein the group column access unit, the hash table access unit, the aggregation state access unit, and the value column access unit are separate and distinct hardware units;

wherein the group column access unit, the hash table access unit, the aggregation state access unit, and the value column access unit each have a separate and distinct local memory.

18. The system of claim 17, wherein the instructions further cause hardware of the aggregation state access unit to:

determine that the pointer for the first group has not yet been generated;

in response to determining that the pointer for the first group has not yet been generated, allocate memory to store the aggregation data for the first group;

generate the pointer for the first group;

wherein the pointer for the first group identifies an address of the allocated memory.

19. The system of claim 17, wherein the instructions further cause:

hardware of the hash table access unit to map a second group value stored in a second row to a second address;

hardware of the aggregation state access unit to retrieve aggregation data identified by a second pointer stored at the second address for a second group;

hardware of the value column access unit to update an aggregate value in the aggregation data identified by the second pointer based on a value in the second row of the second column.

20. The system of claim 17, wherein the instructions further cause:

hardware of the hash table access unit to map a second group value in a second row of the first column to the address;

hardware of the aggregation state access unit to compare the group value to the second group value and in response to determining that the group value and the second group value match, updating the aggregate value in the aggregation data based on a second value in the second row of the second column.

21. The system of claim 20, wherein in response to determining that the group value and the second group value do not match:

the instructions further cause hardware of the aggregation state access unit to;

allocate memory to store aggregation data for a second group;

generate a second pointer that identifies an address of the allocated memory;

store the second pointer in the aggregation data for the first group.

22. The system of claim 17 wherein the instructions further cause hardware of the hash-table access unit to apply a hash function to the group value to map the group value to the address.