perf(gfql): index low-cardinality columns so label and type predicates compare codes - #2087

Your instinct on boundary testing found a silent wrong answer in this PR. Fixed in 153a7cf2d, and the test that was written for exactly that case was passing vacuously.

The defect

_code_for matched on type(value) is type(expected), and _positions_via_category_index treated "no code found" as matches nothing (positions[:0]) rather than cannot answer (None). A polars filter does coerce across those types, so a cross-type scalar returned an empty result where the canonical route returns rows. Reproduced with engagement proven on the served leg:

All three are correct at the parent, so this branch introduced them. The docstring asserting "the canonical filter does not conflate them" was simply wrong about its own oracle.

Fix: _code_for returns three states — the code; None for a value of the right type the column does not hold, which genuinely matches nothing; and _DECLINE when the scalar's type differs from the column's values, or the column is all-null and offers no type to compare against. The lookup defers to the canonical filter on _DECLINE. Same-type predicates still serve, so the fast path is not lost.

Why the test could not see it

test_boolean_predicate_never_matches_an_integer_column_code existed for this exact case and passed. The whole differential corpus seeded at n({"id": 1}) and walked e_forward — and node 1 has no outgoing edge, so every case compared [] == []. A fast path that drops every row is structurally invisible to an empty-vs-empty corpus.

Rewritten so it cannot recur: the corpus walks the direction that has edges; every case asserts the oracle's row count, so a case cannot silently go vacuous; _both turns point-rows off and asserts that both the specialization and the category lookup actually served; the canonical leg is a real oracle (index_policy="off" with the sibling routes off, not another fast path); and a new parametrized family covers the cross-type scalars plus a unit pin on the three-state verdict.

Verified by reinstating the bug: 5 of the new cases fail with it, 41 pass with the fix.

Your question about more indexes — measured, and it points somewhere specific

I timed the primitives the traversal actually calls, at this head, LDBC SNB SF0.1 polars, as a share of each query's own median:

Three conclusions, each killing or backing a candidate:

1. A pre-sorted adjacency is not worth building. The obvious next index — have the adjacency carry its rows already ordered by (key, tiebreak) so the expansion's lexsort disappears — is worth 2.3% of recent-replies and under 0.5% everywhere else. Rejected before building it.
2. The lever that is indicated: key the CSR by dense node row position, not by sorted id. searchsorted plus unique is 25.6% of recent-replies, and nearly all of it is mapping ids to positions and de-duplicating a frontier of ids. A CSR whose offsets are indexed by node row (0..N−1) makes every id→position lookup an O(1) array index and lets the frontier be a dense mark instead of a sort-and-unique. That is the same move EndpointRowsFact already made for edge endpoints, generalized to the traversal itself.
3. No index helps seed-lookup or new-topics. seed-lookup spends 0.043 ms of 1.097 in array work — it is dispatch-bound and needs a one-row materialization path, not an index. new-topics spends 0.15 ms of 68.7; it is polars compute and an index cannot reach it.

Build cost and accounting — two gaps I have not closed yet

Worth stating rather than burying, and I would rather fix them before this merges if you agree:

• The three new structures are built eagerly and unconditionally by gfql_index_all, and gfql_index_categories defaults to every column of both frames, calling unique() on each. On a wide frame that is many full distinct passes that yield no index because the cardinality cap rejects them.
• build_endpoint_rows_fact has no engine gate, so a pandas graph builds a fact only the polars path can consume.
• index_nbytes and show_indexes do not count the new structures, so the memory signal under-reports. The endpoint-rows array is the largest per-edge sidecar added so far.

Local suite at this head: 13289 passed, 24 failed — the same polars-conformance set that fails identically on the untouched parent.

Two more commits since the comment above, head is now 581ac831f, and the three build-hygiene items I flagged as open are now closed.

f9438d201 — build cost, engine gate, memory accounting.

• build_category_index ran an exact distinct pass on every admitted-dtype column before the cardinality cap could reject it, so a wide frame paid a full pass per column that yields no index. It now rules out a clearly-over-cap column with approx_n_unique() first; the margin keeps the sketch's error away from the cap and the exact check still decides everything near it, so the cap itself cannot move. On a 200k-row, 30-high-cardinality-string-column frame: gfql_index_categories 230 → 56 ms, whole gfql_index_all 0.490 → 0.376 s against a 0.069 s base.
• build_endpoint_rows_fact is now polars-only, matching its only consumer. A pandas graph builds zero.
• index_nbytes and show_indexes now cover all three structures. On a 20k-node/80k-edge graph that is 1.38 MB of a 4.89 MB total that was previously invisible. test_every_kind_carries_per_row_reason pinned an exact kind set and now uses ALL_REPORTED_KINDS, so a future fact that forgets to report fails rather than passing quietly.

