Eddies: continuously adaptive query processing

By Ron Avnur, Joseph M Hellerstein. ACM SIGMOD Conference, 2000

1,021 citations recorded by the source corpus.

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 appropriate join algorithms, 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 providing dramatic improvements in dynamic execution environments.

Subfields: Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/070f03f5e8b016628903c56a0011e810d0914d73

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Exploiting Punctuation Semantics in Continuous Data Streams (2003, neutral): “Thus, S[3] is [1] [3] [5].”
QuERy: A Framework for Integrating Entity Resolution with Query Processing (2015, background): “We believe this is also the case for other dynamic query processing approaches such as Eddies [5] (where it is difficult to estimate time complexity as well).”
Towards Sensor Database Systems (2001, methodology): “Other related projects include the TELEGRAPH project at UC Berkeley [1], which studies adaptive query processing techniques, and the SAGRES project at the University of Washington [11], which explores the use of data integration techniques in the context of device networks.”
Database Cracking (2007, background): “Some notable departures from the usual paths in database architecture design include [2, 3, 9, 14].”
Models and issues in data stream systems (2002, background): “In the next two subsections, we will touch upon several approaches to approximation, some of which are peculiar to the data stream model of computation.”
Continuous queries over data streams (2001, background): “The Telegraph project [ AH00 , HF 00, UF01] shares some target applications and basic technical ideas with our problem, although the general approach is different.”
Delay aware querying with Seaweed (2006, neutral): “Many large-scale systems route tuples through longstanding pre-installed queries [2, 3, 10, 13, 23, 30].”
Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams (2003, background): “ofplansharingandindexingquerypredicates[9,10,21]. TelegraphCQ[8]isaproposedextensionofearlierefiortsintoadaptivequeryprocessing[ 4 ,9,21],wherequeryplansarere-ordered throughout the lifetime of a continuous query in response to changes in the execution environment (e.g.”
The cougar approach to in-network query processing in sensor networks (2002, background): “Eddies push the idea of feedback on a tuple-by-tuple basis in online aggregation to adapting join orders at the same frequency [4].”
Chain: operator scheduling for memory minimization in data stream systems (2003, neutral): “In this paper we focus on one aspect of run-time resource allocation, namely operator scheduling.”
Issues in data stream management (2003, methodology): “The cost of a query plan may change for three reasons: change in processing time of an operator, change in selectivity of a predicate, and change in the arrival rate of a stream [4].”
Fjording the stream: an architecture for queries over streaming sensor data (2002, background): “Alternatively, some operators, such as Eddy [3] and XJoin [26] are designed to pursue other computation (e.g. transition to states other than ×) when no data is available on a particular input; the Fjords programming model is naturally suited to such adaptive query processing techniques.”
Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources (2003, background): “As such, it introduces additional dataﬂow logic [1] in the execution plan.”
Data integration: the teenage years (2006, background): “The research on data integration started developing different aspects of adaptive processing in isolation [4, 7, 18, 49, 62, 104, 108], and then came up with unifying architectures for adaptive query processing [59, 61].”