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

Matthias van de Meent <boekewurm+postgres@gmail.com>

From: Matthias van de Meent <boekewurm+postgres@gmail.com>

To: Peter Geoghegan <pg@bowt.ie>

Cc: Tomas Vondra <tomas@vondra.me>, Mark Dilger <mark.dilger@enterprisedb.com>, Heikki Linnakangas <hlinnaka@iki.fi>, pgsql-hackers@lists.postgresql.org

Date: 2025-05-09T21:30:28Z

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 Fri, 9 May 2025 at 20:38, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Fri, May 9, 2025 at 2:04 PM Tomas Vondra <tomas@vondra.me> wrote:
> > Yes, I'm sure it's doing index only scan
>
> Looks that way, from the pair of flame graphs you sent. Thanks for that.
>
> > did you update "bid" or did
> > you leave it as generated by "pgbench -i"?.
>
> I didn't bother with updating, or running VACUUM FULL. I did run
> VACUUM ANALYZE, though (can confirm no heap accesses for the
> index-only scans).
>
> > In fact, all of the malloc() calls seem to happen in AllocSetAllocLarge,
> > which matches the guess that something tripped over allocChunkLimit. Not
> > sure what, though.

> The difference shown by your flame graph is absolutely enormous --
> that's *very* surprising to me. btbeginscan and btrescan go from being
> microscopic to being very prominent. But skip scan simply didn't touch
> either function, at all, directly or indirectly. And neither function
> has really changed in any significant way in recent years. So right
> now I'm completely stumped.

I see some 60.5% of the samples under PostgresMain (35% overall) in
the "bad" flamegraph have asm_exc_page_fault on the stack, indicating
the backend(s) are hit with a torrent of continued page faults.
Notably, this is not just in btree code: ExecInitIndexOnlyScan's
components (ExecAssignExprContext,
ExecConditionalAssignProjectionInfo, ExecIndexBuildScanKeys,
ExecInitQual, etc.) are also very much affected, and none of those
call into index code. Notably, this is before any btree code is
executed in the query.

In the "good" version, asm_exc_page_fault does not show up, at all;
nor does sysmalloc.

@Tomas
Given the impact of MALLOC_TOP_PAD_, have you tested with other values
of MALLOC_TOP_PAD_?

Also, have you checked the memory usage of the benchmarked backends
before and after 92fe23d93aa, e.g. by dumping
pg_backend_memory_contexts after preparing and executing the sample
query, or through  pg_get_process_memory_contexts() from another
backend?

Kind regards,

Matthias van de Meent