Uniformly-distributed random generation of join orders

Abstract In this paper we study the space of operator trees that can be used to answer a join query, with the goal of generating elements form this space at random. We solve the problem for queries with acyclic query graphs. We first count, in O(n^3) time, the exact number of trees that can be used to evaluate a given query on n relations. The intermediate results of the counting procedure then serve to generate random, uniformly distributed operator trees in O(n^2) time per tree. We also establish a mapping between the N operator trees for a query and the integers 1 through N ---i.e.a ranking--- and describe ranking and unranking procedures with complexity O(n^2) and (n^2 log n), respectively.