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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.