perf(gfql): cut per-hop and rows-stage overhead for seeded polars chains - #2084
Conversation
Array-side exact join estimate over null-free integer keys, predicate-first node gather before the wide row gather, and skip the endpoint semi-join when the node filter dropped no ids. Same rows, same order, same trace values. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Replaces the per-hop join+sort plan with searchsorted ranges over step rows pre-sorted by (key, tiebreaks) and two row gathers; identical rows, order, schema. Declines to the frame plan on lazy/null/non-integer inputs. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
rows() gains attach_prop_columns; a bare rows() immediately followed by select is rewritten to request just the alias.column names the select projects, on the pandas, cuDF, and polars bindings builders alike. Anything the select cannot be bounded to keeps attach-all. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
…olars before the pyspark probe
The temporal-constructor scan first checks for a literal '(' so plain text
columns skip the anchored regex; resolve_engine recognizes polars frames
before attempting the (usually absent) pyspark import. Registers the new
polars-dependent test files in the polars CI lane.
Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
…rk (#2084) Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Types the new array-side helpers with ArrayLike/ArrayNamespace instead of Any, takes the select pushdown's column list as Sequence[str], and folds _frame_with_positions onto the general _with_positions helper. Remaining casts carry hygiene-ok reasons. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Satisfies the comment-encoding guard: the lexsort key order, the identity semi-join condition, and the temporal-text prefilter each state their constraint in one line, with no performance vocabulary. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
| return None | ||
| xp, _ = array_namespace(engine) | ||
| left_keys, left_counts = unique_with_counts(xp, col_to_array(left, left_on, engine)) | ||
| right_keys, right_counts = unique_with_counts(xp, col_to_array(right, right_on, engine)) |
There was a problem hiding this comment.
are there stats here pandas/polars/we should be tracking as part of indexing? can also get upperbounds..
There was a problem hiding this comment.
Good question, and the answer turned out to be better than "track more stats".
What the registry already carries. AdjacencyIndex has keys_sorted + group_offsets, which is exact per-key multiplicity, plus n_keys and n_edges. DegreeFact has indeg/outdeg arrays and lo/hi (min/max degree), partitioned by edge type. ColStatsFact has min/max, null_count, n_unique. The hop loop already consumes these at the two gates that run before this one: the frontier gate uses min(index.n_keys) and the gather gate uses lookup_degree off the CSR.
Why this particular call can't be answered from the index. Neither of its inputs is an indexed frame. state is the accumulated path table and oriented is gathered-then-filtered-then-oriented edges, so the identity guard rules out any registry fact, and an upper bound from DegreeFact.hi would be over the unfiltered edges.
But the call was redundant with the very next one. The expansion does searchsorted(sorted_keys, current, 'left'/'right') and takes the range widths. Those widths sum, over state rows, to exactly the sum-over-matched-keys of left_count × right_count that estimate_inner_join_rows returns. Verified on every hop of a real SNB SF0.1 run: 18 hops, 18/18 agreement, zero disagreements. Measured cost of the redundant pass: 0.19–0.67 ms/query, 3.5–4.7% of query time.
What I changed. join.py now exposes plan_path_ordered_expand_join, returning a PathExpandPlan(rows, expand). On the array path rows is the expansion's own range widths, so costing a hop is free; when the array path declines it falls back to estimate_inner_join_rows. The hop loop gates on plan.rows and then calls plan.expand(); the gate condition is unchanged character for character, and estimate_inner_join_rows is no longer imported by bindings.py.
Pinned by test rather than prose: test_expand_plan_rows_is_the_estimate_without_a_second_pass (12 seeds) asserts both that the number matches the estimator and that the estimator is never called to produce it, and test_expand_plan_falls_back_to_the_estimator_when_the_array_path_declines covers the other side.
On the end-to-end effect, honestly. It is not resolvable above this box's noise. An in-process A/B (one process, one loaded graph, arm order alternated, 6 rounds × 41 reps) reads message-replies −5.35% and recent-replies −1.66%, but its A/A control — both arms the shipped planner — reads +4.04% and +3.14%. So the claim is: the removed pass was real and measured at the function level, results are identical, and no end-to-end speedup is being claimed.
Where index-carried stats DO point. I measured the primitives at the top of the stack (#2087 head) to see what is left. On recent-replies, searchsorted is 16.6% and unique is 9.0%, while lexsort is 2.3%. So a pre-sorted adjacency is not worth building, but keying the CSR by dense node row position instead of by sorted id would turn every id→position lookup into an O(1) array index and let the frontier be a dense mark instead of a sort-and-unique. That is the next lever, and it is the same move EndpointRowsFact already made for edge endpoints.
| return None | ||
| xp, _ = array_namespace(engine) | ||
| current = col_to_array(state, current_col, engine) | ||
| keys = col_to_array(step, from_col, engine) |
There was a problem hiding this comment.
array conversions seem undseriable?
There was a problem hiding this comment.
Measured rather than reasoned about: on the shape this code admits, the conversion is free.
Series.to_numpy() on a null-free, single-chunk integer polars column returns a zero-copy view over the Arrow buffer — flags.writeable=False, base is the PySeries. No allocation, no copy. That is not a coincidence: the guard above already requires null-free integer keys, which is exactly the shape polars can expose without materializing.
I instrumented every col_to_array call in a real SNB SF0.1 run and recorded the chunk count and whether the result was a view:
| query | conversions / query | of those, copying | inside the two new helpers |
|---|---|---|---|
| message-replies | 18 | 1 | 0 copying |
| recent-replies | 27 | 0 | 0 copying |
Every conversion inside _estimate_inner_join_rows_arrays and _path_ordered_expand_join_arrays is a view. The single copying conversion in the whole hot path is pre-existing code at bindings.py:586, on a 7-element seed column that happens to have 7 chunks.
The two shapes that do copy are both already excluded here: a multi-chunk column forces polars to rechunk, and a column with nulls upcasts to float64. Worth knowing, since it is a real trap elsewhere — it is what made an earlier array-side ordering lever slower, where to_numpy() on a nullable Float64 column copied 327k values twice per query. That lever was measured and rejected.
| left_idx = xp.repeat(xp.arange(current.shape[0]), counts) | ||
| starts = xp.cumsum(counts) - counts | ||
| right_idx = step_order[xp.repeat(lo - starts, counts) + xp.arange(total)] | ||
| left_part = take_rows(state, left_idx, engine).drop(current_col) # type: ignore[operator] |
There was a problem hiding this comment.
type ignores undseriable
There was a problem hiding this comment.
Agreed, and they are gone — all three, including the one in _estimate_inner_join_rows_arrays.
The root cause was structural: DataFrameT is pd.DataFrame at type-checking time, so anything returned by the engine-polymorphic take_rows looked like a pandas frame, and every polars method called on it needed its own ignore.
The fix is to narrow once instead of ignoring at each call. engine_arrays.py gains:
def as_eager_polars_frame(df: DataFrameT) -> Optional["pl.DataFrame"]:
import polars as pl
return df if isinstance(df, pl.DataFrame) else Noneisinstance narrowing gives mypy a real pl.DataFrame, so the whole body downstream is properly typed and .drop(...) / .rename(...) / .get_column(...) need nothing. A sibling take_rows_polars does the row gather on the already-narrowed frame. The only cast left is the single one at the return boundary, which is the module-wide idiom.
mypy is clean on all three edited modules with no new ignores, and the type-hygiene guard passes at baseline with no growth.
…lars once Review follow-up on #2084. The hop loop called estimate_inner_join_rows and then immediately did the work that computes the same number: the expansion's searchsorted range widths sum, over state rows, to exactly the sum-over-matched-keys of left_count * right_count the estimator returns. Verified on every hop of an LDBC SNB SF0.1 run, 18/18, and measured at 0.19-0.67 ms per query, 3.5-4.7% of query time. plan_path_ordered_expand_join now returns a PathExpandPlan(rows, expand): on the array path `rows` is those range widths, so costing a hop is free; when the array path declines it falls back to the estimator. The gate condition in the hop loop is unchanged, and bindings.py no longer imports the estimator at all. The type ignores are gone with it. DataFrameT is pd.DataFrame at checking time, so every polars method on a take_rows result needed one; as_eager_polars_frame narrows once through isinstance and take_rows_polars gathers on the narrowed frame, so the bodies are properly typed and only the return-boundary cast remains. No end-to-end speedup is claimed: an in-process A/B reads -5.35% and -1.66% on the two affected queries, but its A/A control reads +4.04% and +3.14%, so the effect is below this box's noise floor. What is established is that the removed pass was real, results are identical, and the estimator is provably not called on the served path. Tests pin both halves: the plan's row count equals the estimator's over 12 seeds AND the estimator is never called to produce it, plus the declining fallback. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Perf-regression evidence for this PR — the criterion I had not applied hereI measured decline overhead for #2086 and #2087 and never for this one. Doing it now, the same way: time spent inside the two array helpers only on calls that decline, on the real LDBC SNB SF0.1 fixture, so the number is the decline tax itself rather than a query-level delta competing with box noise.
On polars there are no declines at all — a query that does not qualify never reaches either helper. On pandas the expansion declines four to six times per query, because the array expand is Polars-only, and that costs 0.006–0.010 ms, under 0.03% of the query. The estimator does serve on pandas, which is the branch that gives that engine its share of the win. Boundary coverageThe other half of the standard. I also ran an independent audit of every admission/decline boundary in this diff against the same checklist I used on #2086 and #2087 — empty-vs-empty corpora, another route answering first, oracle-is-another-fast-path, disable mechanism, and engagement. I will post its findings here, and fix anything it turns up, before asking you to merge. |
…or its ordering Auditing this PR against the same boundary standard I had applied to the two above it found two defects and a test that could not have caught either. WRONG ROWS on mixed integer key dtypes. numpy promotes (int64, uint64) to float64, which cannot tell 2**60+1 from 2**60+2, so the array expansion emitted four rows where the frame path emits two. In production this was contained only by a schema-equality guard in bindings.py -- a different file, no test tying it to this function, and path_ordered_expand_join is public. The guard now lives in the helper. The estimator had the same promotion with no guard at all and diverged on pandas (1 against the frame path's 2); it gets the same check, plus an empty-frame guard, since a direct call with an empty left frame indexed left_keys[-1] and raised IndexError. A REGRESSION THIS BRANCH INTRODUCED. Master rejected a hop from a group-by estimate before any expansion work; the costed plan built everything, INCLUDING the lexsort over the whole gathered-edge frame, and only then let the caller gate. A rejected hop at 1M step rows cost 172.99 ms against master's 9.49 -- eighteen times -- at exactly the boundary the gate exists to protect. Counting needs the keys in key order only; ordering within a key needs the tiebreaks. The planner now sorts the keys to count and defers the lexsort into expand(), so a rejected hop never pays for an ordering it discards: 1k 0.48 -> 0.42 ms, 10k 1.59 -> 0.70, 100k 15.60 -> 1.86, 1M 172.99 -> 12.02. What that costs the serving path, measured on the benchmark rather than assumed: polars recent-replies +0.052 ms (0.46%), message-replies +0.007 ms (0.13%), pandas zero. The lexsort beside it is 0.104 ms, so the added sort is about half, as expected for sorting one array instead of lexsorting three. Disclosed and not fixed: the array estimate is slower than the frame estimate past ~10^5 rows (17.95 ms against 9.49 at 1M). It now runs only on the fallback path, so it is bounded, but there is no size guard. The end-to-end test was self-confirming. On polars the query was answered by polars-seeded on BOTH legs, so none of the new seams ran; _covers_ids was true in every param, so the "with endpoint drops" half of its own name had no case; the oracle did not use routes_off; and it passed unchanged with the kernel switched off. It now runs with the sibling routes off, asserts the kernel served, states the expected rows per case, includes a real drop case, and carries the route_engaged marker. Seven new tests. All seven fail with the fixes reverted; 79 pass with them. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
I had not applied your criteria to this PR. Doing so found two defects and a self-confirming test.All three reproduced independently before any fix, and every fix is verified by reverting it and watching the new tests fail. Head is now 1. Mixed integer key dtypes returned wrong rows
In production this was contained only by a schema-equality guard in Worth recording how nearly I missed it: my first reproduction compared the array path against itself, because 2. A regression this branch introduced, at the boundary the cost gate exists to protectMaster rejected a hop from a group-by estimate before any expansion work. The costed plan I added built everything, including the lexsort over the whole gathered-edge frame, and only then let the caller gate.
Counting needs the keys in key order only; ordering within a key needs the tiebreaks. The planner now sorts the keys to count and defers the lexsort into What that costs the serving path, measured on the benchmark rather than assumed: polars recent-replies +0.052 ms (0.46%), message-replies +0.007 ms (0.13%), pandas zero. The lexsort beside it is 0.104 ms, so the added sort is about half of it, which is what sorting one array instead of lexsorting three should cost. Disclosed and not fixed: the array estimate is slower than the frame estimate past about 10^5 rows (17.95 ms against 9.49 at 1M). It now runs only on the fallback path, so it is bounded, but there is no size guard. 3. The only end-to-end test here was self-confirmingIt failed every item of the standard. On polars the query was answered by Rewritten: sibling routes off, the kernel's serving asserted, expected rows stated per case, a real drop case added (seed node 4 reaches creators 1 and 5, so filtering to id 1 drops 5 and the semi-join must run), and the That assertion then earned its keep immediately: rebasing #2086 on top, it fired on five parameters because the array specialization answers first. #2086 now switches that route off for this case, so it keeps testing the frame kernel instead of silently comparing the array route against itself. Decline overheadPosted separately above: zero on polars (a non-qualifying query never reaches either helper), and under 0.03% on pandas. Seven new tests; all seven fail with the fixes reverted, 79 pass with them. Local gfql suite: 13215 passed, 24 failed — the same polars-conformance set that fails identically at the base commit. |
Both were bundled into this PR as pure wins with no test and no number, which is the thing the review standard exists to catch. Measured first, then pinned structurally so neither can regress quietly. resolve_engine on a polars frame: 60.36 -> 3.51 us per call. A failed `from pyspark.sql import DataFrame` is not cached, so while it sat ahead of the polars check every polars frame paid a full sys.path walk. Pinned by watching the import rather than by a timing threshold: resolving a polars frame must not attempt pyspark at all. The temporal-constructor scan: 4.41 -> 1.68 ms on a 50k-row, six-column frame when no column holds a parenthesis, and 4.93 -> 3.13 ms when one does. Asserting the verdicts alone would not pin it, since the prefilter is a pure optimization and the verdicts are the same either way -- so the test swaps in a regex that matches everything, which makes reaching the regex observable: True if it ran, False only if the prefilter short-circuited. Both pins fail at the base commit and pass here. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
…tree The vendored numbers were pre-release and four runs were 52-61 compute commits past their measuring commit, against a policy limit of 12 -- this PR's own drift gate was failing on them. seed-lookup published 1.018 ms at SF0.1 where the shipped tree measures 0.218, and 1.363 at SF1 where it measures 0.281. Re-vendored from pyg-bench with SNB measured on pygraphistry f283a30 (master with #2084, #2086, #2087, #2088, #2090) and GraphBench on 24c0b1e, both under the DGX idle gate and host perf lock with canonical rows asserted identical across engines, scales and repetitions. docs/test_bench_numbers.py now passes: 37 passed, 1 skipped. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Problem
LDBC SNB IC8
recent-replies— a 3-hop seeded chain (2.6k → 2.1k → 464 frontier) that projects six columns, orders and takes 20 — ran 29.3 ms on the measured Polars lane against Neo4j 5.4 and Memgraph 6.3. Profiling on merged master showed the cost is not the traversal: each hop runs about thirteen Polars operations over ~2k-row frames, and each one pays fixed plan and thread fan-out cost. The same query at 4 Polars threads ran 12.9 ms against 22.2 at 20 threads on identical data.Changes
All four are result-preserving: same rows, same order, same dtypes, same index-trace values.
estimate_inner_join_rowscomputes its exact sum-of-products over null-free integer keys withunique/searchsortedinstead of a group-by-and-join plan. Nulls and non-integer keys keep the frame path, because engines disagree on null-key matching.searchsortedranges over step rows pre-sorted by (key, tiebreaks) plus two row gathers.rows()acceptsattach_prop_columns, and a barerows()immediately followed byselectis rewritten to attach only thealias.columnnames the projection reads — the same rewrite in the pandas/cuDF and Polars twins, and in both bindings finishers. Any item that is not a literal, a bare alias id, an edge-alias column, or an existing node column keeps attach-all.(before the anchored regex, andresolve_enginerecognizes Polars frames before probing for pyspark.Measured
LDBC SNB SF0.1, the H684 index lane recipe (native Polars frames,
gfql_index_all, auto node-property indexes, 8 warmups, 31 samples, full record materialization). Local box, 24 threads.cuDF on a local RTX: recent-replies 372 → 174, message-replies 224 → 109. Point queries are unchanged: interleaved A/B of
message-creatorover 201 samples gives master 0.590 / 0.683 / 0.564 against 0.611 / 0.578 / 0.579 ms.Thread sensitivity drops with the array-side work: recent-replies is 9.85 ms at 24 threads and 8.14 at 4, where master was 22.2 and 12.9.
DGX A/B on the benchmark recipe
Three runs per arm on the same H684 recipe against merged master 65c359b, canonical rows identical in every cell.
Every other cell lands within about two percent, except two that deserve naming.
SF1 polars seed-lookup reads +13.5%, but the per-run values overlap completely (master 0.971 / 1.325 / 1.181 against 1.362 / 1.167 / 1.341), so that cell is noise at three runs.
SF1 pandas new-topics read +14.3%, and an interleaved re-run on an idle box reproduced +19.4%, so it was investigated rather than waved off. It is not a code effect. That query's GFQL surface is a one-hop undirected traversal with
rows(source=...), which reaches none of the changed code: the projection rewrite requiressourceto be absent, and instrumenting the bindings module's own references shows zero calls to the three changed helpers. Bisecting to the first commit of this branch still showed +13.5% even though that commit provably makes no calls on the path. The measurement record explains it: the same cell on this harness reads 574.0 / 570.6 / 528.8 on master f7a7253 and 567.1 / 522.8 / 568.8 on master 92ad8c0, both of which predate this work entirely, and an A/A control settles it: running the same interleaved driver with BOTH arms at the current master, one from each of two byte-identical checkouts, gives 567.49 and 476.62 on one checkout against 472.81 and 517.53 on the other — four runs of identical code spanning 472.8 to 567.5, with the first interleaved pair 16.7% apart. The cell is bimodal across roughly 474 to 598 whatever the code is, and this branch drew from the high end.The wider lesson is written up in the benchmark evidence: a three-run median of a bulk cell whose own A/A spread approaches the acceptance gate cannot support a product-vs-product claim, so such cells need an A/A control or many more repetitions before a delta is quoted.
Tests
tests/compute/gfql/index/test_indexed_bindings_hop_overhead.py— the array estimate against the frame estimate across pandas, Polars and cuDF including null, float, nullable-integer and lazy deferrals; predicate-first gather against gather-then-filter over drops, unsorted positions, an absent column that must raise identically, and an empty gather; the covers-ids check; end-to-end indexed against canonical with and without endpoint drops, asserting the semi-join is skipped only when it is the identity; and a twelve-seed fuzz of the array expand join against the frame plan.tests/compute/gfql/test_rows_select_projection_pushdown.py— the pushdown plan itself, then every case run with and without the pushdown on pandas, Polars and cuDF including the decline cases, a spy asserting the narrowed request reaches the builder, and parameter serialization and validation.tests/compute/gfql, chain specializations, chain and hops: 16067 passed, 1162 skipped, 102 xfailed.Review follow-up —
594f78ab6Answers the three review comments; replies are inline on the diff.
The estimate call was redundant with the very next one.
estimate_inner_join_rowscomputed a number the expansion immediately recomputes: itssearchsortedrange widths sum, over state rows, to exactly the sum-over-matched-keys of left_count x right_count. Verified on every hop of a real LDBC SNB SF0.1 run, 18 of 18, and measured at 0.19-0.67 ms per query, 3.5-4.7% of query time.plan_path_ordered_expand_joinnow returns aPathExpandPlan(rows, expand). On the array pathrowsis those range widths, so costing a hop is free; when the array path declines it falls back to the estimator. The gate condition in the hop loop is unchanged character for character, andbindings.pyno longer imports the estimator.The type ignores are gone with it, including the one in
_estimate_inner_join_rows_arrays.DataFrameTispd.DataFrameat checking time, so every polars method on atake_rowsresult needed one;as_eager_polars_framenarrows once throughisinstanceandtake_rows_polarsgathers on the narrowed frame, leaving only the return-boundary cast that is the module-wide idiom.The array conversions are free on the shape this admits.
Series.to_numpy()on a null-free, single-chunk integer column returns a zero-copy view over the Arrow buffer. Instrumenting everycol_to_arraycall in a real SNB run: every conversion inside both new helpers is a view. The one copying conversion in the hot path is pre-existing, on a 7-element column.No end-to-end speedup is claimed. An in-process A/B reads -5.35% and -1.66% on the two affected queries, but its A/A control reads +4.04% and +3.14%, so the effect is below this box's noise floor. What is established is that the removed pass was real, results are identical, and the estimator is provably not called on the served path.
Added tests:
test_expand_plan_rows_is_the_estimate_without_a_second_pass(12 seeds; pins the number AND that the estimator is never called to produce it) andtest_expand_plan_falls_back_to_the_estimator_when_the_array_path_declines. Index and join-helper suites 749 passed; guards, ruff and mypy clean with no new ignores.🤖 Generated with Claude Code
https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp