Hardware implementation of the aggregation/group by operation: filter method

Patent metadata

Field	Value
Publication number	US-9600522-B2
Application number	US-201213590110-A
Country	US
Kind code	B2
Filing date	Aug 20, 2012
Priority date	Aug 20, 2012
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

Techniques are described for performing grouping and aggregation operations. In an embodiment, a request is received to aggregate data grouped by a first column. In response to receiving the request, values are loaded from the first column into an input cache. The values include values, from the first column, from a set of rows. A filter unit is programmed with logic to perform a comparison between a particular value, from the first column of a first row, and values in the first column of a plurality of rows, of the set of rows. Based on the comparison, a predicate result is generated that identifies rows, within the plurality of rows, that have a valued in the first column that matches the particular value. An aggregate value for a second column is generated by aggregating values, from the second column, of each of the rows identified by the predicate result.

First claim

What is claimed is:

1. A method comprising:
receiving a request to aggregate data grouped by a first column;
in response to receiving the request, performing the steps of:
parsing the request to identify one or more predicates associated with the request;
determining how the one or more predicates should be programmed into reconfigurable hardware;
programming the reconfigurable hardware to produce a predicate-specific circuit that implements a filter unit into which the one or more predicates are programmed; and
loading values from the first column into an input cache;

wherein the values loaded into the input cache include values, from the first column, from a set of rows;
wherein the predicate-specific circuit includes logic to perform a comparison between a particular value, from the first column of a first row, and
values in the first column of a plurality of rows, of the set of rows;

based on the comparison of the particular value to values in the first column of the plurality of rows, generating a predicate result that identifies rows, within the plurality of rows, that have values in the first column that match the particular value; and
passing the predicate result produced by the predicate-specific circuit to an aggregation unit that includes logic to generate an aggregate value for a second column by aggregating values, from the second column, of each of the rows identified by the predicate result;
wherein the method is performed by one or more computing devices.

2. The method of claim 1 ,
wherein the predicate result is a bitvector and each bit of the bitvector corresponds to a corresponding row of the set of rows;
wherein generating the predicate result comprises:
setting a bit of the bitvector to a first bit value when values of the corresponding row match the particular value;
setting a bit of the bitvector to a second bit value when the values of the corresponding row does not match the particular value.

3. The method of claim 2 , further:
wherein the bitvector is a first bitvector in a set of bitvectors; and
wherein the method further comprises:
selecting a second row, from the set of rows, for which the corresponding bit has not been set to the first bit value in any bitvector of the set of bitvectors;
programming a comparison circuit into the reconfigurable hardware of the filtering unit;
wherein the comparison circuit has logic to perform a comparison between a second value, from the first column of the second row, and
values in the first column of a second plurality of rows, of the set of rows;

based on the comparison of the second value to values in the first column of the second plurality of rows, generating a second bitvector that identifies rows, within the second plurality of rows, that have values in the first column that match the second value; and
generating a second aggregate value for the second column by aggregating values, from the second column, of each of the rows identified by the second bitvector.

4. The method of claim 3 , wherein the second plurality of rows are rows for which corresponding bits have not been set to the first bit value in any bitvector of the set of bitvectors.

5. The method of claim 3 , wherein determining whether the corresponding bit has not been set to the first bit value in any bitvector of the set of bitvectors comprises performing at least one of a bitwise NOT operation or a bitwise XOR operation on one or more bitvectors in the set of bitvectors to generate a bitvector mask identifying rows for which the corresponding bit has not been set to the first bit value.

6. The method of claim 1 , further comprising:
programming the aggregation unit to perform an aggregation operation specified in the request;
wherein aggregating values of the second column for each of the rows identified by the predicate result comprises:
causing the aggregation unit to apply the aggregation operations to values of the second column.

7. The method of claim 1 further comprising outputting results that include:
a group name identified by the particular value; and
the aggregate value generated by aggregating the values of the second column for each of the rows identified by the predicate result.

8. The method of claim 1 , further comprising:
translating the predicate result into a set of memory addresses;
wherein each memory address in the set of memory addresses identifies a memory location of a row that is part of a first group.

9. A non-transitory computer-readable medium storing instructions, which, when executed by one or more processors, cause one or more computing devices to perform operations comprising:
receiving a request to aggregate data grouped by a first column;
in response to receiving the request:
parsing the request to identify one or more predicates associated with the request;
determining how the one or more predicates should be programmed into reconfigurable hardware;
programming the reconfigurable hardware to produce a predicate-specific circuit that implements a filter unit into which the one or more predicates are programmed; and
loading values from the first column into an input cache;

wherein the values loaded into the input cache include values, from the first column, from a set of rows;
wherein the predicate-specific circuit includes logic to perform a comparison between a particular value, from the first column of a first row, and
values in the first column of a plurality of rows, of the set of rows;

based on the comparison of the particular value to values in the first column of the plurality of rows, generating a predicate result that identifies rows, within the plurality of rows, that have values in the first column that match the particular value; and
passing the predicate result produced by the predicate-specific circuit to an aggregation unit that includes logic to generate an aggregate value for a second column by aggregating values, from the second column, of each of the rows identified by the predicate result.

10. The non-transitory computer-readable medium of claim 9 ,
wherein the predicate result is a bitvector and each bit of the bitvector corresponds to a corresponding row of the set of rows;
wherein instructions for generating the predicate result comprise instructions for:
setting a bit of the bitvector to a first bit value when values of the corresponding row match the particular value;
setting a bit of the bitvector to a second bit value when the values of the corresponding row does not match the particular value.

11. The non-transitory computer-readable medium of claim 10 ,
wherein the bitvector is a first bitvector of a set of bitvectors; and
wherein the instructions further cause one or more computing devices to perform operations comprising:
selecting a second row, from the set of rows, for which the corresponding bit has not been set to the first bit value in any bitvector of the set of bitvectors;
programming a comparison circuit into the reconfigurable hardware of the filtering unit with logic to perform a comparison between
a second value, from the first column of the second row, and
values in the first column of a second plurality of rows, of the set of rows;

based on the comparison of the second value to values in the first column of the second plurality of rows, generating a second bitvector that identifies rows, within the second plurality of rows, that have values in the first column that match the second value; and
generating a second aggregate value for the second column by aggregating values, from the second column, of each of the rows identified by the second bitvector.

12. The non-transito

Assignees

• Schauer Justin
• Amberg Philip
• Hopkins Ii Robert David
• Oracle Int Corp

Inventors

• Schauer Justin
• Amberg Philip
• Hopkins Ii Robert David

Classifications

• G06F17/30501

  Physics · mapped topic

• G06F17/30324

  Physics · mapped topic

• G06F17/30412 Primary

  Physics · mapped topic

• G06F16/24561 Primary

  Intermediate data storage techniques for performance improvement · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title