Automated prefetching improves database traversal speed up to three times
Automated Prefetching for Object Spatial Programming Using Temporal Trace Graphs
DatabasesProgramming Languages
Summary
Many programs need to fetch related pieces of data one after another, which can slow things down. The authors propose a way to plan these fetches ahead of time by understanding how a program explores data objects and where it might go next. They create a special graph that helps predict which data to load early, speeding up the process. Testing this idea on four programs showed it can make some tasks almost three times faster, though sometimes the planning itself costs extra time.
What this means in practice
- •For database application developers: Speed up multi-step object retrieval workflows in applications by automatically planning data prefetching to reduce wait times during database traversals.
- •For enterprise software engineers: Boost efficiency of workflows involving complex data relationships by integrating automatic cross-step prefetch planning into backend systems.
Authors
Baichuan Li, Jayanaka Dantanarayana, Savini Kashmira, Lingjia Tang, Jason Mars
Abstract
Dependent database accesses can serialize application--database round trips on a request's critical path. Planning across traversal steps requires knowing both which relationships a computation may follow and how discovered objects become subsequent execution contexts. We identify a programming-model contract that exposes this information through inspectable access paths and explicit traversal continuation. We demonstrate this contract in Object-Spatial Programming (OSP), where walkers traverse a typed object graph and execute node-type-specific code. We introduce the Temporal Trace Graph (TTG), a bounded, request-specific graph of candidate objects and traversal-derived transitions. At walker spawn, the TTG Builder composes statically extracted access and continuation rules over the live graph from the request's starting node. An asynchronous prefetcher loads planned objects while the walker executes. We implement TTG in Jac/PostgreSQL and evaluate four applications covering linear, multi-hop, recursive, and value-dependent traversals. TTG improves end-to-end latency in three applications, achieving up to 2.99x speedup over the stock runtime. Comparisons with manually staged prefetching characterize the benefits and costs of automatic cross-step planning. The evaluation also shows that planning overhead can exceed avoided demand latency and that value-dependent control can introduce bounded overfetch.