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-21T15:36:18Z
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

On Wed, Mar 19, 2025 at 5:08 PM Peter Geoghegan <pg@bowt.ie> wrote:
> The tricky logic added by 0003-* is my single biggest outstanding
> concern about the patch series. Particularly its potential to confuse
> the existing invariants for required arrays. And particularly in light
> of the changes that I made to 0003-* in the past few days.

A big part of the concern here is with the existing pstate.prechecked
optimization (the one added to Postgres 17 by Alexander Korotkov's
commit e0b1ee17). It now seems quite redundant -- the new
_bt_skip_ikeyprefix mechanism added by my 0003-* patch does the same
thing, but does it better (especially since I taught
_bt_skip_ikeyprefix to deal with simple inequalities in v29). I now
think that it makes most sense to totally replace pstate.prechecked
with _bt_skip_ikeyprefix -- we should use _bt_skip_ikeyprefix during
every scan (not just during skip scans, not just during scans with
SAOP array keys), and be done with it.

To recap, right now the so->scanBehind flag serves two roles:

1. It lets us know that it is unsafe to apply the pstate.prechecked
optimization when _bt_readpage gets to the next page.

2. It lets us know that a recheck of the finaltup tuple is required on
the next page (right now that is limited to forwards scans that
encounter a truncated high key, but I intend to expand it in the
0001-* patch to other cases where we want to move onto the next page
without being 100% sure that it's the right thing to do).

Role #1 is related to the fact that pstate.prechecked works in a way
that doesn't really know anything about SAOP array keys. My Postgres
17 commit 5bf748b8 added role #1, to work around the problem of the
precheck being confused in cases where the scan's array keys are
advanced before we reach the final tuple on the page (the precheck
tuple). That way, scans with array keys were still able to safely use
the pstate.prechecked optimization, at least in simpler cases.

The new, similar _bt_skip_ikeyprefix mechanism has no need to check
scanBehind like this. That's because it is directly aware of both SAOP
arrays and skip arrays (it doesn't actually examine the sk_argument
from a scan key associated with an array, it just looks at the array
itself). That's a big advantage -- especially in light of the
scheduling improvements from 0001-*, which will make many more
_bt_readpage calls see the so->scanBehind flag as set (making us not
use pstate.prechecked). The new scheduling stuff from 0001-* affects
scans with skip arrays and SAOP arrays in just the same way, and yet
right now there's an unhelpful disconnect between what each case will
do once it reaches the next page. This is probably the single biggest
point that makes pstate.prechecked seem like it clashes with
_bt_skip_ikeyprefix: it undermines the principle that array type (SAOP
array vs skip array) should not matter anywhere outside of the lowest
level nbtutils.c code, which is a principle that now seems important.

Another key advantage of the _bt_skip_ikeyprefix mechanism is that it
can plausibly work in many cases that pstate.prechecked currently
can't handle at all. The design of pstate.prechecked makes it an "all
or nothing" thing -- it either works for every scan key required in
the scan direction, or it works for none at all. Not so for
_bt_skip_ikeyprefix; it can set pstate.ikey to skip a prefix of = scan
keys (a prefix of keys known to satisfy all tuples on pstate.page),
without the prefix necessarily including every = scan key. That
flexibility could matter a lot.

Furthermore, it can do this (set pstate.ikey to a value greater than
0) *without* needing to set pstate.forcenonrequired to make it safe
(pstate.forcenonrequired must be set during scans with array keys to
set pstate.ikey to a non-zero value, but otherwise doesn't need to be
set). In other words, it's possible for most scans to use
_bt_skip_ikeyprefix without having to commit themselves to scan all of
the tuples on the page (unlike pstate.prechecked).

I'm pretty sure that this is the right direction already, for the
reasons given, but also because I already have a draft version that
passes all tests. It significantly improves performance in many of my
most important microbenchmarks: unsympathetic cases that previously
had 5%-10% regression in query execution time end up with only 2% - 5%
regressions. I think that that's because the draft patch completely
removes the "prechecked" code path from _bt_check_compare, which is a
very hot function -- especially during these adversarial
microbenchmarks.

Under this new scheme, so->scanBehind is strictly a flag that
indicates that a recheck is scheduled, to be performed once the scan
calls _bt_readpage for the next page. It no longer serves role #1,
only role #2. That seems significantly simpler.

Note that I'm *not* proposing to remove/replace the similar
pstate.firstmatch optimization (also added by Alexander Korotkov's
commit e0b1ee17). That's still independently useful (it'll complement
_bt_skip_ikeyprefix in just the same way as it complemented
pstate.prechecked).


--
Peter Geoghegan