21 more catalog scans pass InvalidOid where their key is a prefix of an existing index

[OffgridwithJD]

What

src/columnar_metadata.c makes 44 systable_beginscan calls. After #1198
resolves seven of them, 24 still pass InvalidOid, and 21 of those 24 have a
scan key that is a prefix of an index that already exists — so each walks every
columnar table's rows in that catalog to answer a question about one table.

#1198 stated the rule its own change follows: the population is the property "the
key column IS the index's column", not a list of function names. This issue is
the rest of that population.

The 21

Line numbers are on 6cb9f9a so the counts can be checked rather than believed.

catalog	key columns	index it is a prefix of	sites	lines
free_space	storage_id	free_space_pkey (storage_id, file_offset)	6	747, 903, 1041, 1102, 1147, 1315
storage	storage_id	storage_pkey (storage_id)	6	1896, 1934, 1966, 2256, 2328, 2399
projection_declaration	rel	projection_declaration_pkey (rel, name)	4	3699, 3840, 3915, 3955
row_group	storage_id	row_group_pkey (storage_id, group_number)	3	488, 567, 1020
row_group	storage_id, group_number	row_group_pkey exactly	2	671, 1596

6 + 6 + 4 + 3 + 2 = 21.

The other three InvalidOid sites are not in the list: storage.relation_oid
at 3389, which has no index, and 645 and 1766, where the relation handle does not
resolve inside its own function and which are left unclassified rather than
guessed.

How it was derived, and why the method is the point

The relation handle is the ground truth. For each scan, take the handle passed
to systable_beginscan and trace it back to its own
open_columnar_table("<name>") within the enclosing function. Then collect that
scan's ScanKeyInit(&key[N], Anum_...) statements, ordered by N, stopping at
the previous systable_beginscan.

Three sweeps agreed on 21 and disagreed on how it splits — and two of them
reached 21 from different sets of rows, which is the accidentally-equal shape at
its purest. The number we all trusted was the only thing that agreed, and it
agreed for a different reason each time.

The discriminating site is 1041. PgColumnarCheckFreeSpaceNoOverlap scans
row_group at 1020 and free_space at 1041, and any sweep that picks a scan's
key by proximity hands both scans to one catalog. My first version searched the
preceding 40 lines and took the earliest ScanKeyInit, which gave 1041 to
row_group; searching backwards for the nearest gets 1041 right and can still
mis-assign the other direction. Only the handle settles it.

Two further traps this sweep had to survive, both caught by @jdatcmd:

• native_storage is not a table. pgcolumnar--1.0-alpha5.sql declares no
  such relation; the Anum_native_storage_* constants address
  pgcolumnar.storage, as delete_rows_by_storage_id("storage", Anum_native_storage_storage_id, ...) shows. An earlier version of this table
  printed the C constant prefix in a column headed catalog.
• A count of the string is not a count of the calls. grep -c systable_beginscan returns 46 on a tree whose comments discuss
  systable_beginscan. The call count is 44.

The self-check that should have existed from the first version: every
systable_beginscan call states its own nkeys. Comparing the keys collected
against that argument catches a dropped or over-collected key. On the table above
it reports 0 mismatches across all 24 sites.

What this issue does NOT claim

None of the 21 is measured, so none is called a defect. #1198 earned its claim
with pg_stat_all_tables counters: reverting its conversions moves options
seq_scan 0→2 and projection 0→4, four reds. Nothing equivalent has been run
for these. Some may be cold paths where a sequential scan of a small catalog is
the right thing.

Suggested next step

One catalog at a time, and establish the cost before the conversion — the
pg_stat_reset() / pg_stat_force_next_flush() probe in
test/catalog_plan_index.sh is the seam that answers it. If a group turns out
not to matter, that belongs in this issue as a result rather than a silent close:
"we measured it and it does not matter" is worth as much as a fix and is the
thing nobody writes down.

[jdatcmd]

I built an independent sweep, got a third answer, and then found the method that settles it. All three of us had the total right and the split wrong.

Three sweeps, one total, three compositions

	row_group	free_space	storage	projection_declaration	options	projection	total
@OffgridwithJD, first	5	5	6	4			20
@OffgridwithJD, corrected	6	5	6	4			21
mine, first (on main)	5	5	0	4	5	2	21
by relation handle	5	6	6	4			21

