Store SBOM reachability on occurrence refs

Ryan Wellsrequested to merge
feature/sbom-occurrence-ref-reachability into master

What does this MR do and why?

This MR adds a reachability column (smallint, nullable, no default) to sbom_occurrence_refs and updates the ingestion layer to write branch-specific reachability values. The column uses the same enum values as sbom_occurrences.reachability. NULL means ingestion has not written this ref yet. That is different from unknown (0), which is a real value.

Reachability (in_use, not_found, or unknown) indicates whether a dependency is actually used by the code. Previously, reachability was stored only on the shared sbom_occurrences row, so a pipeline on one branch would overwrite the value from another branch. With multiple tracked branches per project, the same dependency could report different reachability on different branches, and whichever branch's pipeline ran last would win for everyone.

This MR (the first of a two-MR series) fixes the data model and ingestion. The follow-up MR updates the API/GraphQL layer to read from the new column. Those reads fall back to sbom_occurrences.reachability when a ref has no value yet, so the follow-up does not have to wait for the backfill. There is no user-visible change on its own: GraphQL and REST still read the old column on sbom_occurrences until the follow-up MR lands.

Database

The new column reachability is added to the sbom_occurrence_refs table on the gitlab_sec database. The table is medium-sized. Adding a nullable column with no default is a metadata-only change in PostgreSQL, so there is no table rewrite.

A batched background migration (BackfillSbomOccurrenceRefsReachability) copies existing reachability values from sbom_occurrences onto each occurrence's refs. It only updates refs whose reachability is NULL, and it copies the occurrence value when that value is not NULL (including unknown). A value that ingestion writes after deploy, even unknown, is never overwritten. The backfill is still worth running: once every ref has a value, the read fallback can be removed, and later the sbom_occurrences.reachability column too. Because the copied value belongs to whichever branch's pipeline ran last, a non-default branch's backfilled value can be incorrect until that branch's next pipeline runs and overwrites it. The migration batches over sbom_occurrence_refs.id with a batch size of 10,000 and sub-batch size of 1,000. Per sub-batch, it runs:

UPDATE sbom_occurrence_refs
SET reachability = sbom_occurrences.reachability
FROM sbom_occurrences
WHERE sbom_occurrences.id = sbom_occurrence_refs.sbom_occurrence_id
  AND sbom_occurrence_refs.id IN (<sub-batch ids>)
  AND sbom_occurrence_refs.reachability IS NULL
  AND sbom_occurrences.reachability IS NOT NULL

The ingestion layer now writes reachability per branch. It adds reachability to an existing pluck query (bounded by the ingestion batch size):

SELECT sbom_occurrence_id, reachability
FROM sbom_occurrence_refs
WHERE security_project_tracked_context_id = ?
  AND sbom_occurrence_id IN (...)

Additionally, ingestion now rewrites a ref when only its reachability has changed. Previously, existing refs were skipped unless the occurrence itself changed, which would have left refs stuck on their old value. Refs rewritten this way are reindexed in Elasticsearch. Expect a one-time wave of these after deploy: every existing ref starts as NULL, so the first pipeline that reports on it writes its value once. After that, a ref is only rewritten when its value actually changes.

The Elasticsearch document still reads reachability from the occurrence in this MR. The follow-up switches it to the ref, with the same fallback to the occurrence value.

sbom_occurrences.reachability is still being written, because Siphon replicates it to ClickHouse, and the follow-up reads it as the fallback for refs without a value. Removing that column is future work, once the backfill has filled every ref.

The database testing pipeline already ran the migrations on gitlab.com data, but that run was for the earlier NOT NULL version of the column. It is running again on the current head (job 16942100271).

Query plans

Captured on Database Lab (gitlab-production-sec, Joe session webui-i60687) at MR head 9e57d9c5dc77b3beb7120da4eee4bc3c52aeed30. The reachability column does not exist in production yet, so I added it on the clone first with ALTER TABLE sbom_occurrence_refs ADD COLUMN IF NOT EXISTS reachability smallint (command 510176). On the clone every ref therefore starts as NULL. That matches the state right after the regular migration runs.

Table stats

