Abstract
In many database queries relations are access multiple times during query processing. In these cases query processing can be accelerated by sharing scan operators and possibly other operators based upon the common relations. The standard approach to achieve sharing works as follows. In a first phase, a non-shared tree-shaped plan is generated via a traditional plan generator. In a second phase, common instances of a scan are detected and shared. After that, other possible operators are shared. The result is an operator DAG (directed acyclic graph).
The limitation of this approach is obvious. As sharing influences plan costs, a separation of the optimization into two phases comprises the danger of missing the optimal plan, since the first optimization phase does not know about sharing.
We remedy this situation by (1) introducing a general framework for reasoning about sharing and (2) sketching how this framework can be integrated into a plan generator, which then constructs optimal DAG-structured query evaluation plans.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babcock B, Babu S, Datar M, Motwani R, Thomas D (2004) Operator scheduling in data stream systems. VLDB J 13(4):333–353
Cao Y, Das G, Chan C-Y, Tanx K-L (2008) Optimizing complex queries with multiple relation instances. In: SIGMOD, pp 525–538
Chamberlin D (1998) A complete guide to DB2 universal database. Morgan Kaufmann, San Francisco, CA
Dalvi NN, Sanghai SK, Roy P, Sudarshan S (2001) Pipelining in multi-query optimization. In: PODS
Galindo-Legaria CA, Joshi M (2001) Orthogonal optimization of subqueries and aggregation. In: SIGMOD
Garcia-Molina H, Ullman JD, Widom J (1999) Database System Implementation. Prentice Hall, Upper Saddle River, New Jersey
Gassner P, Lohman GM, Schiefer KB, Wang Y (1993) Query optimization in the ibm db2 family. IEEE Data Eng Bull 16(4):4–18
Graefe G (1990) Encapsulation of parallelism in the volcano query processing system. In: SIGMOD, pp 102–111
Graefe G (1993) Query evaluation techniques for large databases. ACM Comput Surv 25(2):73–170
Graefe G (1994) Volcano – an extensible and parallel query evaluation system. IEEE Trans Knowl Data Eng 6(1):120–135
Graefe G (1995) The cascades framework for query optimization. IEEE Data Eng Bull 18(3):19–29
Graefe G, McKenna WJ (1993) The volcano optimizer generator: Extensibility and efficient search. In: ICDE, pp 209–218
Haas LM, Freytag JC, Lohman GM, Pirahesh H (1989) Extensible query processing in starburst. In: SIGMOD, pp 377–388
Harizopoulos S, Shkapenyuk V, Ailamaki A (2005) Qpipe: A simultaneously pipelined relational query engine. In: SIGMOD, pp 383–394
Krishnamurthy R, Boral H, Zaniolo C (1986) Optimization of nonrecursive queries. In: VLDB’86, pp 128–137
Lohman GM (1988) Grammar-like functional rules for representing query optimization alternatives. In: SIGMOD, pp 18–27
Lorie RA (1974) Xrm – an extended (n-ary) relational memory. IBM Research Report, G320-2096
Maier D (1983) The Theory of Relational Databases. Computer Science Press, Rockville, Maryland
Mumick IS, Finkelstein SJ, Pirahesh H, Ramakrishnan R (1990) Magic is relevant. In: SIGMOD, pp 247–258
Neumann T (2005) Efficient generation and execution of dag-structured query graphs. PhD thesis, Universität Mannheim
Neumann T, Moerkotte G (2004) An efficient framework for order optimization. In: ICDE, pp 461–472
Neumann T, Moerkotte G (2008) Single phase construction of optimal DAG-structured QEPs. Research Report MPI-I-2008-5-002, Max-Planck-Institut für Informatik
Neumann T, Moerkotte G (2009) Single phase construction of optimal DAG-structured QEPs. In: BTW
Rao J, Lindsay BG, Lohman GM, Pirahesh H, Simmen DE (2001) Using eels, a practical approach to outerjoin and antijoin reordering. In: ICDE, pp 585–594
Roy P (1998) Optimization of dag-structured query evaluation plans. M.tech. thesis, Dept. of Computer Science and Engineering, IIT-Bombay, January 1998
Roy P, Seshadri S, Sudarshan S, Bhobe S (2000) Efficient and extensible algorithms for multi query optimization. In: SIGMOD
Selinger PG, Astrahan MM, Chamberlin DD, Lorie RA, Price TG (1979) Access path selection in a relational database management system. In: SIGMOD, pp 23–34
Sellis TK (1988) Multiple-query optimization. ACM Trans Database Syst 13(1):23–52
Simmen DE, Shekita EJ, Malkemus T (1996) Fundamental techniques for order optimization. In: SIGMOD, pp 57–67
Steinbrunn M, Peithner K, Moerkotte G, Kemper A (1995) Bypassing joins in disjunctive queries. In: VLDB, pp 228–238
Zhou J, Larson P-Å, Freytag JC, Lehner W (2007) Efficient exploitation of similar subexpressions for query processing. In: SIGMOD, pp 533–544
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Neumann, T., Moerkotte, G. Generating optimal DAG-structured query evaluation plans . Comp. Sci. Res. Dev. 24, 103–117 (2009). https://doi.org/10.1007/s00450-009-0061-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00450-009-0061-0