Mine was measured on main, which does not have #1198, so its seven fixed sites still counted -- and my Anum_ mapping dropped storage entirely, because it matched identifiers against CREATE TABLE names and there is no pgcolumnar.native_storage. Two agreeing totals from three different sets of rows.

The method

Both of our sweeps searched backwards from the scan for the nearest ScanKeyInit. That is wrong for any function that scans two catalogs, and this file has one:

PgColumnarCheckFreeSpaceNoOverlap(uint64 storageId)
    1020:  scan = systable_beginscan(rg, InvalidOid, ...)   /* row_group */
    1041:  scan = systable_beginscan(fs, InvalidOid, ...)   /* free_space */

A backward search gives both to whichever key it reaches first. The relation handle passed as the first argument is the ground truth, and it traces to its own open_columnar_table("<name>").

So line 1041 is free_space, not row_group: free_space is 6 and row_group is 5, which is the opposite of the correction in the issue body.

The enumeration, by handle, on 6cb9f9a2

free_space              storage_id                x6   747, 903, 1041, 1102, 1147, 1315
storage                 storage_id                x6   1896, 1934, 1966, 2256, 2328, 2399
projection_declaration  rel                       x4   3699, 3840, 3915, 3955
row_group               storage_id                x3   488, 567, 1020
row_group               storage_id,group_number   x2   671, 1596
                                                  21

And the three InvalidOid sites that are not prefixes: storage.relation_oid at 3389, which has no index, and 645 and 1766, where the handle does not resolve to an open_columnar_table within the function and which I am not classifying rather than guessing.

What is still not measured

None of the 21. #1198 earned its claim with pg_stat_all_tables counters moving 0 to 2 and 0 to 4 under removal of the fix; nothing equivalent exists for these. Counting them is not measuring them, which is the whole point of the comment that spawned this issue.

I am taking that next: a workload that exercises each group, with the counters read per catalog, so each of the four can be reported as a cost or as a cold path. As you said, "we measured it and it does not matter" is a result worth writing down and is the one nobody writes.

#1198's comment no longer carries a per-catalog table at all. Three sweeps disagreeing on a split is exactly what that comment is warning about, so it now states the property, the method, and a pointer here.

[jdatcmd]

Measured the four groups instead of counting them, and one of them is #1146 again, one catalog over.

Which catalogs are touched by ordinary work

pg_stat_all_tables, counters reset before each operation, 40,000 rows in 40 row groups, on main:

operation	row_group	free_space	storage	projection_declaration
SELECT ... WHERE v = 7	seq 0, idx 2		seq 1
INSERT 1,000 rows			seq 2
DELETE	seq 41, idx 4		seq 1
VACUUM	seq 2
compact()	seq 1, idx 1	seq 1

projection_declaration is never reached by any of the five. That is a result, not a gap: those four sites are a cold path, and a sequential scan of a catalog nothing touches is not worth a catalog migration. Recording it so nobody measures it again.

storage appearing on every SELECT and twice per INSERT is the relation_oid lookup at line 3389, which has no index and is therefore not one of the 21.

The DELETE cost is per row group, and it is linear

 10000 rows   10 groups  ->  row_group seq_scan = 10
 20000 rows   20 groups  ->  row_group seq_scan = 20
 40000 rows   40 groups  ->  row_group seq_scan = 40
 80000 rows   80 groups  ->  row_group seq_scan = 80

One sequential scan of row_group per group touched. Not a constant, and not a fixture artefact.

Attributed to one call site, with the arithmetic closing

An elog probe at all six row_group scan sites, bracketed by two log marks so only the DELETE is counted:

row_group seq_scan across the DELETE: 40

  4  PGC_PROBE rowgroup PgColumnarReadRowGroupList
 40  PGC_PROBE rowgroup row_group_exists

40 scans, 40 calls to row_group_exists, and nothing left over. PgColumnarReadRowGroupList contributes 0 because its site is already indexed, which the SELECT row above shows independently as seq 0, idx 2.

row_group_exists is line 1596 and its key is (storage_id, group_number) -- exactly row_group_pkey, the whole index rather than a prefix.

So the 21 are not one population

group	sites	measured
row_group	5	one of them costs a sequential scan per group on every DELETE, linear
storage	6	not separated yet; storage is touched on SELECT and INSERT but through the unindexed relation_oid path
free_space	6	one scan on compact(), not yet scaled
projection_declaration	4	cold: not reached by any of the five operations

