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:
“But the mark of American merit in painting, in sculpture, in poetry, in fiction, in eloquence, seems to be a certain grace without grandeur, and itself not new but derivative; a vase of fair outline, but empty,—which whoso sees, may fill with what wit and character is in him, but which does not, like the charged cloud, overflow with terrible beauty, and emit lightnings on all beholders.”
—Ralph Waldo Emerson (1803–1882)
“When we start deceiving ourselves into thinking not that we want something or need something, not that it is a pragmatic necessity for us to have it, but that it is a moral imperative that we have it, then is when we join the fashionable madmen, and then is when the thin whine of hysteria is heard in the land, and then is when we are in bad trouble.”
—Joan Didion (b. 1934)