perf(gfql): native multi-row hop erodes at scale — O(E) edge-frame materialization / #1658 index under-engages on many-seed hops

[lmeyerov]

Summary

GFQL native g.hop()/g.chain seeded point lookups are O(degree)-flat and dominate Kuzu at every scale, but native multi-row traversals (many-seed wavefront) grow super-linearly with graph size and lose their lead. Measured same-session, same-box, matched Kuzu, LDBC SF0.1 → SF1 (~11× data), current master 983d2aff, warm-median, gfql_index=use.

Evidence (raw-JSON verified, pandas native-hop backend)

query	SF0.1 ms	SF1 ms	native growth	Kuzu growth	verdict shift
seed-lookup (point)	0.27	0.30	1.1× (flat)	~1.5×	WIN → WIN (widens 4.9→5.9×)
message-creator (point)	0.24	0.26	1.1× (flat)	~1.5×	WIN → WIN (5.8×)
message-replies (multi-row)	6.58	57.53	8.7×	23.8→36.0 (1.5×)	WIN → LOSE
new-topics (multi-row)	15.8	91.1	5.8×	—	erodes
recent-replies (multi-row)	13.1	89.7	6.8×	—	erodes

Best-engine native-vs-Kuzu tally falls SF0.1 7W/2L → SF1 4W/1T/4L, entirely from multi-row traversal erosion (IS2 WIN→LOSE, IS7 WIN→TIE, IC8 WIN→LOSE). Points and deep-aggregating traversals are unaffected.

Suspected root cause (needs a trace to confirm — do not assume)

The point path hits the #1658 CSR index and is flat. The multi-row path grows ~O(E): candidate causes are (a) the #1658 index not fully engaging when the hop wavefront has many seeds (falls back to a full edge scan), and/or (b) per-call O(E) edge-frame materialization in the harness/executor (the combine_steps/projection family, cf. #1755) that scales with edge count rather than result size.

Why it's fixable (a lever, not a wall)

A prior (uncommitted, never-landed) build with two multi-row opts — memoizing _build_known_pairs and sort/limit-before-projection — recovered the flatness (message-replies stayed a WIN at SF1). So the erosion is addressable; it just isn't on master. This issue tracks landing the real fix + re-measuring.

Ask

1. Trace the multi-row hop on SF1 (gfql_explain + cProfile) to disentangle index-under-engagement vs O(E) materialization.
2. Land the multi-row fast path (index engagement on many-seed hops and/or result-sized materialization).
3. Re-run the native-vs-Kuzu SF0.1→SF1 matrix to confirm multi-row traversals stay flat/winning at scale.

Related: #1755 (single-row seeded abstraction tax, same executor family), #1709 (polars rows-binding NIE). Evidence: plans/gfql-benchmark-numbers/native-vs-competitor-sf{01,1}.md.

[lmeyerov]

Root-cause trace (dgx-spark, LDBC SF0.1→SF1, pandas, warm median) — the erosion is NOT the hop or the index

Traced with gfql_explain/index_trace + cProfile + index-on/off timing + a parity-checked before/after. Verdict: Candidate A (index under-engagement / cost gate) is FALSIFIED; Candidate B (O(E) materialization) is CONFIRMED but relocated — it is a pandas two-axis .loc[keys, cols] projection in the bench harness, not pygraphistry's hop/index/chain.

The index multi-row hop is O(degree)-flat at scale

Single-seed vs 19-seed hop on the SAME SF1 slice (n_keys=3,055,774) — identical decision:

HOP2 (19 seeds): path=index  frontier_n=19  seed_deg_sum=19  decision_reason="frontier below cost gate -> index"
HOP2 (1 seed):   path=index  frontier_n=1   seed_deg_sum=1   decision_reason="frontier below cost gate -> index"

