|
|
 |
| |
|
|
|
Degradation of Complexity for Join Enumeration via Weight Measure on CMP |
|
|
|
PP: 1445-1454 |
|
|
|
Author(s) |
|
|
|
Yongheng Chen,
Kerui Chen,
YaoJin Lin,
|
|
|
|
Abstract |
|
|
| 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. |
|
|
|
|
|
|
|
