An Intelligent Search Method for Query Optimization by Semijoins

Query optimization strategies based on the reduction of the referenced relations by means of semijoins have received considerable attention. The limitations of such strategies have to do with computational efficiency (very large search space of semijoin reduction sequences), optimality of the solution (when heuristics are used), and generality of the class of queries allowed (e.g., simple queries, chain queries, tree queries). We consider the problem of finding an optimal semijoin sequence that fully reduces a given tree query. We present a new method that “intelligently” navigates the space of all semijoin sequences and returns an optimal solution. We report on experiments that show that our method performs very efficiently; on average, less than five percent of the search space is searched before an optimal solution is found. Other advantages of the method are: 1) ease of implementation, 2) generality of the cost model considered, and 3) ability to handle tree queries with arbitrary target lists.