Efficient enumeration of non-isomorphic processing trees

Enumeration of search spaces belonging to join queries, so far comprises large sets of isomorphic processing trees, i.e. trees that can be equalized by only commutative exchange of the input relations to the operators. Since these differences can be handled effectively by the costing method it is sufficient to focus on the enumeration of non-isomorphic processing trees only. This restriction reduces the size of the search space by factor 2^k, k being the number of operators. In this paper we present a technique that generates all non-isomorphic trees belonging to an arbitrarily shaped query graph. The algorithm generates sequences over the query graph's edges which are simultaneously turned into processing trees. During the incremental expansion of sequence prefixes the remaining edges are classified and only those not leading to isomorphic duplicates are appended. This incremental proceeding causes only little overhead leading to superior performance.