Hypergraph based reorderings of outer join queries with complex predicates
Authors:
Open Access
- 22 May 1995
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 24 (2) , 304-315
Abstract
Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an "as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with duplicates and/or outer join predicates that are other than " simple. " Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, we present the needed hypergraph abstraction and algorithms for reordering such queries with joins and outer joins. As a result, the query optimizer can explore a significantly larger space of execution plans, and choose one with a low cost. Further, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.Keywords
This publication has 8 references indexed in Scilit:
- Outerjoins as disjunctions1994
- Outer joins and filters for instantiating objects from relational databases through viewsIEEE Transactions on Knowledge and Data Engineering, 1994
- Extensible/rule based query rewrite optimization in Starburst1992
- Query graphs, implementing trees, and freely-reorderable outerjoins1990
- Outerjoin optimization in multidatabase systems1990
- Optimization of nested SQL queries revisited1987
- A state transition model for distributed query processingACM Transactions on Database Systems, 1986
- Access path selection in a relational database management system1979