Horton

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

Matthias van de Meent <boekewurm+postgres@gmail.com>

View thread
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
To: Peter Geoghegan <pg@bowt.ie>, Tomas Vondra <tomas@vondra.me>
Cc: Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2024-09-12T14:49:24Z
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 Mon, 9 Sept 2024 at 21:55, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Sat, Sep 7, 2024 at 11:27 AM Tomas Vondra <tomas@vondra.me> wrote:
> > I started looking at this patch today.
>
> Thanks for taking a look!
>
> > The first thing I usually do for
> > new patches is a stress test, so I did a simple script that generates
> > random table and runs a random query with IN() clause with various
> > configs (parallel query, index-only scans, ...). And it got stuck on a
> > parallel query pretty quick.
>
> I can reproduce this locally, without too much difficulty.
> Unfortunately, this is a bug on master/Postgres 17. Some kind of issue
> in my commit 5bf748b8.
[...]
> In short, one or two details of how backends call _bt_parallel_seize
> to pick up BTPARALLEL_NEED_PRIMSCAN work likely need to be rethought.

Thanks to Peter for the description, that helped me debug the issue. I
think I found a fix for the issue: regression tests for 811af978
consistently got stuck on my macbook before the attached patch 0001,
after applying that this patch they completed just fine.

The issue to me seems to be the following:

Only _bt_first can start a new primitive scan, so _bt_parallel_seize
only assigns a new primscan if the process is indeed in _bt_first (as
provided with _b_p_s(first=true)). All other backends that hit a
NEED_PRIMSCAN state will currently pause until a backend in _bt_first
does the next primitive scan.

A backend that hasn't requested the next primitive scan will likely
hit _bt_parallel_seize from code other than _bt_first, thus pausing.
If this is the leader process, it'll stop consuming tuples from
follower processes.

If the follower process finds a new primary scan is required after
finishing reading results from a page, it will first request a new
primitive scan, and only then start producing the tuples.

As such, we can have a follower process that just finished reading a
page, had issued a new primitive scan, and now tries to send tuples to
its primary process before getting back to _bt_first, but the its
primary process won't acknowledge any tuples because it's waiting for
that process to start the next primitive scan - now we're deadlocked.

---

The fix in 0001 is relatively simple: we stop backends from waiting
for a concurrent backend to resolve the NEED_PRIMSCAN condition, and
instead move our local state machine so that we'll hit _bt_first
ourselves, so that we may be able to start the next primitive scan.
Also attached is 0002, which adds tracking of responsible backends to
parallel btree scans, thus allowing us to assert we're never waiting
for our own process to move the state forward. I found this patch
helpful while working on solving this issue, even if it wouldn't have
found the bug as reported.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)