Adaptive query processing for improving responsiveness of wide-area queries
Tolga Urhan, Michael J. M. Franklin · 2002
The explosive growth of the Internet and the World Wide Web has made tremendous amounts of data available on-line. Emerging standards such as XML, and maturing mediator-wrapper technologies make it possible to pose more sophisticated, declarative queries over data sources that are distributed across a wide-area network. Processing queries in a wide-area environment, however, poses significant performance problems. Network congestion, site overloads, and failures introduce unpredictable and sporadic delays in data transmission and adversely affect the response of queries that depend on delayed data. Traditional query processing techniques remain largely ineffective for coping with such dynamic problems due to their static nature. This thesis proposes adaptive query execution techniques for improving the responsiveness of queries that are executed over a wide-area environment in the presence of unpredictable delays. The techniques we propose improve wide-area query response by modifying certain aspects of the query execution in reaction to such delays. Our first work, Query Scrambling addresses the initial delay problem where the first access to data is unexpectedly delayed. It reacts to unexpected delays by modifying, on-the-fly, the execution plan of a query so that progress can be made on other parts of the plan. Query Scrambling first attempts to change the scheduling of query operators for relatively short initial delays. For longer delays it dynamically modifies the shape of the query plan by adding and/or removing query operators. In order to cope with slow and bursty data arrival we have developed a complementary approach, based on a fully pipelined join operator we call XJoin. Full pipelining is a promising approach to coping with such delays as it allows scheduling of operators to adjust to the arrival properties of the data. XJoin is optimized to produce initial results quickly and can hide severe cases of intermittent delays in data arrival by utilizing a novel, reactively scheduled background process. Finally, we propose techniques for controlling the flow of data in a pipelined query plan to further speed up the delivery of the tuples. We distinguish between two query types based on the how the user prefers the query results to be delivered. For cases where the tuples in the query result are all of equal importance we propose a dynamic rate-based pipeline scheduling policy that produces more results during the early stages of query execution. The proposed policy dynamically constructs a schedule of operators so that the output rate is maximized. For cases where the result tuples have varying degrees of importance, we propose a dynamic tuple regulation algorithm that produces more important tuples during the early stages of query execution by allowing important tuples to get ahead of less important ones in the pipeline. We propose variations of this technique that allow various parts of a query plan to participate in the regulation of tuple flow. For all of the techniques proposed, we present the results of detailed performance studies based on a series of implementations. The results show that the proposed techniques are effective in improving the responsiveness of wide-area queries in the presence of unpredictable delays.