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: Aleksander Alekseev <aleksander@timescale.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2024-07-02T16:55:59Z
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

On Tue, Jul 2, 2024 at 12:25 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached v2 fixes this bug. The problem was that the skip support
> function used by the "char" opclass assumed signed char comparisons,
> even though the authoritative B-Tree comparator (support function 1)
> uses signed comparisons (via uint8 casting). A simple oversight.

Although v2 gives correct answers to the queries, the scan itself
performs an excessive amount of leaf page accesses. In short, it
behaves just like a full index scan would, even though we should
expect it to skip over significant runs of the index. So that's
another bug.

It looks like the queries you posted have a kind of adversarial
quality to them, as if they were designed to confuse the
implementation. Was it intentional? Did you take them from an existing
test suite somewhere?

The custom instrumentation I use to debug these issues shows:

_bt_readpage: 🍀  1981 with 175 offsets/tuples (leftsib 4032, rightsib 3991) ➡️
 _bt_readpage first: (c, n)=(b, 998982285), TID='(1236,173)',
0x7f1464fe9fc0, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 173,
nmatching: 174 ✅
_bt_readpage: 🍀  3991 with 175 offsets/tuples (leftsib 1981, rightsib 9) ➡️
 _bt_readpage first: (c, n)=(b, 999474517), TID='(4210,9)',
0x7f1464febfc8, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 173,
nmatching: 174 ✅
_bt_readpage: 🍀  9 with 229 offsets/tuples (leftsib 3991, rightsib 3104) ➡️
 _bt_readpage first: (c, n)=(c, 1606), TID='(882,68)', 0x7f1464fedfc0,
from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
_bt_readpage: 🍀  3104 with 258 offsets/tuples (leftsib 9, rightsib 1685) ➡️
 _bt_readpage first: (c, n)=(c, 706836), TID='(3213,4)',
0x7f1464feffc0, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
*** SNIP, many more "nmatching: 0" pages appear after these two ***

The final _bt_advance_array_keys call for leaf page 3991 should be
scheduling a new primitive index scan (i.e. skipping), but that never
happens. Not entirely sure why that is, but it probably has something
to do with _bt_advance_array_keys failing to hit the
"has_required_opposite_direction_only" path for determining if another
primitive scan is required. You're using an inequality required in the
opposite-to-scan-direction here, so that path is likely to be
relevant.

-- 
Peter Geoghegan