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.
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Manegold, S, Boncz, P.A, Nes, N.J, & Kersten, M.L. (2004). Cache-Conscious Radix-Decluster Projections. In Proceedings 2004 VLDB Conference: The 30th International Conference on Very Large Databases (VLDB) (pp. 684–695). doi:10.1016/B978-012088469-8.50061-9