Title and Author of Paper
Eddies: Continuously Adaptive Query Processing. Ron Avnur and Joseph M. Hellerstein.
Summary
Eddies describes a query optimization system that continuously reorders operators in a query plan as the it runs. This insight is based on the observation that assumptions made about the database at the time that a query is submitted will rarely hold throughout the duration of query processing.
Query plans can be reordered using two criteria: synchronization barriers and moments of symmetry. Synchronization barriers exist whenever an operator is waiting for a table scan to complete before making forward progress. In general, these barriers limit concurrency and one goal of the eddies system is to avoid or improve these barriers by selecting an appropriate join algorithm.
With moments of symmetry, the system identifies query operators that are symmetric: that do not distinguish between the inputs.
Consider the traditional nested-loops join, for example. The “outer” relation in a nested-loops join is synchronized with the “inner” relation, but not vice versa: after each tuple is consumed from the outer relation, a barrier is set until a full scan of the inner is completed.
Eddies can identify times when a barrier is reached and the order of the inputs to a join can be reordered to increase performance. Such moments are called moments of symmetry. Moments of symmetry also allow for the swapping of join algorithms, as long as the join algorithms themselves are commutative. By combining commutativity of joins with moments of symmetry allows for very aggressive reordering of a query plan.
Before eddies, query optimization has been viewed as a coarse-grained, static problem. Eddies allow a more fine-grained, adaptive optimization method. In large scale systems, performance can vary and be unpredictable: eddies can help make local optimizations to such a system to improve performance.
The paper goes in to much more detail on how eddies are implemented within a system, and some experimental data on the performance of eddies in different query settings. The interested reader can refer to the original paper for more details.