Horton

Re: Adding skip scan (including MDAM style range skip scan) to nbtree

Masahiro Ikeda <ikedamsh@oss.nttdata.com>

View thread
From: Masahiro Ikeda <ikedamsh@oss.nttdata.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Tomas Vondra <tomas@vondra.me>, Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2024-11-29T02:33:47Z
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 2024-11-26 07:32, Peter Geoghegan wrote:
> On Mon, Nov 25, 2024 at 4:07 AM Masahiro Ikeda 
> <ikedamsh@oss.nttdata.com> wrote:
>> One thing I am concerned about is that it reduces the cases where the
>> optimization of _bt_checkkeys_look_ahead() works effectively, as the
>> approach
>> skips the skip immediately on the first occurrence per page.
> 
> I noticed that with the recent v17 revision of the patch, my original
> MDAM paper "sales_mdam_paper" test case (the complicated query in the
> introductory email of this thread) was about 2x slower. That's just
> not okay, obviously. But the issue was relatively easy to fix: it was
> fixed by making _bt_readpage not apply the "skipskip" optimization
> when on the first page for the current primitive index scan -- we
> already do this with the "precheck" optimization, so it's natural to
> do it with the "skipskip" optimization as well.
> 
> The "sales_mdam_paper" test case involves thousands of primitive index
> scans that each access only one leaf page. But each leaf page returns
> 2 non-adjoining tuples, with quite a few non-matching tuples "in
> between" the matching tuples. There is one matching tuple for "store =
> 200", and another for "store = 250" -- and there's non-matching stores
> 201 - 249 between these two, which we want _bt_checkkeys_look_ahead to
> skip over. This is exactly the kind of case where the
> _bt_checkkeys_look_ahead() optimization is expected to help.

Great! Your new approach strikes a good balance between the trade-offs
of "skipskip" and "look ahead" optimization. Although the regression 
case
I provided seems to be a corner case, your regression case is realistic
and should be addressed.

>> Again, the above results are provided for reference, as I believe that
>> many users prioritize stability and I'd like to take your new 
>> approach.
> 
> Adversarial cases specifically designed to "make the patch look bad"
> are definitely useful review feedback. Ideally, the patch will be 100%
> free of regressions -- no matter how unlikely (or even silly) they may
> seem. I always prefer to not have to rely on anybody's opinion of what
> is likely or unlikely.  :-)
> 
> A quick test seems to show that this particular regression is more or
> less fixed by v18. As you said, the _bt_checkkeys_look_ahead stuff is
> the issue here (same with the MDAM sales query). You should confirm
> that the issue has actually been fixed, though.

Thanks to your new patch, I have confirmed that the issue is fixed.

I have no comments on the new patches. If I find any new regression
cases, I'll report them.

Regards,
-- 
Masahiro Ikeda
NTT DATA CORPORATION