Randomized approximation algorithms for query optimization problems on two processors

Query optimization problems for expensive predicates have received much attention in the database community. In these situations, the output to the database query is a set of tuples that obey certain conditions, where the conditions may be expensive to evaluate computationally. In the simplest case when the query looks for the set of tuples that simultaneously satisfy two expensive conditions on the tuples and these can be checked in two different distributed processors, the problem reduces to one of ordering the condition evaluations at each processor to minimize the time to output all the tuples that are answers to the query. We improve upon a previously known deterministic 3-approximation for this problem: In the case when the times to evaluate all conditions at both processors are identical, we give a 2-approximation; In the case of non-uniform evaluation times, we present a 8/3-approximation that uses randomization. While it was known earlier that no deterministic algorithm (even with exponential running time) can achieve a performance ratio better than 2, we show a corresponding lower bound of 3/2 for any randomized algorithm.