Bloom filter costing estimation

Patent metadata

Field	Value
Publication number	US-9454574-B2
Application number	US-201414229211-A
Country	US
Kind code	B2
Filing date	Mar 28, 2014
Priority date	Mar 28, 2014
Publication date	Sep 27, 2016
Grant date	Sep 27, 2016

Abstract

Bloom filter cost estimation engine for improved performance and accuracy is described. An example method includes building an execution plan for a join operation having a plurality of levels, where the execution plan includes a top join operator at a top level, a leaf scan operator on a bottom level, and one or more intermediate operators between the top level and the bottom level. A row reduction effect of applying a Bloom filter is determined by simulating a semi-join operation over table statistic representation at each of the plurality of levels of the execution plan. A cost savings of the join operation is calculated based on the row reduction effect at the each of the plurality of the levels.

First claim

What is claimed is:

1. A method, comprising:
building, by a computing device, an execution plan for a join operation having a plurality of levels, including a top level comprising a top join operator, a bottom level comprising a leaf scan operator, and an intermediate level comprising an intermediate operator between the top level and the bottom level;
determining, by the computing device, a row reduction effect of applying a Bloom filter by simulating a semi-join operation over a table statistic representation at each of the plurality of levels of the execution plan;
calculating, by the computing device, a cost savings of applying the Bloom filter to the join operation based on the row reduction effect at the each of the plurality of levels; and
integrating, by the computing device, the Bloom filter to the execution plan upon determining that the cost savings of applying the Bloom filter to the join operation exceeds a joint cost, wherein the joint cost is based on a cost associated with build side and probe side of the Bloom filter.

2. The method of claim 1 , wherein the table statistic representation comprises a histogram of data distribution variables on a table involved in the join operation and row count variables associated with the table.

3. The method of claim 1 , where the simulating the semi-join operation comprising:
simulating the semi-join operation between the table statistic representation at the each of the plurality of levels and a build side of an original derived table.

4. The method of claim 3 , further comprising:
generating a new table statistic representation at the each of the plurality of levels, based on corresponding data distribution variables and row count variables.

5. The method of claim 4 , further comprising:
updating the row count variable by adding a false positive rate to the row count variable at the each of the plurality of levels.

6. The method of claim 1 , wherein the integrating further comprises:
integrating the Bloom filter to the execution plan upon determination that a final probing reduced row count is less than 90% of an original scan row count and

(

(

c
n

-

c
n
′

)

c
n

>

10
⁢
%

,

wherein Cn is a top join cost associated with the top join operator without applying the Bloom filter, and Cn′ is the top join cost after applying the Bloom filter.

7. The method of claim 1 , wherein the join operation is an equi-join operation.

8. The method of claim 1 , wherein the join operation comprises a hash join, a sort merge join, and a reformatting based nested loop join.

9. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to execute a plurality of modules, the modules comprising:
a plan builder, configured to build art execution plan for a join operation having a plurality of levels, including a top level comprising a top join operator, a bottom level comprising a leaf scan operator, and an intermediate level comprising an intermediate operator between the top level and the bottom level,
a operation simulator, configured to determine a row reduction effect of applying a Bloom filter by simulating a semi-join operation over a table statistic representation at each of the plurality of levels of the execution plan;
a cost calculator, configured to calculate a cost savings of applying the Bloom filter to the join operation based on the row reduction effect at the each of the plurality of levels; and
a plan integrator, configured to integrate the Bloom filter to the execution plan upon determining that the cost savings of applying the Bloom filter to the join operation exceeds a joint cost, wherein the joint cost is based on a cost associated with build side and probe side of the Bloom filter.

10. The system of claim 9 , wherein the table statistic representation comprises a histogram of data distribution variables on a table involved in the join operation and row count variables associated with the table.

11. The system of claim 9 , where the operation simulator is further configured to:
simulate the semi-join operation between the table statistic representation at the each of the plurality of levels and a build side of an original derived table.

12. The system of claim 11 , where the operation simulator is further configured to:
generate a new table statistic representation at the each of the plurality of levels, based on corresponding data distribution variables and row count variables.

13. The system of claim 12 , where the operation simulator is further configured to:
update the row count variable by adding a false positive rate to the row count variable at the each of the plurality of levels.

14. The system of claim 9 , wherein the plan integrator is further configured to:
integrate the Bloom filter to the execution plan upon determination that a final probing reduced row count is less than 90% of an original scan row count and

(

(

c
n

-

c
n
′

)

c
n

>

10
⁢
%

,

wherein Cn is a top join cost associated with the top join operator without applying the Bloom filter, and Cn′ is the top join cost after applying the Bloom filter.

15. The system of claim 9 , wherein the join operation is an equi-join operation.

16. The system of claim 9 , wherein the join operation comprises a hash join, a sort merge join, and a reformatting based nested loop join.

17. A non-transitory computer readable storage medium having instructions encoded thereon, execution of which, by a processor, cause the processor to perform operations comprising:
building, by a computing device, an execution plan for a join operation having a plurality of levels, including a top level comprising a top join operator, a bottom level comprising a leaf scan operator, and an intermediate level comprising an intermediate operator between the top level and the bottom level;
determining, by the computing device, a row reduction effec

Assignees

• Cheng Xun
• Sybase Inc

Inventors

• Cheng Xun

Classifications

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title

• G06F17/30469 Primary

  Physics · mapped topic