Cache-Oblivious Nested-Loop Joins

Speaker:	Bingsheng HE
		Department of Computer Science and Engineering
		Hong Kong University of Science and Technology

Title:		"Cache-Oblivious Nested-Loop Joins"

Date:		Monday, 18 September 2006

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F
		(Leung Yat Sing Lecture Theatre, near lift nos. 25/26)
		HKUST

ABSTRACT:

We propose to adapt the newly emerged cache-oblivious model to relational
query processing.  Our goal is to automatically achieve an overall
performance comparable to that of fine-tuned algorithms on a multi-level
memory hierarchy.  This automaticity is because cache-oblivious algorithms
assume no knowledge about any specific parameter values, such as the
capacity and block size of each level of the hierarchy. As a first step,
we propose recursive partitioning to implement cache-oblivious nested-loop
joins (NLJs) without indexes, and recursive clustering and buffering to
implement cache-oblivious NLJs with indexes. Our theoretical results and
empirical evaluation on three different architectures show that our
cache-oblivious NLJs match the performance of their manually optimized,
cache-conscious counterparts.

This is joint work with Dr. Qiong LUO.


**********************
Biography:

Bingsheng HE is currently a fourth-year PhD student at the Department of
Computer Science and Engineering, the Hong Kong University of Science &
Technology. His supervisor is Dr. Qiong LUO. His research interests are in
cache-centric in-memory query processing techniques, including their
applications in XML and scientific computing.