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

Tomas Vondra <tomas@vondra.me>

From: Tomas Vondra <tomas@vondra.me>

To: Matthias van de Meent <boekewurm+postgres@gmail.com>, Peter Geoghegan <pg@bowt.ie>

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

Date: 2025-05-09T22:54:10Z

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 5/9/25 23:30, Matthias van de Meent wrote:
> ...
>> 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.
> 

Yes. Have you tried reproducing the issue? It'd be good if someone else
reproduced this independently, to confirm I'm not hallucinating.

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

I tried, and it seems 4MB is sufficient for the overhead to disappear.
Perhaps some other mallopt parameters would help too, but my point was
merely to demonstrate this is malloc-related.

> 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?
> 

I haven't noticed any elevated memory usage in top, but the queries are
very short, so I'm not sure how reliable that is. But if adding 4MB is
enough to make this go away, I doubt I'd notice a difference.


regards

-- 
Tomas Vondra