DeepFinder Performance Benchmark

2. Headline charts

Interpretation: depth 1 and 2 always return all paths the user has. From depth 3 onward, most users have more paths than we currently surface — they just don't see them.

3. What we measured

For each query, we recorded:

Sample size: 500 measurements per depth (1, 2, 3, 4) per run = 2,000 queries per run × 4 runs = 8,000 baseline queries, plus 2,400 sweep queries. Random synthetic contact as target each time.

Plain-English glossary

• p50 / p95 / p99: Sort all 500 latency measurements smallest to largest. p50 is the middle one (the typical case). p95 is the 25th-from-worst (what 95% of users will experience or better). p99 is the 5th-from-worst (the slow tail).
• Hop: One step through a work_overlap edge. "Walked 3 hops" = "we crossed 3 shared-employer connections between user and target."
• Branching factor: How many edges leave each contact in the graph. Higher = more paths, more work for the recursive walk.
• Truncation: Returning fewer paths than the SQL actually found. Caused by the public max_paths cap (50 at benchmark time, now 100).

4. The graph we tested against

We didn't have prod data on staging, so we generated a synthetic graph designed to mirror the largest real customer network: Inovia Capital (collection #1201).

How we sized it

Single read-only query on production aggregate stats:

SELECT
  COUNT(DISTINCT cwe.organization_id) AS distinct_orgs,
  COUNT(*)                            AS total_cwes,
  COUNT(DISTINCT cwe.contact_id)      AS distinct_contacts
FROM user_contact_collections ucc
JOIN contact_work_experiences cwe ON cwe.contact_id = ucc.contact_id
WHERE ucc.collection_id = 1201
  AND cwe.organization_id IS NOT NULL;

Topology generator

Distribution we got

5. Four independent runs

We ran the same benchmark four times to confirm reproducibility.

Run 1 (100 iterations × 4 depths)

Run 2 (500 iterations)

Run 3 (500 iterations)

Run 4 (500 iterations — buffer pool fully warm)

Interpretation

• Depths 1-2 are rock-solid stable — sub-millisecond variance across runs. Essentially "free" queries.
• Depth 3 has higher variance at p95/p99 — Run 3 saw p95=44.5 vs Run 2's 14.4 (3× spread). This is real: the cost depends on which random target was picked. A target with rich work history explores a much bigger frontier.
• Depth 4 is consistently around p95 70 ms, p99 100-120 ms. The truncation cap (50) actually stabilizes the upper tail because once we hit it the walk stops.
• Truncation rates are stable across runs: ~70% at depth 3, ~94% at depth 4.
• Run 4 was noticeably faster — buffer pool was fully warm by then (cumulative cache from runs 1-3).

The variance at depth 3 is a feature, not a bug — it's telling us "some users have richer networks than others, and DeepFinder's cost reflects that."

6. What this means in product terms

"Should we raise the depth cap from 3 to 4?"

Performance says yes — depth 4 is fast enough.

• Depth 4 p95: ~70 ms (margin to 250 ms cap: 3.5× slack)
• Depth 4 p99: ~100-120 ms (margin to 250 ms cap: 2× slack)
• No timeouts observed across 1,500 depth-4 queries

The decision is purely about whether 4-hop connections feel meaningful to users — not about whether the system can compute them.

"Are we losing user value because of the 50-path cap?"

Yes — at depth 3+, ~70-94% of the time at the benchmark-time default. When a user hit this endpoint and we told them "you have 50 paths to this person," in a network like Inovia they probably had many more we just clipped. Raising the cap is safe from a perf standpoint at depth 3, but adds latency at depth 4 (see the max_paths sweep below). Default has since been raised to 100.

Are the cap defaults right?

7. Parameter sweeps

MAX_EDGES_PER_HOP sweep (depth 3, 200 iterations each)

MAX_EDGES_PER_HOP bounds how many overlap edges DeepFinder follows from each contact during the recursive walk. Too low → miss real paths. Too high → frontier explodes.

