Join with Bloom-filters

Question

can you tell me how i can use a bloom-filter by a joining operation with two tables?

let's assume that:

Table A ={A_id,B_id,age}, Table B = {B_id, color}.

now i want to use a bloom-filter so i can do the join operation faster, but i do not know how i can use this in this case. I would first take from A the PK A_id and bloom-filter that with some hash functions and just mark the indexes with 1 and then i would do the same operation with Table B and finally just AND both results. but it's not correct...

Answer 1

A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives. A join (specifically, an equi-join) which is expected to have some non-matching keys can be sped up by pre-processing the valid keys from one table into a Bloom filter. The join operator tests each key from the other table against the Bloom filter first and only does a full lookup for each positive ("maybe in the set") result.

For instance if you are joining on B_id above, you might first preprocess all of the B_id's in table B into a Bloom filter, and use it to test each B_id in table A for a possible match. If a B_id from A tests negative in the filter, you can discard it, so you only consult table B for B_id's which are either in B or are false positives.

The benefit of using a pre-filter is basically in the number of negatives it can eliminate at a lower per-key cost than a full lookup. The filter may also be a smaller size than the set of keys it represents, so it can be broadcast to all threads or nodes that are processing the join in a distributed environment.

Ives and Taylor summarize a number of techniques like this in Sideways Information Passing for Push-Style Query Processing.