Consolidating the #9577 frontier-eviction PRs — findings + proposed next steps

[shiva-istari]

Hi all — thanks for the work on the maxfrontiersize k-shortest-path fix (#9577). We now have four open PRs targeting the same bug (#9576, #9599, #9607, #9678), plus a correctness harness (dgraph-benchmarks#95), and we'd like to consolidate down to one.

This post lays out what we found reviewing all four against the current source of your branches (fetched today), plus a benchmark cross-check. Based on it we're proposing to close two and move one forward — but we don't want to close anything over your heads, so please read the section on your PR and tell us if we've misread it. Corrections very welcome.

The short version

• Reviewed against current branch heads: fix(query): correct frontier trimming in shortest path #9599 and fix(query): correct frontier eviction in shortest path priority queue #9678 evict correctly; feat: Added a backpressure mechanism to shortestPath #9576 and fix(query): evict highest-cost node when MaxFrontierSize exceeded in shortest path #9607 do not.
• fix(query): correct frontier trimming in shortest path #9599 and fix(query): correct frontier eviction in shortest path priority queue #9678 are mechanically equivalent in the eviction path.
• Proposal: close feat: Added a backpressure mechanism to shortestPath #9576 and fix(query): evict highest-cost node when MaxFrontierSize exceeded in shortest path #9607, merge one of fix(query): correct frontier trimming in shortest path #9599 / fix(query): correct frontier eviction in shortest path priority queue #9678, and add a fast in-repo regression test (with the heavy large-graph check kept external).

Nothing here is a criticism of the effort — #9576 and #9607 both move in the right direction; the issue is specific and mechanical, detailed below.

Code review — verified against current PR source (fetched today)

PR	evicts	order	cap=0 guarded	proposed action
#9576	eviction unchanged — still pq.Pop() (removes the last heap slot, an arbitrary leaf)	evict-then-push	No	close
#9599	max (TrimToMax)	push-then-evict	Yes	keep (correct)
#9607	max (removeMax)	evict-then-push	No	close
#9678	max (removeMax)	push-then-evict	Yes	keep (correct)

@hr-alebel — as we read the current branch, the eviction path is unchanged: both sites still call pq.Pop() directly, which returns old[n-1] — the last element of the backing array, an arbitrary heap leaf, not the highest-cost node it should evict (the original bug). The PR's contribution is the watermark that throttles frontier expansion (it stops exploring new levels once the frontier reaches ~60% of the cap) — which changes how fast the frontier grows, not what gets evicted. So the optimum can still be dropped on eviction. Did we miss a change to the eviction itself? If the intent is expansion-throttling as a complement rather than a fix to eviction, that's useful context — let us know.

@veeceey — removeMax() picks the right target (highest cost), but two things as we read it: (1) it's evict-then-push, so a higher-cost newcomer can displace a lower-cost existing node before it's even compared; and (2) MaxFrontierSize=0 is unguarded, so at cap=0 it evicts before every push and the query stalls. #9599/#9678 avoid both by pushing first and guarding the zero cap. (A reviewer also flagged the O(n) scan at capacity.) Does that match your understanding?

@Schwarf — this looks correct to us: pq.Pop() gone, TrimToMax evicts the max, push-then-trim, cap<=0 guarded. We saw you pushed the trimming regression test on 2026-07-06 — thanks, that's still active. Your defense of push-then-trim over trim-before-push (vs #9607) matches exactly what we found independently.

@shaunpatterson — also correct: removeMax evicting the max, push-then-evict, MaxFrontierSize>0 guarded, and the broadest test coverage of the four (unit tests for removeMax/eviction plus integration tests running k-shortest queries at binding frontiers).

#9599 and #9678 are mechanically equivalent in the eviction path (both: drop pq.Pop(), push then evict the max node, guard the zero cap). The maintainers already flagged the #9599/#9607 overlap in review; our read resolves it — push-then-evict is the correct order.

Benchmark cross-check (directional — see caveat)

The harness (dgraph-benchmarks#95) compares Dgraph's output to a gonum v0.17 YenKShortestPaths oracle as sorted path-cost vectors, sweeping maxfrontiersize. On roadCOL (DIMACS Colorado, 435,666 nodes / 1,057,066 edges), 100 banded targets from gid=1, numpaths=2:

% = correct-of-returned; t = timeouts (excluded from denominator).

frontier	main	#9576	#9599	#9607	#9678
100	2% (t9)	3% (t3)	4% (t0)	3% (t0)	4% (t0)
1000	15% (t11)	15% (t11)	18% (t0)	18% (t0)	18% (t1)
2000	23% (t8)	23% (t12)	23% (t2)	23% (t0)	23% (t0)

Caveat, in the interest of not overclaiming: these are from an earlier sweep and haven't been re-verified against a fixed denominator yet (timeouts are currently excluded, which flatters the numbers), and caps large enough to numerically separate the two correct PRs (10K+) OOM'd on the bench VM. So we're basing the close/keep calls on the code review above, not these numbers. We'll republish the table against correct/attempted with peak-memory once the bench box is back up.

Two things the table does show clearly: (1) the bug reproduces on every branch under a binding cap, and (2) it's eviction-specific — uncapped, results reach 100% correct (37/37 on #9599), climbing 23% → 71% → 100% as the cap rises.

One framing point worth stating so we're all talking about the same thing: a bounded frontier is approximate by design — losing some optimal paths under a tight cap is expected. The #9577 defect is narrower — evicting the wrong element so the optimum is lost far more than a correct bounded eviction would. The correct-eviction PRs (#9599/#9678) fix that; they don't (and can't) make a tight cap lossless.

A note on the existing tests

#9678's integration tests already run k-shortest queries at binding frontiers — nice. But all the PR tests (both #9599's and #9678's) run on ≤5-node hand-built graphs with light assertions (the one binding k-shortest test only checks the optimal weight appears, via require.Contains, not the full k-cost set). On a 5-node graph the frontier barely binds, so they pass without exercising the failure we see on 400K-node graphs.

Worth stressing: the miss isn't size, it's that the tests aren't adversarial — none is built so that a wrong eviction and a correct one produce different answers. You don't need a big graph to reproduce #9577; you need a small hand-built one where (a) the frontier provably exceeds a small maxfrontiersize so eviction fires, and (b) the optimum-bearing node is the one buggy eviction discards. A neat way to assert it without an external oracle: pick a frontier that binds but is still large enough that a correct algorithm returns the full answer, then assert capped result == uncapped result on that graph — correct code passes, buggy code fails. That test runs in milliseconds and would go red on main/#9576/#9607 and green on #9599/#9678.

Proposed next steps — your input wanted before we act

1. Close feat: Added a backpressure mechanism to shortestPath #9576 and fix(query): evict highest-cost node when MaxFrontierSize exceeded in shortest path #9607 — for the specific reasons above. @hr-alebel and @veeceey, if you think we've misread your branch, please say so here and we'll hold off.
2. Merge one of fix(query): correct frontier trimming in shortest path #9599 / fix(query): correct frontier eviction in shortest path priority queue #9678. They're equivalent and both correct, so this is mostly a call for the two of you: do you have a preference? Options we see — merge fix(query): correct frontier eviction in shortest path priority queue #9678 (broadest tests) with credit to fix(query): correct frontier trimming in shortest path #9599, or merge fix(query): correct frontier trimming in shortest path #9599 (actively maintained) and port fix(query): correct frontier eviction in shortest path priority queue #9678's integration tests into it. Happy either way; we'd rather you two agree than have us pick arbitrarily.
3. in-repo (fast, blocking): add a small adversarial reproduction test to dgraph's own suite — a hand-built graph at a binding frontier that asserts capped == uncapped, so it goes red on buggy eviction and green on the fix. Runs in milliseconds, no dataset, safe for CI.

Please weigh in — especially @hr-alebel and @veeceey, since we don't want to close your PRs without giving you the chance to point out anything we've missed. Thanks again for all the work on this.

[hr-alebel]

Hi,

The proposal from my side fixes a more technical issue. As you noted you dont need a large graph to recreate the issue i have. All you need is a dense graph with a lot of connections between nodes, our tests set has ~10k nodes with almost 200k edges.

With the way dgraph currently operates this causes the the Yen K Algorithm to explode on memory usage, i am talking multiple dozens of GB of RAM.

The cause for that was the fact that the exploration happens independently of the verification of paths. Meaning that if you have enough CPU Cores to run the exploration really fast, it fills the queue at high speed, where emptying it is fairly slow.

So the idea of my implementation was to have a way to throttle down the exploration, so that a system with "moderate" amounts of RAM can run the search without crashing on OOM. Basically exchanging RAM with execution speed.

The implementation was specifically targeted at changing exploration (as you noted), because it seemed to be the easiest lever to change in my specific issue, especially with the idea of not changing the original behaviour of the rest of the functionality.

Edit:

the idea of not changing the original behaviour of the rest of the functionality

This mostly is important in the sense that for my usecase the correctness of all returned paths is more important than the overall speed, meaning ANY eviction is potentially a path that would have been returned.

[shiva-istari]

Thanks — that context helps a lot, and it matches our reading: #9576 changes how fast the frontier
grows, not what gets evicted, and that was deliberate.

The memory explosion you describe is real, and we can corroborate it first-hand: in our sweeps (DIM
ACS road graphs, numpaths=2), runs at maxfrontiersize ≥ 10K or unbounded repeatedly took the bench
VM down, with the alpha process pinned at the 48 GB cgroup cap we'd set — the same "multiple dozens
of GB" scale you hit. So the problem your PR targets is genuine; it's just a different problem fro
m #9577's wrong-element eviction.

Your follow-up is where we'd land too: backpressure as a query-time option. The two knobs are compl
ementary — maxfrontiersize bounds memory by evicting (inherently lossy; #9599/#9678 make the evic
tion pick the right victim), while your throttle bounds memory by trading speed (lossless with resp
ect to returned paths). For your use case, where any eviction is a potentially lost path, the throt
tle is arguably the right tool and eviction the wrong one.

Concretely: we'll close #9576 against #9577 as proposed, and we'd encourage you to open a separate
feature issue for an expansion-backpressure query option (rebased on the merged eviction fix, since
the two compose). Happy to link it from here. Would you be up for filing that?

[hr-alebel]

To add to my comment. I guess from reading the other PRs, mine is probably better solved as an option to the dql call. That way a user can decide on query time if they want to have higher speed or a deterministic but slower result.

[Schwarf]

Hi @shiva-istari,

thanks you very much for the detailed review and for summarizing the PRs.
I’d be happy to continue with #9599 as the base, given that it was the earlier correct push-then-trim eviction fix and already includes a regression test.
Of course, if @shaunpatterson has a different preference, I’m happy to coordinate so we avoid duplicating work.

[shiva-istari]

Thanks @Schwarf — works for us. Plan, pending @shaunpatterson's ack:

1. fix(query): correct frontier trimming in shortest path #9599 as the merge base — earlier of the two correct fixes (Feb vs Apr), actively maintained, already carries the TrimToMax regression test.
2. Port fix(query): correct frontier eviction in shortest path priority queue #9678's test coverage into it — the priority-queue unit tests plus the binding-frontier
   integration tests — with commit credit to @shaunpatterson.
3. Strengthen the equivalence test while porting: fix(query): correct frontier eviction in shortest path priority queue #9678 already has the right two ingredients s
   eparately — JSONEq(unconstrained, constrained) assertions (but at a cap that never binds on the t
   est graph) and binding-cap tests (but asserting only that the optimal weight appears). Combining th
   em — full-result equality at a cap that provably forces eviction — gives the adversarial red/green
   test from the post, in milliseconds, no dataset.

@shaunpatterson — we saw you rebased #9678 on the 14th, so flagging this directly: does the plan ab
ove work for you? If we haven't heard back in a week or so we'll proceed and credit you in the port
ed tests either way. The test coverage you wrote is the part that outlives both PRs — thanks for th
at.

[Schwarf]

Hi @shiva-istari,
any updates on this?

[shiva-istari]

@Schwarf sorry for going quiet on this for so long, that's on me.

Since Shaun hasn't chimed in, let's just move forward with #9599 as the base like we
discussed. Would you be up for adding the test coverage to your branch? Mainly two things:

• Bring over the priority-queue unit tests and the frontier integration tests from fix(query): correct frontier eviction in shortest path priority queue #9678
• Add the one test we talked about earlier in this thread: compare the full result of a
  capped vs uncapped query, with the cap set low enough that eviction actually kicks in.
  fix(query): correct frontier eviction in shortest path priority queue #9678 got close but never quite combined the two and that's really the test that
  would have caught k shortest path does not return the shortest path when using MaxFrontierSize #9577 from day one.

[Schwarf]

Hi @shiva-istari,

yes, I’ll do so on the weekend.