Ryan Johnson
Ippokratis Pandis
Babak Falsafi
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.
- S. Agrawal, S. Chaudhuri, and V. R. Narasayya. "Automated selection of materialized views and indexes in SQL databases." In Proc. VLDB, 2000. Google Scholar
Digital Library
- P. A. Boncz, S. Manegold, and M. L. Kersten. "Database Architecture Optimized for the New Bottleneck: Memory Access." In Proc. VLDB, 1999. Google ScholarDigital Library
- W. Brigde, A. Joshi, M. Keihl, T. Lahiri, J. Loaiza and N. MacNaughton. "The Oracle Universal Server Buffer." In Proc. VLDB, 1997. Google ScholarDigital Library
- J. Chen, D. DeWitt, F. Tian, and Y. Wang. "NiagaraCQ: A scalable continuous query system for internet databases." In Proc. SIGMOD, 2000. Google ScholarDigital Library
- C. Cook. "Database Architecture: The Storage Engine." Microsoft SQL Server 2000 Technical Article, 2001.Google Scholar
- N. Dalvi, S. K. Sanghai, P. Roy, and S. Sudarshan. "Pipelining in Multi-Query Optimization." In Proc. PODS, 2001. Google ScholarDigital Library
- P. M. Fernandez. "Red Brick Warehouse: A Read-Mostly RDBMS for Open SMP Platforms." In Proc. SIGMOD, 1994. Google ScholarDigital Library
- N. Hardavellas, I. Pandis, R. Johnson, N. Mancheril, A. Ailamaki, and B. Falsafi. "Database Servers on Chip Multiprocessors: Limitations and Opportunities." In Proc. CIDR, 2007.Google Scholar
- S. Harizopoulos, and A. Ailamaki. "A Case for Staged Database Systems." In Proc. CIDR, 2003.Google Scholar
- S. Harizopoulos, V. Liang, D. Abadi, and S. Madden. "Performance Tradeoffs in Read-Optimized Databases." In Proc. VLDB, 2006. Google ScholarDigital Library
- S. Harizopoulos, V. Shkapenyuk, and A. Ailamaki. "QPipe: A Simultaneously Pipelined Relational Query Engine." In Proc. SIGMOD, 2005. Google ScholarDigital Library
- W. Hasan, and R. Motwani. "Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism." In Proc. VLDB, 1994. Google ScholarDigital Library
- Z. Ives, D. Florescu, M. Friedman, A. Levy, and D. S. Weld. "An Adaptive Query Execution System for Data Integration." In Proc. SIGMOD, 1999. Google ScholarDigital Library
- C. Lang, B. Bhattacharjee, T. Malkemus, S. Padmanabhan, and K. Wong. "Increasing Buffer-Locality for Multiple Relational Table Scans through Grouping and Throttling." In Proc. ICDE, 2007.Google ScholarCross Ref
- S. R. Madden, M. A. Shah, J. M. Hellerstein, and V. Raman. "Continuously Adaptive Continuous Queries over Streams." In Proc. SIGMOD, 2002. Google ScholarDigital Library
- S. Padmanabhan, T. Malkemus, R. Agarwal, and A. Jhingran. "Block Oriented Processing of Relational Database Operations in Modern Computer Architectures." In Proc. ICDE, 2001. Google ScholarDigital Library
- P. Ranganathan, K. Gharachorloo, S. V. Adve, and L. A. Barroso. "Performance of Database Workloads on Shared-Memory Systems with Out-of-Order Processors." In Proc. ASPLOS, 1998. Google ScholarDigital Library
- N. Roussopoulos. "View Indexing in Relational databases." In ACM TODS, 7(2):258--290, 1982. Google ScholarDigital Library
- P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. "Efficient and Extensible Algorithms for Multi Query Optimization." In Proc. SIGMOD, 2000. Google ScholarDigital Library
- T. K. Sellis. "Multiple Query Optimization." In ACM TODS, 13(1):23--52, 1988. Google ScholarDigital Library
- M. Shao, A. Ailamaki and B. Falsafi. "DBmbench: Fast and Accurate Database Workload Representation on Modern Microarchitecture." In Proc. of CASCON, 2005. Google ScholarDigital Library
- M. Spiliopoulou, M. Hatzopoulos, and C. Vassilakis. "A Cost Model for the Estimation of Query Execution Time in a Parallel Environment Supporting Pipeline." In Computers & Artificial Intelligence, 14(1), 1996.Google Scholar
- TPC (Transaction Processing Performance Council). TPC Benchmark H (Decision Support) Standard Specification, Revision 2.6.0, 2006.Google Scholar
- T. Urhan, and M. J. Franklin. "XJoin: A Reactively-Scheduled Pipelined Join Operator." In IEEE Data Eng. Bull. 23(2), 2000.Google Scholar
- A. N. Wilschut, and P. M. G. Apers. "Dataflow Query Execution in a Parallel Main-Memory Environment." In Proc. of PDIS, 1991. Google ScholarDigital Library
- A. N. Wilschut, and S. A. van Gils. "A Model for Pipelined Query Execution." In Proc. MASCOTS, 1993. Google ScholarDigital Library
- J. Zhou, and K. A. Ross. "Buffering Database Operations for Enhanced Instruction Cache Performance." In Proc. SIGMOD, 2004. Google ScholarDigital Library
- M. Zukowski, P. A. Boncz, and M. L. Kersten. "Cooperative Scans." CWI TR INS-E0411, 2004.Google Scholar
Recommendations
Ideal Secret Sharing Schemes with Share Selectability
Information and Communications SecurityAbstractIn this paper, we investigate a new concept, called share selectable secret sharing, where no unauthorized set can obtain information of the secret (in the information-theoretic sense) even if shares are selectable as arbitrary values which are ...
The Size of a Share Must Be Large
A secret sharing scheme permits a secret to be shared among participants of an n -element group in such a way that only qualified subsets of participants can recover the secret. If any nonqualified subset has absolutely no information on the secret, ...
Image Secret Sharing Construction for General Access Structure with Meaningful Share
This article describes how the (k, n) threshold image secret sharing technology can recover the secret image even n − k shares are lost, or n−k servers do not work, which is useful for cloud storage, etc. Image secret sharing for general access ...
Comments