The index-fetch penalty prices a path by its own row estimate, not the rows its consumer pulls: 57x regression on DISTINCT ON (last point per host)

[ChronicallyJD]

Summary

The index-fetch penalty prices an index path by its own row estimate, not by the
number of rows the plan above it will actually pull. When a node on top stops early —
a skip scan for DISTINCT ON, and by the same argument a Unique or a semijoin — the
penalty is computed for 100,000,000 fetches that never happen, and the plan is costed
out of existence.

Found while re-measuring docs/benchmarks.md for 1.0-alpha. It is a 57x regression
on q7, the canonical time-series query ("last point per host"), and it is my defect
from #355/#362/#363.

Evidence

cpu_pgc, 100M rows, (hostname, time DESC) btree, max_parallel_workers_per_gather = 4.

SELECT DISTINCT ON (hostname) hostname, time, usage_user
FROM cpu_pgc ORDER BY hostname, time DESC;

Penalty on (default):

Unique  (cost=3760904.85..15984368.90 rows=3998)
  ->  Gather Merge  (cost=3760904.85..15734368.90 rows=100000000)
        ->  Sort  (cost=3759904.79..3822404.79 rows=25000000)
              Sort Key: hostname, "time" DESC
              ->  Parallel Custom Scan (ColumnarScan) on cpu_pgc  (cost=0.00..337633.75)

Penalty off:

Unique  (cost=0.57..2375.93 rows=3998)
  ->  Custom Scan (SkipScan) on cpu_pgc  (cost=0.57..2365.93 rows=3998)
        ->  Index Scan using cpu_pgc_hostname_time_idx on cpu_pgc  (cost=0.57..2427872.31 rows=100000000)

arm	plan	measured
penalty on (default)	Gather Merge + Sort over a full scan	44,057 ms
penalty off	SkipScan over the index	769 ms

The planner discards a path it prices at 2,376 in favour of one it prices at
15,984,369, because the cheap one has been made expensive by the penalty.

Mechanism

columnar_penalize_index_fetches charges the index path using p->rows:

add = columnar_index_fetch_penalty(rel, p->rows, rho, nproj, decodedWidth, false);

For this path p->rows is 100,000,000 — the index scan's own estimate. The
SkipScan above it pulls 3,998. So the penalty models 100M row-group fetches for a
plan that performs about four thousand.

#360's body claimed this case was handled: "total_cost only, never startup_cost — a
LIMIT that stops the scan early pays the penalty proportionally, because the planner
fractions total - startup". That reasoning covers a LIMIT applied to this path.
It does not cover a separate path built on top of this one, which re-costs rather
than fractions. A skip scan is exactly that.

Note the SkipScan node here comes from TimescaleDB, which is loaded on the benchmark
cluster and applies its skip-scan rewrite to any suitable index. The defect is not
TimescaleDB's — it is that the penalty makes the underlying index path too expensive
for any early-stopping consumer to be built on, and Unique over an index scan is
the same shape without any extension involved.

Why the existing guards did not catch it

test/analyze_stats.sh covers a selective point lookup (#171/#159), a clustered
ORDER BY, an early-column prefix query (#363), and the unclustered ORDER BY the
penalty is for. Every one of those consumes the whole path it prices. None has a node
above the scan that stops early, so the "must not over-fire" direction is tested only
where rows-fetched equals rows-estimated.

Fix direction

Not started; I want the approach argued before I write it.

1. Cost the penalty from the rows the path will actually return in context. Hard
   at set_rel_pathlist time, because the consumer does not exist yet.
2. Cap the penalty by a bound the consumer cannot exceed — for example do not let
   the penalty push a path above the cheapest full-scan alternative by more than some
   factor, on the grounds that a plan which would be discarded outright deserves a
   second look.
3. Apply the penalty in set_cheapest/upper-path costing instead, where the
   consumer is known. Bigger change; probably the correct one.
4. Do not penalize when the index path can serve an ordering the query wants
   (pathkeys non-empty and matching), since that is the case where a consumer is
   most likely to stop early. Narrow, cheap, and would fix this instance — but it is a
   heuristic, not a model.

Alpha

Flagging for the release decision rather than deciding it. It is on by default, and
pgcolumnar.enable_index_fetch_penalty = off restores the old behaviour, so there is a
documented workaround. But "last point per host" is a headline time-series shape, and a
57x regression on it with the default settings is the kind of thing an alpha gets
judged on.

I would rather hold the cross-engine benchmark table than publish 44,057 ms for q7
without saying why it is that number.

[ChronicallyJD]

Both directions measured, and the naive fix would be wrong

I checked whether this is a TimescaleDB interaction. It is not — the same shape
reproduces with no TimescaleDB anywhere, on a plain Unique over an index scan. But
measuring the other direction changed what the fix has to be, so recording it before
anyone acts on the issue as filed.

Without TimescaleDB: the penalty is correct, and load-bearing

Container, no timescaledb (pg_extension = plpgsql,pgcolumnar), 4,000,000 rows,
4,000 hosts, index on (host, ts DESC):

SELECT DISTINCT ON (host) host, ts, v FROM lp ORDER BY host, ts DESC;

arm	plan	measured
penalty on	Sort over Custom Scan (ColumnarScan)	4,710 ms
penalty off	Unique over Index Scan	still running past 8 minutes

Here there is no skip scan, so Unique genuinely pulls all 4,000,000 rows through
scattered by-row-number fetches. The penalty steers away from a plan that is more
than 100x worse, which is exactly its job.

So the defect is narrower than the title suggests

The penalty is right when the consumer reads the whole path and wrong when the
consumer stops early. On the bench, TimescaleDB's SkipScan pulls 3,998 rows out of
100,000,000, and the penalty charges for all 100,000,000.

This rules out the obvious fixes. Do not exempt DISTINCT ON, do not exempt paths
with useful pathkeys, and do not weaken the penalty generally — every one of those
would reintroduce the 100x on the shape above, which is the same query text. The two
cases are indistinguishable by the query and distinguishable only by what sits above
the scan.

That pushes toward option (3) from the issue — cost the fetch where the consumer is
known — and away from (4), which I had listed as "narrow and cheap". It is cheap and
it is wrong.

What I got wrong in the issue as filed

I wrote the mechanism as "the penalty is computed for 100,000,000 fetches that never
happen". That is right for the bench case and I stated it as though it were the whole
story. It is half: in the majority case those fetches do happen and the penalty is
what saves the query. The issue title says "not the rows its consumer pulls", which
still holds, but read the paragraph above it as the correction.

I have not started a fix. Given it is default-on and now has a measured 57x in one
direction and a measured 100x+ in the other, I do not think it should be rushed.

[ChronicallyJD]

The no-TimescaleDB arm finished. Replacing my "still running past 8 minutes" with the
measured number:

arm	plan	measured
penalty on	Sort over Custom Scan (ColumnarScan)	4,710 ms
penalty off	Unique over Index Scan	170,965 ms

36x in the penalty's favour on the shape where the consumer reads the whole path,
against 57x against it on the bench where a skip scan pulls 3,998 rows out of
100,000,000. Same query text, opposite verdicts, decided entirely by what sits above
the scan.

That is the number to hold in mind when picking a fix: whatever replaces the current
model has to keep the 36x while giving back the 57x.