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: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 2: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 3: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 4: S. Chandrasekaran and M. J. Franklin. "Streaming Queries over Streaming Data." In Proc. VLDB, 2002.
• 5: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 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: Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.59-70, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375561]
• 9: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 10: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• 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: Phillip M. Fernandez, Red brick warehouse: a read-mostly RDBMS for open SMP platforms, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.492, May 24-27, 1994, Minneapolis, Minnesota, United States
• 13: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• 14: Goetz Graefe, Iterators, schedulers, and distributed-memory parallelism, Software—Practice & Experience, v.26 n.4, p.427-452, April 1996 [doi>10.1002/(SICI)1097-024X(199604)26:4<427::AID-SPE20>3.3.CO;2-8]
• 15: G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994 [doi>10.1109/69.273032]
• 16: Jim Gray, The next database revolution, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007570]
• 17: S. Harizopoulos and A. Ailamaki. "A Case for Staged Database Systems." In Proc. CIDR, 2003.
• 18: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 19: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 20: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 21: Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 22: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 23: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• 24: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 25: Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986 [doi>10.1145/7239.7336]
• 26: P. Sarda, J. R. Haritsa. "Green Query Optimization: Taming Query Optimization Overheads through Plan Recycling," In Proc. VLDB, 2004.
• 27: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 28: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Case for Enhanced Abstract Data Types, Proceedings of the 23rd International Conference on Very Large Data Bases, p.66-75, August 25-29, 1997
• 29: Junho Shim , Peter Scheuermann , Radek Vingralek, Dynamic Caching of Query Results for Decision Support Systems, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.254, July 28-30, 1999 [doi>10.1109/SSDM.1999.787641]
• 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: Jingren Zhou , Kenneth A. Ross, Buffering databse operations for enhanced instruction cache performance, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007592]