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-05-06T22:00:37Z
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, May 2, 2025 at 3:04 PM Peter Geoghegan <pg@bowt.ie> wrote:
> I would like to commit the first patch later today, ahead of shipping
> beta1. But the second patch won't make it into beta1.

Committed the first patch last Friday.

Attached is v2, whose 0002- bugfix patch is essentially unchanged
compared to v1 -- there are now comments explaining why RowCompare
keys cannot safely use the pstate.forcenonrequired behavior (in the
presence of a higher-order array). There is also a new 0001- patch
(not to be confused with the prior 0001- patch that I committed last
week).

I plan to commit everything in the next couple of days, barring any objections.

> 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. I know of only 3 queries where this
> happens, 2 of which are from my repro -- it's actually really hard to
> find an example of this, even if you go out of your way to.

The new 0001- patch addresses these concerns of mine about
pstate.forcenonrequired affecting primscan scheduling.

It turned out that this unprincipled behavioral inconsistency was only
possible because of an inconsistency in how the recheck within
_bt_scanbehind_checkkeys works in the presence of relevant truncated
high key attributes -- an inconsistency compared to similar code
within _bt_advance_array_keys. Now (with the new 0001- patch applied),
we won't allow a scan with an "almost matching" set of array keys to
continue with reading the next page in the case where the keys merely
satisfy the next page's high key's untruncated attribute prefix values
-- we won't accept it when there's uncertainty due to other arrays
pertaining to attributes that are truncated within the next page's
high key/finaltup.

There is no reason to believe that this matters on correctness ground,
or even on performance grounds, but it does seem like the principled
approach. We shouldn't cross more than one leaf page boundary before
resolving our uncertainty about whether or not stepping to the next
leaf page (i.e. not starting another primscan) is the right thing to
do.

Note again that this is a very narrow issue: it could only happen when
we advanced the array keys on a page to values that just so happen to
be exact matches for the *next* page's high key, when there were
additional keys corresponding to truncated suffix attributes in that
same next page high key. The chances of things lining up like that are
very slim indeed. But, I find the behavioral inconsistency distracting
and unprincipled, and it's easy enough to just eliminate it
altogether. I haven't formally promised that calling _bt_set_startikey
must never affect the total number of primscans (relative to an
equivalent query/scan where we just don't call it), but that feels
like a good goal.

-- 
Peter Geoghegan