Two docstrings asserted the opposite of the code and are corrected: both CategoryIndex and build_category_index claimed columns with nulls are not indexed. Nulls get a reserved code, which is exactly what makes the null-heavy label__* columns indexable.

What I did not optimize, deliberately: gfql_index_endpoint_rows is still 204 ms on 800k edges. That is real per-edge work bought to remove a per-hop search, a declared setup step like the adjacency build. It is now disclosed in show_indexes rather than optimized away on a hunch.

581ac831f — Categorical columns. pl.Categorical is admitted alongside pl.String, and the build joins on a mapping frame it constructs itself, which is the string-cache-sensitive case — but nothing tested it, and nothing tested that pl.Enum declines. Both verified and pinned, including an end-to-end family against the canonical filter with expected row counts.

Provenance check: do the numbers in the body still hold at the current head?

The DGX A/B table in the description was measured at 6a0da0907. The head is now 581ac831f, which adds a correctness fix that deliberately removes fast-path coverage for cross-type scalars. That could have cost part of the win, so I checked rather than relabelled the numbers.

Engagement is byte-identical. Category lookups served vs declined, on the real LDBC SNB SF0.1 fixture:

The one decline in each was already there before the fix — it is a column with no category index, not a cross-type scalar. No SNB predicate is cross-type, so the fix costs this benchmark nothing.

Timings, interleaved A/B with an A/A control, 5 rounds, arms alternating, local box, medians of per-run medians in ms. Arm A is 6a0da0907, arm B is 581ac831f, arm C is a second checkout of A — so C vs A is the measurement floor and only a B-vs-A delta beyond it would mean anything:

Every B-vs-A delta is at or inside its own A/A floor; seed-lookup's floor is larger than its effect. Canonical rows matched expectations in all 15 runs.

So the published numbers stand at the current head. They are not being relabelled to it: they were measured at 6a0da0907, and this is the evidence that the head since then did not move them.

Retargeted to master, plus two fixes found in a final pass

origin/master is now c5ce5e4f8 (#2086 landed). Base retargeted through the GitHub base field and master merged in — clean, one auto-merge in bin/test-polars.sh.

The coverage baseline was re-checked in both directions after the merge, since a wrong one turns master's lint red and a red lint lane skips every test lane repo-wide: graphistry/compute/gfql/lazy/**/*.py resolves to 24 files and the baseline holds 24 entries, with no target missing from the baseline and no baseline entry outside the target set. This PR adds no lazy-engine file, so it needs no new floor.

1. A docstring that contradicted its own design

gfql_index_categories described eligibility as "no nulls, at most 64 distinct values". build_category_index, in this same PR, says "Nulls ARE coded, under a reserved code" — and the second one is right. It is also the design point the whole change rests on: the null-heavy label__* columns are only indexable because nulls get a reserved code, and that is where most of the measured win comes from.

Verified against the built index rather than the prose: a null-bearing column yields value_codes {'BOUGHT': 0, 'IS_LOCATED_IN': 1} with nulls carrying reserved code 2, and None is never a key — so value_codes.get(None) can never return the null code, and a null predicate declines structurally rather than by luck.

test_category_index.py already pins this (Boolean/String/Int64 columns containing None, asserting the reserved code is never handed out for a queried value), so the prose was cut to a pointer instead of being rewritten into a longer rule it had got wrong.

2. The one dynamic-typing probe this PR added

Scanning only this PR's own added product lines turned up exactly one: getattr(values.dtype, "kind", "") deciding control flow in the endpoint-row resolver. Twelve lines above, the same file already reads str(keys.dtype.kind) directly on the same kind of value from the same helper, with the note "numpy/cupy arrays always carry dtype.kind" — so the probe was guarding against a case the file itself states cannot happen. Replaced with the direct read. mypy clean across 349 files with it in place.

(The sibling probe at build.py:434 is pre-existing on master and is deliberately left alone.)

Verification on the merged tree

• ruff clean; lint exit 0 with no growth on either guard baseline; mypy 351 source files clean; GFQL index suite 1094 passed.
• TCK at the pinned harness 84b098c: 4264 passed / 182 skipped / 689 xfailed / 0 failed — byte-identical to master c5ce5e4f8 on the same harness.
• Bench engagement receipts verified unchanged. The SNB lane proves index engagement by patching _seed_rows_via_property_index, and this PR's category index also answers node-role lookups — so it could plausibly have bypassed that seam and silently degraded every lane receipt to "unverified". Ran the harness's own verify_index_engagement on both arms: identical in all six cells (engaged / built_engaged with matching probe and hit counts; new-topics reaches no seed seam on the baseline too).