Fence the affected package lookup with a LATERAL join

Orin Naamanrequested to merge
fix/pm-affected-packages-lateral-probe into master

What does this MR do and why?

Problem

PackageMetadata::AffectedPackage.for_occurrences joins pm_affected_packages to a VALUES list of up to 50 SBOM components, and its callers iterate the result with each_batch. Before reading anything, each_batch probes the relation with ORDER BY id LIMIT 1.

Depending on the sampled statistics of package_name, Postgres can plan that probe as a scan of the whole primary key with the 50 names as a join filter. On a full advisory dataset, this can exceed the 15-second statement_timeout, and the SBOM scan fails.

Fix

The scope joins through a fenced LATERAL subquery instead of an INNER JOIN on the CTE:

  • LATERAL makes one index seek per component the only way to evaluate the join, so the probe cannot become a primary key scan (LATERAL planner fence)
  • OFFSET 0 stops Postgres from flattening the subquery back into a plain join, which would reopen the scan
  • PackageMetadata::MalwareAffectedPackage.for_occurrences gets the same change
  • each_batch is kept, so a batch still loads at most 1,000 rows
Why the plan flips

package_name has a long tail: a few names have tens of thousands of advisory rows, most have one. ANALYZE samples the column and underestimates its distinct values (on a 4M row dataset: 9,532 estimated, 55,521 actual), so the planner expects more rows per index seek than there are and prices the index plan too high. Once that estimate exceeds the cost of walking the primary key in id order and stopping at the first match, the probe becomes a scan of the whole table. The fence removes that scan from the planner's options instead of depending on the sample.

Why each_batch stays

A slice is bounded to 50 components, but not in rows: one package name can carry many advisory rows. On the full advisory dataset:

Advisory rows in pm_affected_packages
Package names with more than 1,000 advisory rows 375
Package names with more than 5,000 advisory rows 119
linux (purl type deb) 148,334
50 largest Debian package names together 1,168,534

A slice that contains package names like these would load all of those rows in one query. each_batch keeps it at 1,000 rows per batch.

Database

Production clone (Database Lab): no regression

each_batch runs two queries per batch:

  • A probe for the next id (ORDER BY id LIMIT 1)
  • The batch itself (WHERE id >= X).

Both are built from for_occurrences, so both queries changed and both are listed below, before and after.

On GitLab.com the bug does not occur: the planner already picks the index plan for the probe on master, and the two shapes cost the same (863.85 and 865.80). The production clone therefore cannot show the fix. What it shows is that there is no regression: same plan, same pages, same time for both queries. The fix itself is demonstrated on a GDK by forcing the planner (table further below).

Plans from the postgresai CLI on the gitlab-production-main clone, EXPLAIN ANALYZE with 50 Maven (purl_type, name) pairs. Each query ran twice in the same session; the numbers are from the second, warm run, so the times are comparable.

Query Master This MR
each_batch probe (ORDER BY id LIMIT 1) Index Scan on (purl_type, package_name), 222 buffers, 1.6 ms same plan, 222 buffers, 1.6 ms
Batch (WHERE id >= X) Index Scan on (purl_type, package_name), 241 buffers, 2.0 ms same plan, 219 buffers, 1.8 ms

The second each_batch probe (WHERE id >= X ORDER BY id ASC LIMIT 1 OFFSET 1000) has the same shape as the first and is not listed separately.

Regression specs on both callers record the emitted queries and assert that every occurrences_cte query with ORDER BY ... LIMIT goes through the fenced LATERAL subquery.

Probe, master (first, cold run: 80 of its 222 buffers came from disk) 
WITH occurrences_cte(purl_type, name) AS (VALUES (5, '...'), ... 50 pairs ...)
SELECT DISTINCT "pm_affected_packages"."id"
FROM "pm_affected_packages"
INNER JOIN occurrences_cte ON occurrences_cte.purl_type = "pm_affected_packages".purl_type
  AND occurrences_cte.name = "pm_affected_packages".package_name
