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: Mark Dilger <mark.dilger@enterprisedb.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, pgsql-hackers@lists.postgresql.org, Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: 2025-06-11T22:09:55Z
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 Fri, May 2, 2025 at 3:04 PM Peter Geoghegan <pg@bowt.ie> wrote:
> The second patch is more complicated, and seems like something that
> I'll need to spend more time thinking about before proceeding with
> commit. It has subtle behavioral implications, in that it causes the
> pstate.forcenonrequired mechanism to influence when and how
> _bt_advance_array_keys schedules primitive index scans in a tiny
> minority of forward scan cases.

While I have no reason to believe that there were any problems in this
bugfix (which became commit 5f4d98d4), there were problems in the
follow-up, commit 54c6ea8c, "nbtree: Remove useless row compare arg".

I devised a new test case (which is too large to be easily posted to
this list) that shows a RowCompare query that fails with an assertion
failure (the assert added by 54c6ea8c). Here's the query:

select a, b, c, d
from fuzz_skip_scan
where b is not null and (c, d) < (60, 0)
order by a, b, c, d
limit 200 offset 80_000;

There is at least one page where _bt_set_startikey will want to apply
forcenonrequired mode while setting pstate.ikey = 1 (meaning that we
can start _bt_checkkeys calls with the "b" scan key, avoiding
maintenance of the "a" scan key). So clearly we do need support for
forcenonrequired=true + a RowCompare key. The row compare arg wasn't
so useless after all.

With commit 5f4d98d4 in place and commit 54c6ea8c reverted, everything
works here. The row compare on "(c, d)" shouldn't need to prevent
application of pstate.forcenonrequired mode here. The skip array on
"a" is bound to advance on the page anyway, so there's no risk that
we'll do the wrong thing with the RowCompare for the pstate.finaltup
call to _bt_checkkeys, that takes place after the scan's arrays have
been reset.

I'm going to revert my ill-advised commit 54c6ea8c now.

I should give this general area more thought. Some comment updates in
_bt_set_startikey seem in order, at least. But I see no reason to wait
to revert.

-- 
Peter Geoghegan