An adaptive hash join algorithm for multiuser environments
H. Zeller, Jim Gray · Very Large Data Bases · 1990
As main memory becomes a cheaper resource, hash joins are an alternative to the traditional methods of performing equi-joins: nested loop and merge joins. This paper introduces a modified, adaptive hash join method that is designed to work with dynamic changes in the amount of available memory. The general idea of the algorithm is to regulate resource usage of a hash join in a way that allows it to run concurrently with other applications. The algorithm provides good performance for a broad range of problem sizes, allows to join large tables in a small main memory, and uses advanced I/O controllers with tracksize I/O transfers. It has been implemented as a prototype in Nonstop SQL, a DBMS running on Tandem machines.