perf(exec): consume persisted CSR without edge-scale hash-map expansion

[DecisionNerd]

Problem

GraphForge persists derived adjacency as compact CSR, then expands that CSR into HashMap<u64, Vec<(edge_id, neighbor_id)>> views for traversal. Analyst verbs build another AdjacencyGraph containing node/UUID maps, per-node neighbor vectors, and vector maps. On large graphs these edge- and node-scale copies amplify RSS and delay first execution even when the canonical CSR is already valid and ordered.

The M4 scale work cannot realize the memory benefit of bounded index construction if execution immediately recreates object-heavy hash-map representations.

Objective

Consume persisted CSR and canonical dense node identity directly through bounded, borrowable Rust execution views, eliminating full-graph hash-map expansion while preserving every traversal and analyst-verb contract.

Debt / regime

• Debt type: architecture and data
• Quality regime: A compute

Requirements

1. Introduce a CSR-native adjacency view with checked O(1) row lookup over validated offsets and borrowed/owned slices for edge IDs, neighbor IDs, and any required source identity.
2. Preserve outgoing, incoming, and undirected semantics. Undirected iteration must retain the existing deterministic out-before-in tie behavior without materializing a full merged hash map.
3. Replace persisted-CSR conversion to HashMap<u64, Vec<_>> on index hits. Delta overlays and stale/missing-index fallback may use bounded auxiliary structures, but must not copy the complete valid base CSR.
4. Rework analyst projection storage around canonical dense node ordinals, compact UUID arrays/maps only where identity lookup requires them, CSR neighbor ranges, and bounded optional weight/vector columns. Do not duplicate every edge into per-node heap allocations.
5. Preserve typed/wildcard relationship selection, direction, parallel edges, self-loops, mirrored undirected identity, weights, projection fingerprints, runtime/ontology ID separation, and UUID-only public results.
6. Preserve generation revalidation, cancellation, resource limits, structured corruption/staleness errors, and scan-built fallback parity.
7. Integrate memory accounting from feat(api): define a bounded embedded execution resource policy #337 and consume the bounded, deterministic CSR produced by fix(storage): stream adjacency index builds past the 134,217,727-edge Arrow limit #336.
8. Keep Rust authoritative; Python and Node remain thin Arrow adapters.

Acceptance Criteria

• A persisted index hit performs no O(E) base-CSR expansion into hash maps or per-node heap vectors, proved by a deterministic structural counter or representation assertion.
• Traversal and every analyst-verb projection retain canonical schemas, ordering, values/fingerprints, errors, limits, direction, weights, and cancellation behavior.
• Outgoing, incoming, undirected, typed, wildcard, delta-overlay, stale-index, missing-index, and corrupt-index paths have direct parity coverage.
• Peak RSS and cold/warm first-use evidence on accepted test(performance): establish the M4 embedded baseline and entry gate #334 fixtures demonstrate the removed representation amplification; timing remains hardware-specific evidence.
• Selected-subgraph projection remains bounded by the selection plus required index metadata rather than copying the complete graph when the public invocation selects a subset.
• Existing public Rust and thin binding acceptance remains green at the exact changed head.

BDD Completion Scenarios

Scenario: A valid persisted CSR is queried without expansion

Given a committed graph with a fresh persisted adjacency index
When a fixed-hop traversal or analyst projection first accesses adjacency
Then execution reads validated CSR rows directly without constructing an O(E) hash map
And the public result and demand/cancellation evidence match the existing contract.

Scenario: Direction and delta semantics remain deterministic

Given parallel edges, self-loops, incoming/outgoing requests, and committed delta segments
When CSR-native views enumerate typed, wildcard, or undirected adjacency
Then entries appear in the established canonical order with correct identity and weights
And the valid base CSR is not fully copied to apply the overlay.

Scenario: Missing or invalid indexes fail over safely

Given a missing, stale, or corrupt persisted index
When execution resolves adjacency
Then the established rebuild/fallback or structured failure path occurs
And no partial CSR view or incorrect fresh status is exposed.

Implementation Notes

Likely surfaces include crates/graphforge-exec/src/adjacency.rs, algorithm_graph.rs, algorithm projection construction, graphforge-storage CSR readers, delta overlays, traversal execution, projection fingerprints, and M4 memory instrumentation.

Prefer a trait/view boundary that lets traversal and algorithms request deterministic row slices without knowing whether the backing source is persisted CSR, a bounded overlay, or the existing scan-built oracle.

Observability

Record aggregate backing representation, base and overlay rows accessed, selected nodes/edges, bytes retained, peak RSS, fallback reason, and projection fingerprint. Do not log UUIDs, properties, graph contents, or local paths.

Security And Privacy

No network or authorization surface is added. Continue validating CSR offsets, lengths, generation stamps, and contained files before exposing slices. Diagnostics must not expose graph data.

Testing

• Unit-test checked CSR row views, undirected merge ties, empty rows, boundary offsets, corrupt arrays, and overlay precedence.
• Integration-test traversal plus representative rank/cluster/similar/paths/analyze projections against the scan-built oracle.
• Mechanically compare all registered analyst verbs for schema/fingerprint parity through the shared projection boundary.
• Map Scenarios 1 and 2 to Rust integration/property tests and Scenario 3 to corruption/recovery tests; map large RSS evidence to the manual test(performance): establish the M4 embedded baseline and entry gate #334 matrix.
• Run formatting, targeted clippy/tests, and repository-required exact-head CI.

Documentation

Update execution/adjacency architecture, algorithm projection representation, memory-accounting methodology, and evidence-backed scale guidance.

Non-Goals

• Rebuilding CSR from Parquet; fix(storage): stream adjacency index builds past the 134,217,727-edge Arrow limit #336 owns bounded index construction.
• Streaming relational Parquet providers; perf(storage): stream partitioned Parquet execution with bounded memory #339 owns query scans.
• Parallelizing algorithms or changing their numeric semantics.
• GPU, distributed, server, or foreign graph-engine execution.

Related Issues

• test(performance): establish the M4 embedded baseline and entry gate #334 — entry evidence; blocks this issue.
• epic(performance): close M4 embedded performance and scale #335 — M4 close tracker; this issue blocks it.
• fix(storage): stream adjacency index builds past the 134,217,727-edge Arrow limit #336 — bounded deterministic CSR construction; blocks this issue.
• feat(api): define a bounded embedded execution resource policy #337 — embedded resource policy consumed by this issue.

[coderabbitai]

🔗 Related PRs

#217 - feat(api): add embedded write modes [merged]
#234 - feat: add portable project interchange [merged]
#278 - fix(ci): retain certification evidence as artifacts [merged]
#289 - fix(release): amend unpublished main npm artifact [merged]
#297 - docs(release): require one shared product version [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!