Grace Hash Join
A better approach is known as the "grace hash join", after the GRACE database machine for which it was first implemented. This algorithm avoids rescanning the entire relation by first partitioning both and via a hash function, and writing these partitions out to disk. The algorithm then loads pairs of partitions into memory, builds a hash table for the smaller partitioned relation, and probes the other relation for matches with the current hash table. Because the partitions were formed by hashing on the join key, it must be the case that any join output tuples must belong to the same partition. It is possible that one or more of the partitions still does not fit into the available memory, in which case the algorithm is recursively applied: an additional orthogonal hash function is chosen to hash the large partition into sub-partitions, which are then processed as before. Since this is expensive, the algorithm tries to reduce the chance that it will occur by forming as many partitions as possible during the initial partitioning phase.
Read more about this topic: Hash Join
Famous quotes containing the words grace and/or join:
“...and when James and Cephas and John, who were acknowledged pillars, recognized the grace that had been given to me, they gave to Barnabas and me the right hand of fellowship, agreeing that we should go to the Gentiles and they to the circumcised.”
—Bible: New Testament, Galatians 2:9.
“I used to join the murmurings about “Where are the qualified women?” As we murmured, we would all gaze about the room, up toward the chandelier, into the corner behind the potted palm, under the napkin, hoping perhaps that qualified women would pop out like leprechauns.”
—Jane O’Reilly, U.S. feminist and humorist. The Girl I Left Behind, ch. 5 (1980)