Adaptive Aggregation on Chip Multiprocessors

Speaker:	Prof. Kenneth ROSS
		Columbia University

Title:		"Adaptive Aggregation on Chip Multiprocessors"

Date:		Wednesday, 16 July 2008

Time:		4:00pm - 5:00pm

Venue:		Room 5510 (via lifts 25/26), HKUST

Abstract:

The recent introduction of commodity chip multiprocessors requires that
the design of core database operations be carefully examined to take full
advantage of on-chip parallelism.  We examine aggregation in a multi-core
environment, the Sun UltraSPARC T1, a chip multiprocessor with eight cores
and a shared L2 cache. Aggregation is an important aspect of query
processing that is seemingly easy to understand and implement. Our
research, however, demonstrates that a chip multiprocessor adds new
dimensions to understanding hash-based aggregation performance: concurrent
sharing of aggregation data structures and contentious accesses to
frequently used values. We also identify a trade off between private data
structures assigned to each thread versus shared data structures for
aggregation.  Depending on input characteristics, different aggregation
strategies are optimal and choosing the wrong strategy can result in a
performance penalty of over an order of magnitude. We provide a thorough
explanation of the factors affecting aggregation performance on chip
multiprocessors and identify three key input characteristics that dictate
performance: (1) average run length of identical group-by values, (2)
locality of references to the aggregation hash table, and (3) frequency of
repeated accesses to the same hash table location. We then introduce an
adaptive aggregation operator that performs lightweight sampling of the
input to choose the correct aggregation strategy with high accuracy.  Our
experiments verify that our adaptive algorithm chooses the highest
performing aggregation strategy on a number of common input distributions.

This is joint work with John Cieslewicz.

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

Kenneth ROSS is a Professor in the Computer Science Department at Columbia
University in New York City. His research interests touch on various
aspects of database systems, including query processing, query language
design, data warehousing, and architecture-sensitive database system
design.  Professor ROSS received his PhD from Stanford University.  He has
received several awards, including a Packard Foundation Fellowship, a
Sloan Foundation Fellowship, and an NSF Young Investigator award.