query: bounded node-and-neighborhood expansion with edge identities #649

Activity

1. ragnorc

   added

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   featureFeature proposalFeature proposal

   on Sep 5, 2026
2. ragnorc commented on Oct 18, 2026

   

   ragnorc

   on Oct 18, 2026 – with Cursor

   ContributorAuthor

   More actions

   Summary

   A client that has one entity, and does not yet know the schema, needs one bounded read of that entity and the edges that touch it. Typed traversals already return those edges when the client names the edge type. There is no read that selects the incident edge types for the client, keeps the root when it has no neighbor, and returns a page with a truncation signal.

   This gap is still present on main be031fea766fc8b280137f9ad9f34d4d2b3087bc. No other open issue replaces this request. This comment does not close the issue.

   Reproduction

   Verdict: reproduced. The observable gap matches the report. Later traversal work added wildcard and edge alternation inside one pair of node types. It did not add a generic expansion.

   Environment

   • Commit: be031fea766fc8b280137f9ad9f34d4d2b3087bc (origin/main after git fetch origin main on 2026-10-18).
   • Binary: omnigraph 0.14.0, HTTP contract 0.13, internal schema 16. The debug binary in this checkout is newer than every Rust source. The sources were not modified.
   • Graph: local file, CLI embedded engine, branch main. No server. No Cedar policy.

   Seed

   Three node types. Person.code, Ticket.code, and Place.code are string @key properties. Person and Ticket both use the key value shared.

   Edges: Knows: Person -> Person (since, note), WorksAt: Person -> Place (role), Mentions: Ticket -> Person (weight). Endpoints are not @unique, so two Knows edges can share the same ends.

   Load commit hb1.01M578ENCNFQTQX289B0ZTFVKJ.1.01M578ENCNFQTQX289B0ZTFVKJ: 12 Person, 1 Ticket, 1 Place, 12 Knows, 1 WorksAt, 1 Mentions.

   hub has 10 outgoing Knows edges. k1 (note peer, since 2019) and k2 (note again, since 2021) both go to a. Incoming Knows k6 comes from a. WorksAt w1 goes to hq. lonely has no edge. loop has self-loop k5 and incoming k4. Mentions m1 goes from Ticket shared to Person shared.

   What one call does

   omnigraph schema show writes the full .pg source (324 bytes for this schema). GET /graphs/{graph_id}/schema returns that same source string. GET /graphs/discovery lists graph ids. It does not expand an entity. The only entity read route is POST /graphs/{graph_id}/query.

   Attempt	Result
   expand $p: Person { code: "hub" }	Q001. Exit 1.
   match { $x }	T6: $x is not bound. Exit 1.
   $p * $n with only $p: Person declared	T5: wildcard traversal requires explicitly declared source and destination node bindings. Exit 1.
   $p (knows | worksAt) $n	T5: endpoint $n resolves to type Person but edge WorksAt expects Place. Exit 1.
   optional { $p knows $n }	Q001. Exit 1.
   limit 2 offset 2	Q001, expected order_clause. Exit 1.
   return { $e }	T23: an edge binding cannot be used bare. Exit 1.
   $e.role on a Person-to-Person wildcard	T6: edge Knows has no property role. Exit 1.

   What the client must do, and what it gets

   These rows are from the load commit, except the snapshot pair, which is marked.

   The client reads the schema. It then runs one traversal per edge type and direction, or one wildcard per declared pair of node types.

   Outgoing Knows with an edge binding returns 10 rows. Both parallel edges are present, with $e.@id, $e.@type (Knows), $e.@src, $e.@dst, since, and note. Incoming Knows returns 1 row (k6). Undirected <knows> returns 11 rows (the 10 outgoing plus k6). It does not include WorksAt.

   $p $e:* $n with $n: Person returns those same 10 outgoing Knows rows. $p $e:* $c with $c: Place returns w1 (role eng). One wildcard does not cross the two destination types.

   One match that requires both a Knows traversal and a WorksAt traversal returns 10 rows. Every row repeats w1. The two patterns multiply. A root with no Knows edge is dropped, even when a WorksAt edge exists.

   A node read of lonely returns 1 row (@id lonely). The same root with a required knows traversal returns row_count 0 and exit 0. The root is absent. count { $p knows $n } = 0 keeps the root and returns no edges.

   The self-loop query on loop returns 1 row, k5, with $e.@src and $e.@dst both loop. Undirected <knows> from loop returns 2 rows, k4 and k5. k5 appears once.

   Mentions from Ticket shared returns 1 row. The ticket @id is shared and the person @id is shared. A Person read of key shared returns Shared Person. A Ticket read of key shared returns Shared Ticket. The id string does not carry the type.

   limit 2 with order { $e.@id asc } on outgoing Knows returns k1 and k10. row_count is 2. The JSON object has query_name, target, row_count, columns, rows, and graph_commit_id. It has no truncation field and no page token. String order is k1, k10, k11, k12, k2. A follow-up $e.@id > "k10" with limit 2, pinned to the load commit, returns k11 and k12. A follow-up $e.@id > "k2" returns k3 and k4 and skips k10, k11, and k12.

   set traversal_work_limit = 1 on the Person wildcard fails before any row: resource limit exceeded for traversal_work_limit: actual 2, limit 1. Exit 1. The same setting on a named knows query with limit 1 returns 1 row. Exit 0.

   An insert of Knows from hub to lonely then publishes commit hb1.01M578ENCNFQTQX289B0ZTFVKJ.2.01M578HT7615G0TA7V0B1N1XH8. A head read finds that edge, id 01M578HT6YS2NG3QESQ70G24A9. The same query with --snapshot set to the load commit returns row_count 0. Each call has one graph_commit_id. Two calls share a snapshot only when the client passes that id.

   explain of the named Knows query shows ExpandExec with mode=indexed_scan.

   Difference from the report

   The report describes the gap and does not include a seed. The gap matches. crates/omnigraph/src/exec/query.rs is not in this tree. The cited tree is 02d182b6. On this main the expansion operator is ExpandExec. Wildcard and alternation exist. Neighborhood pagination is still outside the RFC that added them.

   Root cause

   The engine can expand one edge selection on one snapshot. It has no selection that means "every edge that touches this entity".

   A wildcard member set is the edges whose two ends are the two declared node types (typecheck.rs, EdgeSelector::Wildcard). Direction follows the declared source type (resolve_member). Knows and WorksAt do not share a destination type, so one wildcard cannot return both. An alternation uses the same endpoint rule. That is the T5 above.

   A required traversal keeps a root only when the pattern matches. There is no optional traversal. #658 tracks that language gap for one pattern. An empty neighborhood here also needs the root row, and it needs every incident type in one result. Those are different contracts.

   limit is a result cut. In query.pest the limit clause is the word limit plus an integer. There is no offset. ReadOutput.page is for branch diff only (openapi.json). A successful limited query does not say that more rows exist. scan_edges_stream filters one edge dataset with an IN list of source ids. It does not set Lance limit or offset. The result limit is a later plan node. traversal_work_limit applies to wildcard and alternation. It fails the query. It does not return a page.

   A one-column @key id is the scalar string (canonical_key_id). Two types can store the same string. The type is what separates them.

   Policy for a read is the graph or the branch. Per-entity and per-property authorization is not available (policy). This run did not install a policy. The expansion must use the same gate the query uses. It must not add a second channel.

   The affected class is every client that shows one entity and its incident edges. That includes the CLI, POST /query, and a tool that can run only a typed read. The missing piece is a contract. The commits in this run are intact.

   Recommended fix

   Add one typed read that expands a type-qualified root on one captured snapshot. Lower it to the per-type indexed probes the engine already runs. Do not add a neighborhood table, a side index, or a transport flag that means "expand everything".

   The contract:

   • The caller passes a node type plus a stable id or the declared key. The type is required. The id string alone is ambiguous, as shared shows.
   • The server takes the incident edge types from the captured catalog. The caller may filter by edge type and by direction. The caller names the display properties. A property that is not on that edge type is an error, as T6 is today. Do not invent a display field.
   • Each edge stays one row. The row carries the edge id, the canonical type, the stored @src and @dst, the direction of this match, and the requested properties. Parallel edges stay separate. A self-loop stays one row. Do not collapse rows by the pair of ends.
   • A root with no selected edge returns the root and an empty edge list. The call succeeds.
   • One response pins one graph_commit_id.
   • The page bound is a maximum number of edge rows. The response says when the page is short of the full neighborhood, and it returns a cursor. A stable cursor is (edge type, direction, edge id) in a documented order. A bare offset is not in the grammar. String order of ids is a real order, and k10 sorts before k2, so the cursor must be the engine's order.
   • Start with one hop. A deeper bound needs its own visited-count and result-count rules. Today's multi-hop traversal is a shortest-path distance. It does not return every edge on a cycle.
   • The scan for one page stops at the page bound, or the query fails with a named limit. A success that drops rows with no signal is a partial result. The deny-list rejects that shape.
   • Authorization is the branch read that already gates POST /query. Diagnostics use that same decision. Finer entity and property views belong to the actor-view work, not to a special case in this read.

   This keeps invariant 3 (one snapshot), invariant 9 (the meaning lives in the typed plan), invariant 7 (indexes stay derived), invariant 8 (a cut is visible), and invariant 11 (the response size is bounded). A second HTTP meaning that does not lower to that plan would split the contract. A maintained adjacency structure would add a second authority.

   Tradeoff. This design puts a clear page identity and one snapshot first. It does not build one index that covers every edge table. Each edge type remains its own Lance dataset. A single physical structure across those tables is the quality this choice defers. A fast list with a silent cut is a wrong answer.

   Alternatives

   • Keep client fan-out. The client can do this today. It reads the full schema, compiles one query per type pair and direction, and passes --snapshot (HTTP field snapshot) so the calls share a commit. limit does not say that the page is incomplete. This is the current behavior.
   • Optional traversals (#658) keep a root when one pattern misses. They do not union Knows and WorksAt.
   • Correlated count { } projections (#1050) return one count per named pattern. They do not return edge ids or neighbors. That issue treats a neighborhood route as a second query surface and prefers a projection for counts. Counts can land there. Identities still need this expansion.
   • Focused schema descriptions (#650) would tell the client the edges of one type without the full source. The client would still send the fan-out.
   • PR #884 would bind an interface. It is a draft. It does not define an open neighborhood or a page of mixed edge types.
   • The typed-edge-alternation RFC is accepted and complete. It says neighborhood pagination is outside that RFC.

   Liability. A limit with no cursor becomes a contract the first time a client treats the prefix as the full neighborhood. Shipping the read before actor views (PR #951) means every branch reader sees every incident edge the branch read allows. That is the same scope as POST /query today. A queue of neighborhood rows, or a shadow adjacency table, would add authority the manifest does not own.

   Lance

   Pinned Lance is 11.0.0 (released 2026-08-30). Latest stable is v13.0.0 (2026-10-07). v12.0.0 is between them. v14 is beta only (beta.19 on 2026-10-16).

   The edge probe is a filtered scan of one edge dataset. In the v11.0.0 scanner, use_scalar_index defaults to true, and limit(limit, offset) skips and cuts physical rows of that one scan. OmniGraph's scan_edges_stream sets the IN filter and the batch size. It does not set that limit. A btree answers equality, range, IN, and IS NULL (BTree). The plan for the named Knows query in this run is indexed_scan. A missing index is a full scan with the same rows. The engine logs that fallback. Index coverage is derived state.

   Upstream items that matter, and do not close this issue:

   • PR #9481, merged 2026-10-14, after v13.0.0. It moves the btree scalar index to the row-address domain. It is not in a stable release. OmniGraph tables use stable row ids. A later bump has to re-check address-domain coverage. The PR does not return a graph neighborhood.
   • Open PR #9875: a batched exact-match lookup on a scalar index. That can make an endpoint IN probe cheaper. It is still one column of one dataset.
   • Open PR #10122 and open PR #10041: address-domain index coverage and remap on stable-row-id tables. They protect index results across compaction. They do not add a page of mixed edge types.
   • Open issue #9817: a btree or full-text index with more than one segment can return a stale value after an update. OmniGraph already rebuilds a lagging index whole for this reason. A Lance fix changes the safety of the probe. It does not add the call.
   • Open PR #8568 and open PR #7836: take-shaped predicates and dynamic filters inside one scan. Open PR #9373: deletion checks from row offsets. These are single-dataset read paths.
   • Open PR #9468: a Python LanceScanner.take. It is not the Rust scan OmniGraph uses.

   No open or merged Lance change reads across datasets or returns a typed graph neighborhood. A neighborhood page must key on edge identity. A Lance row offset is not stable across compaction, so it is the wrong cursor.

   Related work

   • #658 is optional traversal for one pattern. It is open. It does not union edge types.
   • #648 is graph-wide search. Its reproduction comment names this issue as neighborhood expansion.
   • #650 is a focused schema description.
   • #1050 is count and exists as projections. It links here and chooses a projection for counts.
   • #606 is closed. Search contracts continue as PR #793. That work does not define this expansion.
   • #991 would add schema and ad-hoc read tools. Those tools would still run typed queries.
   • #989 is node identity across graphs. This request stays inside one graph.
   • #884 and #951 are the draft directions for a type union and for finer reads.
   • The alternation RFC (2026-09-30) records that neighborhood pagination is outside that RFC.

   Supersession: none. #649 remains the request for one bounded expansion that returns edge identities.

   Limitations

   • The run is the CLI on a local file graph. It is not a served HTTP call and not a Cedar 403.
   • hub has 10 outgoing Knows edges. That shows the page gap. It does not measure memory at a high degree. The statement that scan_edges_stream does not set a Lance limit is from the source, not from a byte counter in this run.
   • The two parallel edges use supplied ids. The edge added later uses a generated id. Both stay distinct.
   • Lance citations here are the btree format page and the pinned v11.0.0 scanner source. Release notes and the PRs above are the upstream comparison.