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
On Tue, Aug 18, 2026 at 8:16 AM Dan Stefura
<dstefura@bluecatnetworks.com> wrote:
-- 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);
This is an unrealistic index. The unusual thing about it isn't that
45,000 rows all share the same owner_id (owner_id = 999999); it's that
all of the values from the second column (range_start) are perfectly
unique (at least within the 45k owner_id = 999999 top-level grouping),
even though there's a third column that's also perfectly unique
(range_end), followed by a fourth low-cardinality column (category).
In other words, the relevant index tuples are laid out in the index as
follows (here I'm showing the first 15 "owner_id = 999999" rows, in
index order):
┌──────────┬─────────────┬───────────┬──────────┐
│ owner_id │ range_start │ range_end │ category │
├──────────┼─────────────┼───────────┼──────────┤
│ 999,999 │ 256 │ 511 │ CAT1 │
│ 999,999 │ 512 │ 767 │ CAT2 │
│ 999,999 │ 768 │ 1,023 │ CAT3 │
│ 999,999 │ 1,024 │ 1,279 │ CAT4 │
│ 999,999 │ 1,280 │ 1,535 │ CAT0 │
│ 999,999 │ 1,536 │ 1,791 │ CAT1 │
│ 999,999 │ 1,792 │ 2,047 │ CAT2 │
│ 999,999 │ 2,048 │ 2,303 │ CAT3 │
│ 999,999 │ 2,304 │ 2,559 │ CAT4 │
│ 999,999 │ 2,560 │ 2,815 │ CAT0 │
│ 999,999 │ 2,816 │ 3,071 │ CAT1 │
│ 999,999 │ 3,072 │ 3,327 │ CAT2 │
│ 999,999 │ 3,328 │ 3,583 │ CAT3 │
│ 999,999 │ 3,584 │ 3,839 │ CAT4 │
│ 999,999 │ 3,840 │ 4,095 │ CAT0 │
└──────────┴─────────────┴───────────┴──────────┘
Why is this index shape the most useful one for your application?
Would it not make more sense if the index columns were in a different
order, such as (owner_id, category, range_start, range_end)?
A good rule of thumb with multicolumn indexes is that columns that are
typically used with = conditions should come before columns that are
typically used with range/inequality conditions (obviously range_start
and range_end only really make sense as something used with inequality
conditions like < and >=). Even if some queries omit category
entirely, performance will still be decent with this alternative
design because skip scan will efficiently skip to the next "category"
by performing another index search (there are only 5 distinct
categories).
Maybe your existing index shape has worked okay for you in the past
because you know that "range_start <= range_end" is always true. That
sounds like the kind of thing that might be better handled with range
types and a GiST index.
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.
I am almost certain that the effect you're seeing is due to skip array
maintenance for a scan that cannot possibly benefit from their use.
This is a known issue, described at the end of the commit message of
commit 8a510275.
--
Peter Geoghegan
Thanks for your feedback, it has been very helpful.
Our index shape may not have been intentional, it has been there for a very long time and performed ok until now.
We are experimenting with moving the index before the columns with range/inequality conditions and it certainly helps. The below reproduction steps improve 5x with pg18.6 and even 2.6x with pg17.
With our actual schema and real data it brings it to pg17 speeds.
Thanks for the explanation, it is very much appreciated.
-Dan
From: Peter Geoghegan <pg@bowt.ie>
Date: Tuesday, August 18, 2026 at 12:24 PM
To: Dan Stefura <dstefura@bluecatnetworks.com>
Cc: pgsql-bugs@lists.postgresql.org <pgsql-bugs@lists.postgresql.org>
Subject: Re: B-tree index scan ~2x slower on PG18 vs PG17 for skewed equality-prefix + range-condition lookups, with essentially the same plan
On Tue, Aug 18, 2026 at 8:16 AM Dan Stefura
<dstefura@bluecatnetworks.com> wrote:
-- 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);
This is an unrealistic index. The unusual thing about it isn't that
45,000 rows all share the same owner_id (owner_id = 999999); it's that
all of the values from the second column (range_start) are perfectly
unique (at least within the 45k owner_id = 999999 top-level grouping),
even though there's a third column that's also perfectly unique
(range_end), followed by a fourth low-cardinality column (category).
In other words, the relevant index tuples are laid out in the index as
follows (here I'm showing the first 15 "owner_id = 999999" rows, in
index order):
┌──────────┬─────────────┬───────────┬──────────┐
│ owner_id │ range_start │ range_end │ category │
├──────────┼─────────────┼───────────┼──────────┤
│ 999,999 │ 256 │ 511 │ CAT1 │
│ 999,999 │ 512 │ 767 │ CAT2 │
│ 999,999 │ 768 │ 1,023 │ CAT3 │
│ 999,999 │ 1,024 │ 1,279 │ CAT4 │
│ 999,999 │ 1,280 │ 1,535 │ CAT0 │
│ 999,999 │ 1,536 │ 1,791 │ CAT1 │
│ 999,999 │ 1,792 │ 2,047 │ CAT2 │
│ 999,999 │ 2,048 │ 2,303 │ CAT3 │
│ 999,999 │ 2,304 │ 2,559 │ CAT4 │
│ 999,999 │ 2,560 │ 2,815 │ CAT0 │
│ 999,999 │ 2,816 │ 3,071 │ CAT1 │
│ 999,999 │ 3,072 │ 3,327 │ CAT2 │
│ 999,999 │ 3,328 │ 3,583 │ CAT3 │
│ 999,999 │ 3,584 │ 3,839 │ CAT4 │
│ 999,999 │ 3,840 │ 4,095 │ CAT0 │
└──────────┴─────────────┴───────────┴──────────┘
Why is this index shape the most useful one for your application?
Would it not make more sense if the index columns were in a different
order, such as (owner_id, category, range_start, range_end)?
A good rule of thumb with multicolumn indexes is that columns that are
typically used with = conditions should come before columns that are
typically used with range/inequality conditions (obviously range_start
and range_end only really make sense as something used with inequality
conditions like < and >=). Even if some queries omit category
entirely, performance will still be decent with this alternative
design because skip scan will efficiently skip to the next "category"
by performing another index search (there are only 5 distinct
categories).
Maybe your existing index shape has worked okay for you in the past
because you know that "range_start <= range_end" is always true. That
sounds like the kind of thing that might be better handled with range
types and a GiST index.
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.
I am almost certain that the effect you're seeing is due to skip array
maintenance for a scan that cannot possibly benefit from their use.
This is a known issue, described at the end of the commit message of
commit 8a510275.
--
Peter Geoghegan