Source-linked AI summary
Automated Prefetching for Object Spatial Programming Using Temporal Trace Graphs
Baichuan Li, Jayanaka Dantanarayana, Savini Kashmira, Lingjia Tang, Jason Mars
TL;DR
Dependent database accesses can serialize round trips on a request’s critical path, motivating plans that span traversal steps. The paper introduces TTG, which composes access and continuation rules into bounded candidate plans and prefetches them during execution; it improves latency in three applications, with up to 2.99× speedup over the stock runtime.
Problem
Dependent database accesses can serialize application–database round trips on the request’s critical path because each result may identify the object needed by the next access.
Source: §1 · p. 1Method
TTG composes inspectable access paths and explicit continuation rules over the live graph at walker spawn into bounded candidate plans, which an asynchronous prefetcher loads during traversal.
Source: §1 · pp. 1–2, §2.2 · p. 3Results
TTG improves end-to-end latency in LinkedList, Jacord, and JDrive but not LittleX, and achieves up to 2.99× speedup over the stock runtime.
Source: §6 · p. 11, §7 · p. 11Takeaways & Limitations
The results indicate that exposing traversal continuation can support request-specific storage planning, but its performance benefit depends on workload and the costs of planning and prefetching.
Source: §6 · p. 11, §7 · p. 12LittleX shows that planning overhead can exceed avoided demand latency, and a high runtime-cache hit rate alone does not ensure lower end-to-end latency.
Source: §4.2 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
Dependent database accesses can serialize round trips on the request’s critical path, while composing plans across traversal steps requires knowing how discovered objects become later execution contexts. The paper identifies a programming-model contract for this planning and introduces TTG as a request-specific implementation of it.
1 Introduction
- Dependent database accesses can serialize application–database round trips on a request’s critical path, making repeated boundary crossings dominate latency.Planning ahead requires determining which objects will be needed before execution reaches their accesses.Source: §1 · p. 1
- In conventional OOP, an analyzer may need to trace discovered objects through queues, loop iterations, aliases, containers, and method calls to recover traversal continuation.That continuation links object discovery to the subsequent computation and its accesses.Source: §1 · p. 1
- The proposed contract pairs inspectable access paths with explicit continuation rules, allowing local rules to compose into bounded candidate plans from a request’s starting object.OSP [14] instantiates the contract through typed traversal expressions, visit scheduling, and ability dispatch.Source: §1 · pp. 1–2
- TTG composes statically extracted access and continuation rules over the live graph at walker spawn, while an asynchronous prefetcher loads planned objects during traversal.Later demand accesses can reuse prefetched object data and previously resolved topology.Source: §1 · p. 2
- Up to 2.99× end-to-end speedup over the stock runtime is reported for TTG, which is evaluated across four traversal workloads.The evaluation also characterizes planning overhead, cache behavior under value-dependent control, and trade-offs with manually staged prefetching.Source: §1 · p. 2
2 Background
OSP represents data and relationships as typed nodes and edges and runs stateful walkers over that graph; visits schedule later execution contexts. The problem formulation bounds a request-specific prefetch plan, and TTG represents candidate objects and traversal-derived transitions in a bounded graph.
2.1 Object-Spatial Programming
- OSP defines node, edge, and walker classes: nodes carry data, edges represent typed relationships, and walkers execute application logic as they visit nodes.Together, node and edge instances form the graph over which walkers execute.Source: §2.1 · p. 2
- Walker abilities can run on node entry or exit, and visit statements schedule selected nodes as subsequent execution contexts.Traversal expressions select related nodes through typed edges; intermediate nodes on a path need not be scheduled themselves.Source: §2.1 · p. 2
- Without TTG, the Jac runtime resolves topology and materializes objects on demand, blocking the walker for synchronous backing-store reads when required data is uncached.Reads can be batched within a traversal operation, but begin only when execution reaches that operation.Source: §2.1 · p. 3
2.2 Problem statement
- For a request, the planning problem is to choose candidate nodes before walker execution, using spawn-time information to cover as many actually read nodes as possible within a configured bound.The plan is bounded by L, and value-dependent pruning may leave planned nodes unused while some requested nodes remain outside the plan.Source: §2.2 · p. 3
- A TTG is a bounded, request-specific directed graph rooted at the spawn node; its vertices are candidate objects and its edges record traversal-rule-derived candidates.Targets scheduled by visit can be expanded further, and breadth-first discovery levels encode logical traversal progression rather than execution timestamps.Source: §2.2 · p. 3
3 Implementation
The implementation turns walker code into a bounded, request-specific plan at spawn, resolves topology before traversal, and fetches planned objects while the walker executes.
3.1 Architecture Overview
- At walker spawn, the Builder runs a synchronous PostgreSQL query that returns at most L candidate IDs and topology rows for the session-local GTI.The Prefetcher then loads object data while traversal runs, and demand accesses reuse cached data and topology.Source: §3.1 · pp. 3–4, Figure 2 · p. 4
3.2 Static Analyzer
- The Analyzer collects typed traversal paths, ability triggers, and visit usage from ability ASTs and statically resolvable helpers.When an edge type cannot be resolved statically, it records the generic edge class; extracted rules are cached on the loaded walker class, while each spawn gets a request-specific plan.Source: §3.2 · pp. 4–5
3.3 TTG Builder
- The Builder expands matching rules breadth-first, deduplicates candidates, follows visit targets for further expansion, and truncates the plan to budget L.This bounds the plan despite data-dependent reachable sets, broad frontiers, deep paths, or cycles.Source: §3.3 · p. 5
- In PostgreSQL, a recursive CTE composes typed-path SQL fragments and returns bounded UUIDs with topology rows, without materializing a separate TTG adjacency structure.The GTI caches resolved relationships for traversal; object data is loaded separately and asynchronously.Source: §3.3 · p. 5
3.4 Prefetcher
- After planning, round-robin background workers batch-read planned UUIDs into the runtime cache while the walker executes, and demand reads reuse cached documents.The evaluated runtime stores raw Python dictionaries and materializes Jac objects on demand.Source: §3.4 · p. 6
4 Evaluation
The evaluation tests TTG on four traversal workloads and finds end-to-end latency improvements in three, with outcomes depending on planning cost, candidate coverage, and prefetch timing. Against SeLeP, TTG improves latency on LinkedList, Jacord, and JDrive, while neither approach helps LittleX.
4.1 Experimental Setup
- The sweep measures end-to-end latency, storage requests, cache hits, and plan-size diagnostics across prefetch limits, including synchronous TTG planning in reported latency.The comparison includes the stock Jac runtime and manually staged prefetching (MSP); TTG planning and walker execution are both included in its latency.Source: §4 · p. 6, §4.1 · p. 7, §4.2 · p. 7
- The four workloads cover chain traversal, social-feed and recursive-reply access, and value-dependent folder-tree traversal.JDrive prunes subtrees rooted at trashed folders; the four applications use substantially different graph sizes and traversal patterns.Source: §4.1 · p. 6
4.2 Prefetch-Limit Sweeps
- 2.99× speedup on Jacord is TTG’s largest result; across the four applications, it lowers end-to-end latency in three.The result is measured at prefetch limit 12000 on Jacord; LittleX is the exception.Source: Figure 6 · p. 8, §4.2 · pp. 8–9
- LittleX’s fastest TTG configuration reaches 9638 ms versus 9491 ms for the stock runtime, a 0.98× speedup; at limit 12500, planning takes 1393 ms while walker time falls by 341 ms.The stock runtime uses 7 backend calls, compared with 14 for TTG at its fastest configuration.Source: Figure 6 · p. 8, §4.2 · p. 8, Figure 7 · p. 9
- TTG reduces latency and backend calls on LinkedList, Jacord, and JDrive, but Jacord’s first visit can occur before its prefetched objects are available.LinkedList reaches 2.87× speedup at limit 1250; Jacord reaches 2.99× at limit 12000, while smaller limits remain near baseline. JDrive reaches 2.32× at limit 500, with a conservative plan that can include folders the request does not read.Source: §4.2 · pp. 8–9
4.3 Comparison with SeLeP
- On randomized request streams, SeLeP does not reduce median latency, whereas TTG improves it on LinkedList, Jacord, and JDrive; neither helps LittleX.SeLeP eliminates most simulated block misses for LinkedList and Jacord, but block-cache gains need not remove dependent application–database round trips.Source: Figure 9 · p. 10, §4.3 · p. 10, Table 2 · p. 10
5 Related Work
Prior prefetchers expose access information through annotations, profiles, program analysis, batching, or prediction. TTG instead builds a bounded object-level plan from explicit traversal rules and the live graph.
Related prefetching approaches
- Prefetching systems span programmer interfaces, dependency graphs, profile-guided inference, compile-time rewriting, reactive batching, and history-based prediction.Examples include Foreactor [11] and PULSE for programmer-directed mechanisms, and AutoFetch for profile-guided traversal prefetching.Source: §5 · pp. 10–11
TTG’s distinction
- TTG composes traversal-continuation rules over the live graph to plan bounded candidate reads before execution while keeping walker execution client-side.Unlike stored-procedure synthesis such as WeBridge, TTG conservatively handles value-dependent control, with unused candidates bounded by the plan budget.Source: §5 · p. 11
Profile- and workload-driven approaches
- Profile- and workload-driven systems use prior traversals or access patterns, while TTG plans from the current request’s traversal rules and live graph.AutoFetch may lose prediction quality when requests differ from earlier profiles; SeLeP and Pythia use observed access information.Source: §5 · p. 11
Rewriting and reactive batching
- Compile-time rewriting and query extraction batch or derive database operations, whereas reactive batching defers dependent work until results are needed.DBridge also uses asynchronous query prefetching; Sloth accumulates queries through extended lazy evaluation.Source: §5 · p. 11
6 Discussion
TTG helps when avoided demand stalls outweigh planning and prefetching costs, and its performance relative to manual staging varies by workload. Its planning scope and implementation also have explicit semantic, analyzer, and concurrency boundaries.
When planning pays off
- TTG improves LinkedList, Jacord, and JDrive when avoided stalls outweigh costs; with sufficient budgets it beats MSP there, while MSP is faster on LittleX.LittleX offers limited opportunity to offset TTG overhead because the stock runtime already uses few backing-store calls and its multi-hop feed query remains demand-driven.Source: §6 · p. 11
Semantic boundary
- TTG plans structural dependencies but does not evaluate JDrive’s trashed condition, so it may include descendants the walker prunes.The prefetch limit L bounds the number of unused candidates, not their fraction of the plan.Source: §6 · p. 11
Design trade-offs
- Runtime-variable visit types can expand plans by the number of declared edge classes, a cost not measured because all benchmarks use literal edge types.The generated GTI also adds session-local memory proportional to planning-query topology rows.Source: §6 · p. 11
Evaluation scope
- The implementation uses a fixed plan bound and evaluates read-dominated sequential requests; concurrent workloads may add contention and graph updates require cache-consistency mechanisms.Adaptive planning and concurrent execution remain future work.Source: §6 · p. 11
7 Conclusion
The paper identifies a request-planning contract based on inspectable access paths and explicit traversal continuation, and instantiates it in OSP with TTG. Across four Jac/PostgreSQL workloads, TTG reaches up to 2.99× speedup over the stock runtime, while planning overhead and value-dependent control delimit its benefits.
Planning contract
- The proposed contract pairs inspectable access paths with explicit traversal continuation so request-specific plans can span future traversal steps.OSP provides one instantiation of this contract.Source: §7 · p. 11
TTG and evaluation
- TTG composes access and continuation rules over the live graph at walker spawn to produce bounded candidate plans.The evaluation implements TTG in Jac/PostgreSQL across four workloads.Source: §7 · p. 11
Results and limits
- Up to 2.99× end-to-end speedup over the stock runtime was achieved, while LittleX exposed planning overhead and JDrive exposed bounded overfetch from value-dependent control.The results characterize workload-dependent benefits and limits of continuation-based storage planning.Source: §7 · pp. 11–12