Stat Value Source
count(*) of sbom_occurrence_refs ~118,715,444 (39,571,814.67 rows x 3 parallel loops) Joe 510182 (18.2 s)
reltuples 118,511,736 Joe 510180
min(id) / max(id) 4,075,130,908 / 4,738,478,865 Joe 510180
Refs whose occurrence has reachability IS NOT NULL 118,110 of 118,110 in a 0.1% TABLESAMPLE SYSTEM sample (100%) Joe 510222

sbom_occurrences.reachability is smallint DEFAULT 0. It is nullable, but the sample found no occurrence with a NULL value. So I expect the backfill to update nearly every row in the table (~118.7M rows). Refs that ingestion writes first are skipped.

1. Backfill sub-batch UPDATE

BackfillSbomOccurrenceRefsReachability declares cursor :id, so it is a cursor-based migration. Each batch is the next 10,000 real rows by id. Inside a batch, the first sub-batch takes the first 1,000 ids from the batch start. Later sub-batches use a keyset bound on the last id of the previous sub-batch. The IN (...) is the sub_batch.select(:id) subquery.

I took a real batch from the middle of the table. It starts at id 4400001543 and its 10,000th row is 4400042891. This is the SQL for its first sub-batch:

UPDATE sbom_occurrence_refs
SET reachability = sbom_occurrences.reachability
FROM sbom_occurrences
WHERE sbom_occurrences.id = sbom_occurrence_refs.sbom_occurrence_id
  AND sbom_occurrence_refs.id IN (SELECT "sbom_occurrence_refs"."id" FROM "sbom_occurrence_refs" WHERE ("sbom_occurrence_refs"."id") <= (4400042891) AND ("sbom_occurrence_refs"."id") >= (4400001543) ORDER BY "sbom_occurrence_refs"."id" ASC LIMIT 1000)
  AND sbom_occurrence_refs.reachability IS NULL
  AND sbom_occurrences.reachability IS NOT NULL

Later sub-batches in the same batch keep the <= (4400042891) bound and replace >= (4400001543) with "sbom_occurrence_refs"."id" > <last id of the previous sub-batch>.

All 1,000 rows in this sub-batch matched and were updated. Joe runs EXPLAIN ANALYZE inside a transaction that is rolled back, so the warm run updated the same 1,000 rows again.

First sub-batch, cold run (Joe 510492): 630.3 ms total, 540.2 ms execution, 1,000 rows 
 Update on public.sbom_occurrence_refs  (cost=43.40..3650.24 rows=0 width=0) (actual time=538.012..538.015 rows=0 loops=1)
   Buffers: shared hit=36037 read=585 dirtied=98 written=12
   WAL: records=6879 fpi=86 bytes=1103702
   I/O Timings: read=466.630 write=0.505
   ->  Nested Loop  (cost=43.40..3650.24 rows=5 width=46) (actual time=13.007..295.147 rows=1000 loops=1)
         Buffers: shared hit=10751 read=410 dirtied=1
         WAL: records=160 fpi=1 bytes=16603
         I/O Timings: read=272.523 write=0.000
         ->  Nested Loop  (cost=42.84..3635.78 rows=5 width=46) (actual time=4.808..13.231 rows=1000 loops=1)
               Buffers: shared hit=6161 dirtied=1
               WAL: records=160 fpi=1 bytes=16603
               I/O Timings: read=0.000 write=0.000
               ->  HashAggregate  (cost=42.27..52.27 rows=1000 width=40) (actual time=4.771..5.658 rows=1000 loops=1)
                     Group Key: "ANY_subquery".id
                     Batches: 1  Memory Usage: 121kB
                     Buffers: shared hit=1161 dirtied=1
                     WAL: records=160 fpi=1 bytes=16603
                     I/O Timings: read=0.000 write=0.000
                     ->  Subquery Scan on "ANY_subquery"  (cost=0.57..39.77 rows=1000 width=40) (actual time=0.060..4.377 rows=1000 loops=1)
                           Buffers: shared hit=1161 dirtied=1
                           WAL: records=160 fpi=1 bytes=16603
                           I/O Timings: read=0.000 write=0.000
                           ->  Limit  (cost=0.57..29.77 rows=1000 width=8) (actual time=0.044..4.098 rows=1000 loops=1)
                                 Buffers: shared hit=1161 dirtied=1
                                 WAL: records=160 fpi=1 bytes=16603
                                 I/O Timings: read=0.000 write=0.000
                                 ->  Index Only Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs sbom_occurrence_refs_1  (cost=0.57..86.74 rows=2951 width=8) (actual time=0.042..3.985 rows=1000 loops=1)
                                       Index Cond: ((sbom_occurrence_refs_1.id <= '4400042891'::bigint) AND (sbom_occurrence_refs_1.id >= '4400001543'::bigint))
                                       Heap Fetches: 1145
                                       Index Searches: 1
                                       Buffers: shared hit=1161 dirtied=1
                                       WAL: records=160 fpi=1 bytes=16603
                                       I/O Timings: read=0.000 write=0.000
               ->  Index Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs  (cost=0.57..3.58 rows=1 width=22) (actual time=0.007..0.007 rows=1 loops=1000)
                     Index Cond: (sbom_occurrence_refs.id = "ANY_subquery".id)
                     Index Searches: 1000
                     Filter: (sbom_occurrence_refs.reachability IS NULL)
                     Buffers: shared hit=5000
                     I/O Timings: read=0.000 write=0.000
         ->  Index Scan using sbom_occurrences_pkey on public.sbom_occurrences  (cost=0.57..2.89 rows=1 width=16) (actual time=0.281..0.281 rows=1 loops=1000)
               Index Cond: (sbom_occurrences.id = sbom_occurrence_refs.sbom_occurrence_id)
               Index Searches: 1000
               Filter: (sbom_occurrences.reachability IS NOT NULL)
               Buffers: shared hit=4590 read=410
               I/O Timings: read=272.523 write=0.000
Settings: random_page_cost = '1.5', seq_page_cost = '4', effective_cache_size = '338688MB', jit = 'off', work_mem = '100MB'
Query ID: 2320780336777100776


stats:

Time: 630.265 ms
  - planning: 90.050 ms
  - execution: 540.215 ms
    - I/O read: 466.630 ms
    - I/O write: 0.505 ms
First sub-batch, warm run (Joe 510494): 56.2 ms total, 48.9 ms execution, 1,000 rows 
 Update on public.sbom_occurrence_refs  (cost=43.40..3650.24 rows=0 width=0) (actual time=48.508..48.511 rows=0 loops=1)
   Buffers: shared hit=39649 read=11 dirtied=16 written=12
   WAL: records=6923 fpi=3 bytes=559553
   I/O Timings: read=4.994 write=0.469
   ->  Nested Loop  (cost=43.40..3650.24 rows=5 width=46) (actual time=7.063..16.320 rows=1000 loops=1)
         Buffers: shared hit=13530
         WAL: records=159 fpi=0 bytes=8334
         I/O Timings: read=0.000 write=0.000
         ->  Nested Loop  (cost=42.84..3635.78 rows=5 width=46) (actual time=7.018..11.611 rows=1000 loops=1)
               Buffers: shared hit=8530
               WAL: records=159 fpi=0 bytes=8334
               I/O Timings: read=0.000 write=0.000
               ->  HashAggregate  (cost=42.27..52.27 rows=1000 width=40) (actual time=6.939..7.260 rows=1000 loops=1)
                     Group Key: "ANY_subquery".id
                     Batches: 1  Memory Usage: 121kB
                     Buffers: shared hit=3530
                     WAL: records=159 fpi=0 bytes=8334
                     I/O Timings: read=0.000 write=0.000
                     ->  Subquery Scan on "ANY_subquery"  (cost=0.57..39.77 rows=1000 width=40) (actual time=0.086..6.316 rows=1000 loops=1)
                           Buffers: shared hit=3530
                           WAL: records=159 fpi=0 bytes=8334
                           I/O Timings: read=0.000 write=0.000
                           ->  Limit  (cost=0.57..29.77 rows=1000 width=8) (actual time=0.072..5.997 rows=1000 loops=1)
                                 Buffers: shared hit=3530
                                 WAL: records=159 fpi=0 bytes=8334
                                 I/O Timings: read=0.000 write=0.000
                                 ->  Index Only Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs sbom_occurrence_refs_1  (cost=0.57..86.74 rows=2951 width=8) (actual time=0.070..5.867 rows=1000 loops=1)
                                       Index Cond: ((sbom_occurrence_refs_1.id <= '4400042891'::bigint) AND (sbom_occurrence_refs_1.id >= '4400001543'::bigint))
                                       Heap Fetches: 1912
                                       Index Searches: 1
                                       Buffers: shared hit=3530
                                       WAL: records=159 fpi=0 bytes=8334
                                       I/O Timings: read=0.000 write=0.000
               ->  Index Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs  (cost=0.57..3.58 rows=1 width=22) (actual time=0.004..0.004 rows=1 loops=1000)
                     Index Cond: (sbom_occurrence_refs.id = "ANY_subquery".id)
                     Index Searches: 1000
                     Filter: (sbom_occurrence_refs.reachability IS NULL)
                     Buffers: shared hit=5000
                     I/O Timings: read=0.000 write=0.000
         ->  Index Scan using sbom_occurrences_pkey on public.sbom_occurrences  (cost=0.57..2.89 rows=1 width=16) (actual time=0.004..0.004 rows=1 loops=1000)
               Index Cond: (sbom_occurrences.id = sbom_occurrence_refs.sbom_occurrence_id)
               Index Searches: 1000
               Filter: (sbom_occurrences.reachability IS NOT NULL)
               Buffers: shared hit=5000
               I/O Timings: read=0.000 write=0.000
