To share or not to share?

Ryan Johnson, Nikos Hardavellas, Ippokratis Pandis, Naju G. Mancheril, Stavros Harizopoulos, Kivanc Sabirli, Anastasia Ailamaki, Babak Falsafi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Title of host publication33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings
EditorsJohannes Gehrke, Christoph Koch, Minos Garofalakis, Karl Aberer, Carl-Christian Kanne, Erich J. Neuhold, Venkatesh Ganti, Wolfgang Klas, Chee-Yong Chan, Divesh Srivastava, Dana Florescu, Anand Deshpande
PublisherAssociation for Computing Machinery, Inc
Pages351-362
Number of pages12
ISBN (Electronic)9781595936493
StatePublished - Jan 1 2007
Event33rd International Conference on Very Large Data Bases, VLDB 2007 - Vienna, Austria
Duration: Sep 23 2007Sep 27 2007

Publication series

Name33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

Other

Other33rd International Conference on Very Large Data Bases, VLDB 2007
CountryAustria
CityVienna
Period9/23/079/27/07

Fingerprint

Engines
Work sharing
Trade-offs
Data base
Query
Intuition
Approximation
Complex systems
Prototype
Decision support

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems and Management
  • Information Systems
  • Software

Cite this

Johnson, R., Hardavellas, N., Pandis, I., Mancheril, N. G., Harizopoulos, S., Sabirli, K., ... Falsafi, B. (2007). To share or not to share? In J. Gehrke, C. Koch, M. Garofalakis, K. Aberer, C-C. Kanne, E. J. Neuhold, V. Ganti, W. Klas, C-Y. Chan, D. Srivastava, D. Florescu, ... A. Deshpande (Eds.), 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings (pp. 351-362). (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings). Association for Computing Machinery, Inc.
Johnson, Ryan ; Hardavellas, Nikos ; Pandis, Ippokratis ; Mancheril, Naju G. ; Harizopoulos, Stavros ; Sabirli, Kivanc ; Ailamaki, Anastasia ; Falsafi, Babak. / To share or not to share?. 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. editor / Johannes Gehrke ; Christoph Koch ; Minos Garofalakis ; Karl Aberer ; Carl-Christian Kanne ; Erich J. Neuhold ; Venkatesh Ganti ; Wolfgang Klas ; Chee-Yong Chan ; Divesh Srivastava ; Dana Florescu ; Anand Deshpande. Association for Computing Machinery, Inc, 2007. pp. 351-362 (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).
@inproceedings{6b0692012768414cae99ba0506b9fac3,
title = "To share or not to share?",
abstract = "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.",
author = "Ryan Johnson and Nikos Hardavellas and Ippokratis Pandis and Mancheril, {Naju G.} and Stavros Harizopoulos and Kivanc Sabirli and Anastasia Ailamaki and Babak Falsafi",
year = "2007",
month = "1",
day = "1",
language = "English (US)",
series = "33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings",
publisher = "Association for Computing Machinery, Inc",
pages = "351--362",
editor = "Johannes Gehrke and Christoph Koch and Minos Garofalakis and Karl Aberer and Carl-Christian Kanne and Neuhold, {Erich J.} and Venkatesh Ganti and Wolfgang Klas and Chee-Yong Chan and Divesh Srivastava and Dana Florescu and Anand Deshpande",
booktitle = "33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings",

}

Johnson, R, Hardavellas, N, Pandis, I, Mancheril, NG, Harizopoulos, S, Sabirli, K, Ailamaki, A & Falsafi, B 2007, To share or not to share? in J Gehrke, C Koch, M Garofalakis, K Aberer, C-C Kanne, EJ Neuhold, V Ganti, W Klas, C-Y Chan, D Srivastava, D Florescu & A Deshpande (eds), 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings, Association for Computing Machinery, Inc, pp. 351-362, 33rd International Conference on Very Large Data Bases, VLDB 2007, Vienna, Austria, 9/23/07.

To share or not to share? / Johnson, Ryan; Hardavellas, Nikos; Pandis, Ippokratis; Mancheril, Naju G.; Harizopoulos, Stavros; Sabirli, Kivanc; Ailamaki, Anastasia; Falsafi, Babak.

33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. ed. / Johannes Gehrke; Christoph Koch; Minos Garofalakis; Karl Aberer; Carl-Christian Kanne; Erich J. Neuhold; Venkatesh Ganti; Wolfgang Klas; Chee-Yong Chan; Divesh Srivastava; Dana Florescu; Anand Deshpande. Association for Computing Machinery, Inc, 2007. p. 351-362 (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - To share or not to share?

AU - Johnson, Ryan

AU - Hardavellas, Nikos

AU - Pandis, Ippokratis

AU - Mancheril, Naju G.

AU - Harizopoulos, Stavros

AU - Sabirli, Kivanc

AU - Ailamaki, Anastasia

AU - Falsafi, Babak

PY - 2007/1/1

Y1 - 2007/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85011117116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011117116&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85011117116

T3 - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

SP - 351

EP - 362

BT - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

A2 - Gehrke, Johannes

A2 - Koch, Christoph

A2 - Garofalakis, Minos

A2 - Aberer, Karl

A2 - Kanne, Carl-Christian

A2 - Neuhold, Erich J.

A2 - Ganti, Venkatesh

A2 - Klas, Wolfgang

A2 - Chan, Chee-Yong

A2 - Srivastava, Divesh

A2 - Florescu, Dana

A2 - Deshpande, Anand

PB - Association for Computing Machinery, Inc

ER -

Johnson R, Hardavellas N, Pandis I, Mancheril NG, Harizopoulos S, Sabirli K et al. To share or not to share? In Gehrke J, Koch C, Garofalakis M, Aberer K, Kanne C-C, Neuhold EJ, Ganti V, Klas W, Chan C-Y, Srivastava D, Florescu D, Deshpande A, editors, 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. Association for Computing Machinery, Inc. 2007. p. 351-362. (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).