Distributed query optimization by one-shot fixed-precision semi-join execution

Abstract

A novel semijoin execution strategy is proposed which allows parallelism and processes multiple semijoins simultaneously. In practice most of the parameters needed for query optimization, such as relation cardinality and selectivity, are of fixed-precision. Imposing this fixed-precision constraint, an efficient distributed query processing algorithm is developed. For situations where the fixed-precision constraint does not apply, a method to truncate the parameters and use the same algorithm to find near-optimal solutions is proposed. By analyzing the truncation errors, a quantitative comparison between the near-optimal solutions and the optimal ones is provided.