Cache-Conscious Radix-Decluster Projections

This chapter deals with the problem of performing large equi-joins with projections in a cache-conscious manner. Performance may vary by more than an order of magnitude with different relation projectivity, thus proving that projection cost can have a strong impact on overall join efficiency. The main contribution, the Radix-Decluster algorithm, is the crucial tool of MonetDB to process huge tables with a good access pattern, both in terms of CPU cache access as well as I/O access. The chapter evaluates various cache-conscious join (projection) strategies both on the N-ary Storage Model (NSM) and Decomposition Storage Model (DSM) storage schemes. It concludes that Partitioned Hash-Join significantly improves performance for MonetDB and DSM as well as for the NSM pre-projection strategy. Moreover, the performance evaluation shows that Radix-Decluster is pivotal in making DSM post-projection the most efficient overall strategy