Optimizing complex queries with multiple relation instances

ABSTRACT

Today's query processing engines do not take advantage of the multiple occurrences of a relation in a query to improve performance. Instead, each instance is treated as a distinct relation and has its own independent table access method. In this paper, we present MAPLE, a Multi-instance-Aware PLan Evaluation engine that enables multiple instances of a relation to share one physical scan (called SharedScan) with limited buffer space. During execution, as SharedScan pulls a tuple for any instance, that tuple is also pushed to the buffers of other instances with matching predicates. To avoid buffer overflow, a novel interleaved execution strategy is proposed: whenever an instance's buffer becomes full, the execution is temporarily switched to a drainer (an ancestor blocking operator of the instance) to consume all the tuples in the buffer. Thus, the execution is interleaved between normal processing and drainers. We also propose a cost-based approach to generate a plan to maximize the shared scan benefit as well as to avoid interleaved execution deadlocks. MAPLE is light-weight and can be easily integrated into existing RDBMS executors. We have implemented MAPLE in PostgreSQL, and our experimental study on the TPC-DS benchmark shows significant reduction in execution time.

REFERENCES

• 1: Microsoft SQL Server Library. http://msdn2.microsoft.com/en-us/library/bb545450.aspx.
• 2: PostgreSQL. http://www.postgresql.org/.
• 3: TPC BENCHMARK Decision Support. http://www.tpc.org/tpcds/.
• 4: Ramesh Bhashyam, TPC-D—the challenges, issues and results, ACM SIGMOD Record, v.25 n.4, p.89-93, Dec. 1996 [doi>10.1145/245882.245908]
• 5: Eugene Inseok Chong , Souripriya Das , George Eadon , Jagannathan Srinivasan, An efficient SQL-based RDF querying scheme, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 6: Latha S. Colby , Richard L. Cole , Edward Haslam , Nasi Jazayeri , Galt Johnson , William J. McKenna , Lee Schumacher , David Wilhite, Redbrick Vista: Aggregate Computation and Management, Proceedings of the Fourteenth International Conference on Data Engineering, p.174-177, February 23-27, 1998
• 7: Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Journal of Computer and System Sciences, v.66 n.4, p.728-762, 1 June 2003 [doi>10.1016/S0022-0000(03)00031-X]
• 8: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 9: Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004 [doi>10.1145/974750.974754]
• 10: Stavros Harizopoulos , Vladislav Shkapenyuk , Anastassia Ailamaki, QPipe: a simultaneously pipelined relational query engine, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066201]
• 11: C. A. Lang, B. Bhattacharjee, T. Malkemus, S. Padmanabhan, and K. Wong. Increasing buffer-locality for multiple relational table scans through grouping and throttling. In ICDE, pages 1136--1145, 2007.
• 12: Christian A. Lang , Bishwaranjan Bhattacharjee , Tim Malkemus , Kwai Wong, Increasing buffer-locality for multiple index based scans through intelligent placement and index scan speed control, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 13: 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
• 14: 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
• 15: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, ACM SIGMOD Record, v.27 n.2, p.130-141, June 1998
• 16: K. Wilkinson, C. Sayers, H. A. Kuno, and D. Reynolds. Efficient rdf storage and retrieval in jena2. In SWDB, pages 131--150, 2003.
• 17: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States
• 18: Jingren Zhou , Per-Ake Larson , Johann-Christoph Freytag , Wolfgang Lehner, Efficient exploitation of similar subexpressions for query processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247540]
• 19: Marcin Zukowski , Sándor Héman , Niels Nes , Peter Boncz, Cooperative scans: dynamic bandwidth sharing in a DBMS, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
interleaved execution, query optimization, query processing, shared scan