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.