Stableness in large join query optimization

In relational database model, the use of exhaustive search methods in the large join query optimization is prohibitive because of the exponential increase of search space. An alternative widely discussed is the use of randomized search techniques. Several previous researches have been showed that the use of randomized sampling in query optimization permits to find, in average, near optimal plans in polynomial time. However, due to their random components, the quality of yielded plans for the same query may vary a lot, making the response time of a submitted query unpredictable. On the other hand, the use of heuristic optimization may increase stability of response time. This characteristic is essential in environments where response time must be predicted. In this paper, we will compare a randomized algorithm and a heuristic algorithm applied to large join query optimization. We used an open source DBMS as experimental framework and we compared the quality and stability of these algorithms.