ORDER BY "pm_affected_packages"."id" ASC LIMIT 1
 Limit  (cost=863.85..863.85 rows=1 width=8) (actual time=86.702..86.704 rows=1 loops=1)
   Buffers: shared hit=142 read=80 dirtied=37
   ->  Unique  (cost=863.85..864.71 rows=173 width=8) (actual time=86.700..86.701 rows=1 loops=1)
         Buffers: shared hit=142 read=80 dirtied=37
         ->  Sort  (cost=863.85..864.28 rows=173 width=8) (actual time=86.698..86.699 rows=1 loops=1)
               Sort Key: pm_affected_packages.id
               Sort Method: quicksort  Memory: 25kB
               Buffers: shared hit=142 read=80 dirtied=37
               ->  Nested Loop  (cost=0.43..857.42 rows=173 width=8) (actual time=5.146..86.661 rows=69 loops=1)
                     Buffers: shared hit=139 read=80 dirtied=37
                     ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.001..0.054 rows=50 loops=1)
                     ->  Index Scan using index_pm_affected_packages_on_purl_type_and_package_name on public.pm_affected_packages  (cost=0.43..17.03 rows=11 width=25) (actual time=0.793..1.731 rows=1 loops=50)
                           Index Cond: ((pm_affected_packages.purl_type = "*VALUES*".column1) AND (pm_affected_packages.package_name = "*VALUES*".column2))
                           Buffers: shared hit=139 read=80 dirtied=37
Probe, this MR 
WITH occurrences_cte(purl_type, name) AS (VALUES (5, '...'), ... 50 pairs ...)
SELECT DISTINCT "pm_affected_packages"."id"
FROM occurrences_cte,
  LATERAL (SELECT * FROM "pm_affected_packages"
           WHERE "pm_affected_packages".purl_type = occurrences_cte.purl_type
             AND "pm_affected_packages".package_name = occurrences_cte.name
           OFFSET 0) "pm_affected_packages"
ORDER BY "pm_affected_packages"."id" ASC LIMIT 1
 Limit  (cost=865.80..865.80 rows=1 width=8) (actual time=0.398..0.399 rows=1 loops=1)
   Buffers: shared hit=222
   ->  Sort  (cost=865.80..865.82 rows=11 width=8) (actual time=0.397..0.398 rows=1 loops=1)
         Sort Key: pm_affected_packages.id
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: shared hit=222
         ->  HashAggregate  (cost=865.63..865.74 rows=11 width=8) (actual time=0.371..0.378 rows=69 loops=1)
               Group Key: pm_affected_packages.id
               Batches: 1  Memory Usage: 32kB
               Buffers: shared hit=219
               ->  Nested Loop  (cost=0.43..864.26 rows=550 width=8) (actual time=0.028..0.348 rows=69 loops=1)
                     Buffers: shared hit=219
                     ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.001..0.011 rows=50 loops=1)
                     ->  Index Scan using index_pm_affected_packages_on_purl_type_and_package_name on public.pm_affected_packages  (cost=0.43..17.05 rows=11 width=258) (actual time=0.005..0.006 rows=1 loops=50)
                           Index Cond: ((pm_affected_packages.purl_type = "*VALUES*".column1) AND (pm_affected_packages.package_name = "*VALUES*".column2))
                           Buffers: shared hit=219
Batch, master 
WITH occurrences_cte(purl_type, name) AS (VALUES (5, '...'), ... 50 pairs ...)
SELECT DISTINCT "pm_affected_packages".*
FROM "pm_affected_packages"
INNER JOIN occurrences_cte ON occurrences_cte.purl_type = "pm_affected_packages".purl_type
  AND occurrences_cte.name = "pm_affected_packages".package_name
WHERE "pm_affected_packages"."id" >= 413700
 Unique  (cost=865.18..870.77 rows=172 width=127) (actual time=0.406..0.434 rows=34 loops=1)
   Buffers: shared hit=241
   ->  Sort  (cost=865.18..865.61 rows=172 width=127) (actual time=0.405..0.408 rows=34 loops=1)
         Sort Key: pm_affected_packages.id, pm_affected_packages.pm_advisory_id, pm_affected_packages.created_at, pm_affected_packages.updated_at, pm_affected_packages.purl_type, pm_affected_packages.package_name, pm_affected_packages.distro_version, pm_affected_packages.solution, pm_affected_packages.affected_range, pm_affected_packages.fixed_versions, pm_affected_packages.overridden_advisory_fields, pm_affected_packages.versions
         Sort Method: quicksort  Memory: 31kB
         Buffers: shared hit=241
         ->  Nested Loop  (cost=0.43..858.79 rows=172 width=127) (actual time=0.026..0.351 rows=34 loops=1)
               Buffers: shared hit=219
               ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.001..0.023 rows=50 loops=1)
               ->  Index Scan using index_pm_affected_packages_on_purl_type_and_package_name on public.pm_affected_packages  (cost=0.43..17.05 rows=11 width=127) (actual time=0.005..0.006 rows=1 loops=50)
                     Index Cond: ((pm_affected_packages.purl_type = "*VALUES*".column1) AND (pm_affected_packages.package_name = "*VALUES*".column2))
                     Filter: (pm_affected_packages.id >= 413700)
                     Rows Removed by Filter: 1
                     Buffers: shared hit=219
