DPG: A Cache-Efficient Accelerator for Sorting and for Join Operators

Retrieval of records on disk is well-known to be at the heart of many database problems. We show that the cor-responding movement of records in main memory has now become a severe bottleneck for many database operations. This is due to the stagnating latency of main memory, even while CPU speed, main memory bandwidth, and disk speed all continue to improve. As a result, record movement has become the dominant cost in main memory sorting. We present a new algorithm for fast record retrieval, distribute-probe-gather, or DPG. DPG has important ap-plications both in sorting and in joins. Current main mem-ory sorting algorithms split their work into three phases: extraction of key-pointer pairs; sorting of the key-pointer pairs; and copying of the original records into the destina-tion array according the sorted key-pointer pairs. The copy-ing in the last phase dominates today’s sorting time. Hence, the use of DPG in the third phase provides an accelerator for existing sorting algorithms. DPG also provides two new join methods for foreign key joins: DPG-move join and DPG-sort join. The resulting join methods with DPG are faster because DPG join is cache-efficient and at the same time DPG join avoids the need for sorting or for hashing. The ideas presented for foreign key join can also be extended to faster record pair retrieval for spatial and temporal databases.