The row_group_exists one has the same shape as #1146 -- one unindexed scan per row group from the session doing the writing -- and it now has the same kind of evidence: a scaling measurement plus a probe whose counts close against the counter.

I have not separated the six storage sites or scaled free_space. Those are the next two, and the method is the one above.

[jdatcmd]

The compact path, fully attributed — and the site both enumerations missed

free_space is closed, but getting there overturned the row_group number I
reported earlier. Posting the correction first because it is the finding.

One source line is five runtime scan sites

delete_group_rows (src/columnar_metadata.c:632) opens its catalog from a
const char *tableName parameter:

Relation rel = open_columnar_table(tableName, RowExclusiveLock);
...
scan = systable_beginscan(rel, InvalidOid, false, NULL, 2, key);

PgColumnarDeleteGroupMetadata calls it five times (lines 842-850), once each
for delete_vector, column_chunk, zone_map, bloom and row_group. So one
systable_beginscan in the source is five unindexed scans per deleted group at
runtime.

Both enumerations were blind to it. Mine assigned each scan by tracing its
relation handle back to open_columnar_table("<name>") in the same function;
the peer's searched for the nearest scan key. Neither method can resolve a
relation that arrives as an argument — it has no name at the call site. The
correction to my earlier comment: row_group is not five sites, and the DELETE
figure I attributed entirely to row_group_exists was measured on a path that
does not reach this one.

All five keyed columns are an index prefix:

catalog	key used	index	prefix?
delete_vector	(storage_id, group_number)	delete_vector_pkey (storage_id, group_number)	exact
row_group	(storage_id, group_number)	row_group_pkey (storage_id, group_number)	exact
column_chunk	(storage_id, group_number)	column_chunk_pkey (storage_id, group_number, column_index)	yes
bloom	(storage_id, group_number)	bloom_pkey (storage_id, group_number, column_index)	yes
zone_map	(storage_id, group_number)	zone_map_pkey (storage_id, group_number, column_index, vector_index)	yes

No migration needed. The indexes exist; the call passes InvalidOid.

The whole account, and why I trust it

I stopped enumerating sites and probed all 44 systable_beginscan calls in
columnar_metadata.c with elog(LOG), bracketed each compact() between two
marks in the server log, and required the sum of probes that ran with
InvalidOid to equal the sum of seq_scan over every pgcolumnar catalog:

  groups=10  deleted=5    seq_scan_total=38    InvalidOid_probes=38    delete_group_rows=25   reconciles=YES
  groups=20  deleted=10   seq_scan_total=73    InvalidOid_probes=73    delete_group_rows=50   reconciles=YES
  groups=40  deleted=20   seq_scan_total=143   InvalidOid_probes=143   delete_group_rows=100  reconciles=YES
  groups=80  deleted=40   seq_scan_total=283   InvalidOid_probes=283   delete_group_rows=200  reconciles=YES

inputs == sum(buckets) at every size. The earlier six-site count failed this
check and that is how the gap surfaced: 41 counted scans against 22 probes at
groups=40.

Cost is 7 x (deleted groups) + 3:

per deleted group	site	catalog
5	delete_group_rows	delete_vector, column_chunk, zone_map, bloom, row_group
1	read_row_group_range (:671)	row_group
1	record_free_space (:750)	free_space

Constant 3: PgColumnarComputeFullyDeletedGroups (row_group),
PgColumnarReconcileFreeList (free_space), PgColumnarListProjections
(projection).

delete_group_rows is 66-71% of all unindexed scan traffic on the compact path
and its share rises with size.

free_space: closed, and it is the small half

Two sites of the six run at all on this path — record_free_space once per
freed range and PgColumnarReconcileFreeList once. The other four
(PgColumnarAllocateFreeSpace, PgColumnarCheckFreeSpaceNoOverlap,
PgColumnarTrailingFreeSpaceSafe, PgColumnarDeleteFreeSpaceAtOrAbove) are
cold here. record_free_space keys on (storage_id, file_offset) against
free_space_pkey (storage_id, file_offset) — exact prefix, also free.

What this does to the framing question

@OffgridwithJD — your point about the population lands harder than you put it.
You said defining it as "the key is a prefix of an index that already exists"
excludes the no-index case, which is the expensive one. True. But
delete_group_rows is inside that population on every one of its five arms
and was missed anyway, because the population was enumerated by source relation
handle rather than by what runs. The defect is not only where the boundary
was drawn, it is that a static enumeration cannot see a relation opened from a
parameter at all. The probe-everything-and-reconcile method has no such blind
spot, and it costs one build.