Settings: random_page_cost = '1.5', seq_page_cost = '4', effective_cache_size = '338688MB', jit = 'off', work_mem = '100MB'
Query ID: 2320780336777100776


stats:

Time: 56.248 ms
  - planning: 7.341 ms
  - execution: 48.907 ms
    - I/O read: 4.994 ms
    - I/O write: 0.469 ms
Later sub-batch (`id > 4400021716`), warm run (Joe 510498): 38.7 ms total, 34.3 ms execution, 1,000 rows. The cold run (Joe 510496) took 600.1 ms total. 
 Update on public.sbom_occurrence_refs  (cost=43.68..3650.52 rows=0 width=0) (actual time=33.946..33.949 rows=0 loops=1)
   Buffers: shared hit=40448 dirtied=13 written=13
   WAL: records=7147 fpi=0 bytes=551916
   I/O Timings: read=0.000 write=0.551
   ->  Nested Loop  (cost=43.68..3650.52 rows=5 width=46) (actual time=5.993..13.831 rows=1000 loops=1)
         Buffers: shared hit=13515
         WAL: records=146 fpi=0 bytes=7626
         I/O Timings: read=0.000 write=0.000
         ->  Nested Loop  (cost=43.12..3636.06 rows=5 width=46) (actual time=5.966..9.770 rows=1000 loops=1)
               Buffers: shared hit=8515
               WAL: records=146 fpi=0 bytes=7626
               I/O Timings: read=0.000 write=0.000
               ->  HashAggregate  (cost=42.55..52.55 rows=1000 width=40) (actual time=5.919..6.192 rows=1000 loops=1)
                     Group Key: "ANY_subquery".id
                     Batches: 1  Memory Usage: 121kB
                     Buffers: shared hit=3515
                     WAL: records=146 fpi=0 bytes=7626
                     I/O Timings: read=0.000 write=0.000
                     ->  Subquery Scan on "ANY_subquery"  (cost=0.57..40.05 rows=1000 width=40) (actual time=0.131..5.576 rows=1000 loops=1)
                           Buffers: shared hit=3515
                           WAL: records=146 fpi=0 bytes=7626
                           I/O Timings: read=0.000 write=0.000
                           ->  Limit  (cost=0.57..30.05 rows=1000 width=8) (actual time=0.093..5.340 rows=1000 loops=1)
                                 Buffers: shared hit=3515
                                 WAL: records=146 fpi=0 bytes=7626
                                 I/O Timings: read=0.000 write=0.000
                                 ->  Index Only Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs sbom_occurrence_refs_1  (cost=0.57..45.11 rows=1511 width=8) (actual time=0.092..5.259 rows=1000 loops=1)
                                       Index Cond: ((sbom_occurrence_refs_1.id <= '4400042891'::bigint) AND (sbom_occurrence_refs_1.id > '4400021716'::bigint))
                                       Heap Fetches: 1836
                                       Index Searches: 1
                                       Buffers: shared hit=3515
                                       WAL: records=146 fpi=0 bytes=7626
                                       I/O Timings: read=0.000 write=0.000
               ->  Index Scan using sbom_occurrence_refs_pkey on public.sbom_occurrence_refs  (cost=0.57..3.58 rows=1 width=22) (actual time=0.003..0.003 rows=1 loops=1000)
                     Index Cond: (sbom_occurrence_refs.id = "ANY_subquery".id)
                     Index Searches: 1000
                     Filter: (sbom_occurrence_refs.reachability IS NULL)
                     Buffers: shared hit=5000
                     I/O Timings: read=0.000 write=0.000
         ->  Index Scan using sbom_occurrences_pkey on public.sbom_occurrences  (cost=0.57..2.89 rows=1 width=16) (actual time=0.004..0.004 rows=1 loops=1000)
               Index Cond: (sbom_occurrences.id = sbom_occurrence_refs.sbom_occurrence_id)
               Index Searches: 1000
               Filter: (sbom_occurrences.reachability IS NOT NULL)
               Buffers: shared hit=5000
               I/O Timings: read=0.000 write=0.000
