Ron Avnur and Joseph M. Hellerstein

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1078
1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1078.pdf

In large federated and shared-nothing databases, resources can exhibit widely fluctuating characteristics. Assumptions made at the time a query is submitted will rarely hold throughout the duration of query processing. As a result, traditional static query optimization and execution techniques are ineffective in these environments.

In this paper we introduce a query processing mechanism called an eddy, which continuously reorders operators in a query plan as it runs. We characterize the moments of symmetry during which pipelined joins can be easily reordered, and the synchronization barriers that require inputs from different sources to be coordinated. By combining eddies with join algorithms appropriate to large-scale environments, we merge the optimization and execution phases of query processing, allowing each tuple to have a flexible ordering of the query operators. This flexibility is controlled by a combination of fluid dynamics and a simple learning algorithm. Our initial implementation demonstrates promising results, with eddies performing nearly as well as a static optimizer/executor in static scenarios, and adapting to run-time changes in the execution environment.

BibTeX citation:

@techreport{Avnur:CSD-99-1078,
    Author = {Avnur, Ron and Hellerstein, Joseph M.},
    Title = {Continuous Query Optimization},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1999},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5714.html},
    Number = {UCB/CSD-99-1078},
    Abstract = {In large federated and shared-nothing databases, resources can exhibit widely fluctuating characteristics. Assumptions made at the time a query is submitted will rarely hold throughout the duration of query processing. As a result, traditional static query optimization and execution techniques are ineffective in these environments. <p>In this paper we introduce a query processing mechanism called an eddy, which continuously reorders operators in a query plan as it runs. We characterize the moments of symmetry during which pipelined joins can be easily reordered, and the synchronization barriers that require inputs from different sources to be coordinated. By combining eddies with join algorithms appropriate to large-scale environments, we merge the optimization and execution phases of query processing, allowing each tuple to have a flexible ordering of the query operators. This flexibility is controlled by a combination of fluid dynamics and a simple learning algorithm. Our initial implementation demonstrates promising results, with eddies performing nearly as well as a static optimizer/executor in static scenarios, and adapting to run-time changes in the execution environment.}
}

EndNote citation:

%0 Report
%A Avnur, Ron
%A Hellerstein, Joseph M.
%T Continuous Query Optimization
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1078
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5714.html
%F Avnur:CSD-99-1078