Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results

Minimizing both the response time to produce the first few thousand results and the overall execution time is important for interactive querying. Cur-rent join algorithms either minimize the execution time at the expense of response time or minimize response time by producing results early without optimizing the total time. We present a hash-based join algorithm, called early hash join, which can be dynamically configured at any point dur-ing join processing to tradeoff faster production of results for overall execution time. We demon-strate that varying how inputs are read has a major effect on these two factors and provide formulas that allow an optimizer to calculate the expected rate of join output and the number of I/O op-erations performed using different input reading strategies. Experimental results show that early hash join performs significantly fewer I/O oper-ations and executes faster than other early join algorithms, especially for one-to-many joins. Its overall execution time is comparable to standard hybrid hash join, but its response time is an or-der of magnitude faster. Thus, early hash join can replace hybrid hash join in any situation where a fast initial response time is beneficial without the penalty in overall execution time exhibited by other early join algorithms.