Cache-Oblivious Databases: Limitations and Opportunities

Cache-oblivious techniques, proposed in the theory community, have optimal asymptotic bounds on the amount of data transferred between any two adjacent levels of an arbitrary memory hierarchy. Moreover, this optimal performance is achieved without any hardware platform specific tuning. These properties are highly attractive to autonomous databases, especially because the hardware architectures are becoming increasingly complex and diverse. In this paper, the authors present their design, implementation, and evaluation of the first cache-oblivious in-memory query processor, EaseDB. Moreover, they discuss the inherent limitations of the cache-oblivious approach as well as the opportunities given by the upcoming hardware architectures.