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: Mark Dilger <mark.dilger@enterprisedb.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, pgsql-hackers@lists.postgresql.org, Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: 2025-05-02T19:04: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 Fri, May 2, 2025 at 2:22 PM Peter Geoghegan <pg@bowt.ie> wrote:
> A slight variant of my fuzzing Python script did in fact go on to
> detect a couple of bugs.
>
> I'm attaching a compressed SQL file with repros for 2 different bugs.
> The first bug was independently detected by some kind of fuzzing
> performed by Mark Dilger, reported elsewhere [1].

Picking up from the email with the big attachment...

Both bugs are from commit 8a510275, "Further optimize nbtree search
scan key comparisons" (not the main skip scan commit). I actually
wrote code very much like the code from these patches that appeared in
certain versions of the skip scan patch series -- it was originally
supposed to be defensive hardening. This so-called hardening wasn't
kept in the final committed version because I incorrectly believed
that it wasn't necessary.

I would like to commit the first patch later today, ahead of shipping
beta1. But the second patch won't make it into beta1.

In practice the bug fixed by the first patch is more likely to affect
users, and (unlike the bug fixed by the second patch), it involves a
hard crash. The first patch prevents us from dereferencing a NULL
pointer (pstate) within _bt_advance_array_keys (unless on an
assert-enabled build, where we get an assertion failure first). It
would also be possible to fix the issue by testing if pstate itself is
not a NULL pointer in the usual defensive style, but I find the
approach taken in the first patch slightly more natural.

The second patch is more complicated, and seems like something that
I'll need to spend more time thinking about before proceeding with
commit. It has subtle behavioral implications, in that it causes the
pstate.forcenonrequired mechanism to influence when and how
_bt_advance_array_keys schedules primitive index scans in a tiny
minority of forward scan cases. I know of only 3 queries where this
happens, 2 of which are from my repro -- it's actually really hard to
find an example of this, even if you go out of your way to.

Allowing pstate.forcenonrequired to affect primscan scheduling like
this is something that I have been avoiding up until now, since that
makes things cleaner -- but I'm starting to think that that goal isn't
important enough to force the second patch to be significantly more
complicated than what I came up with here. It's not like the
behavioral differences represent a clear regression; they're just
slightly different to what we see in cases where
pstate.forcenonrequired/pstate.ikey is forcibly not applied (e.g., by
commenting-out the calls to _bt_set_startikey made by _bt_readpage).

My approach in the second patch is to simply call _bt_start_array_keys
ahead of the finaltup call to _bt_checkkeys when
pstate.forcenonrequired, which has the merit of being relatively
simple (it's likely the simplest possible approach). I'm unwilling to
pay too much of a cost in implementation complexity just to avoid
side-effects in _bt_advance_array_keys/primscan scheduling, but maybe
I'll find that the cost isn't too high.

-- 
Peter Geoghegan