What this tells us

1. The cap of 25 is not the binding constraint at all. Mean paths only nudges from 39 → 43 across all cap values — the public max_paths (50 at benchmark time) clipped long before the frontier cap kicked in.
2. Even MAX_EDGES_PER_HOP=10 returns ~95% as many paths as the default. If you wanted to cut perf cost, dropping to 10 is essentially free in user-visible terms.
3. The cap exists for adversarial cases, not the average case. A hyper-connected hub contact (think a hiring-manager with hundreds of overlaps) would push the recursive frontier to thousands without the cap. Our synthetic doesn't generate those, so we don't see the cap save us — but it's correct insurance.

Recommendation: keep at 25. Don't tighten (small risk of cutting real edges from hub contacts), don't loosen (no benefit because max_paths clips first).

max_paths sweep (depths 3 and 4, 200 iterations each)

The public max_paths param (backed by the DEFAULT_LIMIT constant) clips paths returned to the API caller. We tested 50, 100, 200, 500.

What this tells us

1. At depth 3, raising max_paths is essentially free. p95 stays around 12-15 ms across all values. Mean paths jumps 43 → 99 (max_paths 50 → 500) and truncation drops 67% → 2%. You can comfortably triple max_paths at depth 3 with zero perf cost.
2. At depth 4, max_paths is the perf knob. Higher value = more rows to sort and serialize. max_paths=500 hits p95 312 ms — over the 250 ms budget. max_paths=200 lands at 201 ms (knife edge).
3. Diminishing returns are clear. max_paths 50 → 200 doubles paths returned; 200 → 500 only adds 16% more. Most users have under 100 useful paths even at depth 3.
4. A depth-aware max_paths could give the best of both worlds:
   • depth 1-3: max_paths=200 (truncation 12%, p95 still ~15 ms)
   • depth 4: max_paths=100 (truncation 90%, p95 ~115 ms — well under budget)

Recommendation (applied): default raised to max_paths=100; hard cap at 500. MAX_LIMIT clamps user-supplied values. For 4-hop loads consider clamping to 100 in the controller.

walk_rows verification (H4) — direct EXPLAIN ANALYZE measurement

