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: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: 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-02-23T17:19:17Z
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, Feb 14, 2025 at 6:06 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v24, which breaks out these recent changes to primscan
> scheduling into their own commit/patch (namely
> v24-0002-Improve-nbtree-SAOP-primitive-scan-scheduling.patch). The
> primscan scheduling improvement stuff hasn't really changed since
> v23, though (though I did polish it some more). I hope to be able to
> commit this new primscan scheduling patch sooner rather than later
> (though I don't think that it's quite committable yet).

The patch series recently bitrot due to conflicting changes on HEAD,
so I decided to post a new v25 now.

New in v25:

* Fixed a regression with parallel index scans caused by the improved
scheduling logic added by
0002-Improve-nbtree-SAOP-primitive-scan-scheduling.patch.

v24 did not account for how "firstPage=false" calls to _bt_readpage
might originate from _bt_first (not _bt_next) during parallel scans,
even during the first page for the parallel worker's primitive
scan/_bt_first call -- which made the heuristics added to
_bt_advance_array_keys do the wrong thing by not terminating primitive
scan based on faulty information. This was possible via the parallel
scan _bt_readnextpage "seized=true" path, which led to regressions. In
v24 we now pass "firstPage=true" whenever a call to _bt_readpage
happens through _bt_first, no matter the details (for the first
_bt_readpage call's page).

* The additional EXPLAIN ANALYZE logic (that shows "Index Searches:
N") added by 0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch has
been adjusted, and no longer divides by nloops.

I explain why dividing by nloops has some fairly bad consequences on
the thread I started for the quasi-independent enhancement to EXPLAIN
ANALYZE output:

https://postgr.es/m/CAH2-WzmebSkeKPGw7TEaNw9=Qx-X8fAnFw916Fd2V8VVqYqqaQ@mail.gmail.com

* Polished commit messages.

* Added more test coverage. The LOC covered percentage is now at just
over 90% for nbtutils.c. We now have coverage for almost all of the
new code that advances the scan's skip arrays, including code that
deals with NULL values that is seldom reached.

--
Peter Geoghegan