This paper proposes an optimization algorithm named join order algorithm Using Predefined Optimal joinorder or is called JAPO algorithm to optimize join cost. Optimal joinorder solutions for all possible join patter...
详细信息
ISBN:
(纸本)9781538619797;9781538619780
This paper proposes an optimization algorithm named join order algorithm Using Predefined Optimal joinorder or is called JAPO algorithm to optimize join cost. Optimal joinorder solutions for all possible join patterns are predefined and stored in a file using Dynamic Programming with Memorization technique or is called DPM algorithm. JAPO algorithm searches joinorder solutions from the predefined optimal joinorders using hash function instead of traversing all search space. Experiments are conducted and join costs obtained by JAPO algorithm are compared with DPM algorithm and greedy algorithm named GOO. The experimental results show that JAPO algorithm with polynomial time complexity obtains almost 100 percent of optimal joinorder solutions. DPM algorithm obtains 100 percent of optimal joinorder solutions with factorial time complexity. GOO algorithm with polynomial time complexity obtains sub-optimal solutions and number of optimal solutions obtained by GOO algorithm decreases when number of relations to be joined is increased.
暂无评论