Bloom filter utilization for join processing

Patent metadata

Field	Value
Publication number	US-10242063-B2
Application number	US-201615214551-A
Country	US
Kind code	B2
Filing date	Jul 20, 2016
Priority date	Aug 31, 2015
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

A computer-implemented method includes inserting a bloom filter creation stage after an inner data source identification stage, wherein a join operation is to be performed to join an outer data source with the inner data source. The method inserts a bloom filter search stage after an outer data source identification stage, wherein each row of data from the outer data source is searched against a bloom filter for the inner data source during the bloom filter search stage. The method initializes a read on the inner data source. Subsequent to determining the bloom filter creation stage is complete, the method initializes a read on the outer data source. The method performs the join operation at a join stage.

First claim

What is claimed is:

1. A method comprising:
inserting, by one or more processors, a bloom filter creation stage after an inner data source identification stage, wherein a join operation is to be performed to join an outer data source with the inner data source;
responsive to determining a plurality of optimization conditions are satisfied, wherein the plurality optimization conditions at least specify that the join operation does not have any additive stages between the inner data source and a join stage, determining, by one or more processors, to insert a first bloom filter search stage after an outer data source identification stage;
inserting, by one or more processors, the first bloom filter search stage after the outer data source identification stage, wherein each row of data from the outer data source is searched against a first bloom filter for the inner data source during the first bloom filter search stage;
initializing, by one or more processors, a read on the inner data source, wherein a plurality of rows from the inner data source pass through to the join stage;
responsive to determining the bloom filter creation stage is complete, initializing, by one or more processors, a read on the outer data source against the first bloom filter, wherein the plurality of rows from the inner data source pass through to the bloom filter creation stage; and
performing, by one or more processors, the join operation of the inner data source and the outer data source at the join stage.

2. The method of claim 1 , further comprising:
creating, by one or more processors, an inner data set based at least on the inner data source and the first bloom filter.

3. The method of claim 1 , further comprising:
generating, by one or more processors, a second bloom filter based on reference data during a dataset creation job;
inserting, by one or more processors, the second bloom filter after a data source during the dataset creation job; and
updating, by one or more processors, a path to the second bloom filter in an inner dataset header for the inner data source.

4. The method of claim 3 , further comprising:
subsequent to determining the plurality optimization conditions are satisfied, determining, by one or more processors, to insert a second bloom filter search stage after the outer data source identification stage.

5. The method of claim 3 , further comprising:
subsequent to determining the plurality optimization conditions are not satisfied, determining, by one or more processors, to perform the join operation between the inner data source and the outer data source at the join stage without the second bloom filter.

6. The method of claim 1 , wherein the plurality optimization conditions are further selected from a group consisting of: join keys pass through unmodified from the inner data source to the join, join keys pass through unmodified from the outer data source to the join, and a cost of a specific join operation without a bloom filter is greater than a processing cost of the specific join operation with the bloom filter.

7. The method of claim 1 , further comprising:
sending, by one or more processors, the plurality of rows from the inner data source to the join stage, wherein the one or more rows are not searched against the first bloom filter;
responsive to determining, the bloom filter creation stage is complete, notifying, by one or more processors, the first bloom filter search stage that the bloom filter creation stage is complete; and
loading, by one or more processors, the first bloom filter at the first bloom filter search stage.

Assignees

• IBM

Inventors

• Bhide Manish A
• Mudambi Shyam R
• Padmanabhan Sriram K
• Tirumalaraju Vivek S

Classifications

• G06F16/2456 Primary

  Join operations · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F16/24542

  Plan optimisation · CPC title

• G06F16/2453

  Query optimisation · CPC title