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

May I suggest a fix/improvement regarding "so->skipScan = false;" being
set in "btbeginscan":
https://github.com/postgres/postgres/blob/b8a1bdc458e3e81898a1fe3d26188bc1dcbac965/src/backend/access/nbtree/nbtree.c#L356
.

It should also be reset in "btrescan": i.e. when we rescan the index, we
should also reset "so->skipScan = false".

Our Timescaledb extension has scenarios changing ">" quals to "=" and back
on rescan and it breaks when so->Skipscan needs to be reset from true to
false.
I'm not aware of any such scenarios in regular PG but they might come up in
the future. It's a small and safe tweak it seems, hopefully it can get into
PG18 release.

Thank you,
Natalya Aksman
Senior Software Engineer, TigerData

On Wed, Sep 10, 2025 at 9:34 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

> 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
>