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

Hi! Sorry for my later feedback, I didn't have enough time because of my
work and the conference that was held during these two days.

On 28.03.2025 23:15, Peter Geoghegan wrote:
> On Thu, Mar 27, 2025 at 6:03 PM Alena Rybakina
> <a(dot)rybakina(at)postgrespro(dot)ru> wrote:
>> I replied an example like this:
> This example shows costs that are dominated by heap access costs. Both
> the sequential scan and the bitmap heap scan must access 637 heap
> blocks. So I don't think that this is such a great example -- the heap
> accesses are irrelevant from the point of view of assessing how well
> we're modelling index scan related costs.
You are right, the example was not very successful, to be honest I
couldn't find better example.
>> I think it would be useful to show information that we used an index scan but at the same time we skipped the "region" column and I assume we should output how many distinct values the "region" column had.
>>
>> For example it will look like this "Skip Scan on region (4 distinct values)":
>> What do you think?
> As I said on our call today, I think that we should keep the output
> for EXPLAIN ANALYZE simple. While I'm sympathetic to the idea that we
> should show more information about how quals can be applied in index
> scan node output, that seems like it should be largely independent
> work to me.
>
> Masahiro Ikeda wrote a patch that aimed to improve matters in this
> area some months back. I'm supportive of that (there is definitely
> value in signalling to users that the index might actually look quite
> different to how they imagine it looks, say by having an
> omitted-by-query prefix attribute).
Thank you for your insights and explanation. I agree that this is a
separate piece of work, and I’ll definitely take a closer
look at Masahiro Ikeda’s contributions.
> I don't exactly know what the most
> useful kind of information to show is with skip scan in place, since
> skip scan makes the general nature of quals (whether a given qual is
> what oracle calls "access predicates", or what oracle calls "filter
> predicates") is made squishy/dynamic by skip scan, in a way that is
> new.
>
> The relationship between the number of values that a skip array ever
> uses, and the number of primitive index scans is quite complicated.
> Sometimes it is actually as simple as your example query, but that's
> often not true. "Index Searches: N" can be affected by:
>
> * The use of SAOP arrays, which also influence primitive scan
> scheduling, in the same way as they have since Postgres 17 -- and can
> be mixed freely with skip arrays.
I see that this work is really voluminous and yes, I agree with you that
optimization for skipping index scanning
in terms of displaying information about changing quals, if any, can
even be done using Oracle as an example.
For example, if you introduce a new range ANY(<every possible 'a'
value>) due to skipping the first column
in the index key, it will be useful for users to know. Or if you define
a new range that the skip array will consider
during the index scan. Well, and other things related to this, but not
specifically with your patch, for example
in the case of conflicting conditions or defining boundaries in the case
of index scanning, like, when a>1 and a>10
we need to scan only a>10.

This optimization was also introduced by you earlier even before the
patch on skip optimization, but I think it also lacks
some output in the explain.

> * The availability of opclass skipsupport, which makes skip arrays
> generate their element values by addition/subtraction from the current
> array element, rather than using NEXT/PRIOR sentinel keys.
>
> The sentinel keys act as probes that get the next real (non-sentinel)
> value that we need to look up next. Whereas skip support can often
> successfully guess that (for example) the next value in the index
> after 268 is 269, saving a primitive scan each time (this might not
> happen at all, or it might work only some of the time, or it might
> work all of the time).

To be honest, I missed your point here. If possible, could you explain
it in more detail?

> * Various primitive index scan scheduling heuristics.
>
> Another concern here is that I don't want to invent a special kind of
> "index search" just for skip scan. We're going to show an "Index
> Searches: N" that's greater than 1 with SAOP array keys, too -- which
> don't use skip scan at all (nothing new about that, except for the
> fact that we report the number of searches directly from EXPLAIN
> ANALYZE in Postgres 18).

I agree with you, this is an improvement. "Index Searches: N" shows the
number of individual index searches, but
it is still not clear enough. Here you can additionally determine what
happened based on the information about
the number of scanned pages, but with large amounts of data this is
difficult.

By the way, are you planning to commit additional output to the explain
about skipped pages? I think, together with
the previous ones, the information about index scanning would be
sufficient for analysis.

Although I am still learning to understand correctly this information in
the explain.
By the way, I have long wanted to ask, maybe you can advise something
else to read on this topic?
Maybe not in this thread, so as not to overload this.
> There really is almost no difference between
> a scan with a skip array and a scan of the same index with a similar
> SAOP array (when each array "contains the same elements", and is used
> to scan the same index, in the same way). That's why the cost model is
> as similar as possible to the Postgres 17 costing of SAOP array scans
> -- it's really the same access method. Reusing the cost model makes
> sense because actual execution times are almost identical when we
> compare a skip array to a SAOP array in the way that I described.

Yes, I agree with that.

> The only advantage that I see from putting something about "skip scan"
> in EXPLAIN ANALYZE is that it is more googleable that way. But it
> seems like "Index Searches: N" is almost as good, most of the time. In
> any case, the fact that we don't need a separate optimizer index
> path/executor node for this is something that I see as a key
> advantage, and something that I'd like EXPLAIN ANALYZE to preserve.
I think it is worth adding "skip scan" information, without it it is
difficult in my opinion to evaluate
whether this index is effective in comparison with another, looking only
at the information on
scanned blocks or Index search or I missed something?

I'm not sure that I correctly understood about "separation optimizer
index path/executor stage". Do you mean that it's better to do all the
optimizations during index execution rather than during index execution?
I just remember you mentioned the Goetz Graefe interview on the call and
and this was precisely his point of view, with which you agree. Is that
what you mean?

> The problem with advertising that an index scan node is a skip scan
> is: what if it just never skips? Never skipping like this isn't
> necessarily unexpected. And even if it is unexpected, it's not
> necessarily a problem.

I agree that there may not be a place for this to be used, but it is
worth showing information about it if it does happen.

On the other hand, here we need to be able to determine when it was
necessary to perform skip scan optimization, but
it was not there. But I'm not sure that it is possible to display this
in the explain - only when analyzing the received query plan,
namely the buffer statistics.

>> I didn't see any regression tests. Maybe we should add some tests? To be honest I didn't see it mentioned in the commit message but I might have missed something.
> There are definitely new regression tests -- I specifically tried to
> keep the test coverage high, using gcov html reports (like the ones
> from coverage.postgresql.org) The test updates appear towards the end
> of the big patch file, though. Maybe you're just not used to seeing
> tests appear last like this?
>
> I use "git config diff.orderfile ... " to get this behavior. I find it
> useful to put the important changes (particularly header file changes)
> first, and less important changes (like tests) much later.
>
> Thanks for taking a look at my patch!

Yes, indeed, everything is in place, sorry, I didn't notice it right
away, I'll be more attentive and I'll take note of your advice about the
git - I haven't used such methods before)

--
Regards,
Alena Rybakina
Postgres Professional