1. A method of performing a database join, comprising: receiving a query specifying a join of a first table and a second table; determining a new predicate for the query based on a bit map, for a plurality of tuples of the join, between a first column of the first table, and a second column of the second table; and modifying the query such that the query comprises the new predicate; generating the bit map, wherein generating the bit map comprises: determining a plurality of potential value pairs between the first column and the second column; determining a plurality of actual value pairs in a plurality of tuples resulting from the join query; and setting a bit in the bit map to 1 for each of the plurality of actual value pairs.