Reordering execution in tertiary memory databases

Abstract

In the relational data model the order of fetching data does not affect the correctness of query semantics. This flexibility has been exploited in query optimization by statically reordering data accesses. However, once a query is optimized, it is processed in a fixed order in most systems, with the result that data requests are made in a fixed order. Only limited forms of runtime reordering can be provided by low-level device managers that schedule I/O requests from multiple users, or by asynchronous batch prefetch requests. More aggressive reordering strategies are essential in scenarios where the latency of access to data objects varies widely and dynamically, as in tertiary devices. This paper presents such a strategy. Our key innovation is to exploit dynamic reordering to match execution order to the optimal data fetch order, in all parts of the plan-tree. To demonstrate the practicality of our approach and the impact of our optimizations, we report on a prototype implementation based on Postgres. Using our system, typical I/O cost for queries on tertiary memory databases is as much as an order of magnitude smaller than on conventional systems.