Hardware implementation of the filter/project operations

Patent metadata

Field	Value
Publication number	US-9727606-B2
Application number	US-201213590032-A
Country	US
Kind code	B2
Filing date	Aug 20, 2012
Priority date	Aug 20, 2012
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

Techniques are described for performing filter and project operations. In an embodiment, a set of predicates that specify criteria for filtering results to a query is received. Based on a particular predicate of the set of predicates, a predicate result for at least one portion of a particular column is generated. The predicate result identifies rows within the first column that satisfy the particular predicate. Rows are selected and returned as results to the query based at least in part on the predicate result. In an embodiment, the predicate result is a bitvector where each bit of the bitvector corresponds to a particular row within the particular column and identify whether the particular row satisfies the particular predicate.

First claim

What is claimed is:

1. A method comprising:
based on a predicate that specifies criteria for filtering results of a query that targets a table, programming reconfigurable hardware of a filtering unit with the predicate;
wherein the predicate specifies a condition for a particular column of the table;
wherein programming the reconfigurable hardware with the predicate creates a filter unit hardware circuit that is configured to apply the predicate;
causing the filter unit hardware circuit to generate a first predicate result by loading values, from the particular column, into the filter unit hardware circuit;
wherein hardware configuration of the filter unit hardware circuit causes the predicate to be applied to the values;
wherein the first predicate result identifies rows of the table that have values, within the particular column, that satisfy the condition specified by the predicate;
selecting rows to return, as results of the query, based at least in part on the first predicate result;
returning the selected rows as results to the query;
based on a second predicate that specifies criteria for filtering results that targets the table, programming the reconfigurable hardware of the filtering unit with the second predicate;
wherein the second predicate specifies a condition for a second column of the table;
wherein programming the reconfigurable hardware with the predicate creates a second filter unit hardware circuit that is configured to apply the second predicate;
causing the second filter unit hardware circuit to generate a second predicate result by loading values, from the second column, into the second filter unit hardware circuit;
wherein hardware configuration of the second filter unit hardware circuit causes the second predicate to be applied to the values;
wherein the second predicate result identifies rows of the table that have values, within the second column, that satisfy the condition specified by the second predicate;
wherein the method is performed by one or more computing devices.

2. The method of claim 1 wherein the first predicate result is a bitvector and each bit of the bitvector corresponds to a particular row and identifies whether the particular row satisfies the condition specified by the predicate.

3. The method of claim 1 , wherein: the query includes both the predicate and the second predicate; and
selecting rows to return as results based at least in part on the first predicate result comprises:
combining the first predicate result with the second predicate result to generate a combined result;
using the combined result to identify rows that satisfy both the first predicate and the second predicate;
selecting rows identified by the combined result as satisfying both the first predicate and the second predicate.

4. The method of claim 1 wherein the predicate is a first predicate of a set of predicates associated with the query, the method further comprising:
for each predicate of the set of predicates:
programming a particular circuit into the reconfigurable hardware of the filtering unit based on said each predicate, of the set of predicates, that specifies particular criteria for filtering results of the query;
generating a predicate result by loading values from at least one portion of a column into the filtering unit and causing the filtering unit to apply said each predicate to the values;

wherein selecting rows to return as results comprises:
combining each predicate result to generate a final result that identifies rows that satisfy all criteria specified by the set of predicates;
selecting the rows that are identified by the final result as satisfying the criteria specified by the set of predicates.

5. The method of claim 4 ,
wherein the predicate result generated for said each predicate is used to determine which row values to provide to the filtering unit for evaluation of a next predicate;
wherein the set of predicates are evaluated in a serial order;
wherein the serial order is based on a likelihood that a predicate will filter out a large number of rows;
wherein predicates that are more likely to filter out a large number of rows are evaluated before predicates that are less likely to filter out a large number of rows.

6. The method of claim 4 , wherein selecting rows as results further comprises:
translating the final 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 satisfies the criteria specified by the set of predicates.

7. The method of claim 1 , wherein causing the filter unit hardware circuit to generate a first predicate result by loading values, from the particular column, into the filter unit hardware circuit comprises:
generating a first bit value for a corresponding row of the particular column if a value of the corresponding row satisfies the condition;
generating a second bit value, different than the first bit value, for the corresponding row if the value of the corresponding row does not satisfy the condition.

8. The method of claim 1 , wherein causing the filter unit hardware circuit to generate a first predicate result by loading values, from the particular column, into the filter unit hardware circuit comprises:
loading a first set of values from the particular column stored in a first block of memory:
causing the filtering unit to apply the predicate to the first set of values to generate a first bitvector that identifies rows of the table that have values stored within the first block of memory that satisfy the condition specified by the predicate;
loading a second set of values from the particular column stored in a second block of memory:
causing the filtering unit to apply the predicate to the second set of values to generate a second bitvector that identifies rows of the table that have values stored within the second block of memory that satisfy the condition specified by the predicate.

9. The method of claim 1 , wherein causing the filter unit hardware circuit to generate a first predicate result by loading values, from the particular column, into the filter unit hardware circuit comprises causing the filtering unit to concurrently apply the predicate to a plurality of values from the particular column.

10. 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 operations comprising:
based on a predicate that specifies criteria for filtering results of a query that targets a table, programming reconfigurable hardware of a filtering unit with the predicate;
wherein the predicate specifies a condition for a particular column of the table; wherein programming the reconfigurable hardware with the predicate creates a filter unit hardware circuit that is configured to apply the predicate;
causing the filter unit hardware circuit to generate a first predicate result by loading values, from the particular column, into the filter unit hardware circuit;
wherein hardware configuration of the filter unit hardware circuit causes the predicate to be applied to the values;
wherein the first predicate result identifies rows of the table that have values, within the particular column, that satisfy the condition specified by the predicate;
selecting rows to return, as results of the query, based at least in part on the first predicate result;
returning the selected rows as results to the query;
based on a second predicate that specifies criteria for filtering results that targets the table, programming the reconfigurable hardware of the filtering unit with the second predicate;
wherein the second p

Assignees

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

Inventors

• Schauer Justin
• Amberg Philip
• Hopkins Ii Robert David
• Lexau Jon

Classifications

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/2453 Primary

  Query optimisation · CPC title

• G06F17/30867

  Physics · mapped topic

• G06F17/30477

  Physics · mapped topic