Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB’07), Vienna, Austria, September 2007.
Ryan Johnson*, Stavros Harizopoulos†, Nikos Hardavellas*, Kivanc Sabirli*†, Ippokratis Pandis*, Anastasia Ailamaki*‡, Naju G. Mancheril*, Babak Falsafi*‡
*Carnegie Mellon University
†Massachusetts Institute of Technology
‡Ecole Polytechnique Fédérale de Lausanne
http://www.pdl.cmu.edu/
Intuitively, aggressive work sharing among concurrent queries in a
database system should always improve performance by
eliminating redundant computation or data accesses. We show
that, contrary to common intuition, this is not always the case in
practice, especially in the highly parallel world of chip multiprocessors.
As the number of cores in the system increases, a
trade-off appears between exploiting work sharing opportunities
and the available parallelism. To resolve the trade-off, we develop
an analytical approach that predicts the effect of work sharing in
multi-core systems. Database systems can use the model to
determine, statically or at runtime, whether work sharing is
beneficial and apply it only when appropriate.
The contributions of this paper are as follows. First, we introduce and analyze the effects of the trade-off between work sharing and parallelism on database systems running complex decision-support queries. Second, we propose an intuitive and simple model that can evaluate the trade-off using real-world measurement approximations of the query execution processes. Furthermore, we integrate the model into a prototype database execution engine, and demonstrate that selective work sharing according to the model outperforms never-share static schemes by 20% on average and always-share ones by 2.5x.
FULL PAPER: pdf