• hop2 index-on: 0.187 → 0.208 ms (SF0.1→SF1, 11.7× data) = 1.1× flat
• hop2 index-off (forced scan): 12.72 → 303.31 ms = 23.9× O(E) — the index correctly kills this
• cost gate never trips: frontier_n=19 ≪ 0.5·n_keys (1.5M). est_result_rows=19.
• index_seeded_hop = 1.8% of the full executor at SF1.

The O(E) erosion is 97% the pandas result projection

cProfile of _run_message_replies_native_hop (SF1, 10 calls, 0.623 s):

0.605  pandas indexing __getitem__   <- the two nodes.loc[keys, cols] calls (97%)
0.592  _reindex_with_indexers        (tottime 29%)
0.408  _take_nd_ndarray              (tottime 57%)
0.011  index_seeded_hop              <- the actual hop (1.8%)

Isolating the projection (keys = the 13/19 replies, so a tiny result):

strategy	SF0.1	SF1	growth
nodes.loc[keys, cols] (two-axis _multi_take)	1.56	19.08 ms	12.2× O(N)
nodes.loc[keys][cols] (row-take then col-select)	0.100	0.116 ms	1.2× flat
nodes.reindex(keys)[cols]	0.090	0.100 ms	flat

pandas .loc[row_list, col_list] reindexes both axes with allow_fill=True over the full-height object blocks → allocates N-row buffers even for 19 keys. Same shape as #1755 lever-2 (O(N) full-column materialization), here in the harness projection.

Parity-checked prototype (message-replies SF1)

Clone the executor changing only nodes.loc[keys, cols] → nodes.loc[keys][cols], byte-compare output:

PARITY: True   (19 rows == 19 rows, identical)
ORIGINAL : 62.39 ms
PATCHED  :  0.76 ms   -> 82.2x
Kuzu SF1 : 36.00 ms

Verdict flips native WIN→LOSE (0.6×) back to a 47× WIN.

Targeted fix

Replace every two-axis nodes.loc[keys, cols] with nodes.loc[keys][cols] (or .reindex(keys)[cols]) in the native-hop executors (_run_message_replies_native_hop, _run_recent_replies_native_hop, _run_new_topics_native_hop, _run_expand_order_limit_native_hop, _run_message_creator_native_hop). Result-sized, byte-parity. This generalizes the sort/limit-before-projection flatness the issue references. Fix lands in the bench harness runner.py, not pygraphistry core — pygraphistry's native hop + #1658 CSR index are already O(degree)-flat at 5.3M edges (0.19→0.21 ms), which vindicates the native-dominance thesis. #1756's premise ("native multi-row hop erodes" / "#1658 does not engage on many-seed hops") is a misattribution: the erosion is the harness's pandas .loc projection.

Full trace + probes: plans/gfql-benchmark-numbers/multirow-hop-erosion-trace.md; probes/logs in /home/lmeyerov/dgx-scratch-bench/{probe_multirow,probe_proj,probe_fix}.py.

[lmeyerov]

Closing: the premise is a misattribution. The trace above proves pygraphistry's native hop + #1658 CSR index are O(degree)-flat at scale (0.187→0.208 ms across 11.7× data at 5.3M edges; the many-seed hop takes path=index identically to the single-seed control — Candidate A falsified by direct gfql_explain). The measured SF1 "erosion" is 97% a pandas two-axis nodes.loc[keys, cols] projection in the pyg-bench harness (_run_message_replies_native_hop et al.), which reindexes both axes O(N-nodes) even for a 19-row result — NOT pygraphistry core, NOT the chain executor (native-hop never touches it).

Fix (nodes.loc[keys, cols] → nodes.loc[keys][cols]) = 62.39→0.76 ms (82×), byte-identical output, flipping native LOSE→47× WIN. That fix belongs in the pyg-bench harness, not this repo. pygraphistry core is vindicated here; no pygraphistry change is needed. Tracking the harness projection fix + a clean SF0.1→SF1 native-vs-Kuzu re-measure in pyg-bench.

(Distinct from #1755, which is a real pygraphistry combine_steps abstraction tax on the Cypher surface — that one stands.)