Repository navigation
perf(gfql): narrow a seeded point query's edges on codes before building a frame - #2090
Conversation
Every AST object is validated TWICE inside a single execution. `gfql` builds a Chain from the caller's ops, which validates them; the execution path then constructs a throwaway Chain purely to validate them again, and deliberately unwraps an already-validated Chain to do it. Measured redundancy factor 1.7-1.8x by counting ASTSerializable.validate calls in one execution. This is not a benchmark artifact, and that was checked before building. The SNB harness reuses AST objects across repetitions, so a memo keyed on object identity would show a large benchmark win and do nothing for a real caller; that was rejected. What is removed here is redundant WITHIN a single call, so a caller that passes a plain list and reuses nothing pays both passes today. The re-validation exists to catch a caller that built a Chain, mutated its ops, and then executed it. That caller is unaffected and still raises, pinned for both entry points. The signal is explicit and narrow: Chain.gfql_validated(), set only by gfql on a Chain it just built, never inferred from the Chain itself, and it cannot be forged onto a Chain constructed with validate=False. Two sites needed it -- the polars branch, and the pandas path, which unwraps the Chain before validating and so loses any marker. Measured in-process, arms alternated, 6 rounds x 31 reps, each against its own A/A control (LDBC SNB SF0.1, polars): seed-lookup 0.995 -> 0.897 ms (-0.098, A/A floor 0.034) message-replies 1.714 -> 1.640 ms (-0.074, A/A floor 0.011) recent-replies 3.488 -> 3.390 ms (-0.098, A/A floor 0.022) Three to seven times its own floor on each. It is a fixed per-query cost, so it helps every query and every engine. No end-to-end claim: a cross-process A/B against master cannot resolve 0.1 ms, its own A/A floor running +3.3% to +12.5%. Tests: 8 new, covering both sides -- gfql validates once, chain called directly still re-validates, a Chain mutated after construction is still caught through both entry points, the mark cannot be forged, and malformed queries raise identical error codes. Validation suites 746 pass. Broad compute suite 14980 pass / 32 fail, an identical failure set to untouched master on this box. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
…ing a frame A seeded point query gathers the seed's incident edges into a frame and then filters that frame. Attributing seed-lookup's polars calls by call site showed where its time actually goes: 0.233 ms in the edge filter, 0.132 in the collect underneath it, and 0.175 gathering the candidates -- 46% of a 1.17 ms query spent materializing rows that the predicate then throws away. The candidates are row POSITIONS before they are a frame. When the edge predicate is one the category index from #2087 can answer, the filter runs on uint8 codes and only the surviving rows are gathered. That is the same structure #2087 built for the array traversal, reused by the point path -- which is the concrete answer to "does the indexing work hint at more indexes we can use for the others": the index already existed, the point path just was not asking it. Anything the index cannot answer falls back to gather-then-filter unchanged, so the canonical filter stays the authority on 3-valued and dtype behaviour. `_index_edge_rows` is now a thin wrapper over a new `_index_edge_positions`, so the gather and the lookup are separable without changing what the gather does. Measured interleaved, arms alternated, 5 rounds x 41 reps, against its own A/A control (LDBC SNB SF0.1, polars, local): seed-lookup 1.019 -> 0.476 ms (-53.3%, A/A floor -5.0%, ranges disjoint) message-creator 0.572 -> 0.540 (-5.5%, floor +4.1%) message-replies 1.774 -> 1.710 (-3.6%, floor -0.6%) recent-replies 3.449 -> 3.522 (+2.1%, floor +1.4%) message-content 0.395 -> 0.395 ( 0.0%, floor +1.4%) Only seed-lookup moves beyond its own floor, and it moves by ten times that floor with non-overlapping ranges. Rows correct in every arm and repetition. NO bench claim is made here: local and bench are not related by a ratio (same commit, the ratio across queries spans 0.84x to 2.54x), so the competitor comparison needs its own bench run. Tests cover both sides of the boundary from the first commit: three indexed predicates (one survivor, several survivors, a value the column never holds) against gather-then- filter as oracle with expected row counts asserted; six predicates the index cannot answer (absent, empty, unindexed column, cross-type scalar, missing column, mixed) which must fall back and still agree, including agreeing on the exception; an engagement pin that fails if the narrowing never runs, verified by disabling it; and the no-index case. Registered in the polars lane and marked route_engaged, verified across all ten routes-off modes. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
… the module CI caught what a local run could not: the new test module imported polars at module scope, so `test-gfql-core` -- a lane where polars is not installed -- failed to IMPORT the file rather than skipping it. The sibling index tests already use `pytest.importorskip` at module scope for exactly this; this file now matches. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
…on how it got there The previous suite asserted mostly that the narrowing engaged, which is an implementation fact; a caller cannot observe it at all. Rewritten around the boundary that IS observable: the same query, on either side of "can the category index answer this edge predicate", must return the same rows in the same order or raise the same error. Every case now states its expected rows outright before comparing them to gather-then-filter, so a case cannot pass by both routes being empty. Fifteen cases, eight answerable and seven not, covering source order with non-contiguous edges, reverse direction, two coded columns, a high-null coded column, a value the column never holds, a seed with no edges, a seed matching no node, a float column, a non-scalar predicate, an absent column, a null predicate, a cross-type scalar that must raise identically, parallel edges, and a graph with no index at all. The engagement pins are kept but demoted to one labelled pair, asserted over the same two lists, and scoped to the EDGE frame -- the old pin counted node seed lookups through the same helper, so it would have reported engagement for predicates that were never narrowed. Mutation-checked: dropping the survivor mask fails 4, reversing source order fails 3. (Answering a null predicate from the code map instead of declining is an equivalent mutant -- the value map never holds None, so both paths return empty.) Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Parked pending bench numbers — and the local evidence does not currently justify mergingWhat the narrowing is actually worth, isolatedMeasured with both arms on the same tree — arm A forces
Rows identical and equal to expected in every arm and every query — no correctness cost. But it improves one query of six, by about 0.3 ms, and nothing else moves outside the control band. Two corrections that follow from this:
Where that leaves itThe standing bar for this release says a number that only helps the query it was built for is not a result. On this evidence, that is what this PR is. It is parked rather than closed because seed-lookup is the cell that was historically a loss, and 0.3 ms measured against a competitor is a different claim from 0.3 ms measured against our own 4 ms envelope — so the dgx bench lane, which has to run for the release anyway, decides merge-or-close. Kept regardless of that outcomeThe tests were rewritten onto the caller-visible boundary ( Mutation-checked: dropping the survivor mask fails 4 cases, reversing source order fails 3. (Answering a null predicate from the code map instead of declining is an equivalent mutant — the value map never holds Local numbers throughout: they attribute work inside one box, sit beside no competitor arm, and are not convertible to bench numbers. |
Two docstrings explained rationale that is either obvious from the call site or, since the boundary-test rewrite, pinned by tests. `_index_edge_positions` kept a paragraph justifying why it was split out, which its only caller makes plain. `_gathered_edges_matching` spelled out that declining keeps the canonical filter authoritative over 3-valued and dtype behaviour -- now asserted directly by the seven not-answerable cases. Net 3 insertions / 11 deletions, all prose. Behaviour unchanged; the file's 34 boundary tests pass and neither guard baseline grew. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
Correction: the bench reverses my previous comment. This should merge.My earlier comment argued this PR helps only the query it was built for and was not worth merging. That was wrong, and the bench shows it. Now that #2084/#2086/#2087/#2088 are on master, I re-measured the release scoreboard on the tree that would ship without this PR. SF0.1 polars, 5 runs per arm, rows verified equal across arms and stable within each for all 7 cells, zero bad probes.
4.1x worse without it. Against Memgraph 0.460 that is the difference between a 2.1x win and a clear loss on the release's headline cell. The two arms are comparable — checked, not assumed. Every other cell agrees closely between them: message-content 0.161/0.163, message-creator 0.225/0.239, message-replies 1.766/1.385, new-topics 42.026/42.266, recent-replies 5.364/5.326, tag-cooccurrence 32.849/32.176. Only seed-lookup moved. It also removes the variance: ±2% with this PR (0.215-0.223), ±89% and bimodal without (0.655-1.239). That fits the mechanism precisely — the materialization this PR avoids is what was variable. Why my local isolation misled meLocal isolation measured -6.9% / 0.296 ms on one query of six. Both readings are real. The local SNB-mirroring lane's seed-lookup envelope is ~4.3 ms, dominated by costs this PR never touches; the bench envelope for the same query is 0.2-0.9 ms. The same absolute saving is 7% of one and most of the other. I never scaled the local number into a bench claim, which is why this ended as a wrong recommendation rather than a wrong published figure. It is a good argument for the rule. Before merging
Tests, comments and typing are already addressed: the suite was rewritten onto the caller-visible boundary (15 cases, 8 answerable / 7 not, expected rows stated outright) and mutation-checked, the docstrings were trimmed to what the tests do not already carry, and the PR adds no dynamic typing. |
…w-lookup # Conflicts: # graphistry/compute/chain.py # graphistry/tests/compute/gfql/test_chain_validation_reuse.py
Lane 4 settles it — mergingInterleaved A/B on one master, 5 runs per arm alternating under the idle gate and the host perf lock. A = master
The seed-lookup ranges are disjoint — A [0.630, 0.787, 0.842, 0.966, 1.021], B [0.219, 0.219, 0.222, 0.224, 0.227]. Every B run beats every A run, and B's spread is 3.6% against A's 62%. Nothing else moves outside its noise, so this PR owns exactly one cell. Against Memgraph 0.460 on the same board, that cell is a 2.07x win at 0.222 and a loss at 0.842. Pinsgraphistry/pyg-bench#270 adds an SNB cell-floor checker — SNB had none, which is why the regression above could only be found by re-measuring an arm by hand — and commits floors for this cell at both scales. The floors guard the median AND the worst run, because without this change the cell is bimodal rather than uniformly slow, and a median-only floor would pass a cell that is intermittently 4x slow. Verified against both arms of the lane it describes: exit 0 with the change, exit 1 without, tripping on both criteria. BarCI 89/89 at |
…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) <[email protected]> Claude-Session: https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp
1 participant
Problem
A seeded point query gathers the seed's incident edges into a frame and then filters that frame. Attributing
seed-lookup's polars calls by call site shows where the time actually goes:DataFrame.filterLazyFrame.collectDataFrame.__getitem__That is 46% of a 1.17 ms query spent materializing rows the predicate then discards.
Change
The candidates are row positions before they are a frame. When the edge predicate is one the category index from #2087 can answer, the filter runs on uint8 codes and only the surviving rows are gathered.
This is the same structure #2087 built for the array traversal, reused by the point path — the concrete answer to "maybe its indexing work hints at more indexes we can use for the others". The index already existed; the point path simply was not asking it.
Anything the index cannot answer falls back to gather-then-filter unchanged, so the canonical filter stays the authority on three-valued and dtype behaviour.
_index_edge_rowsbecomes a thin wrapper over a new_index_edge_positions, so the lookup and the gather are separable without changing what the gather does.Measured
Interleaved, arms alternated per round, 5 rounds × 41 reps, each against its own A/A control. LDBC SNB SF0.1, polars, local.
Only seed-lookup moves beyond its own floor, and it moves by ten times that floor with non-overlapping ranges ([0.987–1.065] against [0.472–0.489]). Rows correct in every arm and repetition.
No bench claim is made here. Local and bench are not related by a ratio — measured on the same commit, the local/bench ratio across queries spans 0.84x to 2.54x — so the competitor comparison needs its own bench run. That run is queued.
Tests
Both sides of every boundary, from the first commit rather than retrofitted:
Registered in the polars lane, marked
route_engaged, and verified across all ten routes-off modes. Broad compute suite: 15176 passed, failure set identical to untouched master.Stacked on the experiment tree (
f332bbf9b= #2087's head with #2088 applied), so it carries #2084, #2086, #2087 and #2088 beneath it.🤖 Generated with Claude Code
https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp