On the correct and complete enumeration of the core search space
Authors:
Open Access
- 22 June 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 493-504
Abstract
Reordering more than traditional joins (e.g. outerjoins, antijoins) requires some care, since not all reorderings are valid. To prevent invalid plans, two approaches have been described in the literature. We show that both approaches still produce invalid plans.\ud \ud We present three conflict detectors. All of them are (1) correct, i.e., prevent invalid plans, (2) easier to understand and implement than the previous (buggy) approaches, (3) more flexible in the sense that the restriction that all predicates must reject nulls is no longer required, and (4) extensible in the sense that it is easy to add new operators. Further, the last of our three approaches is complete, i.e., it allows for the generation of all valid plans within the core search space.\uKeywords
This publication has 11 references indexed in Scilit:
- Top down plan generation: From theory to practice2013
- A new, highly efficient, and easy to implement top-down join enumeration algorithm2011
- Reducing outer joinsThe VLDB Journal, 2008
- Dynamic programming strikes back2008
- Execution strategies for SQL subqueries2007
- Canonical abstraction for outerjoin optimization2004
- Orthogonal optimization of subqueries and aggregation2001
- Outerjoin simplification and reordering for query optimizationACM Transactions on Database Systems, 1997
- Hypergraph based reorderings of outer join queries with complex predicatesACM SIGMOD Record, 1995
- Query graphs, implementing trees, and freely-reorderable outerjoins1990