Hypothesis H4 ("depth-3 walk_rows p99 < 50,000") was previously inferred from latency. We now measure it directly: perf:deep_finder_explain wraps the recursive CTE in EXPLAIN (ANALYZE, FORMAT JSON, BUFFERS), parses the plan tree, and sums Actual Rows across every node. 100 iterations × depths 1-4 against the 500k-contact synthetic graph (collection #4386):

What this tells us

1. H4 passes with margin. Depth-3 walk_rows p99 = 3,645 — 13.7× under the 50,000 budget. The recursive walk is doing far less work than we feared at the planning stage.
2. Walk size grows ~10× per hop, not exponentially. p50: 7 → 83 → 482 → 4,404. The MAX_EDGES_PER_HOP=25 cap and the target-rooted backward-BFS shape (frontier × seed-side join) both contribute to keeping fan-out tame.
3. Peak frontier is much smaller than total walk. Depth-3 p99 peak is 651 rows in any single plan node — well within work_mem for sort/hash operations.
4. Zero disk reads observed. All 800 queries served from buffer cache after warmup. The contact_connections indexes fit comfortably in shared_buffers at 500k contacts / 2.3M edges.
5. Depth 4 is still under the H4 threshold (29,367 vs 50,000). The latency cost at depth 4 (114 ms p95) comes mostly from the Ruby-side path-building + sort, not the SQL walk itself.

Reproduce: bundle exec rake "perf:deep_finder_explain[100,4,<collection_id>]"

Concurrent load — does DeepFinder hold up under contention?

One DeepFinder call is fast in isolation. Real production traffic stacks calls; we need to know how the system behaves when many users (or many tabs from one user) hit the endpoint simultaneously. Task perf:deep_finder_concurrent spins up N threads, each pulling targets from a shared queue and running DeepFinder.call until exhausted. Connection pool is bumped to N+5 for the run so threads don't block on connection waits.

What this tells us

1. Throughput plateaus around 14-17 req/s regardless of concurrency. Adding threads within a single Ruby process doesn't increase total throughput — it just spreads the same work across more in-flight calls.
2. Per-call latency scales nearly linearly with concurrency. p50: 65 → 232 → 767 → 799 → 2,492 ms as we go 1 → 5 → 10 → 20 → 50 threads. This is the canonical signature of GVL-bound execution: Ruby's Global VM Lock means only one thread can run Ruby code at a time, even though DB IO releases the GVL. Path-building, sorting, and hydration result-construction all run inside the GVL.
3. Error rate stays under 1% even at 50× concurrency. One timeout at c=5 and one at c=50 — both deep_finder.timeout at 250 ms. The recursive CTE plus contended buffer cache occasionally hits the SQL statement_timeout, but the system degrades gracefully (it doesn't lock up or cascade).
4. Implication for production: horizontal scaling (multiple Puma worker processes) is the way to scale throughput. A single Puma worker with 5 threads will sustain ~14 req/s; 4 workers gives 56 req/s with no per-call latency penalty.
5. Implication for hot users: a single tab firing many DeepFinder calls in parallel (e.g. autocomplete suggestion fan-out) will see latency degrade rather than benefit from parallelism. Frontend should serialize or batch requests for a single user.

Reproduce: bundle exec rake "perf:deep_finder_concurrent[50,500,3,<collection_id>]"

8. Hypothesis verdicts

9. How to reproduce

One-command setup:

cd ~/Desktop/projects/getro
make up                              # Brings up dev env

# Seed (~5 min)
docker exec getro_backend bin/rails runner /tmp/perf_seed_500k_inovia.rb

# Backfill (~40 min — the longest step)
docker exec getro_backend bin/rails runner /tmp/perf_backfill_synthetic_only.rb

# Run benchmark (~7 min for 500 iter × 4 depths)
docker exec getro_backend bundle exec rake 'perf:deep_finder_load_test[500,4]'

The rake task accepts:

perf:deep_finder_load_test[iterations, max_depth, collection_id]

• iterations — queries per depth (default 100)
• max_depth — 1..4. Setting 4 lifts the production hard cap of 3 just for the test (restored on exit).
• collection_id — optional. If set, attaches synthetic contacts as shared UCC rows on an existing collection (e.g. 11 for the dev "GetroJobs staging environment"). If omitted, creates a synthetic collection.

Cleanup

All synthetic rows are tagged with prefixes (perf-synth- for contacts, PERF_SYNTH_ for orgs). Cleanup is a single multi-statement DELETE.

10. Impact: before vs after the cap changes

We shipped two changes informed by this benchmark. This section quantifies what users actually get from each.

Change A — DEFAULT_LIMIT 50 → 100 (a.k.a. max_paths param)

At depth 3, doubling the default cap nearly doubled the number of paths users see, and cut the truncation rate almost in half — with no measurable latency impact.

In plain English: before, two-thirds of users at depth 3 had paths we silently dropped. After, only about a third do — and the user still gets twice as many paths visibly. At depth 4, the change costs ~40 ms of latency at p95 (75.9 → 114.2 ms) — still well under the 250 ms budget — in exchange for nearly doubling visible paths.

Change B — MAX_DEPTH_HARD_CAP 3 → 4

Before this change, an API caller passing ?max_depth=4 got silently clamped to 3. After, callers can opt in to 4-hop searches when they want deeper reach.

In plain English: users who explicitly want "show me anyone within 4 hops" now get that — at a slight latency cost (114 ms vs 14 ms for 3-hop) but well within the timeout. Default behavior is unchanged, so existing integrations see zero impact.

Change C — MAX_LIMIT clamp at 500 (server-side guard)

A safety net we added because the API previously accepted any positive value. A caller passing max_paths=10000 could force expensive sorting and risk hitting the SQL statement_timeout. (The deprecated ?limit= alias is still accepted for backwards compatibility but routes to the same clamp.)

No user-visible change in normal cases — only blocks abusive / accidentally-huge requests.

Change D — In-network filter at every recursive hop (correctness fix)

The original DeepFinder enforced UCC.shared membership only on the terminal contact of the walk (the seed-side endpoint). At depth 3+, this allowed paths to traverse arbitrary out-of-network contacts as middle hops — a divergence from the 2-hop sister Finder (which requires every via_contact to be in UCC.shared) and from the curated-network product contract.

The fix: an EXISTS subquery inside the recursive lateral, evaluated before ORDER BY so the MAX_EDGES_PER_HOP cap picks the 25 most-recent in-network edges. Out-of-network edges no longer compete for cap budget. This also resolves the multi-network scaling concern flagged earlier — the walk only ever traverses the current network's subgraph regardless of total graph size.

To keep the per-edge UCC probe cheap, a partial covering index was added (20260507163048):

CREATE INDEX CONCURRENTLY index_ucc_in_network_membership
  ON user_contact_collections (contact_id, collection_id)
  WHERE source = 5 AND user_id IS NOT NULL;

Each EXISTS probe becomes a single index-only scan. Benchmarked at 50 iterations × 4 depths against collection #4386 (worst case for EXISTS — all 500k contacts are in UCC.shared, so the filter prunes nothing):

Walk_rows essentially unchanged — H4 still passes (depth-3 p99 = 3,444 vs the 50,000 budget). What did change: mean paths returned jumped 47-1,449% across deeper queries because the 25-edge cap is no longer wasted on out-of-network dead-end branches. Depth 4 went from 5.9 → 91.4 paths (truncation 4% → 92%) — the walker was previously starving in-network edges to follow noisy out-of-network ones.

Production expectation

The benchmark above is the worst case: every contact is in UCC, so EXISTS prunes nothing and adds pure overhead. Real customers will see the opposite — a 50k-contact network in a 10M-edge global graph means EXISTS rejects ~99.5% of edges via index seek, so the recursive walk shrinks 100-200×. Depth-4 latency in production should be substantially under the pre-fix numbers.

Architectural follow-up (not required): a per-collection edge join table (contact_connection_collections) would replace the EXISTS probe with a direct B-tree lookup — see ADR follow-up. Worth doing if depth-4 p99 ever creeps toward 250 ms under real load.

11. Full post-fix re-run (2026-05-08)

All headline benchmarks re-measured against the same 500k synthetic graph (collection #4386) with the in-network filter (commit 90df3db2) + partial covering index (ed5b86f5) in place. Sections §2-§7 above reflect pre-fix baseline numbers — kept as historical anchors. This section is the source of truth for current behaviour.

11.1 Latency by depth

Read: Run 2's p95 is the right number to plan against. Depth 1-3 sit comfortably under the 250 ms timeout. Depth 4 p95 (204 ms) is just under budget; p99 (370 ms) crosses it on the synthetic worst case (every contact in UCC — no filter benefit). Production sparse networks should land well below.

11.2 walk_rows verification (H4)

Direct EXPLAIN ANALYZE measurement — same methodology as §7.5, post-fix:

H4 still passes at depth 3: 4,036 walk_rows p99 vs 50,000 budget — 12.4× under. Depth 4 p99 (53,968) marginally exceeds the H4 ceiling at the absolute tail, driven by occasional fan-out on hub contacts; p95 (24,754) sits well within. Zero disk reads — index still fits in shared_buffers.

11.3 MAX_EDGES_PER_HOP sweep (post-fix)

Same methodology as §7 (200 iter × depth 3, sweeping cap values). Post-fix the cap interacts differently with latency than pre-fix:

Surprising finding: post-fix, MAX_EDGES_PER_HOP=10 has the lowest tail latency (p99 129 ms vs 745 ms at the current 25). Mean paths only drops from 67.8 to 61.0 — modest. The cap-25 default was tuned pre-fix; post-fix the in-network filter already prunes most edges, so a tighter per-hop cap reduces variance without losing meaningful coverage. Recommendation: consider lowering to 10 — open question whether the path-coverage trade is worth the latency stability.

11.4 max_paths sweep (post-fix)

Same methodology as §7 (200 iter at depths 3 and 4):

Read: Depth 3 stays well within budget across all caps. Depth 4 latency scales with max_paths: the higher the cap, the more paths to sort/hydrate post-walk, the more p99 grows. max_paths=100 at depth 4 (current default) sits at p95 ~490 ms in the synthetic worst case — over the 250 ms timeout. Production should land lower, but if depth 4 becomes a hot path, consider a depth-aware controller clamp (depth 4 → max 50).

11.5 Concurrent load (post-fix)

Full curve, 500 calls × depth 3, same setup as §7.6 (connection pool bumped to N+5):

Head-to-head vs §7.6 pre-fix

What this tells us

1. Big win. The partial covering index pays its biggest dividend under contention: index-only scans on the EXISTS probe avoid heap fetches that thrash the buffer pool when many threads compete. Throughput jumps 2.5–3.2× across c=5/20/50 with zero timeouts (vs 2 in pre-fix).
2. Sweet spot is c=5 post-fix (45.3 req/s, p99 279 ms) — the system has room to pipeline a few requests per Ruby worker, but contention dominates beyond that. Pre-fix the curve plateaued at ~14-17 req/s regardless of concurrency.
3. Serial p99 regressed (178 → 351 ms) — the EXISTS subquery adds per-edge overhead in the synthetic worst case (every contact is in UCC). Production sparse networks should avoid this hit, since the EXISTS prunes 99%+ of edges before the recursion expands them. p50 actually improved at c=1.
4. Still GVL-bound for serial throughput (single Ruby process plateaus 17-45 req/s). Horizontal scaling (multiple Puma workers) remains the production path.

Reproduce: bundle exec rake "perf:deep_finder_concurrent[N,500,3,<collection_id>]" for N ∈ {1, 5, 20, 50}.

11.6 Net changes vs pre-fix

Honest summary: single-query latency degraded modestly at depth 3 (still well under timeout) and notably at depth 4 (p99 over timeout in synthetic worst case). In exchange:

• Correctness contract restored — paths only traverse in-network contacts.
• Multi-network scaling concern resolved — walk size is per-network, not per-graph.
• Path coverage massively improved — 1.5-15× more useful intros surfaced per query.
• Concurrent throughput 2.5× higher — the more meaningful number for production load.

The synthetic is the worst case for latency (every contact in UCC means EXISTS adds overhead with no filtering benefit). Production sparse networks should land between pre-fix and post-fix synthetic numbers, leaning toward the better end as the EXISTS prunes 99%+ of edges via index seek.

12. Open follow-ups

• ☑ Add walk_rows instrumentation (EXPLAIN ANALYZE per query) to confirm H4 directly — shipped (rake task perf:deep_finder_explain; results in §7.5 above; H4 passes with 13.7× margin).
• ☑ Test with concurrent load (e.g. 50 parallel DeepFinder calls) to verify perf under contention — shipped (rake task perf:deep_finder_concurrent; results in §7.6 above; throughput plateaus ~14 req/s within a single Ruby process — GVL-bound; horizontal scaling is the answer).
• ☐ Run the same benchmark on staging once we mirror real Inovia data (Privacy/T015 review pending).
• ☑ Decide on LIMIT=50 increase — shipped (commit 29b04563: DEFAULT_LIMIT → 100, MAX_LIMIT clamp at 500).
• ☑ Decide whether to lift MAX_DEPTH_HARD_CAP — shipped (commit 29b04563: lifted from 3 to 4).

Companion docs: spec.md · performance.md · index.html · raw CSVs in backend/out/perf/