QPipe: a simultaneously pipelined relational query engine

ABSTRACT

Relational DBMS typically execute concurrent queries independently by invoking a set of operator instances for each query. To exploit common data retrievals and computation in concurrent queries, researchers have proposed a wealth of techniques, ranging from buffering disk pages to constructing materialized views and optimizing multiple queries. The ideas proposed, however, are inherently limited by the query-centric philosophy of modern engine designs. Ideally, the query engine should proactively coordinate same-operator execution among concurrent queries, thereby exploiting common accesses to memory and disks as well as common intermediate result computation.This paper introduces on-demand simultaneous pipelining (OSP), a novel query evaluation paradigm for maximizing data and work sharing across concurrent queries at execution time. OSP enables proactive, dynamic operator sharing by pipelining the operator's output simultaneously to multiple parent nodes. This paper also introduces QPipe, a new operator-centric relational engine that effortlessly supports OSP. Each relational operator is encapsulated in a micro-engine serving query tasks from a queue, naturally exploiting all data and work sharing opportunities. Evaluation of QPipe built on top of BerkeleyDB shows that QPipe achieves a 2x speedup over a commercial DBMS when running a workload consisting of TPC-H queries.

References

1. S. Agrawal, S. Chaudhuri, and V. R. Narasayya. "Automated selection of materialized views and indexes in SQL databases." In Proc. VLDB, 2000.
2. J. A. Blakeley, P. Larson, and F. W. Tompa. "Efficiently updating materialized views." In Proc SIGMOD, 1986.
3. M. Carey et al. "Shoring Up Persistent Applications." In Proc. SIGMOD, 1994.
4. S. Chandrasekaran and M. J. Franklin. "Streaming Queries over Streaming Data." In Proc. VLDB, 2002.
5. J. Chen, D. DeWitt, F. Tian, and Y. Wang. "NiagaraCQ: A scalable continuous query system for internet databases." In Proc. SIGMOD, 2000.
6. H. T. Chou and D. J. DeWitt. "An evaluation of buffer management strategies for relational database systems." In Proc. SIGMOD, 1985.
7. C. Cook. "Database Architecture: The Storage Engine." Miscrosoft SQL Server 2000 Technical Article, July 2001. Available at: http://msdn.microsoft. com/library
8. N. Dalvi, S. K. Sanghai, P. Roy, and S. Sudarshan. "Pipelining in Multi-Query Optimization." In PODS, 2001.
9. S. Dar, M. J. Franklin, B. T. Jonsson, D. Srivastava, and M. Tan. "Semantic Data Caching and Replacement." In Proc. VLDB, 1996.
10. D. J. DeWitt, S. Ghandeharizadeh, D. A. Schneider, A. Bricker, H. Hsiao, and R. Rasmussen. "The Gamma Database Machine Project." In IEEE TKDE, 2(1), pp. 44--63, Mar. 1990.
11. D. J. DeWitt. "The Wisconsin Benchmark: Past, Present, and Future." The Benchmark Handbook, J. Gray, ed., Morgan Kaufmann Pub., San Mateo, CA (1991).
12. P. M. Fernandez. "Red Brick Warehouse: A Read-Mostly RDBMS for Open SMP Platforms." In SIGMOD, 1994.
13. S. Finkelstein. "Common expression analysis in database applications." In Proc. SIGMOD, 1982.
14. G. Graefe. "Iterators, Schedulers, and Distributed-memory Parallelism." In Software-practice and experience, Vol. 26 (4), pp. 427--452, Apr. 1996.
15. G. Graefe. "Volcano - An Extensible and Parallel Query Evaluation System." In TKDE 6(1): 120--135, 1994.
16. J. Gray. "The Next Database Revolution." Keynote, SIGMOD, 2004.
17. S. Harizopoulos and A. Ailamaki. "A Case for Staged Database Systems." In Proc. CIDR, 2003.
18. T. Johnson and D. Shasha. "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm." In Proc. VLDB, 1994.
19. N. Kabra and D. J. DeWitt. "Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans." In Proc. SIGMOD, 1998.
20. S. R. Madden, M. A. Shah, J. M. Hellerstein, and V. Raman. "Continuously Adaptive Continuous Queries over Streams." In Proc. SIGMOD, 2002.
21. N. Megiddo and D. S. Modha. "ARC: A Self-Tuning, Low Overhead Replacement Cache." In Proc. FAST, 2003.
22. E. J. O'Neil, P. E. O'Neil, and G. Weikum. "The LRU-K page replacement algorithm for database disk buffering." In Proc. SIGMOD, 1993.
23. N. Roussopoulos. "View indexing in relational databases." In ACM Trans. on Database Systems 7(2):258--290,1982.
24. P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. "Efficient and Extensible Algorithms for Multi Query Optimization." In Proc. SIGMOD, 2000.
25. G. M. Sacco and M. Schkolnick. "Buffer management in relational database systems." In ACM TODS, 11(4):473--498, Dec. 1986.
26. P. Sarda, J. R. Haritsa. "Green Query Optimization: Taming Query Optimization Overheads through Plan Recycling," In Proc. VLDB, 2004.
27. T. K. Sellis. "Multiple Query Optimization." In ACM TODS, 13(1):23--52, Mar. 1988.
28. P. Seshadri, M. Livny, and R. Ramakrishnan. "The Case for Enhanced Abstract Data Types." In Proc. VLDB, 1997.
29. J. Shim, P. Scheuermann, and R. Vingralek. "Dynamic caching of query results for decision support systems." In Proc. SSDBM, 1999.
30. V. Shkapenyuk, R. Williams, S. Harizopoulos, and A. Ailamaki. "Deadlock Resolution in Pipelined Query Graphs." Carnegie Mellon University Technical Report, CMU-CS-05-122, 2005.
31. J. Zhou and K. A. Ross. "Buffering Database Operations for Enhanced Instruction Cache Performance." In Proc. SIGMOD, 2004.

• Information systems

  • Data management systems

    • Database management system engines

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory