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

Hi Masahiro,

On Tue, Nov 19, 2024 at 3:30 AM Masahiro Ikeda <ikedamsh(at)oss(dot)nttdata(dot)com> wrote:
> Apologies for the delayed response. I've confirmed that the costing is
> significantly
> improved for multicolumn indexes in the case I provided. Thanks!
> https://www.postgresql.org/message-id/TYWPR01MB10982A413E0EC4088E78C0E11B1A62%40TYWPR01MB10982.jpnprd01.prod.outlook.com

Great! I made it one of my private/internal test cases for the
costing. Your test case was quite helpful.

Attached is v15. It works through your feedback.

Importantly, v15 has a new patch which has a fix for your test.sql
case -- which is the most important outstanding problem with the patch
(and has been for a long time now). I've broken those changes out into
a separate patch because they're still experimental, and have some
known minor bugs. But it works well enough for you to assess how close
I am to satisfactorily fixing the known regressions, so it seems worth
posting quickly.

> IIUC, why not add it to the documentation? It would clearly help users
> understand how to tune their queries using the counter, and it would
> also show that the counter is not just for developers.

The documentation definitely needs more work. I have a personal TODO
item about that.

Changes to the documentation can be surprisingly contentious, so I
often work on it last, when we have the clearest picture of how to
talk about the feature. For example, Matthias said something that's
approximately the opposite of what you said about it (though I agree
with you about it).

> From the perspective of consistency, wouldn't it be better to align the
> naming
> between the EXPLAIN output and pg_stat_all_indexes.idx_scan, even though
> the
> documentation states they refer to the same concept?
>
> I personally prefer something like "search" instead of "scan", as "scan"
> is
> commonly associated with node names like Index Scan and similar terms.
> To maintain
> consistency, how about renaming pg_stat_all_indexes.idx_scan to
> pg_stat_all_indexes.idx_search?

I suspect that other hackers will reject that proposal on
compatibility grounds, even though it would make sense in a "green
field" situation.

Honestly, discussions about UI/UX details such as EXPLAIN ANALYZE
always tend to result in unproductive bikeshedding. What I really want
is something that will be acceptable to all parties. I don't have any
strong opinions of my own about it -- I just think that it's important
to show *something* like "Index Searches: N" to make skip scan user
friendly.

> (3)
>
> > v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch
>
> The counter should be added in blgetbitmap().

Fixed.

> (4)
>
> > v14-0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch
> > doc/src/sgml/bloom.sgml
>
> The below forgot "Index Searches: 1".
>
> -&gt; Bitmap Index Scan on btreeidx2 (cost=0.00..12.04
> rows=500 width=0) (never executed)
> Index Cond: (i2 = 898732)
> Planning Time: 0.491 ms
> Execution Time: 0.055 ms
> (10 rows)

Fixed (though I made it show "Index Searches: 0" instead, since this
particular index scan node is "never executed").

> Although we may not need to fix it, due to the support for skip scan,
> the B-tree
> index is now selected over the Bloom index in my environment.

I am not inclined to change it.

> Although I tested with various data types such as int, uuid, oid, and
> others on my
> local PC, I could only identify the regression case that you already
> mentioned.

That's good news!

> Although it's not an optimal solution and would only reduce the degree
> of performance
> degradation, how about introducing a threshold per page to switch from
> skip scan to full
> index scan?

The approach to fixing these regressions from the new experimental
patch doesn't need to use any such threshold. It is effective both
with simple "WHERE id2 = 100" cases (like the queries from your
test.sql test case), as well as more complicated "WHERE id2 BETWEEN 99
AND 101" inequality cases.

What do you think? The regressions are easily under 5% with the new
patch applied, which is in the noise.

At the same time, we're just as capable of skipping whenever the scan
encounters a large group of skipped-prefix-column duplicates. For
example, if I take your test.sql test case and add another insert that
adds such a group (e.g., "INSERT INTO t SELECT 55, i FROM
generate_series(-1000000, 1000000) i;" ), and then re-run the query,
the scan is exactly as fast as before -- it just skips to get over the
newly inserted "55" group of tuples. Obviously, this also makes the
master branch far, far slower.

As I've said many times already, the need to be flexible and offer
robust performance in cases where skipping is either very effective or
very ineffective *during the same index scan* seems very important to
me. This "55" variant of your test.sql test case is a great example of
the kinds of cases I was thinking about.

> Is it better to move prev_numSkipArrayKeys =*numSkipArrayKeys after the
> while loop?
> For example, the index below should return *numSkipArrayKeys = 0 instead
> of 1
> if the id3 type does not support eq_op.
>
> * index: CREATE INDEX test_idx on TEST (id1 int, id2 int, id3 no_eq_op,
> id4 int);
> * query: SELECT * FROM test WHERE id4 = 10;

Nice catch! You're right. Fixed this in v15, too.

Thanks for the review
--
Peter Geoghegan