Fetch by row number re-reads and re-decodes the whole row group, making UPDATE and DELETE quadratic within a group

[jdatcmd]

Found while measuring whether the ColumnarDeleteVectorBufferedDeleted nested
scan (left unfixed by the July audit) is worth fixing. It is not the problem. The
problem is larger and sits in the fetch-by-row-number path.

Measurements

PostgreSQL 17 non-assert, UPDATE t SET v = v + 1 over the whole table,
EXPLAIN ANALYZE execution time.

Cost grows with the square of the row count, not linearly:

rows	with unique index	without unique index
5,000	878 ms	333 ms
10,000	4,452 ms	1,623 ms
20,000	19,211 ms	6,901 ms

Doubling the rows multiplies the time by about 4.3 to 5. It happens with and
without a unique index, so this is not the uniqueness check.

More row groups makes it faster, which is the opposite of a per-row-group
cost. 20,000 rows held constant, unique index present:

row groups	update
1	15,743 ms
2	6,775 ms
10	1,403 ms

So the term is quadratic in the rows within a row group. Splitting the same
rows across ten groups divides the work by roughly ten.

The column cache does not help:

rows	cache off	cache on
20,000	15,846 ms	14,693 ms
10,000	4,454 ms	4,957 ms

pgcolumnar.enable_column_cache caches decompressed streams, so this says
decompression is not where the time goes.

Mechanism

ColumnarReadRowByNumber (src/columnar_reader.c:1271) fetches one row by
reading its entire row group each time:

• groupBuffer = palloc(rg->byteLength) and ColumnarReadLogicalData pull the
  whole group's bytes,
• columnar_native_decode_chunk decodes each column's chunk in full,
• and then a for (i = 0; i < rowInGrp; i++) walk steps to the row's position
  inside the decoded chunk.

Fetching N rows from one group therefore costs N times the group's size, plus a
walk that is linear in the row's offset. Nothing is retained between calls, so
two consecutive fetches of adjacent rows in the same group repeat all of it.

Every caller of the fetch path pays this: index scans that return many rows from
one group, bitmap scans, UPDATE and DELETE reached by index, and the
uniqueness check.

It matters at the defaults. stripe_row_limit is 150,000, so one group can hold
150,000 rows; extrapolating the measured curve from 20,000 rows in one group puts
a full-group update in the tens of minutes.

Direction, not yet a design

Two independent pieces, either of which helps on its own:

1. Reuse the decoded group across consecutive fetches. The bytes at a given
   fileOffset are immutable once written, so a decoded group can be keyed by
   (storageId, fileOffset, byteLength) without an invalidation problem.
   Visibility is checked per fetch against the delete vector and row mask, which
   is separate from the decoded values, so caching values does not affect what a
   snapshot sees. Bounding memory is the real design question, since a decoded
   group of 150,000 rows across many columns is not small.
2. Remove the linear walk to the row position. Fixed-width columns can index
   directly; variable-width ones need an offset the decoder could produce.

I have not implemented either. The path is on the read side and adjacent to
correctness, so it wants a written plan and a review before code, not an
overnight patch.

Not the cause

ColumnarDeleteVectorBufferedDeleted, which the audit record lists as left
unfixed, is called only under the uniqueness check, and the quadratic behaviour
is present without a unique index at similar magnitude. Its nested scan is real
but is not what makes these numbers. Worth keeping on the list, not worth fixing
first.

[ChronicallyJD]

Measured a few things against the plan on PG 18.4. The ordering in it is right, and I can now say so with data rather than agreement, because I set out to argue the opposite and the measurement said no.

B before C is correct, and here is the evidence

Reading the code, step 4 looked like it had to be a co-equal quadratic term: two per-column walks per fetch, for (i = 0; i < rowInGrp; i++) over the validity bitmap and then for (i = 0; i < present; i++) calling ColumnarDecodeValue on every skipped value, which for a varlena column allocates and copies each time. Summed over a scan of one group that is O(groupsize^2), the same order as the re-decode, which would have meant B alone could not make the path linear.

It does not behave that way. One row group, 20,000 rows, UPDATE of 1,000 rows by index at three positions:

rows updated	time
first 1,000	5,069 ms
middle 1,000	5,431 ms
last 1,000	5,424 ms

