Query processing in firm real-time database systems
HweeHwa Pang · 1994
this memory is used to hold the hash table for the first partition; the R and S tuples that belong to this partition can thus be joined in memory directly as S is being scanned. The Hybrid Hash Join algorithm was shown to have performance superior to that of GRACE [DeWi84]. The Hybrid Hash Join algorithm is designed to make full use of the memory that a join has available when it first starts execution. During the course of execution, however, there may be a mismatch between the amount of memory that the DBMS can allocate to the join and the size of its R partitions. One possible cause of this discrepancy is due to incorrect estimation of the hash attribute distribution. This results in a situation where some R partitions are larger than the allocated memory, while other R partitions are under-sized. In [Naka88], a modification of Hybrid Hash Join was proposed to deal with this memory misfit problem. Instead of deciding on the number of partitions at the beginning, the proposed modification splits the inner relation into smaller subsets, called buckets, which will later be grouped into partitions. The number of buckets is a parameter of the algorithm. Each bucket is assigned a memory-resident hash table that is initially empty. As