Uniformly-Distributed Random Generation of Join Orders
César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten, M. Y. Vardi, G. Gottlob · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1994
. 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 O(n 2 log n), respectively. 1 Introduction 1.1 Background The selection of a join evaluation order is a major task of relational query optimizers [Ull82, CP85, KRB85]. The problem can be stated as that of finding an operator tree to evaluate a given query, so that the estimated evaluation cost is minimum. In pract...