Horton

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

Peter Geoghegan <pg@bowt.ie>

View thread
From: Peter Geoghegan <pg@bowt.ie>
To: Matthias van de Meent <boekewurm+postgres@gmail.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Masahiro Ikeda <ikedamsh@oss.nttdata.com>, Tomas Vondra <tomas@vondra.me>, Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2025-03-28T21:59:22Z
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 →

  1. nbtree: Always set skipScan flag on rescan.

  2. meson: Build numeric.c with -ftree-vectorize.

  3. Fix "variable not found in subplan target lists" in semijoin de-duplication.

  4. Revert "nbtree: Remove useless row compare arg."

  5. nbtree: Remove useless row compare arg.

  6. Prevent premature nbtree array advancement.

  7. nbtree: tighten up array recheck rules.

  8. Avoid treating nonrequired nbtree keys as required.

  9. Adjust overstrong nbtree skip array assertion.

  10. Make NULL tuple values always advance skip arrays.

  11. Avoid extra index searches through preprocessing.

  12. Improve nbtree skip scan primitive scan scheduling.

  13. Further optimize nbtree search scan key comparisons.

  14. Add nbtree skip scan optimization.

  15. Improve nbtree array primitive scan scheduling.

  16. nbtree: Make BTMaxItemSize into object-like macro.

  17. Show index search count in EXPLAIN ANALYZE, take 2.

  18. Make parallel nbtree index scans use an LWLock.

  19. Show index search count in EXPLAIN ANALYZE.

  20. Avoid nbtree parallel scan currPos confusion.

  21. nbtree: Remove useless 'strat' local variable.

  22. Normalize nbtree truncated high key array behavior.

  23. Refactor handling of nbtree array redundancies.

  24. Fix nbtree pgstats accounting with parallel scans.

  25. Avoid parallel nbtree index scan hangs with SAOPs.

  26. Show Parallel Bitmap Heap Scan worker stats in EXPLAIN ANALYZE

  27. Enhance nbtree ScalarArrayOp execution.

  28. Skip checking of scan keys required for directional scan in B-tree

  29. Instead of using a numberOfRequiredKeys count to distinguish required

Attachments

On Tue, Mar 25, 2025 at 7:45 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
> I've once again renamed, this time to _bt_set_startikey).

Attached is v32, which has very few changes, but does add a new patch:
a patch that adds skip-array-specific primitive index scan heuristics
to _bt_advance_array_keys (this is
v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).

I feel compelled to do something about cases like the ones highlighted
by the attached test case, heikki-testcase-variant.sql. This shows how
the new heuristic added by my recent commit 9a2e2a28 can still
sometimes fail to ever be reached, in cases rather like the ones that
that was supposed to address [1]. This test case I'm posting now is
based on Heikki's adversarial test case (the one he posted back in
January). I've pushed it a bit further, demonstrating a remaining need
to tweak the primscan scheduling heuristics in light of skip scan. If
you run heikki-testcase-variant.sql against a patched server, without
v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch, you'll see
exactly what I'm concerned about .

I am somewhat breaking my own rule about not inventing heuristics that
specifically care about which type of array (skip vs SAOP array) are
involved here. In my defense, the new heuristic isn't particularly
likely to influence primscan scheduling. It will seldom be needed or
have any noticeable influence, but just might be crucial with cases
like the one from the test case. It seems a little too hard for skip
scans to actually get the behavior from commit 9a2e2a28 -- which is
something that we really shouldn't leave to chance.

The plan around committing this work hasn't changed: I still intend to
commit everything next Wednesday or Thursday. Hope to get a review of
the new scan heuristic before then, but it's a small adjunct to what I
did in commit 9a2e2a28, so not too concerned about it adding risk.

Thanks

[1] https://postgr.es/m/aa55adf3-6466-4324-92e6-5ef54e7c3918@iki.fi

--
Peter Geoghegan