Patent ID: 8145642

Claim:
A method of combining information from a first source with information from a second source, wherein each piece of information from the first source is associated with a join key value, and each piece of information from the second source is associated with a join key value, the method comprising: hashing the pieces of information from the first source to hash buckets of a hash table by applying a hash function to join key values associated with the pieces of information from the first source; building a plurality of bitmap filter chunks that indicate the hash buckets to which the pieces of information from the first source are hashed; wherein the plurality of bitmap filter chunks are spread among a plurality of nodes; merging the plurality of bitmap filter chunks to create a bitmap filter; causing each of a plurality of probe-phase producer slaves to repeatedly perform the steps of obtaining a piece of information from the second source; determining the hash bucket to which the piece of information from the second source hashes by applying the hash function to the join key value associated with the piece of information from the second source; inspecting the bitmap filter to determine whether the piece of information from the second source hashes to a hash bucket to which a piece of information from the first source was hashed; and sending the piece of information from the second source to a probe-phase consumer slave, of a plurality of probe-phase consumer slaves, only if the second source hashes to a hash bucket to which at least one piece of information from the first source was hashed; wherein the plurality of probe-phase consumer slaves generate combined information by combining, based on join key values, (a) the pieces of information from the first source that the plurality of probe-phase consumer slaves receive from the probe side producer slaves with (b) the pieces of information of the second source; wherein the combined information is stored in a non-transitory computer-readable storage medium; wherein the method is performed by one or more computing devices.