Batch, this MR 
WITH occurrences_cte(purl_type, name) AS (VALUES (5, '...'), ... 50 pairs ...)
SELECT DISTINCT "pm_affected_packages".*
FROM occurrences_cte,
  LATERAL (SELECT * FROM "pm_affected_packages"
           WHERE "pm_affected_packages".purl_type = occurrences_cte.purl_type
             AND "pm_affected_packages".package_name = occurrences_cte.name
           OFFSET 0) "pm_affected_packages"
WHERE "pm_affected_packages"."id" >= 413700
 HashAggregate  (cost=882.13..882.24 rows=11 width=127) (actual time=0.393..0.400 rows=34 loops=1)
   Group Key: pm_affected_packages.id, pm_affected_packages.pm_advisory_id, pm_affected_packages.created_at, pm_affected_packages.updated_at, pm_affected_packages.purl_type, pm_affected_packages.package_name, pm_affected_packages.distro_version, pm_affected_packages.solution, pm_affected_packages.affected_range, pm_affected_packages.fixed_versions, pm_affected_packages.overridden_advisory_fields, pm_affected_packages.versions
   Batches: 1  Memory Usage: 40kB
   Buffers: shared hit=219
   ->  Nested Loop  (cost=0.43..865.63 rows=550 width=127) (actual time=0.026..0.356 rows=34 loops=1)
         Buffers: shared hit=219
         ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.001..0.013 rows=50 loops=1)
         ->  Subquery Scan on pm_affected_packages  (cost=0.43..17.19 rows=11 width=127) (actual time=0.005..0.007 rows=1 loops=50)
               Filter: (pm_affected_packages.id >= 413700)
               Rows Removed by Filter: 1
               Buffers: shared hit=219
               ->  Index Scan using index_pm_affected_packages_on_purl_type_and_package_name on public.pm_affected_packages pm_affected_packages_1  (cost=0.43..17.05 rows=11 width=127) (actual time=0.005..0.006 rows=1 loops=50)
                     Index Cond: ((pm_affected_packages_1.purl_type = "*VALUES*".column1) AND (pm_affected_packages_1.package_name = "*VALUES*".column2))
                     Buffers: shared hit=219
GDK with the full advisory dataset (4.0M rows): the fix

Setup: pm_affected_packages synced from the advisory export (4,003,326 rows, 55,521 distinct package_name values, n_distinct sampled as 9,532), Postgres 17.8, GDK defaults. On those defaults the planner picks the index plan at any list size, so the primary key plan is forced for the "before" runs with:

SET enable_sort = off; SET enable_hashagg = off; SET random_page_cost = 4;

This takes the sort step of the index plan away from the planner and stands in for an instance whose statistics make the primary key plan look cheaper.

Probe, forced, 50 Maven pairs

Master This MR
Plan Parallel Index Scan using pm_affected_packages_pkey, VALUES as join filter Index Scan using index_pm_affected_packages_on_purl_type_and_package_name
Rows visited 4,008,425 (the whole table) 68
Buffers 275,012 218
Execution time 12,060 ms 0.5 ms

With the fence the planner has no other way to evaluate the join, so it keeps the index seeks even though the sort it needs for ORDER BY id LIMIT 1 is disabled (the 10000000000 in the cost is the disabled-node penalty).

Probe, master, forced 
 Limit  (cost=1000.45..8320.63 rows=1 width=8) (actual time=12050.418..12059.781 rows=1 loops=1)
   Buffers: shared hit=201153 read=73859
   ->  Unique  (cost=1000.45..2563060.71 rows=350 width=8) (actual time=12050.417..12059.780 rows=1 loops=1)
         Buffers: shared hit=201153 read=73859
         ->  Gather Merge  (cost=1000.45..2563059.84 rows=350 width=8) (actual time=12050.417..12059.779 rows=1 loops=1)
               Workers Planned: 2
               Workers Launched: 2
               Buffers: shared hit=201153 read=73859
               ->  Unique  (cost=0.43..2562019.42 rows=175 width=8) (actual time=44.385..8043.581 rows=22 loops=3)
                     Buffers: shared hit=201153 read=73859
                     ->  Nested Loop  (cost=0.43..2562018.98 rows=175 width=8) (actual time=44.385..8043.573 rows=22 loops=3)
                           Join Filter: ((pm_affected_packages.purl_type = "*VALUES*".column1) AND (pm_affected_packages.package_name = "*VALUES*".column2))
                           Rows Removed by Join Filter: 66807056
                           Buffers: shared hit=201153 read=73859
                           ->  Parallel Index Scan using pm_affected_packages_pkey on pm_affected_packages  (cost=0.43..264905.48 rows=1670628 width=25) (actual time=0.654..1428.428 rows=1336142 loops=3)
                                 Buffers: shared hit=201153 read=73859
                           ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.000..0.004 rows=50 loops=4008425)
 Planning Time: 3.935 ms
 Execution Time: 12059.862 ms