I have not measured the fix. Passing the right index oid to delete_group_rows
is a five-line change and I will take it, with the before/after measured by this
same reconciliation.

Still open on my side: the six storage sites, less the 3389 one now in #1210.

[OffgridwithJD]

The table in this issue is incomplete, and the missing entry is larger than
everything in it. @jdatcmd found it; I am recording it here because this issue
publishes the sweep.

delete_group_rows (columnar_metadata.c:632) takes the catalog as a
const char *tableName parameter and the key column as an AttrNumber
parameter:

rel  = open_columnar_table(tableName, RowExclusiveLock);
ScanKeyInit(&key[0], storageAttno, ...);
ScanKeyInit(&key[1], groupAttno, ...);
scan = systable_beginscan(rel, InvalidOid, false, NULL, 2, key);

PgColumnarDeleteGroupMetadata calls it five times — delete_vector,
column_chunk, zone_map, bloom, row_group (lines 842–850). One source
line, five unindexed scans per deleted group at runtime, and 66–71% of all
unindexed scan traffic on the compact path, with the share rising with size.

Neither static method could see it, by construction. Mine resolved a scan's
catalog by tracing its relation handle to an open_columnar_table("<literal>");
the earlier one took the nearest ScanKeyInit. When both the relation and the
key arrive as arguments, there is no literal at the call site for either method
to read. This is not a boundary drawn slightly wrong — it is a static
enumeration being the wrong instrument.

And it is worse than a miss: my sweep reported it and I did not chase it. It
is line 645, one of the three I listed above as "left unclassified rather than
guessed". Of those three, one is now #1210 and one is this. Both of the major
findings were in the unclassified residue, and the 21 I tabulated are the smaller
half. I treated the bucket I could not classify as leftovers instead of as the
part that needed a different instrument.

The instrument that works is a reconciliation, not a better sweep. Probe all
44 systable_beginscan sites with elog and require

sum(InvalidOid probe fires) == sum(seq_scan) across every pgcolumnar catalog

@jdatcmd's readings close exactly at four sizes (38/38, 73/73, 143/143, 283/283),
and the earlier six-site count failed the same check — 41 counted against 22
probed — which is the only reason the gap was noticed at all. A static count has
no such check available; that is the argument for not relying on one.

The table above is still correct for what it covers. It is no longer offered as
the population.

[jdatcmd]

#1213 takes the nine sites, and what is left of this issue

Nine scan sites converted, measured before and after:

catalog	seq_scan before	after
bloom	20	0
column_chunk	20	0
delete_vector	20	0
zone_map	20	0
free_space	22	0
row_group	43	0

The compaction path cost 7 x (retired groups) + 3 sequential scans and now
costs none of them. No catalog migration: every key was already an index prefix.
Both harnesses ship, and restoring InvalidOid on all nine reddens 13 of the
shell suite's 21 arms. Suite measured green on PG 15, 16, 17, 18 (assert and
non-assert) and 19.

Two of the nine were assert-only (PgColumnarCheckFreeSpaceNoOverlap) and
were the last found, because the probe run that closed the account was on a
release build and reported the path fully clean while the assert-enabled suite
still showed one scan on each of two catalogs. Any scan-count measurement here
is a measurement of one build kind.

What remains under this issue

• The six storage sites. storage.relation_oid is measured in Every planned query scans pgcolumnar.storage twice; relation_oid has no index #1210 and is
  stale after ALTER COLUMN TYPE (storage.relation_oid is orphaned by ALTER COLUMN TYPE, silently disabling the written-stripe-limit lookup #1211), so it needs the staleness fixed
  before the index, or the index makes a wrong answer arrive faster. Those two
  issues carry it; this one should probably not.
• PgColumnarListProjections scans projection by storage_id, which leads
  projection_pkey. One scan per maintenance operation, constant rather than
  per-group. Left alone only because fix: probe options and projection catalogs through their primary keys #1198 was in flight in the same file; it is
  a one-line change and nothing blocks it.

Everything else originally counted here is either converted by #1213 or was
never a real site — the original enumeration counted a comment about
systable_beginscan as a call, and missed five real ones behind a parameter.