GQ: optional traversals that preserve unmatched root rows #658

Activity

1. ragnorc

   added

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   featureFeature proposalFeature proposal

   on Sep 5, 2026
2. azimafroozeh

   added

   needs-rfcSize L: the design must land as an RFC before any codeSize L: the design must land as an RFC before any code

   acceptedTriaged and validated; open for a PRTriaged and validated; open for a PR

   P-highHigh priorityHigh priority

   and removed

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   on Oct 1, 2026
3. ragnorc commented on Oct 18, 2026

   

   ragnorc

   on Oct 18, 2026 – with Cursor

   ContributorAuthor

   More actions

   Summary

   A required traversal keeps a root only when the pattern matches. A root with no matching neighbor is absent from the result. GQ has no optional pattern that keeps that root and returns a null neighbor or a null edge.

   A client that wants the entity and its optional context runs two queries, or joins the rows itself. This is a missing language contract. The commits in this run are intact.

   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 gap matches the report. Later query work added Boolean expressions, is null, wildcard traversal, and edge alternation. It did not add an optional pattern.

   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 the commit. The sources were not modified. rustc is 1.97.1.
   • Graph: local file, CLI embedded engine, branch main. No server. No Cedar policy.

   Seed

   Person.code, Place.code, and Ghost.code are string @key properties. Person.note and Knows.note are String?. Knows.since is I64. WorksAt.role is String?. Knows and WorksAt have no @unique, so two Knows edges can share the same ends. Ghost and Haunts stay empty.

   Load commit hb1.01M57SG9Q2YA49Q15J89JWJZGD.1.01M57SG9Q2YA49Q15J89JWJZGD: 8 Person, 1 Place, 0 Ghost, 6 Knows, 2 WorksAt.

   • lonely has no edge. note is null.
   • one has one Knows edge to ada (since 2019, note peer) and one WorksAt edge to hq.
   • many has Knows edges to bob, to cara, and two parallel edges to ada (since 2010, note old, and since 2020, note null).
   • loop has self-loop Knows (since 2001). @src and @dst are both loop.
   • worker has WorksAt to hq and no Knows edge.
   • ada, bob, and cara have no outgoing Knows edge.

   The empty graph, before that load, is commit 01M57SG5MK81GC3XXSKH6T6RQ3.

   Attempted optional syntax

   Attempt	Result
   optional { $p knows $n } inside match	Q001. Expected a clause. Exit 1.
   optional match { $p knows $n } after the match	Q001. Expected return. Exit 1.
   $p optional $n	T4. Unknown edge type optional. Exit 1.
   $p knows? $n	Q001. Exit 1.
   return { $p.code, count { $p knows $n } as knows }	Q001. Exit 1.
   not { $p knows $n } then return { $n.code }	T6. $n is not bound. Exit 1.
   return { $e } on a bound edge	T23. An edge binding cannot be used bare. Exit 1.

   optional is not a keyword. The words "optional edge binding" in query.pest name the edge variable in $p $e:knows $n. That variable may be absent from the query text. The edge match is still required.

   What a required traversal returns

   These rows are from the load commit.

   A node read of all Person rows returns 8 rows. A required $p knows $n returns 5 rows: loop/loop, many/ada, many/bob, many/cara, one/ada. lonely, ada, bob, cara, and worker are absent. Exit 0. row_count is 0 for lonely alone.

   Unbound $p knows $n on many returns 3 rows, one per neighbor. The two parallel edges to ada become one row. Bound $p $e:knows $n on many returns 4 rows. Each row has $e.@id, $e.since, and $e.note. The 2020 edge has a null note. The JSON object omits e.note. The columns list still contains e.note.

   one with a bound edge returns 1 row. The self-loop returns 1 row, with $e.@src and $e.@dst both loop. Undirected <knows> on loop returns that same 1 row.

   Ghost has no rows. $g haunts $p returns row_count 0. The same traversal on the empty-graph commit returns row_count 0. Exit 0 in both cases.

   $n.name = "Ada" after the traversal returns 2 rows (many and one). loop and the other neighbors of many are absent. Roots with no Knows edge are absent too. $e.note is null returns the two edges whose note is null. It does not keep a root that has no edge. $e.note = "old" returns the one edge whose note is old. The null note does not match =.

   not { $p knows $n } returns the 5 roots with no outgoing Knows edge. It returns no neighbor column. exists { $p knows $n } returns loop, many, and one. count { $p knows $n } = 0 returns the same 5 roots as not. A filter inside the not block changes the test: not { $p knows $n $n.name = "Ada" } returns 6 roots. many and one are absent because each has an Ada neighbor. The block still binds nothing the outer return can read.

   A match that requires both Knows and WorksAt returns 1 row, one/ada/hq. worker has a workplace and no Knows edge, so worker is absent. The two patterns multiply. Here the product is 1.

   limit 2 with order { $p.code asc, $n.code asc } returns loop/loop and many/ada. row_count is 2. one is absent. The JSON object has query_name, target, row_count, columns, rows, and graph_commit_id. It has no truncation field. count($p) over the required traversal returns 5. That is the matched row count.

   explain of $p.note prints p.note: String?. explain of the required traversal prints n.code: String. The neighbor column is non-null because the row exists only when the neighbor exists. A node read of lonely lists column p.note and returns {"p.code":"lonely"}. The null string is omitted. return { $n } for one returns one object, @id ada, with code, name, and note. The object is present.

   Indexed path and CSR path

   explain of the unbound Knows query records mode indexed_scan, alternative csr, and index_facts(edge:Knows) []. This Knows table has no index segment. The edge probe is a filtered scan of that one dataset.

   OMNIGRAPH_EXPAND_INDEXED_MAX_FRONTIER=0 selects mode csr for the same query. The ordered rows are the same five pairs. Exit 0.

   The same environment variable selects mode csr on the bound-edge query. The four many rows match the indexed_scan plan's rows, including the omitted null note. The bound-edge executor does not read that mode. It always scans the edge table. Those two bound runs are one scan, planned under two labels.

   Workaround, and the snapshot

   The client reads every Person row, then reads the Knows rows, and joins on Person.code (@id for this key). On the load commit the first query has 8 rows and the unbound second query has 5. The five roots with no outgoing Knows edge appear only in the first query.

   An append of one Knows edge from lonely to ada publishes hb1.01M57SG9Q2YA49Q15J89JWJZGD.2.01M57SSG7RK0GM4M0VSQQ4T3EA. A head read of the traversal returns 6 rows, including lonely/ada. The same query with --snapshot set to the load commit returns the original 5 rows. Two calls share a snapshot only when the client passes that id.

   Difference from the report

   The report describes the gap on 0.10.0 at 02d182b6. This run did not start that binary. On this main the gap is the same shape. optional { ... } still fails at parse. A required traversal still drops unmatched roots. crates/omnigraph/src/exec/query.rs is not in this tree. The operator is ExpandExec. The grammar now has and, or, not, and is null. Those expressions filter a required match. They do not keep an unmatched root.

   Root cause

   A match clause is a negation, a block aggregate, an exists block, a binding, a traversal, or a filter (query.pest line 145). not { ... } is an anti-join (line 178). It keeps outer rows whose inner count is 0. Variables bound only inside the block are not visible outside it. That is the T6 above.

   The traversal executor emits a pair only for a neighbor it reached. A source row with an empty neighbor list emits nothing (execute_expand_bfs in graph.rs). Unbound traversal keeps one row per distinct neighbor. A bound edge keeps one row per edge (produce_bound_edge_pairs). The destination id column of that operator is non-null (expand.rs, expand_output_schema). The destination HashJoinExec probes those ids. An empty probe does not read the destination table.

   A filter in the same match runs on the rows the traversal emitted. It cannot see a root the traversal already dropped. is null keeps a matched row whose stored value is null. It does not invent a row for a missing edge.

   The result schema follows the property declaration. projection_field marks a bare node non-null (typecheck.rs). ReadOutput.columns is a list of names (lib.rs). The JSON writer omits a null string. The column name remains. explain is where String and String? are visible.

   LeftOuter in the planner is the branch-diff sort-merge join. It is not a traversal.

   The affected class is every query that must return a root together with a relationship that may be absent. That includes the CLI and POST /query. The missing piece is a contract.

   Recommended fix

   Write an RFC before code. The issue already has the needs-rfc label. Add one optional pattern to the typed plan. Lower it through the expand operator the engine already runs. Do not add a second route, a transport flag, or a neighborhood table.

   The contract:

   • The spelling is a block, optional { ... }, in the same position as not { ... }. optional is not an edge name in that position.
   • Bindings the block introduces are visible outside the block, and they are nullable. A name bound outside the block stays that outer binding.
   • Multiplicity follows a required traversal, plus the zero case. Zero matches produce one root row and null optional bindings. One match produces one row. An unbound traversal produces one row per distinct neighbor. A bound edge produces one row per edge, so parallel edges stay separate. A self-loop produces one row. An empty root set produces no row.
   • A filter inside the block chooses which matches exist. Zero surviving matches keep the root and null bindings. A filter outside the block that reads an optional binding keeps the row only when the predicate is true. A comparison on a null binding drops that row. That outer filter is the explicit request. The planner must not move a predicate across the block boundary. Either direction changes which roots survive.
   • ExpandExec emits one null-padded pair for a source row that produced no pair. The indexed probe and the CSR walk both do this. The bound-edge scan does this too. The destination join for an optional binding keeps a null id and does not look up a row. A required traversal stays non-null, as it is today.
   • explain shows String? (and the matching node and edge types) for those columns. columns stays the name list. A null string stays the omitted key this writer already uses. A null node object is JSON null, not {} and not an omitted key. Stored nulls and missing neighbors must stay distinct when the value is an object.
   • order and limit stay row cuts after that product. A limit can hide a later root. Document that. Do not add a list of neighbors in this issue. Nested maps and collections stay out of scope. A count per root belongs to #1050.
   • Indexed execution, CSR execution, and the scan used when the edge index is absent return the same rows. The matrix includes an empty graph and a self-loop. The bound-edge path must run the executor the plan names, or the test must name the scan it actually runs.

   This keeps invariant 3 (one snapshot), invariant 9 (the meaning lives in the typed plan), invariant 7 (indexes stay derived), and invariant 8 (a null is typed, and a filter boundary is visible). A union of the inner rows with a not { } result would scan twice and would still have two schemas.

   Tradeoff. This design puts a documented row and a nullable type first. It does not build one index that covers every edge table, and it does not pack the neighbors into one list cell. Each edge type remains its own Lance dataset. A packed list would change limit, order, and count. That list is the nested shape this issue defers. A fast list with a silent cut is a wrong answer. Clarity of the row, and a type the compiler can check, come before that packing.

   Alternatives

   • Keep the client join. The client can do this today. It passes --snapshot so the two calls share a commit. The result has no null neighbor column. This is the current behavior.
   • #649 would return one entity and every incident edge, and it would keep a root with no edge. It does not add an optional pattern for one named edge. Its reproduction comment says the two contracts differ.
   • #1050 would project count { } and exists { } as one value per outer row. It says an optional traversal cross-multiplies, so it is the wrong tool for those counts. Presence can land there. The neighbor row still needs this pattern.
   • A patch that unions the traversal with not { } cannot type one nullable column. It also doubles the edge read.
   • The planner LeftOuter join compares two versions of one table for branch diff. Using it as the traversal would sort whole tables. The expand probe already selects by source id.

   Liability. New syntax is additive. A required traversal stays non-null. A stored query that adopts the block is a different result schema, and that schema must say so in explain before clients bind to it. Shipping the block before that schema, or before the rule for an outer filter, lets a client treat a dropped root as an empty neighborhood. A queue of optional 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, filter_expr sets the predicate, use_scalar_index defaults to true, and limit cuts physical rows of that one scan (scanner.rs). OmniGraph's scan_edges_stream sets the IN filter and the batch size. It does not set that limit. The only JoinType in that scanner is Inner, and it joins a vector hit to a full-text hit on one dataset. Lance merge_insert uses Left, Right, and Full to decide which source and target rows a write keeps. That join is a write plan. It does not return a query row for a missing graph neighbor.

   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. A later bump has to re-check address-domain coverage on stable row ids. The PR does not keep an unmatched graph root.
   • Open PR #9875. It adds ScalarIndex::lookup for a batch of equality keys. A null key matches nothing. That can make an endpoint IN probe cheaper. It is still one column of one dataset. A null key that matches nothing is the opposite of an optional root row.
   • 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 pattern.
   • v13.0.0 includes PR #7905, BM25F across columns of one table. OmniGraph is on Lance 11, so this API is not in the pin. It does not join two graph tables.

   No open or merged Lance change adds an optional graph pattern or a nullable binding in a query result. The nulls in this feature are query-time values. They are not stored cells. A Lance release that changes scanner nulls or index lookup changes the probe cost and the stale-index fence. It does not implement the GQ block.

   Related work

   • #649 is a bounded expansion of one entity across incident edge types. Its reproduction comment on this commit links here and keeps the two requests separate.
   • #648 is graph-wide search. Its reproduction comment names query: bounded node-and-neighborhood expansion with edge identities #649 as neighborhood expansion. It does not define optional match.
   • #1050 is count and exists as return projections. It links here and rejects optional traversal for counts, because the rows cross-multiply.
   • #763 is closed. It measures the cost of a correlated not { } traversal. It does not add a nullable binding.
   • The shared expression model is a draft, and its predicate work is on main. It defines not { } as an anti-join. It does not add an optional block.
   • PR #670 is the draft RFC 0056, one language for control operations. Its "optional" clauses are command syntax and the page object. The RFC text has no optional-match design.
   • PR #884 would bind an interface. It is a draft. It does not define a nullable neighbor.
   • The alternation RFC is accepted and complete. Neighborhood pagination is outside that RFC. Optional match is outside it too.

   Supersession: none. #658 remains the request for an optional traversal that preserves unmatched root rows, with nullable bindings and documented multiplicity.

   Limitations

   • The run is the CLI on a local file graph. It is not a served HTTP call and not a Cedar 403.
   • This run did not start the 0.10.0 binary named in the report.
   • Knows has no index segment in this graph. The indexed_scan label's probe is a filtered scan. The unbound CSR comparison is a second executor. The bound-edge CSR label is not a second executor.
   • The seed is small. The row counts belong to this seed. They show multiplicity. They do not measure a high-degree node.
   • The append that moves the head is one edge. It shows that two unpinned calls can observe different commits.
   • Lance pages on lance.org returned empty HTML shells here. The scanner citation is the v11.0.0 source. Release notes and the PRs above are the upstream comparison.