`expand_observations`' scoring join is O(C + U) as a hash join and O(U x C) as a
nested loop, where C is the connected-source set and U the unnested candidate
source ids. PostgreSQL picks between them from its row estimate for the
`connected_sources` CTE, and that estimate was 1 against an actual ~3,700: the
capped column came out of a LATERAL + LIMIT subquery, which carries no
n_distinct statistic, so DISTINCT over it was estimated at 2 and the NOT EXISTS
anti-join took that to 1. A 1-row inner side makes the nested loop look free, so
it won on cost and lost by four orders of magnitude at runtime — 15s and ~15M
rejected join rows on a realistically-shaped bank, matching the plans reported
in the issue.
Rank with row_number() instead. Identical output — same cap, same ordering,
unit_id is unique — but the capped column now traces to unit_entities.unit_id, so
the estimate comes from real statistics (207-3,449 against 2,242-4,193 actual)
and the nested loop is priced honestly. Measured over 12 seed sets on the fixture
below: p50 15,013ms -> 217ms, with the full scored set identical.
The set-difference rewrite proposed in #3512 also clears the reported bank, but
it leaves the estimate at 2 and survives only because a set-op prices the nested
loop just above the hash join: 1.0-1.2x headroom against 1.6-1.8x here.
The trade is that ranking reads every unit_entities row of a matched entity where
the LATERAL stopped at per_entity_limit off the index: O(sum of degree) rather
than O(entities x per_entity_limit). At parity up to ~12k-degree hubs, +50%
traversal cost at 38k.
Why the perf suite never caught it
----------------------------------
`recall-with-observations` measured 0.45s on the same query a realistically
shaped bank runs in 15s. Two fixture properties were wrong, and neither alone
reproduces the bug — measured on the suite's own bank:
sources=113 sources=mean 2
old vocabulary 450ms 270ms
new vocabulary 951ms 15,013ms
- The entity vocabulary was a fixed 145 names at every scale, so degree grew with
bank size instead of the entity count growing: 142 entities at median degree 40
with not one entity mentioned once, and every seed reaching 142 of 142
entities. It now grows with the corpus (1,354 entities, median degree 3, 449
mentioned once, seeds reaching 54).
- Sources per observation was a constant. Real counts are long-tailed — the
reported bank ran mean 1.7 / p95 4 — so it is now the mean of a Pareto draw.
At mean 2 the fixture still emits observations carrying several hundred
sources, keeping the array-length path from #3085 exercised.
`recall-with-observations` at scale=large will step up when this lands: the
suite can finally see this query. The SQL fix is in the same change so the
dashboard moves once, not twice.
Oracle's expand_observations has the same DISTINCT-over-LATERAL shape and is
deliberately left alone — no Oracle instance was available to measure it, and its
cardinality estimation differs. Documented in ops_oracle.py.
Tests
-----
- test_per_entity_cap_bounds_hub_traversal pins that the window ranks the same
rows the LATERAL selected; it fails if the cap is widened or dropped.
- test_perf_fixture_shape asserts the post-resolution entity graph keeps a long
tail. It simulates the entity resolver's intra-batch fuzzy merge, because the
tail names have to stay under the 0.5 pg_trgm threshold: a tail generated as
"<stem> <counter>" scores 0.73 and the resolver collapsed 2,814 names to 159,
silently restoring the flat graph the vocabulary exists to avoid.
Nicolò Boschi
5f137bf391