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-04-01T02:02:25Z
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 Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg@bowt.ie> wrote:
> 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).

Attached is v33, which:

* Polishes the recently introduced
0003-Improve-skip-scan-primitive-scan-scheduling.patch logic, and
tweaks related code in _bt_advance_array_keys.

This includes one bug fix affecting backwards scans, which no longer
reuse pstate.skip to stop reading tuples when so->scanBehind was set.
Now _bt_readpage's backwards scan loop tests so.scanBehind directly
and explicitly, instead (there's no such change to its forwards scan
loop, though).

In v32 we could accidentally set pstate.skip (which is mostly intended
to be used by the "look-ahead" optimization added by the Postgres 17
SAOP project) to 0 (InvalidOffsetNumber), which actually represents
"don't skip at all" -- that was wrong. This happened when the
"pstate.skip = pstate.minoffnum - 1" statement gave us
InvalidOffsetNumber because pstate.minoffnum was already 1
(FirstOffsetNumber).

(FWIW, this only affected backwards scans at the point that they read
the index's rightmost leaf page, since any other leaf page has to have
a high key at FirstOffSetNumber, which implies a pstate.minoffnum of
FirstOffsetNumber+1, which meant we set pstate.skip = 1
(FirstOffsetNumber) by subtraction, which accidentally failed to
fail).

* v33 also makes small tweaks and comment clean-ups to the logic in
and around _bt_set_startikey, added by 0002-*, with the goal
simplifying the code, and in particular making the possible impact of
pstate.forcenonrequired on maintenance of the scan's arrays clearer.

We must not break the rule established by the Postgres 17 SAOP work:
the scan's array keys should always track the scan's progress through
the index's key space (I refer to the rule explained by the 17 SAOP
commit's message, see commit
5bf748b86bc6786a3fc57fc7ce296c37da6564b0). While we do "temporarily
stop following that rule" within a given pstate.forcenonrequired call
to _bt_readpage (to save some cycles), that should never have lasting
side-effects; there should be no observable effect outside of
_bt_readpage itself. In other words, the use of
pstate.forcenonrequired by _bt_readpage should leave the scan's arrays
in exactly the same state as _bt_readpage would have left them had it
never used pstate.forcenonrequired mode to begin with.

(FWIW, I have no reason to believe that v32 had any bugs pertaining to
this. AFAICT it didn't actually break "the general rule established by
the Postgres 17 SAOP work", but the explanation for why that was so
was needlessly complicated.)

I'm now very close to committing everything. Though I do still want
another pair of eyes on the newer
0003-Improve-skip-scan-primitive-scan-scheduling.patch stuff before
commiting (since I still intend to commit all the remaining patches
together).

--
Peter Geoghegan