Iterative dynamic programming
Authors:
Open Access
- 1 March 2000
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 25 (1) , 43-82
Abstract
The query optimizer is one of the most important components of a database system. Most commercial query optimizers today are based on a dynamic-programming algorithm, as proposed in Selinger et al. [1979]. While this algorithm produces good optimization results (i.e, good plans), its high complexity can be prohibitive if complex queries need to be processed, new query execution techniques need to be integrated, or in certain programming environments (e.g., distributed database systems). In this paper, we present and thoroughly evaluate a new class of query optimization algorithms that are based on a principle that we calliterative dynamic programming, or IDP for short. IDP has several important advantages: First, IDP-algorithms produce the best plans of all known algorithms in situations in which dynamic programming is not viable because of its high complexity. Second, some IDP variants are adaptive and produce as good plans as dynamic programming if dynamic programming is viable and as good-as possible plans if dynamic programming turns out to be not viable. Three, all IDP-algorithms can very easily be integrated into an existing optimizer which is based on dynamic programming.Keywords
This publication has 11 references indexed in Scilit:
- The Volcano optimizer generator: extensibility and efficient search2002
- A polynomial time algorithm for optimizing join queries2002
- SAP R/3 (tutorial)ACM SIGMOD Record, 1998
- Heuristic and randomized optimization for the join ordering problemThe VLDB Journal, 1997
- On the complexity of generating optimal plans with cross products (extended abstract)1997
- Mariposa: a wide-area distributed database systemThe VLDB Journal, 1996
- Practical predicate placement1994
- Predicate migration1993
- Randomized algorithms for optimizing large join queries1990
- On the optimal nesting order for computing N -relational joinsACM Transactions on Database Systems, 1984