Publication: Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries
Issued Date
2009-11-10
Resource Type
Other identifier(s)
2-s2.0-70350741582
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Proceedings of the 2009 8th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2009. (2009), 463-468
Suggested Citation
Areerat Trongratsameethong, Jarernsri L. Mitrpanont Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries. Proceedings of the 2009 8th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2009. (2009), 463-468. doi:10.1109/ICIS.2009.195 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/27486
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries
Other Contributor(s)
Abstract
The size of the intermediate results produced while executing queries has a direct impact on query optimizers. Larger size of intermediate results requires more memory usage and more computational power to evaluate their join predicates. Furthermore, if memory size is not big enough, secondary storage will be needed. This paper proposes the Exhaustive Greedy (EG) algorithm to optimize the intermediate result sizes of join queries. Exhaustive search and greedy algorithm are combined and modified to identify good join orders. Based on the similar concept of the Greedy Operator Ordering (GOO) algorithm, in order to determine join order selection at subsequent steps, our algorithm also updates join graphs to reflect new size of join nodes and new join selectivities of edges associated with the join nodes at each step. Experiments are conducted and the results reveal that the EG algorithm determines the good join orders. In addition, most intermediate result sizes of join queries estimated by the EG algorithm are comparable to the results estimated by the Exhaustive Search algorithm that is modified to update join graphs, we name it ESU algorithm. © 2009 IEEE.