Settings: random_page_cost = '1.5', seq_page_cost = '4', effective_cache_size = '338688MB', jit = 'off', work_mem = '100MB'
Query ID: -8528316475832965448


stats:

Time: 38.656 ms
  - planning: 4.406 ms
  - execution: 34.250 ms
    - I/O read: 0.000 ms
    - I/O write: 0.551 ms

2. Ingestion pluck (existing_ref_reachabilities)

IngestReportService::BATCH_SIZE is 10, so each slice plucks at most 10 occurrence ids for one tracked context. I used gitlab-org/gitlab (project 278964), tracked context 2176366 (master, the default branch, 7,962 refs), and 10 real occurrence ids that already have refs on that context.

SELECT "sbom_occurrence_refs"."sbom_occurrence_id", "sbom_occurrence_refs"."reachability" FROM "sbom_occurrence_refs" WHERE "sbom_occurrence_refs"."security_project_tracked_context_id" = 2176366 AND "sbom_occurrence_refs"."sbom_occurrence_id" IN (6729589929, 6838111772, 6838111773, 6729589930, 6729589931, 6729589932, 6729589933, 6729589934, 6729589936, 6735613878)
Cold run (Joe 510216): 14.3 ms total, 8.0 ms execution, 10 rows 
 Index Scan using idx_sbom_occurrence_refs_on_sbom_occ_id_and_tracked_context_id on public.sbom_occurrence_refs  (cost=0.57..22.29 rows=1 width=10) (actual time=3.144..7.961 rows=10 loops=1)
   Index Cond: ((sbom_occurrence_refs.sbom_occurrence_id = ANY ('{6729589929,6838111772,6838111773,6729589930,6729589931,6729589932,6729589933,6729589934,6729589936,6735613878}'::bigint[])) AND (sbom_occurrence_refs.security_project_tracked_context_id = 2176366))
   Index Searches: 4
   Buffers: shared hit=17 read=19 dirtied=3
   WAL: records=3 fpi=3 bytes=19823
   I/O Timings: read=7.711 write=0.000
Settings: seq_page_cost = '4', effective_cache_size = '338688MB', jit = 'off', work_mem = '100MB', random_page_cost = '1.5'
Query ID: -6664555556868854797
Time: 14.342 ms
  - planning: 6.320 ms
  - execution: 8.022 ms
    - I/O read: 7.711 ms
    - I/O write: 0.000 ms

Shared buffers:
  - hits: 17 (~136.00 KiB) from the buffer pool
  - reads: 19 (~152.00 KiB) from the OS file cache, including disk I/O
  - dirtied: 3 (~24.00 KiB)
  - writes: 0
