Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal


Volumes > Volume 09 > No. 3


Degradation of Complexity for Join Enumeration via Weight Measure on CMP

PP: 1445-1454
Yongheng Chen, Kerui Chen, YaoJin Lin,
Most contemporary database systems query optimizers exploit System-Rís Bottom-Up dynamic programming method (DP) to find the optimal query execution plan (QEP). The dynamic programming algorithm has a worst case running time, thus for queries with more than 10 joins, it becomes infeasible. To resolve this problem, random strategies are used. In this paper we propose a parallel top-down join enumeration algorithm that is optimal with respect to the partial order graph based on Chip Multi-Processor (CMP). This paper firstly transforms the undirected query graph to Weighted Edge Join Graph (WEJG) according to the edge weight and constructs all partial order join and partial order graph within WEJG. Then the global optimal query plan is achieved according to the parallelize top-down enumeration. Our theoretical results and empirical evaluation show that our algorithm could gracefully degrade the complexity degree for top-down join enumeration with large number of tables and gains impressive in the performance in terms of both output quality and running time.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved