Undeprecate and Optimize `navigate()` for Batch Destination Fetching

[jtnelson]

Undeprecate and Optimize navigate() for Batch Destination Fetching

Summary

navigate() was deprecated in v0.10.0 in favor of select/get
with navigation keys. However, navigate() provides a return
structure that select cannot replicate: per-destination-record
keying (Map<Long, Map<String, Set<TObject>>>). This structure is
essential for ORM-style frameworks (e.g., Runway) that need to
reconstitute individual Records from Collection<Record> fields
without N+1 queries.

This ticket proposes:

1. Undeprecate navigate(Collection<String>, Collection<Long>)
   (and relevant overloads).
2. Rewrite the server-side implementation to use the modern
   Stores.select BFS graph optimization instead of the current
   linear loop through the deprecated AtomicOperation path.
3. Optionally, add a new batch-aware select variant that
   returns per-destination data, so navigate can eventually be
   retired once a proper replacement exists.

---

Motivation

The N+1 Problem in ORMs

When Runway loads a Record that has a Collection<Record> field
(e.g., List<Dock> docks), each element in the collection is a
Link to another record. Without prefetching, loading a parent with
N children requires:

• 1 select(parentId) to get the parent data
• N select(childId) calls inside convert() — one per
  Link in the collection

This is the classic N+1 problem. For a parent with 300 children,
that is 301 round trips.

Why select with Navigation Keys Cannot Replace navigate

The modern select(keys, records) with navigation keys (e.g.,
docks._, docks.name) returns
Map<Long, Map<String, Set<TObject>>> keyed by source record,
not destination record. When a source record has a multi-valued
Link field (e.g., docks links to records 5, 6, and 7), the
select result flattens all destination values under the source
key:

// select("docks.name", [parentId]) returns:
{
  parentId: { "docks.name": ["alpha", "beta", "gamma"] }
}

There is no way to determine that "alpha" came from record 5,
"beta" from record 6, and "gamma" from record 7. The per-
destination association is lost.

navigate() preserves this:

// navigate("docks.name", [parentId]) returns:
{
  5: { "name": ["alpha"] },
  6: { "name": ["beta"] },
  7: { "name": ["gamma"] }
}

This per-destination keying is exactly what an ORM needs to
reconstitute each child Record individually.

Measured Impact

Benchmarks in Runway with 300 collection elements on localhost show
a measurable speedup even though the server-side work is currently
suboptimal:

N+1 (disabled):              ~8,600 us
Navigate prefetch (enabled): ~5,800 us
Speedup:                     ~1.3-1.6x (localhost)

Over a real network, the round-trip elimination alone would turn
300+ sequential RPCs into 2 (one select + one navigate).

---

Current Implementation Analysis

The Deprecated Path is Suboptimal

Operations.navigateKeysRecordsAtomic (Operations.java ~L1256)
does a simple linear loop:

for (long record : records) {
    Map<Long, Map<String, Set<TObject>>> current =
        navigateKeysRecordAtomic(keys, record, timestamp, atomic);
    // ... merge results ...
}

Each navigateKeyRecordAtomic (Operations.java ~L1160) then splits
the key by . and calls atomic.select(key, record) for each stop
in the path, one record at a time:

while (it.hasNext()) {
    key = it.next();
    for (long rec : records) {
        Set<TObject> values = atomic.select(key, rec);
        // ... follow Links ...
    }
    records = nextRecords;
}

Every atomic.select() call registers a read Token in
reads2Lock (AtomicOperation.java ~L646), adding overhead for
conflict tracking that is unnecessary for read-only navigation.

The Modern Path Has Better Infrastructure

Stores.select(Store, Collection<String> keys, long record, long timestamp) (Stores.java ~L301) already has a sophisticated
optimization:

1. Graph construction — builds a Node-based navigation
   graph from all requested keys, merging shared path prefixes
   into a single tree structure.

2. BFS traversal — traverses the graph breadth-first,
   performing bulk selection at junction points:

   if(successors.size() > 1) {
       // Multiple keys share this junction —
       // select the entire record once
       intermediate = store.select(link);
   }

   This avoids redundant reads when multiple navigation keys share
   a common intermediate stop (e.g., docks._ and docks.name
   both traverse through docks).

3. Single lock acquisition — one
   advisoryLock().readLock().lock() for the entire operation.

4. No AtomicOperation overhead — reads directly from the
   Store without registering conflict-tracking tokens.

However, traverseKeyRecordsOptionalAtomic (Operations.java
~L1957), which is the modern replacement, still loops over
records one at a time:

for (long record : records) {
    Set<TObject> values =
        traverseKeyRecordOptionalAtomic(key, record, ...);
}

Each iteration calls Stores.select independently, so the BFS
graph is rebuilt per record and the advisory lock is acquired and
released per record. The graph optimization only helps within a
single record's key set, not across records.

---

Proposed Changes

1. Undeprecate navigate

Remove @Deprecated from the navigate methods in
Concourse.java and ConcourseServer.java. The per-destination
return structure (Map<Long, Map<String, Set<TObject>>>) is a
distinct capability that select does not and cannot provide. It
should be a first-class API.

2. Rewrite navigateKeysRecordsAtomic to Use BFS Graph

Replace the current linear loop with a bulk implementation that:

1. Builds a single Node graph for all navigation keys (reuse
   the existing Node infrastructure from Stores.select).

2. Processes all source records together at each graph level,
   rather than processing one source record at a time. At each
   junction, batch-select all destination records at once:

   // Instead of N calls to store.select(link):
   Map<Long, Map<String, Set<TObject>>> bulk =
       store.select(allLinksAtThisLevel);

3. Uses Store directly instead of AtomicOperation, since
   navigation is a read-only operation that does not need conflict
   tracking tokens. The advisory read lock is sufficient.

4. Acquires the advisory lock once for the entire operation,
   not per-record.

This would make the server-side work genuinely more efficient than
N individual selects: O(depth) bulk reads instead of
O(N * depth) individual reads.

3. (Optional) New Batch Select Variant

If undeprecating navigate is undesirable, consider adding a new
method:

Map<Long, Map<String, Set<TObject>>> selectDestinations(
    Collection<String> keys,
    Collection<Long> records);

Same semantics as navigate (per-destination keying), but
implemented on the modern Stores.select infrastructure from the
start.

---

Impact

Scenario	Current	Proposed
1 parent, 300 children	301 RPCs or 1 RPC with linear server loop	1 RPC with bulk server reads
10 parents, 30 children each	301 RPCs or 1 RPC with 10x linear loop	1 RPC with depth-level batching
Server lock acquisitions	N per-record or N per-AtomicOp-select	1 for entire operation
Read token overhead	N tokens registered in AtomicOperation	None (direct Store reads)

---

Files Affected

File	Change
Concourse.java	Remove @Deprecated from navigate methods
ConcourseServer.java	Remove @Deprecated, update handler to call new implementation
Operations.java	Rewrite navigateKeysRecordsAtomic using bulk BFS; remove @Deprecated
Stores.java	Potentially extend Node graph to support multi-source traversal