The Impact of Catalogs and Join Algorithms on Probabilistic Query Optimization.
J. Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1994
Most of the work on randomized query optimization has relied heavily on the use of transformations rules for the generation of execution plans. Recently, however, we gave evidence that for the problem of choosing a join evaluation order, generating alternatives uniformly at random from the space yields solutions comparable to those obtained with transformation-intensive methods, and requires generating fewer candidate plans. This paper presents a thorough empirical study of the impact of catalogs and join methods on the relative performance of transformation-free and transformation-based randomized optimization. Basically, our previous results remain valid for a wide variety of catalogs and relational profiles. But in contrast with the problem of selecting a join order, selecting join algorithms (e. g. hash, merge, nested-loops) seems better handled by transformations than random picking. We then propose a two-phase approach that combines the speed of random picking with the quality of solutions of transformation-based optimization, and verify experimentally its superiority over the other algorithms, in all the search spaces considered.