Login | Register

A new approach to join reordering in query optimization


A new approach to join reordering in query optimization

Pilehvar, Mostafa (2005) A new approach to join reordering in query optimization. Masters thesis, Concordia University.

[thumbnail of MR04207.pdf]
Text (application/pdf)
MR04207.pdf - Accepted Version


A major task in query optimization is finding an optimal or near-optimal order to perform join operations. Most optimizers perform this join reordering using an exhaustive search algorithm with a dynamic programming technique. This algorithm always gives the optimal join ordering, but is very expensive. An alternative greedy approach is very efficient, but is not guaranteed to produce the optimal order. In this thesis, we introduce a new algorithm called AO * to find the optimal join ordering for a given set of relations. Our algorithm is based on a well-known problem reduction technique of the same name proposed in the context of decomposable production systems. In our algorithm, we build an AND/OR graph from the relations in the query which represents all possible join orders, and an optimal join ordering is an optimal-cost path in this graph. The AO * algorithm is guaranteed to produce the optimal join ordering, as is dynamic programming. While the worst-case performance cost of AO * is comparable to that of dynamic programming, in most instances, it is far more efficient. We compared the performance of AO * with that of dynamic programming and the greedy approach on star-, chain-, circular-, and clique-shaped queries. Our results show that for the first three types of queries, AO * outperforms dynamic programming dramatically. Another finding is that certain properties of the optimal join order have an impact on the performance of AO *

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Pilehvar, Mostafa
Pagination:xiii, 80 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Narayanan, Lata and Grahne, Gosta
Identification Number:QA 76.7 P49 2005
ID Code:8257
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:20
Last Modified:13 Jul 2020 20:03
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top