Repository navigation
perf(gfql): consult precomputed degrees — O(E) kernel pass becomes an O(N) dot - #1871
Merged
Merged
Conversation
…n O(N) dot Wires the facts #1870 landed. sum_e indeg(src(e)) == dot(indeg, outdeg), so with per-type degrees resident the kernel answers without touching the edges: 6.76ms of query work becomes 0.046ms at board scale. Targets q8@100k (the board's last LOSS) and q9 (same shape, slowest cell). Two design points found while wiring, both pinned because a VALUE test cannot see either: - The node-label <-> relationship-type pairing is QUERY-dependent, not resolvable at index time (labels and rel types are different vocabularies). So degrees are built over the whole dense node interval and the consult SLICES to the proved domain -- sound because the bounds proof already guarantees every filtered endpoint lies inside it. An off-by-one there silently MISCOUNTS. - Identity must anchor to the BOUND edge frame, not the per-type subset the fact was counted over. Anchoring to the subset made every lookup miss: facts built, never used, answers still correct. Only an engagement probe revealed it. Gapped node spaces build nothing -- arrays are indexed by id - lo. 13 pins incl. slice-exactness across four domain shapes and a differential vs the scan on random typed graphs. Whole-tree mypy clean apart from two pre-existing degrees.py errors present on a clean tree. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi
Step (2) of the goal, and it was not a formality: the degree pins were pandas-only, and _add_degree_facts used pandas boolean-mask __getitem__, which polars REJECTS. Degree facts would have silently never built on polars -- the board's own engine -- with answers still correct and nothing failing. Filter now dispatches per engine. Pins parametrized over pandas/polars/cudf, registered in POLARS_TEST_FILES, imports guarded with importorskip. 18 pandas+polars pass; cudf arms exercise on the GPU lane. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Wires the facts #1870 landed.
sum_e indeg(src(e))==dot(indeg, outdeg), so with per-type degrees resident the kernel answers without touching the edges: 6.76 ms → 0.046 ms of query work at board scale.Targets q8@100k — the board's last remaining LOSS — and q9, the same degree-product shape and the slowest cell on the board. Not claiming the flip until a VALID lane says so.
Two design points found while wiring, both pinned
The label ↔ rel-type pairing is query-dependent. Node labels and relationship types are different vocabularies, so which label sits at the ends of which rel cannot be resolved at index time. Degrees are built over the whole dense node interval and the consult slices to the proved domain — sound only because the bounds proof already guarantees every filtered endpoint lies inside it. An off-by-one there silently miscounts.
Identity must anchor to the bound edge frame, not the per-type subset the fact was counted over. Anchoring to the subset made every lookup miss — facts built, never used, answers still correct. Only an engagement probe revealed it.
Neither is visible to a value test, which is why both get engagement pins.
Pins
13, including slice-exactness across four domain shapes, the gapped-domain decline (no valid
id - loindexing), identity-vs-partition, and a differential against the scan on random typed graphs.Whole-tree mypy clean apart from two pre-existing
degrees.pyerrors present on a clean tree.🤖 Generated with Claude Code
https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi