Join with Bloom-filters
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.