HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3552
Title: Cache-oblivious query processing
Authors: He, Bingsheng
Issue Date: 2008
Abstract: As CPU caches have become a performance bottleneck for main memory databases, optimizing the cache performance is essential for high-performance query processing on relational databases. Cache-oblivious techniques, proposed by 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 thesis, we present the design, implementation, and evaluation of the first cache-oblivious, in-memory query processor, EaseDB. All query processing algorithms in EaseDB are designed to be cache-oblivious and match the performance of their cache-conscious counterparts. Moreover, we discuss the inherent limitations of the cache-oblivious approach as well as the opportunities given by the upcoming hardware architectures. Specifically, a cache-oblivious technique usually requires sophisticated algorithm design to achieve a comparable performance to its cache-conscious counterpart. Nevertheless, this development-time effort is compensated by the automaticity of performance achievement and the reduced ownership cost. We evaluate EaseDB in comparison with its cache-conscious counterparts on different architectures including Intel, AMD and Ultra-Sparc processors. Our results, with homegrown workloads and micro benchmarks, show that our cache-oblivious algorithms achieve a performance comparable to their fine-tuned cache-conscious counterparts. Moreover, cache-oblivious techniques can outperform their cache-conscious counterparts in multi-threading processors.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008
xiv, 109 leaves : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2008 He
URI: http://hdl.handle.net/1783.1/3552
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.