Seven percent between the first batch and the last, where the walk does roughly forty times the work. So the cost is position-independent: step 3 dominates and step 4 is a rounding error at this shape. C is worth doing, but it is a small constant, and deferring it behind B is the right call.

The one thing I would change

Do not fix the cache at one entry without measuring scattered access first.

One entry is exactly right for the workload that motivated the issue. UPDATE t SET v = v + 1 over the whole table walks rows in row-number order, so consecutive fetches stay inside a group and a single entry hits almost always. But the issue's own list of affected callers leads with index scans, and an index delivers TIDs in index order. On a column uncorrelated with row order, consecutive fetches land in different groups, and a one-entry cache keyed by (storageId, groupNumber) then hits about 1/G of the time, so the fix delivers about a tenth of its value at ten groups and less as the table grows.

Same table, 20,000 rows across ten groups, forcing an index scan, today:

access path	time
row-ordered index	1,214 ms
scattered index	1,481 ms

Both slow today because nothing is cached, which is the point: they are the same cost now and would diverge sharply under a one-entry cache. A small number of entries with LRU replacement, four or eight, costs almost nothing over one and removes the dependence on access order. Worth deciding with a scattered-index benchmark alongside the sequential one rather than after.

A trap for the memory cap

Cap on the decoded size, not on rg->byteLength. The stored size is compressed and encoded; a group of wide text decodes to something much larger, and the ratio is exactly what the encoders exist to maximise. Sizing the cap from the on-disk bytes would admit groups far over the intended budget, and the overshoot would be worst on the tables the cache helps most.

An aside that connects to #130

I tried to report the correlation of the two indexed columns above and pg_stats had no row for either, because ANALYZE collects nothing for a columnar table. That is worth noting here and not only in the limitations doc: the planner chooses between a sequential scan and the index-driven path that triggers this issue without correlation data. So the access pattern that makes #143 worst is partly selected by a planner that cannot see how correlated the index is. It does not change the fix, but it does mean a benchmark that pins enable_seqscan is measuring a plan the planner might not choose on its own.

On the rest

The statement-scope invalidation argument holds up, and GetCurrentCommandId(false) alongside the entry is a clean way to get it without a hook. Keying on the storage id as well is right for the rewrite case. Good that the plan records that ColumnarReadRowGroupList must stay a heap scan; that one cost me a hang.

[jdatcmd]

Step 1 of design/FETCH_BY_ROW_PLAN.md landed in #148: a statement-scoped cache of the decoded row group, keyed by (storage_id, group_number).

Measured on PG18, whole-table UPDATE with every row in one row group:

rows	before	after
5,000	4,322 ms	407 ms	10.6x
10,000	18,416 ms	1,564 ms	11.8x
20,000	57,393 ms	5,228 ms	11.0x

This issue stays open, because the path is still quadratic. Doubling the rows in one group still multiplies the time by about 3.3 to 3.8, against 3.1 to 4.3 before. A hit skips the read and the decode but still walks to the row's position, and that walk is linear in the offset, so summed over a group it remains quadratic. Removing about 90 percent of the cost promoted the walk to the dominant term.

Remaining, in order:

1. Option C, positional indexing, to remove the walk. This is now the whole of what is left of the quadratic behaviour, and the plan's acceptance criterion (a ratio under 3 at N and 2N rows in one group) cannot be met without it.
2. The needed-columns bitmap, for callers that can declare what they need. Smaller, and it cannot help the uniqueness check, which reaches the fetch through core's ordinary slot-filling callback.

Two things found while reviewing #148 that are worth having on this issue rather than only in the PR:

• The cache's safety is not a locking argument. compact_rewrite runs under ShareUpdateExclusiveLock and does not conflict with a reader. What makes it safe is that the storage id is in the key, rewrites retire group numbers instead of reusing them, the entry's geometry is re-checked on each hit, and an entry is used only within the command that filled it. native_rewrite.sh now pins the two of those that are allocator properties.
• Scattered index access is the weak case: an index-driven UPDATE of 2,000 rows across ten groups improves 8x when the index order matches row order and only 1.5x when it does not, against a four-entry cache. Worth revisiting if that shape matters.