Eddies

TLDR

Federated and shared‑nothing databases exhibit highly variable resource characteristics, making static query optimization ineffective because assumptions made at query submission rarely hold during execution. This paper introduces the eddy mechanism, a query processing approach that continuously reorders operators during execution. Eddies detect symmetry moments for easy reordering, coordinate synchronization barriers, and merge optimization and execution, using fluid‑dynamics principles and a simple learning algorithm to flexibly order operators per tuple. Initial implementation shows eddies perform nearly as well as static optimizers in static scenarios and dramatically improve performance in dynamic environments.

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. 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.