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: Masahiro.Ikeda@nttdata.com
Cc: pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2024-07-24T21:14:54Z
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, Jul 15, 2024 at 2:34 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v3, which generalizes skip scan, allowing it to work with
> opclasses/types that lack a skip support routine. In other words, v3
> makes skip scan work for all types, including continuous types, where
> it's impractical or infeasible to add skip support.

Attached is v4, which:

* Fixes a previous FIXME item affecting range skip scans/skip arrays
used in cross-type scenarios.

* Refactors and simplifies the handling of range inequalities
associated with skip arrays more generally. We now always use
inequality scan keys during array advancement (and when descending the
tree within _bt_first), rather than trying to use a datum taken from
the range inequality as an array element directly.

This gives us cleaner separation between scan keys/data types in
cross-type scenarios: skip arrays will now only ever contain
"elements" of opclass input type. Sentinel values such as -inf are
expanded to represent "the lowest possible value that comes after the
array's low_compare lower bound, if any". Opclasses that don't offer
skip support took roughly this same approach within v3, but in v4 all
opclasses do it the same way (so opclasses with skip support use the
SK_BT_NEG_INF sentinel marking in their scan keys, though never the
SK_BT_NEXTKEY sentinel marking).

This is really just a refactoring revision. Nothing particularly
exciting here compared to v3.

-- 
Peter Geoghegan