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(at)bluecatnetworks(dot)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