Warm run (Joe 510220): 15.2 ms total, 2.5 ms execution, 10 rows 
 Index Scan using idx_sbom_occurrence_refs_on_sbom_occ_id_and_tracked_context_id on public.sbom_occurrence_refs  (cost=0.57..22.29 rows=1 width=10) (actual time=1.008..2.433 rows=10 loops=1)
   Index Cond: ((sbom_occurrence_refs.sbom_occurrence_id = ANY ('{6729589929,6838111772,6838111773,6729589930,6729589931,6729589932,6729589933,6729589934,6729589936,6735613878}'::bigint[])) AND (sbom_occurrence_refs.security_project_tracked_context_id = 2176366))
   Index Searches: 4
   Buffers: shared hit=12 read=17
   I/O Timings: read=2.249 write=0.000
Settings: effective_cache_size = '338688MB', jit = 'off', work_mem = '100MB', random_page_cost = '1.5', seq_page_cost = '4'
Query ID: -6664555556868854797
Time: 15.162 ms
  - planning: 12.652 ms
  - execution: 2.510 ms
    - I/O read: 2.249 ms
    - I/O write: 0.000 ms

Shared buffers:
  - hits: 12 (~96.00 KiB) from the buffer pool
  - reads: 17 (~136.00 KiB) from the OS file cache, including disk I/O
  - dirtied: 0
  - writes: 0

The pluck uses the existing unique index idx_sbom_occurrence_refs_on_sbom_occ_id_and_tracked_context_id, so no new index is needed.

Summary

Query Cold Warm Buffers (warm) Rows
Backfill first sub-batch UPDATE (1,000 ids) 630.3 ms (540.2 ms exec) 56.2 ms (48.9 ms exec) 39,649 hit (~309.8 MiB) / 11 read (~88 KiB) / 16 dirtied (~128 KiB) 1,000
Backfill later sub-batch UPDATE (1,000 ids) 600.1 ms (595.8 ms exec) 38.7 ms (34.3 ms exec) 40,448 hit (~316.0 MiB) / 0 read / 13 dirtied (~104 KiB) 1,000
Ingestion pluck (10 ids, 1 tracked context) 14.3 ms (8.0 ms exec) 15.2 ms (2.5 ms exec) 12 hit (~96 KiB) / 17 read (~136 KiB) 10

Backfill duration estimate

  • The batching strategy walks real rows on id, so the number of batches follows the row count, not the id range. That gives ~118.7M / 10,000 = ~11,872 batches.
  • The queue migration doesn't set job_interval, so it uses the default of 2 minutes. At the starting batch size that is 11,872 x 2 min = ~23,744 min, or about 16.5 days.
  • Each job runs 10 sub-batches at 0.04 to 0.6 s each (warm to cold), plus the default 100 ms pause after each sub-batch. That is about 1.5 to 7 s per job, a small share of the 2-minute interval.
  • We accept 16.5 days as the upper bound. Jobs use only a few seconds of each interval, so the batch optimizer will raise the batch size (by up to 1.2x per adjustment) and the run should finish sooner. The sub-batch size stays at 1,000, so the per-query cost above does not change.

References

No issue is linked yet.

Follow-up (switches the API read side to the new column, with a fallback to the occurrence value): !258539 (merged)

Screenshots or screen recordings

Not applicable — this MR has no UI changes. It is a data model and ingestion change only.

How to set up and validate locally

  1. Run bundle exec rails db:migrate to apply the new column and start the background migration.
  2. Run a dependency scanning pipeline with reachability enabled on two different tracked branches, where both branches report a different reachability value for the same package.
  3. In a Rails console, check that Sbom::OccurrenceRef.where(sbom_occurrence_id: <id>).pluck(:security_project_tracked_context_id, :reachability) shows a different value per branch. Re-run one branch's pipeline and confirm that branch's value stays put; the other branch's value should remain unchanged.

Relevant specs:

  • ee/spec/services/sbom/ingestion/tasks/ingest_occurrence_refs_spec.rb
  • spec/lib/gitlab/background_migration/backfill_sbom_occurrence_refs_reachability_spec.rb

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.

🤖 Generated with Claude Code

Edited by Gregory Havenga

Merge request reports