Cost of Hash Join in Software

Creator Code-128 in Software Cost of Hash Join

We now consider the cost of a hash join Our analysis assumes that there is no hashtable over ow First, consider the case where recursive partitioning is not required The partitioning of the two relations r and s calls for a complete reading of both relations, and a subsequent writing back of them This operation requires 2(br + bs ) block accesses, where br and bs denote the number of blocks containing records of relations r and s respectively The build and probe phases read each of the partitions once, calling for a further br + bs accesses The number of blocks occupied by partitions could be slightly more than br + bs , as a result of partially lled blocks Accessing such partially lled blocks can add an overhead of at most 2nh for each of the relations, since each of the nh partitions could have a partially lled block that has to be written and read back Thus, the cost estimate for a hash join is 3(br + bs ) + 4nh

The McGraw Hill Companies, 2001

The overhead 4nh is quite small compared to br + bs , and can be ignored Now consider the case where recursive partitioning is required Each pass reduces the size of each of the partitions by an expected factor of M 1; and passes are repeated until each partition is of size at most M blocks The expected number of passes required for partitioning s is therefore logM 1 (bs ) 1 Since, in each pass, every block of s is read in and written out, the total block transfers for partitioning of s is 2bs logM 1 (bs ) 1 The number of passes for partitioning of r is the same as the number of passes for partitioning of s, therefore the cost estimate for the join is Consider, for example, the join customer 1 depositor With a memory size of 20 blocks, depositor can be partitioned into ve partitions, each of size 20 blocks, which size will t into memory Only one pass is required for the partitioning The relation customer is similarly partitioned into ve partitions, each of size 80 Ignoring the cost of writing partially lled blocks, the cost is 3(100 + 400) = 1500 block transfers The hash join can be improved if the main memory size is large When the entire build input can be kept in main memory, nh can be set to 0; then, the hash join algorithm executes quickly, without partitioning the relations into temporary les, regardless of the probe input s size The cost estimate goes down to br + bs 2(br + bs ) logM 1 (bs ) 1 + br + bs

The hybrid hash join algorithm performs another optimization; it is useful when memory sizes are relatively large, but not all of the build relation ts in memory The partitioning phase of the hash join algorithm needs one block of memory as a buffer for each partition that is created, and one block of memory as an input buffer Hence, a total of nh + 1 blocks of memory are needed for the partitioning the two relations If memory is larger than nh + 1, we can use the rest of memory (M nh 1 blocks) to buffer the rst partition of the build input (that is, Hs0 ), so that it will not need to be written out and read back in Further, the hash function is designed in such a way that the hash index on Hs0 ts in M nh 1 blocks, in order that, at the end of partitioning of s, Hs0 is completely in memory and a hash index can be built on Hs0 When the system partitions r it again does not write tuples in Hr0 to disk; instead, as it generates them, the system uses them to probe the memory-resident hash index on Hs0 , and to generate output tuples of the join After they are used for probing, the tuples can be discarded, so the partition Hr0 does not occupy any memory space Thus, a write and a read access have been saved for each block of both Hr0 and Hs0 The system writes out tuples in the other partitions as usual, and joins them later The savings of hybrid hash join can be signi cant if the build input is only slightly bigger than memory If the size of the build relation is bs , nh is approximately equal to bs /M Thus, hybrid hash join is most useful if M >> bs /M , or M >> bs , where the notation >> denotes much larger than For example, suppose the block size is 4 kilobytes, and the build relation size is 1 gigabyte Then, the hybrid hash join algorithm is useful if the size of memory is signi cantly more than 2 megabytes; memory sizes of 100 megabytes or more are common on computers today