Duplicate-free Generation of Alternatives in Transformation-based Optimizers

Transformation-based optimizers that explore a search space exhaustively usually apply all possible transformation rules on each alternative, and stop when no new information is produced. In general, different sequences of transformation rules may end up deriving the same element. The optimizer must detect and discard these duplicate elements generated by multiple paths. In this paper we consider two questions: How bad is the overhead of duplicate generation? And then, how can it be avoided? We use a restricted class of join reordering to illustrate the problem. For the first question, our analysis shows that as queries get larger, the number of duplicates is several times that of the new elements. And even for small queries, duplicates are generated more often than new elements. For the second question, we describe a technique to avoid generating duplicates, based on keeping track of (a summary of) the derivation history of each element.