B-tree index scan ~2x slower on PG18 vs PG17 for skewed equality-prefix + range-condition lookups, with essentially the same plan

Description
-----------

Hi, (the following was drafted with Claude Code after many experiments)

I've run into a performance regression in PostgreSQL 18 (reproduces on
both 18.4 and 18.6) affecting a fairly ordinary query shape: a
single-table Index Scan using a multicolumn B-tree index of the form
(equality, range, range, equality), with a LIMIT 1. When the leading
equality column is skewed -- i.e. a large number of rows share the
same value -- the same query, using the same index, and choosing
essentially the same plan on both versions, runs noticeably slower on
PG18 than PG17.

I initially suspected a planner/costing regression (different index
or plan chosen), but EXPLAIN (ANALYZE, BUFFERS) shows the same plan
shape, index, and Index Cond on both versions. The small difference
in buffer hits is consistent with separately built indexes, and there
is no disk read in either warm run. The execution-time difference is
therefore not explained by a changed plan or I/O. Limited live gdb
sampling finds _bt_checkkeys() on the active scan path. This suggests
that its PG18 rework for B-tree skip scans may have added per-tuple
overhead to ordinary (non-skip) scans, but I have not established a
line-level cause.

Environment
-----------

- PostgreSQL 17.10 (Debian 17.10-0+deb13u1) vs PostgreSQL 18.4
(Debian 18.4-1.pgdg13+1) and 18.6 (Debian 18.6-1.pgdg13+2)
- Debian 13 (trixie), x86_64
- Reproduces with default postgresql.conf settings; no unusual
configuration

Reproduction steps
-------------------

-- 246,258 rows total; 45,000 of them share owner_id = 999999 (skewed
-- group), each with a distinct, non-overlapping [range_start,
-- range_end] interval.
CREATE TABLE range_lookup_test AS
SELECT
i AS id,
('CAT' || (i % 5))::varchar(255) AS category,
CASE WHEN i <= 45000 THEN 999999::bigint ELSE (i / 6)::bigint END AS owner_id,
(i * 256)::bigint AS range_start,
(i * 256 + 255)::bigint AS range_end
FROM generate_series(1, 246258) i;

CREATE INDEX range_lookup_owner_range_cat_x ON range_lookup_test
USING btree (owner_id, range_start, range_end, category);

ANALYZE range_lookup_test;

-- Look up a match near the middle of the dominant (skewed) group.
PREPARE range_lookup(bigint, bigint, bigint) AS
select t.id from range_lookup_test t
where t.category = 'CAT0' and t.range_start <= $1 AND t.range_end >= $2
and t.owner_id = $3 limit 1;

EXECUTE range_lookup(5760000, 5760000, 999999); -- matches id=22500, expected result

A single execution is fast enough on both versions that the
difference is easiest to see over repeated executions (matching how a
real application would reuse a prepared statement on a pooled
connection):

-- after PREPARE as above, execute 5,000 times in the same session
EXECUTE range_lookup(5760000, 5760000, 999999);
-- (repeated 5,000x)

Timed via "psql -f" on a script containing the PREPARE once followed
by 5,000 EXECUTE lines, fully cache-warm (verified via EXPLAIN
(ANALYZE, BUFFERS), see below):

Total time, 5,000 executions (3 runs each):
PG17.10 : 2.95s / 3.05s / 2.97s
PG18.4 : 5.99s / 5.88s / 5.46s (~1.9x)
PG18.6 : 6.03s / 5.69s / 5.41s (~1.9x -- confirms not fixed by 18.6)

The psql-script timing includes client/protocol and result-output
overhead, although that overhead is the same on both servers. To
isolate server execution, I also ran the same SELECT 5,000 times in a
single PL/pgSQL DO loop (assigning the result to a local variable, so
there is no per-query client output) against session-local copies of
the table on the same host:

PostgreSQL 17.10: 0.730 ms for one warm EXPLAIN ANALYZE execution;
2.220 s for 5,000 loop iterations
PostgreSQL 18.4 : 1.558 ms for one warm EXPLAIN ANALYZE execution;
5.410 s for 5,000 loop iterations

That independent server-side measurement is approximately 2.4x
slower on PG18.4. Both executions scanned the same 139 local index
pages after warming the temporary table's local buffers.

Plan comparison
---------------

EXPLAIN (ANALYZE, BUFFERS), run repeatedly to ensure a fully warm
cache, on both versions:

PG17.10:

