Repository navigation
fix(gfql): a NULL id is not an identity — one NULL-endpoint contract on every engine (#1995) - #1999
Conversation
…on every engine Production answered the NULL-endpoint question both ways: eight sites implemented "a null never links", while the polars hop's `_keep_edges_with_both_endpoints_resolvable` (#1888 round 6) resolved a NULL endpoint to a NULL node id. `MATCH (a)-[x]-(b) RETURN count(*)` over a graph with one NULL endpoint therefore answered polars 4, pandas 6, cuDF 6. Contract chosen and written down in docs/source/gfql/spec/language.md: a NULL id is not an identity, so an edge with a NULL endpoint matches no pattern edge on any surface, from either direction, bound or synthesized node table. openCypher's three-valued logic makes `null = null` UNKNOWN rather than TRUE, and it is the only reading under which an engine agrees with itself. A NULL-id node ROW is still a row and OPTIONAL MATCH still produces NULL bindings; only endpoint resolution is constrained, and nothing raises. Two defects that were wrong under either policy are fixed with it: the polars hop kept a NULL-endpoint edge whose NULL endpoint got no node row (output frame referencing a node it did not carry), and pandas/cuDF answered the same undirected chain 2 edges unnamed and 3 edges NAMED. Enforced at three kernels: the shared pandas/cuDF hop, the polars hop, and the polars single-hop chain fast path. Refs #1995 Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01AjbKuKheqDu78oapRT5AYm
…each get_degrees / get_indegrees / get_outdegrees are raw edge-row tallies, not pattern matches, so they still count a NULL-endpoint edge on whichever endpoint IS an identity. All three engines already agree, so this is a semantic question about what get_degrees means rather than a divergence; stated in the spec and pinned so the boundary cannot drift unnoticed. Refs #1995 Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01AjbKuKheqDu78oapRT5AYm
VerificationAll runs on this box (RTX 3080 Ti, cudf 25.10, polars 1.42, py3.12), from inside a dedicated
|
merge-base 9f93d4577 |
head 280bd9f97 |
Δ | |
|---|---|---|---|
| failed | 2 | 2 | 0 |
| passed | 12977 | 13050 | +73 |
| skipped | 1001 | 1024 | +23 |
| xfailed | 36 | 29 | −7 |
| collected | 14016 | 14105 | +89 |
Totals reconcile exactly: test_endpoint_closure_matrix.py goes 434 → 523 collected (+89), and
+73 passed +23 skipped −7 xfailed = +89. The +23 skips are the new cells' polars-gpu params.
The −7 is precisely the seven strict-xfail cells removed.
Failure set, compared in both directions: identical. Both trees fail only
test_viz_pipeline_conformance.py::test_categorical_searchany_decline_or_correct and
test_engine_coercion.py::TestChainCoercion::test_chain_dask_edges, which are pre-existing on
master and untouched here.
Both worktrees re-asserted clean (git status --short empty) at
9f93d4577 / 280bd9f97 after the runs.
Anti-vacuity
The new pins copied onto the merge-base code: 35 cells RED, 366 passed. Green after.
Red-at-master by pin:
| pin | red cells at 9f93d4577 |
|---|---|
test_a_null_edge_endpoint_matches_nothing_on_the_synthesized_table |
16 |
test_the_chain_gates_a_null_endpoint_bound_or_synthesized |
4 |
test_a_null_edge_endpoint_matches_nothing_on_a_direct_hop |
3 |
test_no_output_frame_references_a_node_it_does_not_carry |
3 |
test_the_null_endpoint_contract_holds_on_string_ids |
3 |
test_cypher_count_counts_only_matchable_edges |
2 |
test_each_null_endpoint_side_is_dropped_on_its_own |
2 |
test_naming_the_ops_does_not_change_the_null_endpoint_answer |
2 |
The remaining new cells are named controls, green at master by design:
test_the_null_free_twin_matches_every_edge (anti-vacuity twin),
test_a_null_id_node_row_is_still_a_row, test_a_null_seed_id_reaches_nothing,
test_get_degrees_counts_raw_edge_rows_not_matchable_edges (deferred boundary), and
test_the_chain_answers_the_same_null_endpoint_question_as_hop — whose old xfail oracle was
the hop's wrong answer, so the chain side was already right.
Cross-engine divergence sweep
104 engine-cells (13 Cypher shapes × 9 chain shapes × 4 hop shapes × bound/synthesized ×
{polars, cuDF} vs the pandas oracle), value-level signatures on both frames:
| fixture | merge-base | head |
|---|---|---|
| NULL-endpoint graph | 31 divergences | 6 |
NULL-free twin (same shape, 3 for every NULL) |
6 | 6 |
The 6 survivors are byte-identical across all four runs and are unrelated to NULLs: a
pre-existing polars EXISTS { } GFQLTypeError, and two synthesized-node-table shapes where
the sweep's fixture queries a node attribute a synthesized table does not have. 25 of 25
NULL-attributable divergences eliminated; zero introduced.
Guards
python bin/ci_comment_density_guard.py → rc=0 (no growth; 2 files now below baseline).
./bin/lint.sh → rc=0 (ruff, type-hygiene guard, comment-encoding guard, relative-import check).
./bin/typecheck.sh → rc=0 (mypy 2.3.1, "no issues found in 334 source files").
CI
77 check runs on 280bd9f97: 72 success, 5 skipped, 0 failures. CI Tests and CodeQL
workflow runs both completed success.
Performance
The pandas/cuDF helper scans before it filters, so a null-free edge table keeps its frame with
no copy. On a 2M-edge graph: null scan 0.5 ms vs a 65 ms seeded 1-hop — 0.8%, and
strictly cheaper than the two isin passes the endpoint-closure gate already runs on the same
frame.
Adjacent-line CHANGELOG conflict under [Development] ### Fixed; both entries kept (#1998's cuDF categorical string predicate, and this branch's #1995 NULL endpoint contract). Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01AjbKuKheqDu78oapRT5AYm
Rebased onto master (
|
9f93d4577 |
a743bf806 |
Δ | attributable to | |
|---|---|---|---|---|
| collected | 14016 | 14118 | +102 | +89 this branch, +13 #1998 |
| failed | 2 | 1 | −1 | #1998 |
| xfailed | 36 | 29 | −7 | this branch's removed xfails |
Post-merge smoke: test_endpoint_closure_matrix.py + predicates/test_str.py +
test_viz_pipeline_conformance.py → 549 passed, 122 skipped, 0 failed, i.e. this branch's
contract pins and #1998's cuDF categorical pins are green together.
The bin/ci_comment_density_guard.py / ./bin/lint.sh / ./bin/typecheck.sh results and the
mutation, red-at-master and divergence-sweep numbers in the previous comment were all measured
on the pre-merge tree; the merge touches CHANGELOG.md only on this branch's side, and
graphistry/compute/predicates/str.py + graphistry/tests/compute/predicates/test_str.py on
master's, so none of those production kernels changed.
The CSR gather is built from the RAW edge frame and is a separate kernel from the scan, so it needs its own cells. 24 cells (6 seed x direction shapes x 4 engines); 4 of them are red at the merge base 9f93d45. Refs #1995 Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01AjbKuKheqDu78oapRT5AYm
Round 3 — the index-backed route pinned too, and a note on the cancelled check
|
| pin | red at 9f93d4577 |
|---|---|
test_a_null_edge_endpoint_matches_nothing_on_the_synthesized_table |
16 |
test_the_chain_gates_a_null_endpoint_bound_or_synthesized |
4 |
test_the_index_backed_route_answers_the_null_contract_too |
4 |
test_a_null_edge_endpoint_matches_nothing_on_a_direct_hop |
3 |
test_no_output_frame_references_a_node_it_does_not_carry |
3 |
test_the_null_endpoint_contract_holds_on_string_ids |
3 |
test_cypher_count_counts_only_matchable_edges |
2 |
test_each_null_endpoint_side_is_dropped_on_its_own |
2 |
test_naming_the_ops_does_not_change_the_null_endpoint_answer |
2 |
Local: test_endpoint_closure_matrix.py → 419 passed, 128 skipped, 0 failed (123 real cuDF
params among them; the skips are all polars-gpu, which wants cudf_polars).
bin/ci_comment_density_guard.py / ./bin/lint.sh / ./bin/typecheck.sh re-run → all rc=0.
On the cancelled check-run
CI Tests on the merge commit a743bf806 shows cancelled, which is not a test failure.
Every job on that run reached success, including the one job the run-level cancel landed on:
test-polars (3.12) ran all 19 steps green — "Polars tests with coverage" success (9m38s) and
"Polars GFQL coverage audit (per-file floors)" success — and was marked cancelled 3 seconds
after its last step completed, at the run level. The preceding run on 280bd9f97 was
completed / success outright (77 check runs: 72 success, 5 skipped, 0 failures). The push of
this commit starts a fresh run; results below.
|
I'm surprised we even consider null-id rows valid. This feels undefined territory. |
|
Handled in The contract now says a NULL ID is not a valid graph identity. Existing permissive ingestion and node-only row scans remain unchanged for compatibility, but are explicitly outside this endpoint-resolution contract. The old
|
Fixes #1995
The decision: a NULL id is not an identity
An edge whose source or destination is NULL matches no pattern edge — on every surface
(
hop, chains, Cypher rows, Cypher aggregates), from either direction, and whether or not thenode table holds a NULL-id row. A NULL seed id likewise resolves to no node.
I adopted the majority position, but established it independently rather than on assertion.
Four lines of evidence, in increasing order of how hard they are to argue with:
null = nullevaluates to UNKNOWN, notTRUE. A pattern edge binds two node identities; an endpoint that cannot be shown equal to any
node identity binds nothing. openCypher has no notion of a "null node", and a relationship
whose endpoint is unknown cannot be shown to connect anything.
hop_eager._keep_edges_with_both_endpoints_resolvable'sa_null_id_is_resolvablebranchfrom design: endpoint-closure contract — five surfaces, five answers for one dangling-edge graph #1888 round 6 — a patch aimed at making polars'
is_inmimic pandas'isin, i.e. atengine parity, never at a semantic decision.
an engine agrees with itself. On master, pandas answered
MATCH (a)-[x]-(b) RETURN count(*)with 6 while the identical pattern as a chain returned 2 edges (4orientations); and the polars
hopkept the(NULL,2)edge while its node output droppedthe NULL row, so the result frame carried an edge referencing a node that was not in it.
Adopting the minority reading requires repairing those; adopting the majority reading
dissolves them.
shapes × bound/synthesized × polars/cuDF vs the pandas oracle) over a NULL-endpoint graph
shows 31 divergences at master → 6 after. The 6 survivors reproduce identically on a
NULL-free twin of the same fixture, so they are unrelated to NULLs (a pre-existing polars
EXISTS { }GFQLTypeError, and two synthesized-node-table shapes where the fixturequeries a node attribute a synthesized table does not have).
Input validity is separate from endpoint resolution. A NULL ID is not a valid graph
identity. This PR preserves existing permissive DataFrame ingestion and node-only row scans
for compatibility, but does not make those source rows valid nodes.
OPTIONAL MATCHNULLbindings remain valid result values, distinct from source identities. A strict/warn input
policy can validate source rows without rejecting generated result bindings.
Written down in
docs/source/gfql/spec/language.md→ Core Concepts → NULL Identity Resolutionand Edge Endpoints.
Count matrix, before and after
Fixture: nodes
id = [0, 1, 2, NULL], edges(0,1) (1,2) (NULL,2)(the issue's fixture).MATCH (a)-[x]-(b) RETURN count(*)MATCH (a)-[x]->(b) RETURN count(*)MATCH (a) RETURN count(*)[n(), e_undirected(), n()][n(), e_forward(), n()], bound24 of 24 cells identical across the three engines after; 10 of 24 divergent before.
The two policy-independent defects
(1) polars kept an edge whose NULL endpoint got no node row. Repro
(
PYTHONPATH=<wt>,graphistry.__file__printed):The edge
(NULL,2)survived round 6'sa_null_id_is_resolvablerule, but the node output isall_nodes.join(needed, how="semi")and a polars join never matches NULL to NULL — so theframe was not endpoint-closed under either policy. Pinned by
test_no_output_frame_references_a_node_it_does_not_carry[hop-*], asserted on the null-awareid spelling (a raw
set(...) <= set(...)is vacuously true for NaN endpoints, sinceNaN != NaN).(2) pandas/cuDF answered the same undirected chain differently named vs unnamed. Repro:
Binding an alias disables the single-hop chain fast path, so the query is served by the full
BFS — and an undirected walk reaches
(NULL,2)through its non-null endpoint2, neverkeying on the NULL at all. The fast path's own comment claimed parity ("the BFS joins never
match NaN↔NaN"), true for
forwardand false forundirected; those three comments now citethe contract instead of the incidental parity fact. Pinned by
test_naming_the_ops_does_not_change_the_null_endpoint_answer, which asserts named ==unnamed and both == the contract.
Both fall out of the contract rather than needing separate repairs.
Implementation — 26 production lines at three kernels
graphistry/compute/hop.py(pandas + cuDF)_drop_null_endpoint_edgesonedges_indexed, before the closure gategraphistry/compute/gfql/lazy/engine/polars/hop_eager.pydrop_null_endpoint_edgesafter_hop_setup_columns; deleted round 6'sa_null_id_is_resolvablewidening (now unreachable — no endpoint reaching the gate is NULL)graphistry/compute/gfql/lazy/engine/polars/chain.pyThe pandas/cuDF helper scans before it filters, so a null-free edge table keeps its frame with
no copy. Measured on 2M edges: the scan is 0.5 ms against a 65 ms seeded 1-hop (0.8%),
and it is strictly cheaper than the two
isinpasses the closure gate already runs.Tests
Removed 4 strict-xfail markers = 7 xfail cells, each because the behavior is now correct —
no assertion was relaxed:
_NULL_NODE_ROW_POLARS_XFAILpolars)_CHAIN_NULL_XFAILpandas,polars,cudf)_CYPHER_COUNT_POLARS_XFAILpolars)_SYNTH_CHAIN_NULL_XFAILpandas,cudf)Suite xfail count moves 36 → 29 accordingly.
Added 12 green endpoint-contract pins plus one non-strict compatibility probe (112
engine-parametrized cells), over a strengthened fixture
that puts a NULL on both endpoint sides (
(NULL,2)and(2,NULL)), plus a NULL-freecontrol twin and a string-id (object-dtype) fixture:
9f93d4577and green after. The remaininggreen cells are named controls:
test_the_null_free_twin_matches_every_edge,test_a_null_seed_id_reaches_nothing, and the chain cell whose old xfail oracle was thehop's wrong answer.
test_current_node_only_scan_preserves_a_null_id_source_rowis anon-strict compatibility probe, not an endpoint-contract pin.
never used as the expected value.
test_the_null_free_twin_matches_every_edgeis the anti-vacuity control: same shape, sameseeds, same walk,
3substituted for every NULL — all 4 edges match, undirected count 8,forward count 4. Without it the cells above would pass against an implementation that
deleted edges for the wrong reason.
Mutation audit (cells killed in
test_endpoint_closure_matrix.py; no site is vacuous):hop.pydrop deletedhop.pysource-side onlyhop.pydestination-side onlyhop.pyfast-scan guard invertedhop_eagerdrop deletedhop_eagersource-side onlyhop_eagerdestination-side onlyThe two polars sites started at 1 kill each — with a node table bound, the closure gate's
is_inalready refuses a NULL endpoint, so those drops are load-bearing only on thesynthesized table. Rather than leave a one-cell guard, the synthesized-table and chain
cells are now swept (both id dtypes × forward/reverse/undirected) instead of sampled.
Deleting round 6's
a_null_id_is_resolvablewidening kills zero cells, which is the point:after the drop runs first, no endpoint reaching that gate is NULL, so the branch was
unreachable. It is removed as dead code, not as a behavior change.
Failure-set comparison
graphistry/tests/compute/(pandas + polars + real cuDF, RTX 3080 Ti / cudf 25.10, withLD_LIBRARY_PATHset to the pipnvidia/*/libdirs and a compiled-ElementwiseKernelprobe,not
cupy.zeros):9f93d4577: 2 failed, 12977 passed, 1001 skipped, 36 xfailedcompared in both directions.
The two merge-base failures (
test_categorical_searchany_decline_or_correct,TestChainCoercion::test_chain_dask_edges) are pre-existing and untouched.bin/ci_comment_density_guard.py,./bin/lint.sh(ruff + type-hygiene + comment-encodingguards),
./bin/typecheck.sh(mypy, 334 files) — allrc=0.test_endpoint_closure_matrix.pyis already inbin/test-polars.sh'sPOLARS_TEST_FILES, sothe new polars cells run in the polars coverage lane.
Deferred, named rather than left unwritten
get_degrees/get_indegrees/get_outdegrees— and the GFQLCALLthat exposes them —are raw edge-row tallies, not pattern matches, so they still count a NULL-endpoint edge on
whichever endpoint is an identity: over the fixture, node 2 has
degree_in2 anddegree_out1 while exactly one matchable edge reaches it in each direction. All threeengines already agree here, so this is a semantic question about what
get_degreesmeansrather than a cross-engine divergence, and moving it would silently change the value of an
existing user-facing column. It is stated in the spec and pinned by
test_get_degrees_counts_raw_edge_rows_not_matchable_edgesso the boundary cannot drift ineither direction unnoticed.
🤖 Generated with Claude Code
https://claude.ai/code/session_01AjbKuKheqDu78oapRT5AYm
Reviewer handoff
Queue position: 1 of 7. Reviews are nonblocking; no campaign PR will be merged by the branch-development agent.
Exact state: finalized stacked head
d31d4cc302d58e8a49fc39e9a74158c4be6bedc9; authoritative CI state is the GitHub Checks panel.Reviewer decisions:
get_degreesremains a raw edge-row tally and is intentionally outside endpoint-resolution semantics.Dependencies and overlap: this is the stack root; #2000 contains this head. Prior changed-file overlaps are already merged conflict-free in the stack.
Safe local reproduction:
Stack / landing
Position: 1 of 7. Predecessor: none (stack root). Successor: #2000.
Landing rule: keep the PR base as
masterand land #1999 → #2000 → #2001 → #2002 → #2003 → #2004 → #2005 using GitHub Create a merge commit only. Do not squash or rebase: each later head contains its predecessor's ancestry. The branch-development agent will not merge.Review model: review this PR's incremental change against its predecessor out of band; review does not block preparation of the remaining queue.
Final validation: two consecutive no-advance review waves; clean incremental diffs; Ruff and added-code typing/comment ratchets green; 1,361 selected local CPU tests passed. Guarded DGX validation passed 164 whole-entity/multiplicity tests, 8 binding-seed tests, and 69 aggregate-selector tests (425 deselected), with exact-source, cuDF 26.02, NVRTC, and Polars-GPU canaries. Direct review found no added prohibited typing, dynamic-attribute, or hygiene escapes.