Competitive Analysis of Adaptive Query Execution

Amol Deshpande
(Professor Joseph M. Hellerstein)
IBM Research Fellowship

Typically, database systems use a static query execution plan for executing a given query. Adaptive query execution refers to adapting the query execution plan in response to changing characteristics of data. Recently, there has been a lot of interest in this problem, e.g., [1].

In this work, we try to apply competitive analysis techniques to the adaptive query exeuction problem to understand the problem better. We are currently addressing a simplified version of the problem where the queries only contain join operations, and the joins are implemented using the symmetric hash join operator [2]. We also assume that the execution model of the online algorithms is similar to the Eddies mechanism proposed by Avnur and Hellerstein [1]. We are later planning to extend the analysis to more complicated cost models, as well as to join algorithms that spill data to disk.

[1]
R. Avnur and J. M. Hellerstein, "Eddies: Continuously Adaptive Query Processing," SIGMOD, Dallas, TX, May 2000.
[2]
A. N. Wilschut and P. M. G. Apers, "Dataflow Query Execution in a Parallel Main-Memory Environment," PDIS, Miami Beach, FL, December 1991.

More information (http://www.cs.berkeley.edu/~amol) or

Send mail to the author : (amol@eecs.berkeley.edu)


Edit this abstract