This paper looks at the problem of multi-join query optimization for symmetric multiprocessors. Optimization algorithms based on dynamic programming and greedy heuristics are described that, unlike traditional methods, include memory resources and pipelining in their cost model. An analytical model is presented and used to compare the quality of plans produced by each optimization algorithm. Experimental results show that, while dynamic programming produces the best plans, simple heuristics often do nearly as well. The same results are also used to highlight the advantages of bushy execution trees over more restricted tree shapes.
展开▼