Hardware implementation of the filter/project operations

• US 9,727,606 B2
• Filed: 08/20/2012
• Issued: 08/08/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: Schauer, Justin, Hopkins, II, Robert David, Amberg, Philip, Lexau, Jon
• Primary Examiner(s): Mackes, Kris
• Assistant Examiner(s): HTAY, LIN LIN M
• Application Number:
  US13/590,032
• Publication Number:
  US 20140052743A1
• Time in Patent Office: 1,814 Days
• Field of Search: 707754
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

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.

Claims

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 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.

11. The one or more non-transitory computer-readable media of claim 10, 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.

12. The one or more non-transitory computer-readable media of claim 10, 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.

13. The one or more non-transitory computer-readable media of claim 10 wherein the predicate is a first predicate of a set of predicates associated with the query, the one or more non-transitory computer-readable media further storing instructions that cause the one or more computing devices to perform operations 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 instructions for selecting rows to return as results comprise instructions for;

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.

14. The one or more non-transitory computer-readable media of claim 13,

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.

15. The one or more non-transitory computer-readable media of claim 13, wherein instructions for selecting rows as results comprises instructions for:

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.

16. The one or more non-transitory computer-readable media of claim 10, wherein instructions for 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 comprise instructions for:

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.

17. The one or more non-transitory computer-readable media of claim 10, wherein instructions for 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 comprise instructions for:

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.

18. The one or more non-transitory computer-readable media of claim 10, wherein instructions for 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 instructions for causing the filtering unit to concurrently apply the predicate to a plurality of values from the particular column.

19. A system comprising:

a control unit that includes one or more hardware processors configured to;

receive a set of predicates that specify criteria for filtering results to a query that targets a table;

based on the set of predicates that specify criteria for filtering results to the query that targets the table, program reconfigurable hardware of a filter unit with a first predicate of the set of predicates;

wherein the first predicate specifies a condition for a particular column of the table;

wherein programming the reconfigurable hardware with the first predicate creates a filter unit hardware circuit that is configured to apply the first predicate of the set of predicates;

cause the filter unit hardware circuit to load values from the particular column of the table and cause the filter unit hardware circuit to apply the particular first predicate, of the set of predicates, that specifies the condition for the particular column of the table;

a filter unit that includes reconfigurable hardware and that is configured to;

receive values from the particular column;

wherein the filter unit hardware circuit that is programmed into the filter unit causes the filter unit to apply the first predicate to the values and generate a first bitvector that identifies rows of the table that have values, within the particular column, that satisfy the condition specified by the first predicate;

generate the first bitvector that identifies rows of the table that have values, within the particular column, that satisfy the condition specified by the first predicate;

a project unit configured to;

select rows to return, as results of the query, based at least in part on the first bitvector;

return the selected rows as results to the query;

wherein the one or more hardware processors are further configured to;

receive a second set of predicates that specify criteria for filtering results to a second query that targets the table;

based on the second set of predicates that specify criteria for filtering results to the second query that targets the table, program reconfigurable hardware of the filter unit with a second predicate of the second set of predicates;

wherein the second predicate specifies a condition for a second column of the table;

wherein programming the reconfigurable hardware with the second predicate creates a second filter unit hardware circuit that is configured to apply the second predicate of the second set of predicates;

cause the second filter unit hardware circuit to load values from the second column of the table and cause the filter unit hardware circuit to apply the second predicate, of the second set of predicates, that specifies the condition for the second column of the table.

20. The system of claim 19 wherein:

the control unit is further configured to;

based on the set of predicates that specify criteria for filtering results to the query that targets the table, program reconfigurable hardware of a filter unit with a third predicate of the set of predicates;

wherein the third predicate specifies a condition for a third column of the table;

wherein programming the reconfigurable hardware with the third predicate creates a third filter unit hardware circuit that is configured to apply the third predicate of the set of predicates;

the filter unit is further configured to;

receive values from the third column and apply the third predicate to the values;

wherein the third filter unit hardware circuit that is programmed into the filter unit causes the filter unit to apply the third predicate to the values and generate a second bitvector that identifies rows of the table that have values, within the third column, that satisfy the condition specified by the third predicate;

generate the second bitvector that identifies rows of the table that have values, within the third column, that satisfy the condition specified by the third predicate;

the system further comprises a combine unit configured to;

combine the first bitvector with the second bitvector by applying a bitwise operator to generate a third bitvector;

wherein the project unit is configured to use the third bitvector to identify rows that satisfy both the first predicate and the third predicate;

select rows identified by the third bitvector as satisfying both the first predicate and the third predicate.