On the optimality of strategies for multiple joins

Abstract

One heuristic that is common in the evaluation of multiple joins is the use of linear strategies. Another common heuristic is to avoid cartesian products; this is because cartesian products produce spurious tuples that have to be eliminated eventually. The purpose of the above heuristics is to restrict, for the sake of tractability, the query optimizer's search for a strategy to a small subspace of the entire strategy space. However, this restriction may also exclude the optimum strategy from the subspace. For example, experiments have shown that for large queries, the cheapest linear strategy could significantly more expensive than the cheapest possible (nonlinear) strategy. The following question thus arises naturally: Under what conditions would the cheapest strategy in a searched subspace be optimum among all strategies? This is a variation of an open problem and is the issue addressed by this paper.