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:
“Loving in truth, and fain in verse my love to show,
That she, dear she, might take some pleasure of my pain,
Pleasure might cause her read, reading might make her know,
Knowledge might pity win, and pity grace obtain,
I sought fit words to paint the blackest face of woe:”
—Sir Philip Sidney (1554–1586)
“In another year I’ll have enough money saved. Then I’m gonna go back to my hometown in Oregon and I’m gonna build a house for my mother and myself. And join the country club and take up golf. And I’ll meet the proper man with the proper position. And I’ll make a proper wife who can run a proper home and raise proper children. And I’ll be happy, because when you’re proper, you’re safe.”
—Daniel Taradash (b. 1913)