Probe, this MR, forced 
 Limit  (cost=10000003378.75..10000003379.00 rows=1 width=8) (actual time=0.276..0.276 rows=1 loops=1)
   Buffers: shared hit=218
   ->  Unique  (cost=10000003378.75..10000003386.25 rows=30 width=8) (actual time=0.276..0.276 rows=1 loops=1)
         Buffers: shared hit=218
         ->  Sort  (cost=10000003378.75..10000003382.50 rows=1500 width=8) (actual time=0.275..0.275 rows=1 loops=1)
               Sort Key: pm_affected_packages.id
               Sort Method: quicksort  Memory: 25kB
               Buffers: shared hit=218
               ->  Nested Loop  (cost=0.43..3299.62 rows=1500 width=8) (actual time=0.034..0.270 rows=68 loops=1)
                     Buffers: shared hit=218
                     ->  Values Scan on "*VALUES*"  (cost=0.00..0.62 rows=50 width=36) (actual time=0.000..0.005 rows=50 loops=1)
                     ->  Index Scan using index_pm_affected_packages_on_purl_type_and_package_name on pm_affected_packages  (cost=0.43..65.38 rows=30 width=258) (actual time=0.004..0.005 rows=1 loops=50)
                           Index Cond: ((purl_type = "*VALUES*".column1) AND (package_name = "*VALUES*".column2))
                           Buffers: shared hit=218
 Planning Time: 0.092 ms
 Execution Time: 0.501 ms

End to end: a 72 component Maven SBOM through SecurityReportBuilder

Run with bin/rails runner against the same database, once with the GDK defaults ("natural") and once with the settings above applied on the connection ("forced"). Queries were recorded with an sql.active_record subscriber.

Master This MR
Natural plan, total 185 ms 144 ms
Forced primary key plan, total 22,572 ms 26 ms
Forced, slowest queries 7,583 / 7,569 / 5,097 / 2,284 ms (the each_batch probes) 3.5 ms
Findings 2 2

Heavy slice through each_batch

A slice with linux, openssl and glibc (purl type deb), 152,705 matching rows, iterated with for_occurrences(...).with_advisory.each_batch. Single runs, GDK defaults.

Master This MR
Batches 153 153
Largest batch 1,000 rows 1,000 rows
Total time 13.8 s 16.5 s

Batching is unchanged by the fence. The extra time comes from the id >= X filter being applied outside the fenced subquery, so each batch re-reads the matched rows before filtering; it is per heavy name and bounded, unlike the full table scan.

References

Screenshots or screen recordings

Not applicable.

How to set up and validate locally

  1. Load the advisory dataset into pm_affected_packages: with PM_SYNC_IN_DEV=true, run bin/rails runner 'PackageMetadata::AdvisoriesSyncWorker.new.perform' repeatedly until the row count stops growing (each run is capped at a few minutes).

  2. In gdk psql, take the index plan away from the planner and run the "Probe, master" query with 50 (purl_type, name) pairs that exist in the table:

    SET enable_sort = off; SET enable_hashagg = off; SET random_page_cost = 4;
EXPLAIN WITH occurrences_cte(purl_type, name) AS (VALUES ...) SELECT DISTINCT ...;

    The plan is a Parallel Index Scan using pm_affected_packages_pkey under a Nested Loop with the VALUES list as a join filter.

  3. Run the "Probe, this MR" query with the same settings. The plan is a Nested Loop over index_pm_affected_packages_on_purl_type_and_package_name.

MR acceptance checklist

Evaluate this MR against the MR acceptance checklist. It helps you analyze changes to reduce risks in quality, performance, reliability, security, and maintainability.

Edited by Bala Kumar

Merge request reports