Horton

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

Tomas Vondra <tomas@vondra.me>

View thread
From: Tomas Vondra <tomas@vondra.me>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com
Date: 2024-09-20T13:45:25Z
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 9/19/24 21:22, Peter Geoghegan wrote:
> On Mon, Sep 16, 2024 at 6:05 PM Tomas Vondra <tomas@vondra.me> wrote:
>> For example, one of the slowed down queries is query 702 (top of page 8
>> in the PDF). The query is pretty simple:
>>
>>   explain (analyze, timing off, buffers off)
>>   select id1,id2 from t_1000000_1000_1_2
>>    where NOT (id1 in (:list)) AND (id2 = :value);
>>
>> and it was executed on a table with random data in two columns, each
>> with 1000 distinct values.
> 
> I cannot recreate this problem using the q702.sql repro you provided.
> Feels like I'm missing a step, because I find that skip scan wins
> nicely here.
> 

I don't know, I can reproduce it just fine. I just tried with v7.

What I do is this:

1) build master and patched versions:

  ./configure --enable-depend --prefix=/mnt/data/builds/$(build}/
  make -s clean
  make -s -j4 install

2) create a new cluster (default config), create DB, generate the data

3) restart cluster, drop caches

4) run the query from the SQL script

I suspect you don't do (3). I didn't mention this explicitly, my message
only said "with uncached data", so maybe that's the problem?


>> This is perfectly random data, so a great
>> match for the assumptions in costing etc.
> 
> FWIW, I wouldn't say that this is a particularly sympathetic case for
> skip scan. It's definitely still a win, but less than other cases I
> can imagine. This is due to the relatively large number of rows
> returned by the scan. Plus 1000 distinct leading values for a skip
> array isn't all that low, so we end up scanning over 1/3 of all of the
> leaf pages in the index.
> 

I wasn't suggesting it's a sympathetic case for skipscan. My point is
that it perfectly matches the costing assumptions, i.e. columns are
independent etc. But if it's not sympathetic, maybe the cost shouldn't
be 1/5 of cost from master?

> BTW, be careful to distinguish between leaf pages and internal pages
> when interpreting "Buffers:" output with the patch. Generally
> speaking, the patch repeats many internal page accesses, which needs
> to be taken into account when compare "Buffers:" counts against
> master. It's not uncommon for 3/4 or even 4/5 of all index page hits
> to be for internal pages with the patch. Whereas on master the number
> of internal page hits is usually tiny. This is one reason why the
> additional context provided by "Index Searches:" can be helpful.
> 

Yeah, I recall there's an issue with that.

>> But with uncached data, this runs in ~50 ms on master, but takes almost
>> 200 ms with skipscan (these timings are from my laptop, but similar to
>> the results).
> 
> Even 50ms seems really slow for your test case -- with or without my
> patch applied.
> 
> Are you sure that this wasn't an assert-enabled build? There's lots of
> extra assertions for the code paths used by skip scan for this, which
> could explain the apparent regression.
> 
> I find that this same query takes only ~2.056 ms with the patch. When
> I disabled skip scan locally via "set skipscan_prefix_cols = 0" (which
> should give me behavior that's pretty well representative of master),
> it takes ~12.039 ms. That's exactly what I'd expect for this query: a
> solid improvement, though not the really enormous ones that you'll see
> when skip scan is able to avoid reading many of the index pages that
> master reads.
> 

I'm pretty sure you're doing this on cached data, because 2ms is exactly
the timing I see in that case.


regards

-- 
Tomas Vondra