Abstract

The execution cost of query plans highly depends on the order in which the joins are executed. We propose a greedy approach for finding a ‘good’join ordering. This approach selects in the sequence of joins the next join operation that will produce the smallest relation (relation with the fewest tuples). Given n relations, at every selection, the greedy algorithm has to consider O (n) join possibilities by estimating or computing the size of the resulting joined relation, and choose the smallest one. The whole process consists of a sequence of (n− 1) joins, resulting in O (n2) estimations. Given the quadratic complexity, the

Date

December 11, 2008

Authors

Shant Karakashian, José Luis Ambite, Berthe Y Choueiry