A polynomial time algorithm for optimizing join queries

Author

Swami, Arun N. ; Iyer, Balakrishna R.

Author_Institution

IBM Almaden Res. Center, San Jose, CA, USA

fYear

1993

fDate

19-23 Apr 1993

Firstpage

345

Lastpage

354

Abstract

The dynamic programming algorithm for query optimization has exponential complexity. An alternative polynomial time algorithm, the IK-KBZ algorithm, is severely limited in the queries it can optimize. Other algorithms have been proposed, including the greedy algorithm, iterative improvement, and simulated annealing. The AB algorithm, which combines randomization and neighborhood search with the IK-KBZ algorithm, is presented. The AB algorithm is much more generally applicable than IK-KBZ, has polynomial time and space complexity, and produces near optimal plans in the space of outer linear join trees. On average, it does better than the other algorithms that do not do an exhaustive search like dynamic programming

Keywords

computational complexity; dynamic programming; query processing; search problems; tree data structures; AB algorithm; IK-KBZ algorithm; dynamic programming algorithm; exhaustive search; exponential complexity; greedy algorithm; iterative improvement; join query optimisation; near optimal plans; neighborhood search; outer linear join trees; polynomial time; polynomial time algorithm; query optimization; randomization; simulated annealing; space complexity; Annealing; Costs; Dynamic programming; Explosions; Greedy algorithms; Heuristic algorithms; Iterative algorithms; Polynomials; Prototypes; Query processing;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Engineering, 1993. Proceedings. Ninth International Conference on

Conference_Location

Vienna

Print_ISBN

0-8186-3570-3

Type

conf

DOI

10.1109/ICDE.1993.344047

Filename

344047