Re: Adding skip scan (including MDAM style range skip scan) to nbtree

Peter Geoghegan <pg@bowt.ie>

From: Peter Geoghegan <pg@bowt.ie>

To: BharatDB <bharatdbpg@gmail.com>

Cc: Tomas Vondra <tomas@vondra.me>, pgsql-hackers@lists.postgresql.org, pgsql-hackers@postgresql.org, Matthias van de Meent <boekewurm+postgres@gmail.com>, rmt@lists.postgresql.org, Mark Dilger <mark.dilger@enterprisedb.com>, Heikki Linnakangas <hlinnaka@iki.fi>, Alexander Korotkov <aekorotkov@gmail.com>

Date: 2025-09-10T19:27:36Z

Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

nbtree: Always set skipScan flag on rescan.
- 454c046094ab 19 (unreleased) landed
- bee763aea13f 18.0 landed
meson: Build numeric.c with -ftree-vectorize.
- 9016fa7e3bcd 19 (unreleased) cited
Fix "variable not found in subplan target lists" in semijoin de-duplication.
- b8a1bdc458e3 19 (unreleased) cited
Revert "nbtree: Remove useless row compare arg."
- dd2ce3792754 18.0 landed
nbtree: Remove useless row compare arg.
- 54c6ea8c81db 18.0 cited
Prevent premature nbtree array advancement.
- 5f4d98d4f371 18.0 landed
nbtree: tighten up array recheck rules.
- 7e25c9363a82 18.0 landed
Avoid treating nonrequired nbtree keys as required.
- 0f08df406822 18.0 landed
Adjust overstrong nbtree skip array assertion.
- 9d924dbb3710 18.0 landed
Make NULL tuple values always advance skip arrays.
- b75fedcab791 18.0 cited
Avoid extra index searches through preprocessing.
- b3f1a13f22f9 18.0 landed
Improve nbtree skip scan primitive scan scheduling.
- 21a152b37f36 18.0 landed
Further optimize nbtree search scan key comparisons.
- 8a510275dd6b 18.0 landed
Add nbtree skip scan optimization.
- 92fe23d93aa3 18.0 landed
Improve nbtree array primitive scan scheduling.
- 9a2e2a285a14 18.0 landed
nbtree: Make BTMaxItemSize into object-like macro.
- 426ea611171d 18.0 landed
Show index search count in EXPLAIN ANALYZE, take 2.
- 0fbceae841cb 18.0 landed
Make parallel nbtree index scans use an LWLock.
- 67fc4c9fd7fa 18.0 landed
Show index search count in EXPLAIN ANALYZE.
- 5ead85fbc811 18.0 landed
Avoid nbtree parallel scan currPos confusion.
- b5ee4e52026b 18.0 cited
nbtree: Remove useless 'strat' local variable.
- b6558e4f837e 18.0 landed
Normalize nbtree truncated high key array behavior.
- 79fa7b3b1a44 18.0 landed
Refactor handling of nbtree array redundancies.
- b524974106ac 18.0 landed
Fix nbtree pgstats accounting with parallel scans.
- c00c54a9ac1e 18.0 landed
- fb4f5e58af97 17.0 landed
Avoid parallel nbtree index scan hangs with SAOPs.
- d8adfc18bebf 18.0 landed
- a24bffc021d9 17.0 landed
Show Parallel Bitmap Heap Scan worker stats in EXPLAIN ANALYZE
- 5a1e6df3b84c 18.0 cited
Enhance nbtree ScalarArrayOp execution.
- 5bf748b86bc6 17.0 cited
Skip checking of scan keys required for directional scan in B-tree
- e0b1ee17dc3a 17.0 cited
Instead of using a numberOfRequiredKeys count to distinguish required
- 7ccaf13a06b8 8.2.0 cited

On Wed, Sep 10, 2025 at 2:49 AM BharatDB <bharatdbpg@gmail.com> wrote:
> As a follow-up to the skip scan regression discussion, I tested a small patch that introduces static allocation/caching of `IndexAmRoutine` objects in `amapi.c`, removing the malloc/free overhead.

I think that it's too late to be considering anything this invasive for 18.

> Test setup :
> - Baseline: PG17 (commit before skip scan)
> - After: PG18 build with skip scan (patched)
> - pgbench scale=1, 100 partitions
> - Query: `select count(*) from pgbench_accounts where bid = 0`
> - Clients: 1, 4, 32
> - Protocols: simple, prepared
>
> Results (tps, 10s runs) :
>
> Mode Clients Before (PG17) After (PG18 w/ static fix)
>
> simple 1 23856 20332 (~15% lower)
> simple 4 55299 53184 (~4% lower)
> simple 32 79779 78347 (~2% lower)
>
> prepared 1 26364 26615 (no regression)
> prepared 4 55784 54437 (~2% lower)
> prepared 32 84687 80374 (~5% lower)
>
> This shows the static fix eliminates the severe ~50% regression previously observed by Tomas, leaving only a small residual slowdown (~2-15%).

The regression that Tomas reported is extreme and artificial. IIRC it
only affects partition queries with a hundred or so partitions, each
with an index-only scan that always scans exactly 0 index tuples, from
a pgbench_accounts that has the smallest possible amount of rows that
pgbench will allow (these are the cheapest possible index-only scans).
Plain index scans are not affected at all, presumably because it just
so happens that we don't allocate a BLCKSZ*2 workspace for plain index
scans, which is enough to put us well under the critical glibc
allocation size threshold (the threshold that the introduction of a
new nbtree support function put us over).

I also couldn't see anything like the 50% regression that Tomas
reported. And I couldn't recreate any problem unless partitioning was
used.

-- 
Peter Geoghegan