Repository navigation
GFQL: route Cypher chain node-id filter through resident node_id index (O(1) point / O(log) range seek) #1676
Description
Activity
- added 10 commits that reference this issue
on Jul 2, 2026 The chain edge-hop also bypasses the resident edge adjacency index (not just the node-id seed)
Adjacent to this issue's node-id-filter scope, there's a second index-blind spot on the same surface: a chain edge step never consults the resident
edge_out_adj/edge_in_adjCSR index, even when the identical hop routed as a directg.hop()call does. So the traversal itself — not only thenode_idseed seek in the scope note — is index-blind insidegfql([...])/Cypher.Reproduced qualitatively on a graph with a resident, valid
edge_out_adjindex (index_policy="use", built viagfql_index_all()). Same untyped single forward hop, only the invocation surface varies:- Direct
g.hop(nodes=..., direction="forward", hops=1)→index_tracepath = index (frontier below cost gate -> index); reachesindex_seeded_hopand returns via the CSR gather. - Chain
g.gfql([n({"id": seed}), e_forward(), n()])— the identical hop — → path = scan (index path not applicable -> scan): it reachesmaybe_index_hop, butindex_seeded_hopreturnsNone, so it falls back to the O(E) scan.
Two distinct sub-gaps to fold into "route chain/Cypher through the index":
- Chain edge-hop → scan. Consistent with this issue's note that "the cost gate is currently only on the direct
hop()path," but the missed index here is the edge adjacency index, not justnode_id. The direct-hop and chain-hop paths should converge on the same routing decision. edge_matchis non-index-coverable. A typede_forward({"type": ...})trips_hop_is_index_coverable(graphistry/compute/gfql/index/api.py:285-293) →query not index-coverable. Heterogeneous graphs need the type predicate, so today the only way to the index is to pre-slice a homogeneous per-edge-type subgraph and hop it untyped. Type-filtered adjacency coverage would be worth considering as part of routing chain/Cypher through the index.
Net: covering both the node-id seed seek and the edge-hop adjacency gather would make indexed seeded traversals competitive on the ergonomic chain/Cypher surface; today only the direct
g.hop()API is index-bounded. (Separate from #1715's row-shaped eager boundary — the hop-chain above has norows()and still scans.)- Direct
Summary
A Cypher point/range lookup —
MATCH (i) WHERE i.id = X RETURN ...(and... WHERE i.id BETWEEN ...) — lowers to a graph-levelASTNode({id: X})filter that runs an O(N) columnar scan even when a residentnode_idCSR index exists. Thenode_idindex (from #1658) is currently only consulted by the seeded hop path (maybe_index_hop), never by a chain node filter. Routing the chain node-id filter through the resident index would turn point lookups into an O(1) seek (and range into O(log N + k)).Evidence (Ladybug head-to-head, 5M nodes / 20M edges, native-per-engine)
GFQL wins the scan-shaped ops (full_scan ~65×, range ~1.2×, scan_rel cuDF ~3.5–3.7×), but point is the one op a persistent-index store still wins:
point: polars ~4.9ms / polars-gpu ~3.8ms (a full 5M-row scan)point: ~0.3ms (B-tree/hash index seek)~4ms is fine in absolute terms, but a resident adjacency/
node_idindex seek would match a graph DB here and complete the "GFQL matches a graph DB on lookups when indexed" story.Scope / design
node_idindex is resident (index_policyallows use) — resolve seeds via the index (searchsorted) instead of a full scan. Related: the pandas-CHAIN-doesn't-consult-the-index gap (LP1/feat(gfql): enrich gfql_explain with planner cost diagnostics (LP1) #1672 finding; cost gate is currently only on the directhop()path).index_policy), exactly as a graph DB always has one; index-absent stays an honest O(N) scan.Notes
RETURNrow-pipeline O(N) cost, which is the pandas point bottleneck — polars point is filter/scan-bound, this issue).