Outerjoin Simplification and Reordering for Query Optimization.

César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
  author    = {C{\'e}sar A. Galindo-Legaria and
               Arnon Rosenthal},
  title     = {Outerjoin Simplification and Reordering for Query Optimization},
  journal   = {ACM Trans. Database Syst.},
  volume    = {22},
  number    = {1},
  year      = {1997},
  pages     = {43-73},
  ee        = {, db/journals/tods/Galindo-LegariaR97.html},
  bibsource = {DBLP,}


Conventional database optimizers take full advantage of associativity and commutativity properties of join to implement efficient and powerful optimizations on select/project/join queries. However, only limited optimization is performed on other binary operators. In this article, we present the theory and algorithms needed to generate alternative evaluation orders for the optimization of queries containing outerjoins. Our results include both a complete set of transformation rules, suitable for new-generation, transformation-based optimizers, and a bottom-up join enumeration algorithm compatible with those used by traditional optimizers.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Index Terms and Review]
[Full Text in PDF Format, 602 KB]


[ANSI 1992]
[Bhargava et al. 1995]
Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315 BibTeX
[Chen 1990]
Arbee L. P. Chen: Outer Join Optimization in Multidatabase Systems. DPDS 1990: 211-218 BibTeX
[Codd 1979]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[Date 1986]
[David 1991]
Michael M. David: Advanced Capabilities of the Outer Join. SIGMOD Record 21(1): 65-70(1992) BibTeX
[Dayal 1983]
Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136 BibTeX
[Dayal 1987]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[Dayal and Hwang 1984]
Umeshwar Dayal, Hai-Yann Hwang: View Definition and Generalization for Database Integration in a Multidatabase System. IEEE Trans. Software Eng. 10(6): 628-645(1984) BibTeX
[Galindo-Legaria 1987]
[Galindo-Legaria 1992]
[Galindo-Legaria 1994]
César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358 BibTeX
[Galindo-Legaria and Rosenthal 1992]
César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409 BibTeX
[Graefe 1990]
Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) BibTeX
[Graefe and DeWitt 1987]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
[Haas et al. 1990]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX
[Kim 1982]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[Lacroix and Pirotte 1976]
[Lee and Wiederhold 1994]
Byung Suk Lee, Gio Wiederhold: Outer Joins and Filters for Instantiating Objects from Relational Databases Through Views. IEEE Trans. Knowl. Data Eng. 6(1): 108-119(1994) BibTeX
[Melton and Simon 1993]
Jim Melton, Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3
Contents BibTeX
[Muralikrishna 1989]
M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85 BibTeX
[Ono and Lohman 1990]
Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 BibTeX
[Özosoyoglu et al. 1989]
Gultekin Özsoyoglu, Victor Matos, Z. Meral Özsoyoglu: Query Processing Techniques in the Summary-Table-by-Example Database Query Language. ACM Trans. Database Syst. 14(4): 526-573(1989) BibTeX
[Rosenthal and Garlindo-Legaria 1990]
Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299 BibTeX
[Rosenthal and Helman 1986]
Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) BibTeX
[Roth et al. 1989]
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Null Values in Nested Relational Databases. Acta Inf. 26(7): 615-642(1989) BibTeX
[Rosenthal and Reiner 1984]
Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343 BibTeX
[Selinger et al. 1979]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Sheth 1991]
[Sheth and Larson 1990]
Amit P. Sheth, James A. Larson: Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Comput. Surv. 22(3): 183-236(1990) BibTeX
[Scholl et al. 1987]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX
[Tay 1990]
Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131 BibTeX
[Ullman 1982]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[Wang and Madnick 1990]
Y. Richard Wang, Stuart E. Madnick: A Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective. VLDB 1990: 519-538 BibTeX

Referenced by

  1. Renée J. Miller, Laura M. Haas, Mauricio A. Hernández: Schema Mapping as Query Discovery. VLDB 2000: 77-88
  2. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
  3. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
  4. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:20 2008