Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries
3
Issued Date
2009
Resource Type
Language
eng
ISBN
9780769536415
Rights
Mahidol University
Rights Holder(s)
IEEE
Suggested Citation
Areerat Trongratsameethong, Jarernsri L. Mitrpanont, เจริญศรี มิตรภานนท์ (2009). Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries. doi:DOI 10.1109/ICIS.2009.195 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/10438
Title
Exhaustive greedy algorithm for optimizing intermediate result sizes of join queries
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.
Description
The 8th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2009), Shanghai, China: 2009. page 463-468.