Repository navigation
Ranking a traversal-introduced binding depends on declaration order #789
Description
Behaviour
Ranking a binding that a traversal introduces depends on the order the match block declares its bindings. With the ranked binding declared first, the query answers; declared after the binding it is reached from, it fails:
query q() { match { $p: Person { name: "p1" } $p knows $d } return { $d.slug } order { bm25($d.body, "needle") } limit 1 }
- Engine v1 (the default):
search-ordered query produced rows without its 'd._score' ranking column. - Engine v2: refused at planning, reported as an internal error (A planner refusal by design is returned as an internal error (HTTP 500) #786), with the fix "order on the traversal's source binding, or match the destination with search()".
The same failure was reported twice from real graph work: a passage search scoped by a matter and its revisions, and a semantic search over the neighbours of one node selected by its key.
Mechanism
The compiler's lowering roots each traversal-connected component at its first-declared binding (crates/omnigraph-compiler/src/ir/lower.rs, scan_root, which prefers a searched binding only inside a correlated block). Only the root gets a scan, and ranking runs on a scan, so a ranked binding that is not the root has nowhere to run. Issue #750's filter half was fixed on engine v2 by #760; this is its ranking half.
Expected
Declaration order is not semantics. The ranked binding roots its component on both engines, so these queries answer regardless of order. On engine v2 the planner may also start from a selective other end (one key-selected node) and rank only the rows the traversal reaches. Only rrf arms on two bindings of one component stay refused, as a typed bad request. Tracked in RFC 0047 (#791, rollout step 4).
Activity
ragnorc commentedon Oct 16, 2026
Triage: reproduction and fix assessment
Summary
When a query ranks a node that a traversal reaches, the result depends on the order of the
matchclauses. If the ranked node is not the first node in its traversal group, the query fails. Engine v2 refuses it at planning. The frozen engine v1 fails at execution. Declaration order must not change the result. RFC 0047, rollout step 4, already gives the fix: the ranked binding becomes the root of its traversal group.Reproduction verdict: reproduced on both engines, with two differences from the report
Environment
mainat864495a863bf92a7f4084dce6b0d47743b112b2a(clean worktree, fetched 2026-10-16).Differences from the report
set engine = v1is refused:unknown value 'v1' for setting 'engine'; expected one of v2(settings.rs). Engine v1 is now the frozen reference engine. I ran it throughSession::with_read_executor(ReferenceEngine), which is the same path that GQT's--- expect same as v1uses.kind: Plan, codeP001), and its fix text changed (see below).Fixture. The report gives no schema or data. I used the smallest fixture that fits the reporter's query.
d3has a higher BM25 score thand1, but onlyp2reachesd3. So a result that ignores the traversal shows up as wrong.Minimal failing test on
main(the reproduction proof). I saved this ascrates/omnigraph-gqt/cases/v2/planner/issue_789_ranked_destination_roots_its_component.gqt. It uses the reporter's exact query:There is no fix yet, so the after-fix half of the test does not apply. With a fix, this case must become green with no change to its expectations.
Both engines, same store. I used a scratch libtest in
omnigraph-gqtthat opens the seeded case store and runs each query on v2 and on the reference engine (cargo test -p omnigraph-gqt --locked --lib scratch_issue_789 -- --nocapture). I also pinned the same outcomes in a green probe.gqtcase.bm25,$pdeclared first,$dnot declaredP001: bm25() orders $d, a traversal destinationsearch-ordered query produced rows without its 'd._score' ranking columnnearest($d.embedding, [1,0])(the "neighbours of one key-selected node" report)P001: nearest() orders $d ...... without its 'd._distance' ranking column$pfirst, then$d: Docdeclared secondP001rrf(nearest($d…), bm25($d…)), both arms on$d,$pfirstP001: nearest() orders $d ...[{"d.slug":"d1"}]$d: Docdeclared first (bm25, nearest, rrf)[{"d.slug":"d1"}][{"d.slug":"d1"}]The v2 diagnostic is now:
{ kind: Plan, code: "P001", stage: plan, expression: bm25($d.body, "needle"), fix: "declare$dfirst inmatch, so the ranking starts the traversal" }. That fix is the workaround, and it works. But it makes the caller do what the language can do itself.Root cause
NodeScan. The group walk starts only from declared bindings, in declaration order (lower.rsL358-L434).scan_rootpicks the first one, or a searched binding only inside a correlated block (performance: a correlated anti-join over a traversal materializes the product — quadratic, then Arrow offset overflow at ~8k rows #763) (L857-L870). It does not know the order key.$dhas no declaration. Only the traversal introduces it. So$dis never a root candidate: the IR isNodeScan $pthenExpand $p -> $d. Reordering the declarations alone cannot fix this case.rankstep finds that the scan of$dis a dependent scan or a hash-join build, and it returnsP001(optimizer.rsL2546-L2586).NodeScan. So the score column of$ddoes not exist, and the query fails at execution. Engine v1 does answer therrfrow (the bug: rrf order on a traversed binding fails on engine v2 #762 shape). This agrees with the v1 table in bug: rrf order on a traversed binding fails on engine v2 #762's retest comment. I did not trace the v1 fusion path that gives this result.The defect is in the shared compiler, not in Lance and not in an engine executor. The reference engine reads the same
QueryIR. So one compiler fix changes both engines, and the frozen v1 files (frozen.rspins) stay unchanged.Recommended fix (correct by design): RFC 0047 step 4 in the compiler
lower_queryto the top-levellower_clauses. This is the variable ofnearestorbm25, or of anrrf()whose two arms rank the same variable. Correlated blocks have no order, so they keep the performance: a correlated anti-join over a traversal materializes the product — quadratic, then Arrow offset overflow at ~8k rows #763 rule.scan_root, at the top level, root the group that holds that variable at that variable.NodeScanof its checked node type. The type is inscope.bindings(BoundVariable::Node) and inResolvedTraversal::{src,dst}_type. Whether a variable is declared must not change the plan's meaning.deferred_filterspath moves their inline filters ({ name: "p1" }) onto theExpandthat introduces them. The traversal loop already makes a reverseExpandwhen only the destination is bound (L529-L555).rrf()arms on two bindings of one group from plannerP005to a compiler type error, as the RFC says. Keep the planner check as a loud internal check, so that a later lowering regression cannot return wrong rows silently.P001arm ofrank.Tests (extend the existing owners):
.gqtcase above, plus steps fornearest, single-bindingrrf(this closes bug: rrf order on a traversed binding fails on engine v2 #762 too), multi-hop and reverse traversals, an undirected traversal, a source with no edges (empty result), and two paths to one document (multiplicity). Add--- expect same as v1where v1 is correct, and--- expect planthat names the ranked root.neareststep in which the global nearest document is not reachable. My fixture givesd1andd3the same vector, so it does not test this. This step proves that the ranked root uses the prefilter gate and the overfetch ladder, and not a top-k that a later filter cuts.NodeScan, and the source's filter moves onto the reverseExpand.P001refusal for this shape: step 4 (nearest_on_a_traversal_destination) ofcases/v2/planner/search_order_on_an_unranked_binding_and_a_destination.gqt, thenearest_destinationpart ofengine_v2_plan_replay.rs::a_search_order_on_a_traversal_destination_is_a_typed_bad_request_issue_786, andranked_var_is_expand_dstinrrf_prefilter_gate.rs::shape_fence_covers_all_fallback_rows. Keep theirrrftwo-binding refusal parts.Edge cases and costs
p1. For a key-selected source with few edges, that is slower than "expand first, then rank". The result stays correct. RFC 0047 step 8 is the performance follow-up for this.docs/dev/lance.mdcontrols this.rrf()with arms on two bindings of one group cannot root both. It stays refused, as the issue says.Alternatives
$d. It adds semantics from text order. Invariant 9 rejects it.Docscan as a hash-join build)expect same as v1cannot guard it. The root choice then lives in two places. This is step 8's area, not a first fix.Software liability. The recommended change adds one input to lowering: the ranked variable. The root becomes a function of the pattern and the leading order key, not of the text order. After five more changes of this kind (cost-based roots, selective-key roots, more ranking functions), the root decision must have one owner. The compiler rule is the semantic default. A planner reversal (step 8) must be a validated rewrite of that default, not a second rule. The open RFC #996 says that it "does not reorder joins or change which binding roots a pattern", so it does not conflict. The quality that this fix gives lower priority is efficiency for key-selected sources. That is acceptable, because correctness comes before performance, and step 8 is tracked.
Lance upstream assessment
combined_fields(BM25F). #9058 says that the filter and coverage forms are still open for single-columnmatchtoo.nearestroot gets a traversal prefilter.Related work
cases/v2/planner/issue_750_destination_search_membership.gqtguards it.rrf()form of this defect, with both arms on one traversal-reached binding. It has the same root cause and is a narrower scope, so the same fix should close it. Ranking a traversal-introduced binding depends on declaration order #789 is the broader issue, and bug: rrf order on a traversed binding fails on engine v2 #762 does not supersede it.scan_rootor references this issue.Limitations
bm25andnearestrows of the table.set engine = v1is gone.