Heuristic algorithms for distributed query processing

Abstract

This paper examines heuristic algorithms for processing distributed queries using generalized joins. As this optimization problem is NP-hard heuristic algorithms are deemed to be justified. A heuristic algorithm to form/formulate strategies to process queries is presented. It has a special property in that its overhead can be “controlled”: The higher its overhead the better the strategies it produces. Modeling on a test-bed of queries is used to demonstrate that there is a trade-off between the strategy's execution and formulation delays. The modeling results also support the notion that simple greedy heuristic algorithms such as are proposed by many researchers are sufficient in that they are likely to lead to near-optimal strategies and that increasing the overhead in forming strategies is only marginally beneficial. Both the strategy formulation and execution delays are examined in relation to the number of operations specified by the strategy and the total size of partial results.