Cache-Oblivious Query Processing

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Cache-Oblivious Query Processing"

By

Mr. Bingsheng He


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.


Date:			Wednesday, 16 July 2008

Time:			10:30a.m.-12:30p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Yang LENG (MECH)

Committee Members:	Prof. Qiong LUO (Supervisor)
			Prof. Frederick H. LOCHOVSKY
			Prof. Lionel M. NI
			Prof. Jiang XU (ECE)
			Prof. Kenneth A. ROSS (Comp. Sci., Columbia Univ.)
			Prof Jeffrey Xu YU (Sys. Engg. & Engg. Mgmt., CUHK)


**** ALL are Welcome ****