Limit (cost=0.42..4.03 rows=1 width=4) (actual time=0.617..0.676 ms rows=1 loops=1)
Buffers: shared hit=142
-> Index Scan using range_lookup_owner_range_cat_x on range_lookup_test t
(cost=0.42..2702.78 rows=749 width=4)
Index Cond: ((owner_id = 999999) AND (range_start <= 5760000) AND (range_end >= 5760000) AND ((category)::text = 'CAT0'::text))
Buffers: shared hit=142

PG18.4 / PG18.6:

Limit (cost=0.42..4.04 rows=1 width=4) (actual time=1.116..1.127 ms rows=1.00 loops=1)
Buffers: shared hit=151
-> Index Scan using range_lookup_owner_range_cat_x on range_lookup_test t
(cost=0.42..2704.88 rows=748 width=4)
Index Cond: ((owner_id = 999999) AND (range_start <= 5760000) AND (range_end >= 5760000) AND ((category)::text = 'CAT0'::text))
Index Searches: 1
Buffers: shared hit=151

The plan shape and Index Cond are the same, the buffer-hit counts are
within ~6% of each other (142 vs 151, both 100% shared hit and zero
read), and cost estimates are in the same ballpark (2702.78 vs
2704.88). The exact number of index pages may vary because the index
was built independently on each version, but it is far too small a
difference to explain the roughly 1.7-1.8x per-call execution-time
difference, growing to ~1.9x in the psql-script measurement.

I confirmed this isn't a page-cache artifact: I re-ran the comparison
immediately after a full restart of both server instances (clearing
shared_buffers) plus "sync; echo 3 > /proc/sys/vm/drop_caches" on the
OS, and the ratio was statistically the same cold (2.33x) as warm
(2.38x, 3-run average). Since every timed run already showed zero
read buffers even before this check, this was expected, but I wanted
to rule it out explicitly.

I also tried a non-skewed variant of the same table (uniform groups
of 6 rows instead of one 45,000-row group) -- that version shows no
measurable difference between PG17 and PG18 at all. The regression
only appears when the leading equality column has one or more large,
skewed groups the scan must walk through before satisfying the range
conditions and reaching LIMIT 1.

Live profiling
---------------

I attached gdb to a backend running the EXECUTE loop above (30,000
iterations) and took 5 stack samples at different points during
execution (gdb -batch -p <pid> -ex "bt" -ex "detach"). _bt_checkkeys
appeared in all 5 of 5 samples. This is only a coarse indication of
where the backend spent time, not a CPU profile or proof of causality:

#0 0x... in ?? ()
#1 0x... in _bt_checkkeys ()
#2 0x... in ?? ()
#3 0x... in ?? ()
#4 0x... in _bt_first ()
#5 0x... in btgettuple ()
#6 0x... in index_getnext_tid ()
#7 0x... in index_getnext_slot ()
#8 0x... in ?? ()
#9 0x... in ExecScan ()
...

One sample additionally caught comparator work happening from inside
_bt_checkkeys:

#0 0x... in toast_raw_datum_size ()
#1 0x... in texteq ()
#2 0x... in FunctionCall2Coll ()
#3 0x... in ?? ()
#4 0x... in ?? ()
#5 0x... in _bt_checkkeys ()
...

(This is the category varchar equality comparison being evaluated as
part of the per-tuple check.)

Suspected area
---------------

Comparing src/backend/access/nbtree/nbtutils.c between the
REL_17_STABLE and REL_18_STABLE branches, _bt_checkkeys() -- invoked
once per candidate index tuple during every B-tree scan, not just
skip-scans -- was substantially reworked, presumably to support the
new skip-scan feature ("Allow skip scans of btree indexes" in the
18.0 release notes):

- PG17: threads pstate->prechecked / pstate->firstmatch fast-path
flags through to _bt_check_compare(), with ikey always starting
at 0.
- PG18: replaces this with pstate->startikey (ikey =
pstate->startikey instead of ikey = 0) and a new
pstate->forcenonrequired parameter, alongside new scan-state
fields (so->needPrimScan, so->scanBehind, so->oppositeDirCheck)
that don't exist in PG17.

I don't have a confirmed line-level culprit. However, the shape of
the regression -- a higher CPU cost that scales with the number of
candidate tuples individually checked within a skewed equality-prefix
group -- is consistent with constant-factor overhead in the common
key-checking path. "Index Searches: 1" in the PG18 plan indicates
that repeated index searches associated with skip scans are not being
performed here: this is one ordinary index descent. That narrows the
suspected area to shared scan/key-checking code rather than proving
that skip-scan-specific control flow is responsible.

Happy to provide any further diagnostics, a larger/smaller
reproduction, or test a patch.

Thanks,
-Dan