NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO

Tarcizio Alexandre Bini, Adriano Lange, Marcos Sfair Sunye, Fabiano Silva, Eduardo Cunha de Almeida

2011

Abstract

In relational database systems the optimization of select-project-join queries is a combinatorial problem. The use of exhaustive search methods is prohibitive because of the exponential increase of the search space. Randomized searches are used to find near optimal plans in polynomial time. In this paper, we investigate the large join query optimization (LJQO) problem by extending randomized algorithms and implementing a 2PO algorithm as a query optimizer in a popular open-source DBMS. We compare our solution with an implementation of a genetic algorithm. Through a multidimensional test schema, we discuss pros and cons about the behavior of these algorithms. Our results show that 2PO algorithm is fast to run and the costs of generated plans are better in most cases when compared to those of the genetic algorithms.

Paper Citation

in Harvard Style

Alexandre Bini T., Lange A., Sfair Sunye M., Silva F. and Cunha de Almeida E. (2011). NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO . In Proceedings of the 13th International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-8425-53-9, pages 151-156. DOI: 10.5220/0003426501510156

in Bibtex Style

@conference{iceis11,
author={Tarcizio Alexandre Bini and Adriano Lange and Marcos Sfair Sunye and Fabiano Silva and Eduardo Cunha de Almeida},
title={NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO},
booktitle={Proceedings of the 13th International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2011},
pages={151-156},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003426501510156},
isbn={978-989-8425-53-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 13th International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO
SN - 978-989-8425-53-9
AU - Alexandre Bini T.
AU - Lange A.
AU - Sfair Sunye M.
AU - Silva F.
AU - Cunha de Almeida E.
PY - 2011
SP - 151
EP - 156
DO - 10.5220/0003426501510156