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: Tomas Vondra <tomas@vondra.me>
Cc: Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2024-11-04T16:41:33Z
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, Oct 28, 2024 at 12:38 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v12, which is yet another revision required only so that
> the patch's latest version applies cleanly on top of master.

Attached is v13, which is the first revision posted that has new
functional changes in quite some time (this isn't just for fixing
bitrot).

The notable change for v13 is the addition of preprocessing that
adjusts skip array attributes > and < operators. These are used for
initial position purposes by _bt_first -- the purpose of this new
preprocessing/transformation is to minimize the number of descents of
the index in certain corner cases involving > and < operators, by
converting them into similar >= and <= operators during preprocessing
where possible. This transformation relies on the opclass skip support
routine, and is strictly optional.

Imagine a qual like "WHERE a > 5" AND b = 3". This will use a range
style skip array on "a", and a regular required scan key on "b". The
new transformation makes the final scan keys output by preprocessing
match what you'd get if the qual had been written "WHERE a >= 6 AND b
= 3". This leads to a modest reduction in the number of descents
required in some cases. It's possible that a naive "a > 5" initial
descent within _bt_first would have wastefully landed on an earlier
leaf page. Whereas now, with v13, our more discriminating "a >= 6 AND
b = 3" initial _bt_first descent will manage to land directly on the
true first page (the inclusion of "b = 3" in the first _bt_first call
makes this possible).

Obviously, the new transformation won't help most individual calls to
_bt_first when a skip array (with a low_compare inequality) is used,
since most individual calls will already have a real skip array
element value (not just the sentinel value -inf or +inf) to work off
of. This is not an essential optimization (it only optimizes the first
_bt_first call for the whole skip scan), but it seems worth having.
Very early versions of the patch had this same optimization, though
that was implemented in a way that wasn't compatible with cross-type
operators. The approach taken in v13 has no such problems, and does
things in a way that's very well targeted -- there's no impact on any
of the other preprocessing steps.

--
Peter Geoghegan