A threshold mechanism for distributed query processing

Abstract

A strategy to process a distributed query is formed using estimates for partial results sizes and delays/costs associated with the network data transfer and CPU processing. To guard against inaccurate estimates the strategy execution is monitored and if estimates are observed to be “inaccurate” the strategy is corrected. This paper presents and compares two methods which can be used to decide whether or not to correct a strategy. In the Reformulation method a new strategy is formulated after executing each relational operation. The Thresholds method is based on the fact that some partial results formed by the strategy's execution are more “critical” than others. The query processing strategy is represented as a network of activities and the Critical Path Method method is used to determine threshold values for partial results. If a partial result is delayed beyond its threshold value the strategy is corrected. The Reformulation and Thresholds methods are evaluated on a test-bed of queries for a modeled application of a DDB.