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

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

From

Peter Geoghegan

Date:

26 June 2024, 19:16:07

Attached is a POC patch that adds skip scan to nbtree. The patch
teaches nbtree index scans to efficiently use a composite index on
'(a, b)' for queries with a predicate such as "WHERE b = 5". This is
feasible in cases where the total number of distinct values in the
column 'a' is reasonably small (think tens or hundreds, perhaps even
thousands for very large composite indexes).

In effect, a skip scan treats this composite index on '(a, b)' as if
it was a series of subindexes -- one subindex per distinct value in
'a'. We can exhaustively "search every subindex" using an index qual
that behaves just like "WHERE a = ANY(<every possible 'a' value>) AND
b = 5" would behave.

This approach might be much less efficient than an index scan that can
use an index on 'b' alone, but skip scanning can still be orders of
magnitude faster than a sequential scan. The user may very well not
have a dedicated index on 'b' alone, for whatever reason.

Note that the patch doesn't just target these simpler "skip leading
index column omitted from the predicate" cases. It's far more general
than that -- skipping attributes (or what the patch refers to as skip
arrays) can be freely mixed with SAOPs/conventional arrays, in any
order you can think of. They can also be combined with inequalities to
form range skip arrays.

This patch is a direct follow-up to the Postgres 17 work that became
commit 5bf748b8. Making everything work well together is an important
design goal here. I'll talk more about that further down, and will
show a benchmark example query that'll give a good general sense of
the value of the patch with these more complicated cases.

A note on terminology
=====================

The terminology in this area has certain baggage. Many of us will
recall the patch that implemented loose index scan. That patch also
dubbed itself "skip scan", but that doesn't seem right to me (it's at
odds with how other RDBMSs describe features in this area). I would
like to address the issues with the terminology in this area now, to
avoid creating further confusion.

When I use the term "skip scan", I'm referring to a feature that's
comparable to the skip scan features from Oracle and MySQL 8.0+. This
*isn't* at all comparable to the feature that MySQL calls "loose index
scan" -- don't confuse the two features.

Loose index scan is a far more specialized technique than skip scan.
It only applies within special scans that feed into a DISTINCT group
aggregate. Whereas my skip scan patch isn't like that at all -- it's
much more general. With my patch, nbtree has exactly the same contract
with the executor/core code as before. There are no new index paths
generated by the optimizer to make skip scan work, even. Skip scan
isn't particularly aimed at improving group aggregates (though the
benchmark I'll show happens to involve a group aggregate, simply
because the technique works best with large and expensive index
scans).

My patch is an additive thing, that speeds up what we'd currently
refer to as full index scans (as well as range index scans that
currently do a "full scan" of a range/subset of an index). These index
paths/index scans can no longer really be called "full index scans",
of course, but they're still logically the same index paths as before.

MDAM and skip scan
==================

As I touched on already, the patch actually implements a couple of
related optimizations. "Skip scan" might be considered one out of the
several optimizations from the 1995 paper "Efficient Search of
Multidimensional B-Trees" [1] -- the paper describes skip scan under
its "Missing Key Predicate" subsection. I collectively refer to the
optimizations from the paper as the "MDAM techniques".

Alternatively, you could define these MDAM techniques as each
implementing some particular flavor of skip scan, since they all do
rather similar things under the hood. In fact, that's how I've chosen
to describe things in my patch: it talks about skip scan, and about
range skip scan, which is considered a minor variant of skip scan.
(Note that the term "skip scan" is never used in the MDAM paper.)

MDAM is short for "multidimensional access method". In the context of
the paper, "dimension" refers to dimensions in a decision support
system. These dimensions are represented by low cardinality columns,
each of which appear in a large composite B-Tree index. The emphasis
in the paper (and for my patch) is DSS and data warehousing; OLTP apps
typically won't benefit as much.

Note: Loose index scan *isn't* described by the paper at all. I also
wouldn't classify loose index scan as one of the MDAM techniques. I
think of it as being in a totally different category, due to the way
that it applies semantic information. No MDAM technique will ever
apply high-level semantic information about what is truly required by
the plan tree, one level up. And so my patch simply teaches nbtree to
find the most efficient way of navigating through an index, based
solely on information that is readily available to the scan. The same
principles apply to all of the other MDAM techniques; they're
basically all just another flavor of skip scan (that do some kind of
clever preprocessing/transformation that enables reducing the scan to
a series of disjunctive accesses, and that could be implemented using
the new abstraction I'm calling skip arrays).

The paper more or less just applies one core idea, again and again.
It's surprising how far that one idea can take you. But it is still
just one core idea (don't overlook that point).

Range skip scan
---------------

To me, the most interesting MDAM technique is probably one that I
refer to as "range skip scan" in the patch. This is the technique that
the paper introduces first, in its "Intervening Range Predicates"
subsection. The best way of explaining it is through an example (you
could also just read the paper, which has an example of its own).

Imagine a table with just one index: a composite index on "(pdate,
customer_id)". Further suppose we have a query such as:

SELECT * FROM payments WHERE pdate BETWEEN '2024-01-01' AND
'2024-01-30' AND customer_id = 5; -- both index columns (pdate and
customer_id) appear in predicate

The patch effectively makes the nbtree code execute the index scan as
if the query had been written like this instead:

SELECT * FROM payments WHERE pdate = ANY ('2024-01-01', '2024-01-02',
..., '2024-01-30') AND customer_id = 5;

The use of a "range skip array" within nbtree allows the scan to skip
when that makes sense, locating the next date with customer_id = 5
each time (we might skip over many irrelevant leaf pages each time).
The scan must also *avoid* skipping when it *doesn't* make sense.

As always (since commit 5bf748b8 went in), whether and to what extent
we skip using array keys depends in large part on the physical
characteristics of the index at runtime. If the tuples that we need to
return are all clustered closely together, across only a handful of
leaf pages, then we shouldn't be skipping at all. When skipping makes
sense, we should skip constantly.

I'll discuss the trade-offs in this area a little more below, under "Design".

Using multiple MDAM techniques within the same index scan (includes benchmark)
------------------------------------------------------------------------------

I recreated the data in the MDAM paper's "sales" table by making
inferences from the paper. It's very roughly the same data set as the
paper (close enough to get the general idea across). The table size is
about 51GB, and the index is about 25GB (most of the attributes from
the table are used as index columns). There is nothing special about
this data set -- I just thought it would be cool to "recreate" the
queries from the paper, as best I could. Thought that this approach
might make my points about the design easier to follow.

The index we'll be using for this can be created via: "create index
mdam_idx on sales_mdam_paper(dept, sdate, item_class, store)". Again,
this is per the paper. It's also the order that the columns appear in
every WHERE clause in every query from the paper.

(That said, the particular column order from the index definition
mostly doesn't matter. Every index column is a low cardinality column,
so unless the order used completely obviates the need to skip a column
that would otherwise need to be skipped, such as "dept", the effect on
query execution time from varying column order is in the noise.
Obviously that's very much not how users are used to thinking about
composite indexes.)

The MDAM paper has numerous example queries, each of which builds on
the last, adding one more complication each time -- each of which is
addressed by another MDAM technique. The query I'll focus on here is
an example query that's towards the end of the paper, and so combines
multiple techniques together -- it's the query that appears in the "IN
Lists" subsection:

select
  dept,
  sdate,
  item_class,
  store,
  sum(total_sales)
from
  sales_mdam_paper
where
  -- omitted: leading "dept" column from composite index
  sdate between '1995-06-01' and '1995-06-30'
  and item_class in (20, 35, 50)
  and store in (200, 250)
group by dept, sdate, item_class, store
order by dept, sdate, item_class, store;

On HEAD, when we run this query we either get a sequential scan (which
is very slow) or a full index scan (which is almost as slow). Whereas
with the patch, nbtree will execute the query as a succession of a few
thousand very selective primitive index scans (which usually only scan
one leaf page, though some may scan two neighboring leaf pages).

Results: The full index scan on HEAD takes about 32 seconds. With the
patch, the query takes just under 52ms to execute. That works out to
be about 630x faster with the patch.

See the attached SQL file for full details. It provides all you'll
need to recreate this test result with the patch.

Nobody would put up with such an inefficient full index scan in the
first place, so the behavior on HEAD is not really a sensible baseline
-- 630x isn't very meaningful. I could have come up with a case that
showed an even larger improvement if I'd felt like it, but that
wouldn't have proven anything.

The important point is that the patch makes a huge composite index
like the one I've built for this actually make sense, for the first
time. So we're not so much making something faster as enabling a whole
new approach to indexing -- particularly for data warehousing use
cases. The way that Postgres DBAs choose which indexes they'll need to
create is likely to be significantly changed by this optimization.

I'll break down how this is possible. This query makes use of 3
separate MDAM techniques:

1. A "simple" skip scan (on "dept").

2. A "range" skip scan (on "sdate").

3. The pair of IN() lists/SAOPs on item_class and on store. (Nothing
new here, except that nbtree needs these regular SAOP arrays to roll
over the higher-order skip arrays to trigger moving on to the next
dept/date.)

Internally, we're just doing a series of several thousand distinct
non-overlapping accesses, in index key space order (so as to preserve
the appearance of one continuous index scan). These accesses starts
out like this:

dept=INT_MIN, date='1995-06-01', item_class=20, store=200
    (Here _bt_advance_array_keys discovers that the actual lowest dept
is 1, not INT_MIN)
dept=1, date='1995-06-01', item_class=20, store=200
dept=1, date='1995-06-01', item_class=20, store=250
dept=1, date='1995-06-01', item_class=35, store=200
dept=1, date='1995-06-01', item_class=35, store=250
...

(Side note: as I mentioned, each of the two "store" values usually
appear together on the same leaf page in practice. Arguably I should
have shown 2 lines/accesses here (for "dept=1"), rather than showing
4. The 4 "dept=1" lines shown required only 2 primitive index
scans/index descents/leaf page reads. Disjunctive accesses don't
necessarily map 1:1 with primitive/physical index scans.)

About another ten thousand similar accesses occur (omitted for
brevity). Execution of the scan within nbtree finally ends with these
primitive index scans/accesses:
...
dept=100, date='1995-06-30', item_class=50, store=250
dept=101, date='1995-06-01', item_class=20, store=200
STOP

There is no "dept=101" entry in the index (the highest department in
the index happens to be 100). The index scan therefore terminates at
this point, having run out of leaf pages to scan (we've reached the
rightmost point of the rightmost leaf page, as the scan attempts to
locate non-existent dept=101 tuples).

Design
======

Since index scans with skip arrays work just like index scans with
regular arrays (as of Postgres 17), naturally, there are no special
restrictions. Associated optimizer index paths have path keys, and so
could (just for example) appear in a merge join, or feed into a group
aggregate, while avoiding a sort node. Index scans that skip could
also feed into a relocatable cursor.

As I mentioned already, the patch adds a skipping mechanism that is
purely an additive thing. I think that this will turn out to be an
important enabler of using the optimizations, even when there's much
uncertainty about how much they'll actually help at runtime.

Optimizer
---------

We make a broad assumption that skipping is always to our advantage
during nbtree preprocessing -- preprocessing generates as many skip
arrays as could possibly make sense based on static rules (rules that
don't apply any kind of information about data distribution). Of
course, skipping isn't necessarily the best approach in all cases, but
that's okay. We only actually skip when physical index characteristics
show that it makes sense. The real decisions about skipping are all
made dynamically.

That approach seems far more practicable than preempting the problem
during planning or during nbtree preprocessing. It seems like it'd be
very hard to model the costs statistically. We need revisions to
btcostestimate, of course, but the less we can rely on btcostestimate
the better. As I said, there are no new index paths generated by the
optimizer for any of this.

What do you call an index scan where 90% of all index tuples are 1 of
only 3 distinct values, while the remaining 10% of index tuples are
all perfectly unique in respect of a leading column? Clearly the best
strategy when skipping using the leading column to "use skip scan for
90% of the index, and use a conventional range scan for the remaining
10%". Skipping generally makes sense, but we legitimately need to vary
our strategy *during the same index scan*. It makes no sense to think
of skip scan as a discrete sort of index scan.

I have yet to prove that always having the option of skipping (even
when it's very unlikely to help) really does "come for free" -- for
now I'm just asserting that that's possible. I'll need proof. I expect
to hear some principled skepticism on this point. It's probably not
quite there in this v1 of the patch -- there'll be some regressions (I
haven't looked very carefully just yet). However, we seem to already
be quite close to avoiding regressions from excessive/useless
skipping.

Extensible infrastructure/support functions
-------------------------------------------

Currently, the patch only supports skip scan for a subset of all
opclasses -- those that have the required support function #6, or
"skip support" function. This provides the opclass with (among other
things) a way to increment the current skip array value (or to
decrement it, in the case of backward scans). In practice we only have
this for a handful of discrete integer (and integer-ish) types. Note
that the patch currently cannot skip for an index column that happens
to be text. Note that even this v1 supports skip scans that use
unsupported types, provided that the input opclass of the specific
columns we'll need to skip has support.

The patch should be able to support every type/opclass as a target for
skipping, regardless of whether an opclass support function happened
to be available. That could work by teaching the nbtree code to have
explicit probes for the next skip array value in the index, only then
combining that new value with the qual from the input scan keys/query.
I've put that off for now because it seems less important -- it
doesn't really affect anything I've said about the core design, which
is what I'm focussing on for now.

It makes sense to use increment/decrement whenever feasible, even
though it isn't strictly necessary (or won't be, once the patch has
the required explicit probe support). The only reason to not apply
increment/decrement opclass skip support (that I can see) is because
it just isn't practical (this is generally the case for continuous
types). While it's slightly onerous to have to invent all this new
opclass infrastructure, it definitely makes sense.

There is a performance advantage to having skip arrays that can
increment through each distinct possible indexable value (this
increment/decrement stuff comes from the MDAM paper). The MDAM
techniques inherently work best when "skipping" columns of discrete
types like integer and date, which is why the paper has examples that
all look like that. If you look at my example query and its individual
accesses, you'll realize why this is so.

Thoughts?

[1] https://vldb.org/conf/1995/P710.PDF
--
Peter Geoghegan

On Tue, Jul 2, 2024 at 9:40 AM Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Tue, Jul 2, 2024 at 9:30 AM Peter Geoghegan <pg@bowt.ie> wrote:
> > > EXPLAIN [ANALYZE] SELECT COUNT(*) FROM test1 WHERE n > 900_000_000;
> >
> > For example, this first test query goes from needing a full index scan
> > that has 5056 buffer hits to a skip scan that requires only 12 buffer
> > hits.
>
> Actually, looks like that's an invalid result. The "char" opclass
> support function appears to have bugs.

Attached v2 fixes this bug. The problem was that the skip support
function used by the "char" opclass assumed signed char comparisons,
even though the authoritative B-Tree comparator (support function 1)
uses signed comparisons (via uint8 casting). A simple oversight. Your
test cases will work with this v2, provided you use "char" (instead of
unadorned char) in the create table statements.

Another small change in v2: I added a DEBUG2 message to nbtree
preprocessing, indicating the number of attributes that we're going to
skip. This provides an intuitive way to see whether the optimizations
are being applied in the first place. That should help to avoid
further confusion like this as the patch continues to evolve.

Support for char(1) doesn't seem feasible within the confines of a
skip support routine. Just like with text (which I touched on in the
introductory email), this will require teaching nbtree to perform
explicit next-key probes. An approach based on explicit probes is
somewhat less efficient in some cases, but it should always work. It's
impractical to write opclass support that (say) increments a char
value 'a' to 'b'. Making that approach work would require extensive
cooperation from the collation provider, and some knowledge of
encoding, which just doesn't make sense (if it's possible at all). I
don't have the problem with "char" because it isn't a collatable type
(it is essentially the same thing as an uint8 integer type, except
that it outputs printable ascii characters).

FWIW, your test cases don't seem like particularly good showcases for
the patch. The queries you came up with require a relatively large
amount of random I/O when accessing the heap, which skip scan will
never help with -- so skip scan is a small win (at least relative to
an unoptimized full index scan). Obviously, no skip scan can ever
avoid any required heap accesses compared to a naive full index scan
(loose index scan *does* have that capability, which is possible only
because it applies semantic information in a way that's very
different).

FWIW, a more sympathetic version of your test queries would have
involved something like "WHERE n = 900_500_000". That would allow the
implementation to perform a series of *selective* primitive index
scans (one primitive index scan per "c" column/char grouping). That
change has the effect of allowing the scan to skip over many
irrelevant leaf pages, which is of course the whole point of skip
scan. It also makes the scan will require far fewer heap accesses, so
heap related costs no longer drown out the nbtree improvements.

--
Peter Geoghegan

Attachment

v2-0001-Add-skip-scan-to-nbtree.patch

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

From

Peter Geoghegan

Date:

02 July 2024, 16:55:59

On Tue, Jul 2, 2024 at 12:25 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached v2 fixes this bug. The problem was that the skip support
> function used by the "char" opclass assumed signed char comparisons,
> even though the authoritative B-Tree comparator (support function 1)
> uses signed comparisons (via uint8 casting). A simple oversight.

Although v2 gives correct answers to the queries, the scan itself
performs an excessive amount of leaf page accesses. In short, it
behaves just like a full index scan would, even though we should
expect it to skip over significant runs of the index. So that's
another bug.

It looks like the queries you posted have a kind of adversarial
quality to them, as if they were designed to confuse the
implementation. Was it intentional? Did you take them from an existing
test suite somewhere?

The custom instrumentation I use to debug these issues shows:

_bt_readpage: 🍀  1981 with 175 offsets/tuples (leftsib 4032, rightsib 3991) ➡️
 _bt_readpage first: (c, n)=(b, 998982285), TID='(1236,173)',
0x7f1464fe9fc0, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 173,
nmatching: 174 ✅
_bt_readpage: 🍀  3991 with 175 offsets/tuples (leftsib 1981, rightsib 9) ➡️
 _bt_readpage first: (c, n)=(b, 999474517), TID='(4210,9)',
0x7f1464febfc8, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 173,
nmatching: 174 ✅
_bt_readpage: 🍀  9 with 229 offsets/tuples (leftsib 3991, rightsib 3104) ➡️
 _bt_readpage first: (c, n)=(c, 1606), TID='(882,68)', 0x7f1464fedfc0,
from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
_bt_readpage: 🍀  3104 with 258 offsets/tuples (leftsib 9, rightsib 1685) ➡️
 _bt_readpage first: (c, n)=(c, 706836), TID='(3213,4)',
0x7f1464feffc0, from non-pivot offnum 2 started page
 _bt_readpage final:  , (nil), continuescan high key check did not set
so->currPos.moreRight=false ➡️  🟢
 _bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
*** SNIP, many more "nmatching: 0" pages appear after these two ***

The final _bt_advance_array_keys call for leaf page 3991 should be
scheduling a new primitive index scan (i.e. skipping), but that never
happens. Not entirely sure why that is, but it probably has something
to do with _bt_advance_array_keys failing to hit the
"has_required_opposite_direction_only" path for determining if another
primitive scan is required. You're using an inequality required in the
opposite-to-scan-direction here, so that path is likely to be
relevant.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

02 July 2024, 17:09:27

On Tue, Jul 2, 2024 at 12:55 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Although v2 gives correct answers to the queries, the scan itself
> performs an excessive amount of leaf page accesses. In short, it
> behaves just like a full index scan would, even though we should
> expect it to skip over significant runs of the index. So that's
> another bug.

Hit "send" too soon. I simply forgot to run "alter table test1 alter
column c type "char";" before running the query. So, I was mistaken
about there still being a bug in v2. The issue here is that we don't
have support for the underlying type, char(1) -- nothing more.

v2 of the patch with your query 1 (when changed to use the "char"
type/opclass instead of the currently unsupported char(1)
type/opclass) performs 395 index related buffer hits, and 5406 heap
block accesses. Whereas it's 3833 index buffer hits with master
(naturally, the same 5406 heap accesses are required with master). In
short, this query isn't particularly sympathetic to the patch. Nor is
it unsympathetic.

--
Peter Geoghegan

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

From

Aleksander Alekseev

Date:

05 July 2024, 11:03:51

Hi Peter,

> It looks like the queries you posted have a kind of adversarial
> quality to them, as if they were designed to confuse the
> implementation. Was it intentional?

To some extent. I merely wrote several queries that I would expect
should benefit from skip scans. Since I didn't look at the queries you
used there was a chance that I will hit something interesting.

> Attached v2 fixes this bug. The problem was that the skip support
> function used by the "char" opclass assumed signed char comparisons,
> even though the authoritative B-Tree comparator (support function 1)
> uses signed comparisons (via uint8 casting). A simple oversight. Your
> test cases will work with this v2, provided you use "char" (instead of
> unadorned char) in the create table statements.

Thanks for v2.

> If you change your table definition to CREATE TABLE test1(c "char", n
> bigint), then your example queries can use the optimization. This
> makes a huge difference.

You are right, it does.

Test1 takes 33.7 ms now (53 ms before the path, x1.57)

Test3 I showed before contained an error in the table definition
(Postgres can't do `n bigint, s text DEFAULT 'text_value' || n`). Here
is the corrected test:

```
CREATE TABLE test3(c "char", n bigint, s text);
CREATE INDEX test3_idx ON test3 USING btree(c,n) INCLUDE(s);

INSERT INTO test3
  SELECT chr(ascii('a') + random(0,2)) AS c,
         random(0, 1_000_000_000) AS n,
         'text_value_' || random(0, 1_000_000_000) AS s
  FROM generate_series(0, 1_000_000);

EXPLAIN ANALYZE SELECT s FROM test3 WHERE n < 10_000;
```

It runs fast (< 1 ms) and uses the index, as expected.

Test2 with "char" doesn't seem to benefit from the patch anymore
(pretty sure it did in v1). It always chooses Parallel Seq Scans even
if I change the condition to `WHERE n > 999_995_000` or `WHERE n =
999_997_362`. Is it an expected behavior?

I also tried Test4 and Test5.

In Test4 I was curious if scip scans work properly with functional indexes:

```
CREATE TABLE test4(d date, n bigint);
CREATE INDEX test4_idx ON test4 USING btree(extract(year from d),n);

INSERT INTO test4
  SELECT ('2024-' || random(1,12) || '-' || random(1,28)) :: date AS d,
         random(0, 1_000_000_000) AS n
  FROM generate_series(0, 1_000_000);

EXPLAIN ANALYZE SELECT COUNT(*) FROM test4 WHERE n > 900_000_000;
```

The query uses Index Scan, however the performance is worse than with
Seq Scan chosen before the patch. It doesn't matter if I choose '>' or
'=' condition.

Test5 checks how skip scans work with partial indexes:

```
CREATE TABLE test5(c "char", n bigint);
CREATE INDEX test5_idx ON test5 USING btree(c, n) WHERE n > 900_000_000;

INSERT INTO test5
  SELECT chr(ascii('a') + random(0,2)) AS c,
         random(0, 1_000_000_000) AS n
  FROM generate_series(0, 1_000_000);

EXPLAIN ANALYZE SELECT COUNT(*) FROM test5 WHERE n > 950_000_000;
```

It runs fast and choses Index Only Scan. But then I discovered that
without the patch Postgres also uses Index Only Scan for this query. I
didn't know it could do this - what is the name of this technique? The
query takes 17.6 ms with the patch, 21 ms without the patch. Not a
huge win but still.

That's all I have for now.

--
Best regards,
Aleksander Alekseev

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

From

Peter Geoghegan

Date:

06 July 2024, 00:44:50

On Fri, Jul 5, 2024 at 7:04 AM Aleksander Alekseev
<aleksander@timescale.com> wrote:
> Test2 with "char" doesn't seem to benefit from the patch anymore
> (pretty sure it did in v1). It always chooses Parallel Seq Scans even
> if I change the condition to `WHERE n > 999_995_000` or `WHERE n =
> 999_997_362`. Is it an expected behavior?

The "char" opclass's skip support routine was totally broken in v1, so
its performance isn't really relevant. In any case v2 didn't make any
changes to the costing, so I'd expect it to use exactly the same query
plan as v1.

> The query uses Index Scan, however the performance is worse than with
> Seq Scan chosen before the patch. It doesn't matter if I choose '>' or
> '=' condition.

That's because the index has a leading/skipped column of type
"numeric", which isn't a supported type just yet (a supported B-Tree
opclass, actually).

The optimization is effective if you create the expression index with
a cast to integer:

CREATE INDEX test4_idx ON test4 USING btree(((extract(year from d))::int4),n);

This performs much better. Now I see "DEBUG:  skipping 1 index
attributes" when I run the query "EXPLAIN (ANALYZE, BUFFERS) SELECT
COUNT(*) FROM test4 WHERE n > 900_000_000", which indicates that the
optimization has in fact been used as expected. There are far fewer
buffers hit with this version of your test4, which also indicates that
the optimization has been effective.

Note that the original numeric expression index test4 showed "DEBUG:
skipping 0 index attributes" when the test query ran, which indicated
that the optimization couldn't be used. I suggest that you look out
for that, by running "set client_min_messages to debug2;" from psql
when testing the patch.

> It runs fast and choses Index Only Scan. But then I discovered that
> without the patch Postgres also uses Index Only Scan for this query. I
> didn't know it could do this - what is the name of this technique?

It is a full index scan. These have been possible for many years now
(possibly well over 20 years).

Arguably, the numeric case that didn't use the optimization (your
test4) should have been costed as a full index scan, but it wasn't --
that's why you didn't get a faster sequential scan, which would have
made a little bit more sense. In general, the costing changes in the
patch are very rough.

That said, this particular problem (the test4 numeric issue) should be
fixed by inventing a way for nbtree to use skip scan with types that
lack skip support. It's not primarily a problem with the costing. At
least not in my mind.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

06 July 2024, 00:57:58

On Fri, Jul 5, 2024 at 8:44 PM Peter Geoghegan <pg@bowt.ie> wrote:
> CREATE INDEX test4_idx ON test4 USING btree(((extract(year from d))::int4),n);
>
> This performs much better. Now I see "DEBUG:  skipping 1 index
> attributes" when I run the query "EXPLAIN (ANALYZE, BUFFERS) SELECT
> COUNT(*) FROM test4 WHERE n > 900_000_000", which indicates that the
> optimization has in fact been used as expected. There are far fewer
> buffers hit with this version of your test4, which also indicates that
> the optimization has been effective.

Actually, with an index-only scan it is 281 buffer hits (including
some small number of VM buffer hits) with the patch, versus 2736
buffer hits on master. So a big change to the number of index page
accesses only.

If you use a plain index scan for this, then the cost of random heap
accesses totally dominates, so skip scan cannot possibly give much
benefit. Even a similar bitmap scan requires 4425 distinct heap page accesses,
which is significantly more than the total number of index pages in
the index. 4425 heap pages is almost the entire table; the table
consists of 4480 mainfork blocks.

This is a very nonselective query. It's not at all surprising that
this query (and others like it) hardly benefit at all, except when we
can use an index-only scan (so that the cost of heap accesses doesn't
totally dominate).

--
Peter Geoghegan

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

From

Date:

12 July 2024, 05:18:56

Hi,

Since I'd like to understand the skip scan to improve the EXPLAIN output
for multicolumn B-Tree Index[1], I began to try the skip scan with some
queries and look into the source code.

I have some feedback and comments.

(1)

At first, I was surprised to look at your benchmark result because the skip scan
index can improve much performance. I agree that there are many users to be
happy with the feature for especially OLAP use-case. I expected to use v18.


(2)

I found the cost is estimated to much higher if the number of skipped attributes
is more than two. Is it expected behavior?

# Test result. The attached file is the detail of tests.

-- Index Scan
-- The actual time is low since the skip scan works well
-- But the cost is higher than one of seqscan
EXPLAIN (ANALYZE, BUFFERS, VERBOSE) SELECT * FROM test WHERE id3 = 101;
                                                              QUERY PLAN
               

---------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_id1_id2_id3 on public.test  (cost=0.42..26562.77 rows=984 width=20) (actual time=0.051..15.533
rows=991loops=1) 
   Output: id1, id2, id3, value
   Index Cond: (test.id3 = 101)
   Buffers: shared hit=4402
 Planning:
   Buffers: shared hit=7
 Planning Time: 0.234 ms
 Execution Time: 15.711 ms
(8 rows)

-- Seq Scan
-- actual time is high, but the cost is lower than one of the above Index Scan.
EXPLAIN (ANALYZE, BUFFERS, VERBOSE) SELECT * FROM test WHERE id3 = 101;
                                                          QUERY PLAN
       

-------------------------------------------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..12676.73 rows=984 width=20) (actual time=0.856..113.861 rows=991 loops=1)
   Output: id1, id2, id3, value
   Workers Planned: 2
   Workers Launched: 2
   Buffers: shared hit=6370
   ->  Parallel Seq Scan on public.test  (cost=0.00..11578.33 rows=410 width=20) (actual time=0.061..102.016 rows=330
loops=3)
         Output: id1, id2, id3, value
         Filter: (test.id3 = 101)
         Rows Removed by Filter: 333003
         Buffers: shared hit=6370
         Worker 0:  actual time=0.099..98.014 rows=315 loops=1
           Buffers: shared hit=2066
         Worker 1:  actual time=0.054..97.162 rows=299 loops=1
           Buffers: shared hit=1858
 Planning:
   Buffers: shared hit=19
 Planning Time: 0.194 ms
 Execution Time: 114.129 ms
(18 rows)


I look at btcostestimate() to find the reason and found the bound quals
and cost.num_sa_scans are different from my expectation.

My assumption is
* bound quals is id3=XXX (and id1 and id2 are skipped attributes)
* cost.num_sa_scans = 100 (=10*10 because assuming 10 primitive index scans
                          per skipped attribute)

But it's wrong. The above index scan result is
* bound quals is NULL
* cost.num_sa_scans = 1


As I know you said the below, but I'd like to know the above is expected or not.

> That approach seems far more practicable than preempting the problem
> during planning or during nbtree preprocessing. It seems like it'd be
> very hard to model the costs statistically. We need revisions to
> btcostestimate, of course, but the less we can rely on btcostestimate
> the better. As I said, there are no new index paths generated by the
> optimizer for any of this.

I couldn't understand why there is the below logic well.

  btcostestimate()
  (...omit...)
              if (indexcol != iclause->indexcol)
              {
                  /* no quals at all for indexcol */
                  found_skip = true;
                  if (index->pages < 100)
                      break;
                  num_sa_scans += 10 * (indexcol - iclause->indexcol);     // why add minus value?
                  continue;                                                  // why skip to add bound quals?
              }


(3)

Currently, there is an assumption that "there will be 10 primitive index scans
per skipped attribute". Is any chance to use pg_stats.n_distinct?

[1] Improve EXPLAIN output for multicolumn B-Tree Index

https://www.postgresql.org/message-id/flat/TYWPR01MB1098260B694D27758FE2BA46FB1C92%40TYWPR01MB10982.jpnprd01.prod.outlook.com

Regards,
--
Masahiro Ikeda
NTT DATA CORPORATION

Attachment

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

From

Peter Geoghegan

Date:

15 July 2024, 18:34:38

On Fri, Jul 12, 2024 at 1:19 AM <Masahiro.Ikeda@nttdata.com> wrote:
> Since I'd like to understand the skip scan to improve the EXPLAIN output
> for multicolumn B-Tree Index[1], I began to try the skip scan with some
> queries and look into the source code.

Thanks for the review!

Attached is v3, which generalizes skip scan, allowing it to work with
opclasses/types that lack a skip support routine. In other words, v3
makes skip scan work for all types, including continuous types, where
it's impractical or infeasible to add skip support. So now important
types like text and numeric also get the skip scan optimization (it's
not just discrete types like integer and date, as in previous
versions).

I feel very strongly that everything should be implemented as part of
the new skip array abstraction; the patch should only add the concept
of skip arrays, which should work just like SAOP arrays. We should
avoid introducing any special cases. In short, _bt_advance_array_keys
should work in exactly the same way as it does as of Postgres 17
(except for a few representational differences for skip arrays). This
seems essential because _bt_advance_array_keys inherently need to be
able to trigger moving on to the next skip array value when it reaches
the end of a SAOP array (and vice-versa). And so it just makes sense
to abstract-away the differences, hiding the difference in lower level
code.

I have described the new _bt_first behavior that is now available in
this new v3 of the patch as "adding explicit next key probes". While
v3 does make new changes to _bt_first, it's not really a special kind
of index probe. v3 invents new sentinel values instead.

The use of sentinels avoids inventing true special cases: the values
-inf, +inf, as well as variants of = that use a real datum value, but
match on the next key in the index. These new = variants can be
thought of as "+infinitesimal" values. So when _bt_advance_array_keys
has to "increment" the numeric value 5.0, it sets the scan key to the
value "5.0 +infinitesimal". There can never be any matching tuples in
the index (just like with -inf sentinel values), but that doesn't
matter. So the changes v3 makes to _bt_first doesn't change the basic
conceptual model. The added complexity is kept to a manageable level,
particularly within _bt_advance_array_keys, which is already very
complicated.

To help with testing and review, I've added another temporary testing
GUC to v3: skipscan_skipsupport_enabled. This can be set to "false" to
avoid using skip support, even where available. The GUC makes it easy
to measure how skip support routines can help performance (with
discrete types like integer and date).

> I found the cost is estimated to much higher if the number of skipped attributes
> is more than two. Is it expected behavior?

Yes and no.

Honestly, the current costing is just placeholder code. It is totally
inadequate. I'm not surprised that you found problems with it. I just
didn't put much work into it, because I didn't really know what to do.

> # Test result. The attached file is the detail of tests.
>
> -- Index Scan
> -- The actual time is low since the skip scan works well
> -- But the cost is higher than one of seqscan
> EXPLAIN (ANALYZE, BUFFERS, VERBOSE) SELECT * FROM test WHERE id3 = 101;
>                                                               QUERY PLAN
>
---------------------------------------------------------------------------------------------------------------------------------------
>  Index Scan using idx_id1_id2_id3 on public.test  (cost=0.42..26562.77 rows=984 width=20) (actual time=0.051..15.533
rows=991loops=1) 
>    Output: id1, id2, id3, value
>    Index Cond: (test.id3 = 101)
>    Buffers: shared hit=4402
>  Planning:
>    Buffers: shared hit=7
>  Planning Time: 0.234 ms
>  Execution Time: 15.711 ms
> (8 rows)

This is a useful example, because it shows the difficulty with the
costing. I ran this query using my own custom instrumentation of the
scan. I saw that we only ever manage to skip ahead by perhaps 3 leaf
pages at a time, but we still come out ahead. As you pointed out, it's
~7.5x faster than the sequential scan, but not very different to the
equivalent full index scan. At least not very different in terms of
leaf page accesses. Why should we win by this much, for what seems
like a marginal case for skip scan?

Even cases where "skipping" doesn't manage to skip any leaf pages can
still benefit from skipping *index tuples* -- there is more than one
kind of skipping to consider. That is, the patch helps a lot with some
(though not all) cases where I didn't really expect that to happen:
the Postgres 17 SAOP tuple skipping code (the code in
_bt_checkkeys_look_ahead, and the related code in _bt_readpage) helps
quite a bit in "marginal" skip scan cases, even though it wasn't
really designed for that purpose (it was added to avoid regressions in
SAOP array scans for the Postgres 17 work).

I find that some queries using my original example test case are about
twice as fast as an equivalent full index scan, even when only the
fourth and final index column is used in the query predicate. The scan
can't even skip a single leaf page at a time, and yet we still win by
a nice amount. We win, though it is almost by mistake!

This is mostly a good thing. Both for the obvious reason (fast is
better than slow), and because it justifies being so aggressive in
assuming that skip scan might work out during planning (being wrong
without really losing is nice). But there is also a downside: it makes
it even harder to model costs at runtime, from within the optimizer.

If I measure the actual runtime costs other than runtime (e.g.,
buffers accesses), I'm not sure that the optimizer is wrong to think
that the parallel sequential scan is faster. It looks approximately
correct. It is only when we look at runtime that the optimizer's
choice looks wrong. Which is...awkward.

In general, I have very little idea about how to improve the costing
within btcostestimate. I am hoping that somebody has better ideas
about it. btcostestimate is definitely the area where the patch is
weakest right now.

> I look at btcostestimate() to find the reason and found the bound quals
> and cost.num_sa_scans are different from my expectation.
>
> My assumption is
> * bound quals is id3=XXX (and id1 and id2 are skipped attributes)
> * cost.num_sa_scans = 100 (=10*10 because assuming 10 primitive index scans
>                           per skipped attribute)
>
> But it's wrong. The above index scan result is
> * bound quals is NULL
> * cost.num_sa_scans = 1

The logic with cost.num_sa_scans was definitely not what I intended.
That's fixed in v3, at least. But the code in btcostestimate is still
essentially the same as in earlier versions -- it needs to be
completely redesigned (or, uh, designed for the first time).

> As I know you said the below, but I'd like to know the above is expected or not.

> Currently, there is an assumption that "there will be 10 primitive index scans
> per skipped attribute". Is any chance to use pg_stats.n_distinct?

It probably makes sense to use pg_stats.n_distinct here. But how?

If the problem is that we're too pessimistic, then I think that this
will usually (though not always) make us more pessimistic. Isn't that
the wrong direction to go in? (We're probably also too optimistic in
some cases, but being too pessimistic is a bigger problem in
practice.)

For example, your test case involved 11 distinct values in each
column. The current approach of hard-coding 10 (which is just a
temporary hack) should actually make the scan look a bit cheaper than
it would if we used the true ndistinct.

Another underlying problem is that the existing SAOP costing really
isn't very accurate, without skip scan -- that's a big source of the
pessimism with arrays/skipping. Why should we be able to get the true
number of primitive index scans just by multiplying together each
omitted prefix column's ndistinct? That approach is good for getting
the worst case, which is probably relevant -- but it's probably not a
very good assumption for the average case. (Though at least we can cap
the total number of primitive index scans to 1/3 of the total number
of pages in the index in btcostestimate, since we have guarantees
about the worst case as of Postgres 17.)

--
Peter Geoghegan

Attachment

v3-0001-Add-skip-scan-to-nbtree.patch

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

From

Peter Geoghegan

Date:

24 July 2024, 21:14:54

On Mon, Jul 15, 2024 at 2:34 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v3, which generalizes skip scan, allowing it to work with
> opclasses/types that lack a skip support routine. In other words, v3
> makes skip scan work for all types, including continuous types, where
> it's impractical or infeasible to add skip support.

Attached is v4, which:

* Fixes a previous FIXME item affecting range skip scans/skip arrays
used in cross-type scenarios.

* Refactors and simplifies the handling of range inequalities
associated with skip arrays more generally. We now always use
inequality scan keys during array advancement (and when descending the
tree within _bt_first), rather than trying to use a datum taken from
the range inequality as an array element directly.

This gives us cleaner separation between scan keys/data types in
cross-type scenarios: skip arrays will now only ever contain
"elements" of opclass input type. Sentinel values such as -inf are
expanded to represent "the lowest possible value that comes after the
array's low_compare lower bound, if any". Opclasses that don't offer
skip support took roughly this same approach within v3, but in v4 all
opclasses do it the same way (so opclasses with skip support use the
SK_BT_NEG_INF sentinel marking in their scan keys, though never the
SK_BT_NEXTKEY sentinel marking).

This is really just a refactoring revision. Nothing particularly
exciting here compared to v3.

--
Peter Geoghegan

Attachment

v4-0001-Add-skip-scan-to-nbtree.patch

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

From

Dmitry Dolgov

Date:

03 August 2024, 19:34:54

> On Wed, Jun 26, 2024 at 03:16:07PM GMT, Peter Geoghegan wrote:
>
> Loose index scan is a far more specialized technique than skip scan.
> It only applies within special scans that feed into a DISTINCT group
> aggregate. Whereas my skip scan patch isn't like that at all -- it's
> much more general. With my patch, nbtree has exactly the same contract
> with the executor/core code as before. There are no new index paths
> generated by the optimizer to make skip scan work, even. Skip scan
> isn't particularly aimed at improving group aggregates (though the
> benchmark I'll show happens to involve a group aggregate, simply
> because the technique works best with large and expensive index
> scans).

I see that the patch is not supposed to deal with aggregates in any special
way. But from what I understand after a quick review, skip scan is not getting
applied to them if there are no quals in the query (in that case
_bt_preprocess_keys returns before calling _bt_preprocess_array_keys). Yet such
queries could benefit from skipping, I assume they still could be handled by
the machinery introduced in this patch?

> > Currently, there is an assumption that "there will be 10 primitive index scans
> > per skipped attribute". Is any chance to use pg_stats.n_distinct?
>
> It probably makes sense to use pg_stats.n_distinct here. But how?
>
> If the problem is that we're too pessimistic, then I think that this
> will usually (though not always) make us more pessimistic. Isn't that
> the wrong direction to go in? (We're probably also too optimistic in
> some cases, but being too pessimistic is a bigger problem in
> practice.)
>
> For example, your test case involved 11 distinct values in each
> column. The current approach of hard-coding 10 (which is just a
> temporary hack) should actually make the scan look a bit cheaper than
> it would if we used the true ndistinct.
>
> Another underlying problem is that the existing SAOP costing really
> isn't very accurate, without skip scan -- that's a big source of the
> pessimism with arrays/skipping. Why should we be able to get the true
> number of primitive index scans just by multiplying together each
> omitted prefix column's ndistinct? That approach is good for getting
> the worst case, which is probably relevant -- but it's probably not a
> very good assumption for the average case. (Though at least we can cap
> the total number of primitive index scans to 1/3 of the total number
> of pages in the index in btcostestimate, since we have guarantees
> about the worst case as of Postgres 17.)

Do I understand correctly, that the only way how multiplying ndistincts could
produce too pessimistic results is when there is a correlation between distinct
values? Can one benefit from the extended statistics here?

And while we're at it, I think it would be great if the implementation will
allow some level of visibility about the skip scan. From what I see, currently
it's by design impossible for users to tell whether something was skipped or
not. But when it comes to planning and estimates, maybe it's not a bad idea to
let explain analyze show something like "expected number of primitive scans /
actual number of primitive scans".

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

From

Peter Geoghegan

Date:

03 August 2024, 22:14:18

On Sat, Aug 3, 2024 at 3:34 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> I see that the patch is not supposed to deal with aggregates in any special
> way.

Right.

> But from what I understand after a quick review, skip scan is not getting
> applied to them if there are no quals in the query (in that case
> _bt_preprocess_keys returns before calling _bt_preprocess_array_keys).

Right.

> Yet such queries could benefit from skipping, I assume they still could be handled by
> the machinery introduced in this patch?

I'm not sure.

There are no real changes required inside _bt_advance_array_keys with
this patch -- skip arrays are dealt with in essentially the same way
as conventional arrays (as of Postgres 17). I suspect that loose index
scan would be best implemented using _bt_advance_array_keys. It could
also "plug in" to the existing _bt_advance_array_keys design, I
suppose.

As I touched on already, your loose index scan patch applies
high-level semantic information in a way that is very different to my
skip scan patch. This means that it makes revisions to the index AM
API (if memory serves it adds a callback called amskip to that API).
It also means that loose index scan can actually avoid heap accesses;
loose scans wholly avoid accessing logical rows (in both the index and
the heap) by reasoning that it just isn't necessary to do so at all.
Skipping happens in both data structures. Right?

Obviously, my new skip scan patch cannot possibly reduce the number of
heap page accesses required by a given index scan. Precisely the same
logical rows must be accessed as before. There is no two-way
conversation between the index AM and the table AM about which
rows/row groupings have at least one visible tuple. We're just
navigating through the index more efficiently, without changing any
contract outside of nbtree itself.

The "skip scan" name collision is regrettable. But the fact is that
Oracle, MySQL, and now SQLite all call this feature skip scan. That
feels like the right precedent to follow.

> Do I understand correctly, that the only way how multiplying ndistincts could
> produce too pessimistic results is when there is a correlation between distinct
> values?

Yes, that's one problem with the costing. Not the only one, though.

The true number of primitive index scans depends on the cardinality of
the data. For example, a skip scan might be the cheapest plan by far
if (say) 90% of the index has the same leading column value and the
remaining 10% has totally unique values. We'd still do a bad job of
costing this query with an accurate ndistinct for the leading column.
We really one need to do one or two primitive index scans for "the
first 90% of the index", and one more primitive index scan for "the
remaining 10% of the index". For a query such as this, we "require a
full index scan for the remaining 10% of the index", which is
suboptimal, but doesn't fundamentally change anything (I guess that a
skip scan is always suboptimal, in the sense that you could always do
better by having more indexes).

> Can one benefit from the extended statistics here?

I really don't know. Certainly seems possible in cases with more than
one skipped leading column.

The main problem with the costing right now is that it's just not very
well thought through, in general. The performance at runtime depends
on the layout of values in the index itself, so the underlying way
that you'd model the costs doesn't have any great precedent in
costsize.c. We do have some idea of the number of leaf pages we'll
access in btcostestimate(), but that works in a way that isn't really
fit for purpose. It kind of works with one primitive index scan, but
works much less well with multiple primitive scans.

> And while we're at it, I think it would be great if the implementation will
> allow some level of visibility about the skip scan. From what I see, currently
> it's by design impossible for users to tell whether something was skipped or
> not. But when it comes to planning and estimates, maybe it's not a bad idea to
> let explain analyze show something like "expected number of primitive scans /
> actual number of primitive scans".

I agree. I think that that's pretty much mandatory for this patch. At
least the actual number of primitive scans should be exposed. Not
quite as sure about showing the estimated number, since that might be
embarrassingly wrong quite regularly, without it necessarily mattering
that much (I'd worry that it'd be distracting).

Displaying the number of primitive scans would already be useful for
index scans with SAOPs, even without this patch. The same general
concepts (estimated vs. actual primitive index scans) already exist,
as of Postgres 17. That's really nothing new.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

03 August 2024, 22:21:43

On Sat, Aug 3, 2024 at 6:14 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Displaying the number of primitive scans would already be useful for
> index scans with SAOPs, even without this patch. The same general
> concepts (estimated vs. actual primitive index scans) already exist,
> as of Postgres 17. That's really nothing new.

We actually expose this via instrumentation, in a certain sense. This
is documented by a "Note":

https://www.postgresql.org/docs/devel/monitoring-stats.html#MONITORING-PG-STAT-ALL-INDEXES-VIEW

That is, we already say "Each internal primitive index scan increments
pg_stat_all_indexes.idx_scan, so it's possible for the count of index
scans to significantly exceed the total number of index scan executor
node executions". So, as I said in the last email, advertising the
difference between # of primitive index scans and # of index scan
executor node executions in EXPLAIN ANALYZE is already a good idea.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

09 August 2024, 21:13:28

On Wed, Jul 24, 2024 at 5:14 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v4

Attached is v5, which splits the code from v4 patch into 2 pieces --
it becomes 0002-* and 0003-*. Certain refactoring work now appears
under its own separate patch/commit -- see 0002-* (nothing new here,
except the commit message/patch structure). The patch that actually
adds skip scan (0003-* in this new version) has been further polished,
though not in a way that I think is interesting enough to go into
here.

The interesting and notable change for v5 is the addition of the code
in 0001-*. The new 0001-* patch is concerned with certain aspects of
how _bt_advance_array_keys decides whether to start another primitive
index scan (or to stick with the ongoing one for one more leaf page
instead). This is a behavioral change, albeit a subtle one. It's also
kinda independent of skip scan (more on why that is at the end).

It's easiest to explain why 0001-* matters by way of an example. My
example will show significantly more internal/root page accesses than
seen on master, though only when 0002-* and 0003-* are applied, and
0001-* is omitted. When all 3 v5 patches are applied together, the
total number of index pages accessed by the test query will match the
master branch. It's important that skip scan never loses by much to
the master branch, of course. Even when the details of the index/scan
are inconvenient to the implementation, in whatever way.

Setup:

create table demo (int4 a, numeric b);
create index demo_idx on demo (a, b);
insert into demo select a, random() from generate_series(1, 10000) a,
generate_series(1,5) five_rows_per_a_val;
vacuum demo;

We now have a btree index "demo_idx", which has two levels (a root
page plus a leaf level). The root page contains several hundred pivot
tuples, all of which have their "b" value truncated away (or have the
value -inf, if you prefer), with just one prefix "a" column left in
place. Naturally, every leaf page has a high key with its own
separator key that matches one particular tuple that appears in the
root page (except for the rightmost leaf page). So our leaf level scan
will see lots of truncated leaf page high keys (all matching a
corresponding root page tuple).

Test query:

select a from demo where b > 0.99;

This is a query that really shouldn't be doing any skipping at all. We
nevertheless still see a huge amount of skipping with this query, ocne
0001-* is omitted. Prior to 0001-*, a new primitive index scan is
started whenever the scan reaches a "boundary" between adjoining leaf
pages. That is, whenever _bt_advance_array_keys stopped on a high key
pstate.finaltup. So without the new 0001-* work, the number of page
accesses almost doubles (because we access the root page once per leaf
page accessed, instead of just accessing it once for the whole scan).

What skip scan should have been doing all along (and will do now) is
to step forward to the next right sibling leaf page whenever it
reaches a boundary between leaf pages. This should happen again and
again, without our ever choosing to start a new primitive index scan
instead (it shouldn't happen even once with this query). In other
words, we ought to behave just like a full index scan would behave
with this query -- which is exactly what we get on master.

The scan will still nominally "use skip scan" even with this fix in
place, but in practice, for this particular query/index, the scan
won't ever actually decide to skip. So it at least "looks like" an
index scan from the point of view of EXPLAIN (ANALYZE, BUFFERS). There
is a separate question of how many CPU cycles we use to do all this,
but for now my focus is on total pages accessed by the patch versus on
master, especially for adversarial cases such as this.

It should be noted that the skip scan patch never had any problems
with this very similar query (same table as before):

select a from demo where b < 0.01;

The fact that we did the wrong thing for the first query, but the
right thing for this second similar query, was solely due to certain
accidental implementation details -- it had nothing to do with the
fundamentals of the problem. You might even say that 0001-* makes the
original "b > 0.99" case behave in the same manner as this similar "b
< 0.01" case, which is justifiable on consistency grounds. Why
wouldn't these two cases behave similarly? It's only logical.

The underlying problem arguably has little to do with skip scan;
whether we use a real SAOP array on "a" or a consed up skip array is
incidental to the problem that my example highlights. As always, the
underlying "array type" (skip vs SOAP) only matters to the lowest
level code. And so technically, this is an existing issue on
HEAD/master. You can see that for yourself by making the problematic
query's qual "where a = any ('every possible a value') and b > 0.99"
-- same problem on Postgres 17, without involving skip scan.

To be sure, the underlying problem does become more practically
relevant with the invention of skip arrays for skip scan, but 0001-*
can still be treated as independent work. It can be committed well
ahead of the other stuff IMV. The same is likely also true of the
refactoring now done in 0002-* -- it does refactoring that makes
sense, even without skip scan. And so I don't expect it to take all
that long for it to be committable.

--
Peter Geoghegan

On Fri, Feb 14, 2025 at 6:06 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v24, which breaks out these recent changes to primscan
> scheduling into their own commit/patch (namely
> v24-0002-Improve-nbtree-SAOP-primitive-scan-scheduling.patch). The
> primscan scheduling improvement stuff hasn't really changed since
> v23, though (though I did polish it some more). I hope to be able to
> commit this new primscan scheduling patch sooner rather than later
> (though I don't think that it's quite committable yet).

The patch series recently bitrot due to conflicting changes on HEAD,
so I decided to post a new v25 now.

New in v25:

* Fixed a regression with parallel index scans caused by the improved
scheduling logic added by
0002-Improve-nbtree-SAOP-primitive-scan-scheduling.patch.

v24 did not account for how "firstPage=false" calls to _bt_readpage
might originate from _bt_first (not _bt_next) during parallel scans,
even during the first page for the parallel worker's primitive
scan/_bt_first call -- which made the heuristics added to
_bt_advance_array_keys do the wrong thing by not terminating primitive
scan based on faulty information. This was possible via the parallel
scan _bt_readnextpage "seized=true" path, which led to regressions. In
v24 we now pass "firstPage=true" whenever a call to _bt_readpage
happens through _bt_first, no matter the details (for the first
_bt_readpage call's page).

* The additional EXPLAIN ANALYZE logic (that shows "Index Searches:
N") added by 0001-Show-index-search-count-in-EXPLAIN-ANALYZE.patch has
been adjusted, and no longer divides by nloops.

I explain why dividing by nloops has some fairly bad consequences on
the thread I started for the quasi-independent enhancement to EXPLAIN
ANALYZE output:

https://postgr.es/m/CAH2-WzmebSkeKPGw7TEaNw9=Qx-X8fAnFw916Fd2V8VVqYqqaQ@mail.gmail.com

* Polished commit messages.

* Added more test coverage. The LOC covered percentage is now at just
over 90% for nbtutils.c. We now have coverage for almost all of the
new code that advances the scan's skip arrays, including code that
deals with NULL values that is seldom reached.

--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

27 February, 21:23:57

On Sun, Feb 23, 2025 at 12:19 PM Peter Geoghegan <pg@bowt.ie> wrote:
> The patch series recently bitrot due to conflicting changes on HEAD,
> so I decided to post a new v25 now.

Attached is v26, which has no functional changes. This is just to fix
yet more bitrot.

--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

08 March, 19:43:33

On Thu, Feb 27, 2025 at 1:23 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v26, which has no functional changes. This is just to fix
> yet more bitrot.

Attached is v27, which fixes bitrot. It also has some notable changes:

* New approach to "Index Searches: N" instrumentation patch, following
the recent revert of the original approach following
"debug_parallel_query=regress" buildfarm failures.

This is being discussed over on the thread that I started to discuss
the EXPLAIN ANALYZE instrumentation work:

https://www.postgresql.org/message-id/CAH2-Wzk%2BcXBD1tnhQ-oagHuY9Fw5uArJE%2BLxfAP2VjZmDawbeQ%40mail.gmail.com

* New patch that makes BTMaxItemSize not require a "Page" arg, so that
it can be used in contexts where a page image isn't close at hand.
This is preparation for the approach taken to parallel index scans,
where we apply a conservative "1/3 of a page" worst case limit on the
size of a datum, but don't have a page to pass to BTMaxItemSize.

I plan on committing this one soon. It's obviously pretty pointless to
make the BTMaxItemSize operate off of a page header, and not requiring
it is more flexible.

--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

11 March, 18:52:44

On Sat, Mar 8, 2025 at 11:43 AM Peter Geoghegan <pg@bowt.ie> wrote:
> I plan on committing this one soon. It's obviously pretty pointless to
> make the BTMaxItemSize operate off of a page header, and not requiring
> it is more flexible.

Committed. And committed a revised version of "Show index search count
in EXPLAIN ANALYZE" that addresses the issues with non-parallel-aware
index scan executor nodes that run from a parallel worker.

Attached is v28. This is just to keep the patch series applying
cleanly -- no real changes here.

--
Peter Geoghegan

On 12.03.2025 23:50, Peter Geoghegan wrote:

On Wed, Mar 12, 2025 at 4:28 PM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:

Thank you for the explanation!

Now I see why these changes were made.

After your additional explanations, everything really became clear and I
fully agree with the current code regarding this part.

Cool.

However I did not see an explanation to the commit regarding this place,
as well as a comment next to the assert and the parallel_aware check and
why BitmapIndexScanState was added in the ExecParallelReInitializeDSM.

I added BitmapIndexScanState to the switch statement in
ExecParallelReInitializeDSM because it is in the category of
planstates that never need their shared memory reinitialized -- that's
just how we represent such a plan state there.

I think that this is supposed to serve as a kind of documentation,
since it doesn't really affect how things behave. That is, it wouldn't
actually affect anything if I had forgotten to add
BitmapIndexScanState to the ExecParallelReInitializeDSM switch
statement "case" that represents that it is in this "plan state
category": the switch ends with catch-all "default: break;".

Agree.

In my opinion, there is not enough additional explanation about this in
the form of comments, although I think that it has already been
explained here enough for someone who will look at this code.

What can be done to improve the situation? For example, would adding a
comment next to the new assertions recently added to
ExecIndexScanReInitializeDSM and ExecIndexOnlyScanReInitializeDSM be
an improvement? And if so, what would the comment say?

After reviewing the logic again, I realized that I was confused precisely in the reinitialization of memory for IndexScanState and IndexOnlyScanState.

As far as I can see, either assert is not needed here, the functions ExecIndexScanReInitializeDSM and ExecIndexScanReInitializeDSM can be called only if parallel_aware is positive, or it makes sense that reinitialization is needed only if parallel_aware is positive, then the condition noted above is not needed. According to your letter (0), the check should be removed there too, but I got confused in the comment. We do not need to reinitialize memory because DSM is instrumentation state only, but it turns out that we are reinitializing the memory, so we don't do it at all?

I attached a diff file to the letter with the comment.

[0] https://www.postgresql.org/message-id/CAH2-WzkMpFsE_hM9-5tecF22jVJSGtKMFMsYqMa-uo73MOxsWw%40mail.gmail.com

-- 
Regards,
Alena Rybakina
Postgres Professional

Attachment

for_reinitialize_memory.diff.no-cfbot

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

From

Alena Rybakina

Date:

18 March, 16:37:33

On 18.03.2025 13:54, Alena Rybakina wrote:

On 12.03.2025 23:50, Peter Geoghegan wrote:
On Wed, Mar 12, 2025 at 4:28 PM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:
Thank you for the explanation!

Now I see why these changes were made.

After your additional explanations, everything really became clear and I
fully agree with the current code regarding this part.
Cool.
However I did not see an explanation to the commit regarding this place,
as well as a comment next to the assert and the parallel_aware check and
why BitmapIndexScanState was added in the ExecParallelReInitializeDSM.
I added BitmapIndexScanState to the switch statement in
ExecParallelReInitializeDSM because it is in the category of
planstates that never need their shared memory reinitialized -- that's
just how we represent such a plan state there.

I think that this is supposed to serve as a kind of documentation,
since it doesn't really affect how things behave. That is, it wouldn't
actually affect anything if I had forgotten to add
BitmapIndexScanState to the ExecParallelReInitializeDSM switch
statement "case" that represents that it is in this "plan state
category": the switch ends with catch-all "default: break;".
Agree.
In my opinion, there is not enough additional explanation about this in
the form of comments, although I think that it has already been
explained here enough for someone who will look at this code.
What can be done to improve the situation? For example, would adding a
comment next to the new assertions recently added to
ExecIndexScanReInitializeDSM and ExecIndexOnlyScanReInitializeDSM be
an improvement? And if so, what would the comment say?
After reviewing the logic again, I realized that I was confused precisely in the reinitialization of memory for IndexScanState and IndexOnlyScanState.
As far as I can see, either assert is not needed here, the functions ExecIndexScanReInitializeDSM and ExecIndexScanReInitializeDSM can be called only if parallel_aware is positive, or it makes sense that reinitialization is needed only if parallel_aware is positive, then the condition noted above is not needed. According to your letter (0), the check should be removed there too, but I got confused in the comment. We do not need to reinitialize memory because DSM is instrumentation state only, but it turns out that we are reinitializing the memory, so we don't do it at all?
I attached a diff file to the letter with the comment.
[0] https://www.postgresql.org/message-id/CAH2-WzkMpFsE_hM9-5tecF22jVJSGtKMFMsYqMa-uo73MOxsWw%40mail.gmail.com

Sorry, I figured it out. The Assert was added to avoid misuse of the function to reinitialize memory and to ensure that it happens when parallel_aware is positive.

-- 
Regards,
Alena Rybakina
Postgres Professional

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

From

Peter Geoghegan

Date:

18 March, 19:41:18

On Tue, Mar 18, 2025 at 9:37 AM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:
> Sorry, I figured it out. The Assert was added to avoid misuse of the function to reinitialize memory and to ensure
thatit happens when parallel_aware is positive. 

Yeah. The assertion is supposed to suggest "don't worry, I didn't
forget to test parallel_aware in this function
[ExecIndexScanReInitializeDSM or ExecIndexScanReInitializeDSM], it's
just that I expect to not be called unless parallel_aware is true".

An alternative approach would have been to explicitly handle
parallel_aware=false in ExecIndexScanReInitializeDSM and
ExecIndexScanReInitializeDSM: they could just return false. That would
make ExecIndexScanReInitializeDSM and ExecIndexScanReInitializeDSM
more consistent with other nearby functions (in nodeIndexScan.c and
nodeIndexOnlyScan.c), at the cost of making the calling code (in
execParallel.c) less consistent. I really don't think that that
alternative is any better to what I actually did (I actually
considered doing things this way myself at one point), though it also
doesn't seem worse. So I'm inclined to do nothing about it now.

--
Peter Geoghegan

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

From

Matthias van de Meent

Date:

18 March, 20:01:00

On Mon, 17 Mar 2025 at 23:51, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
>
> On Tue, 11 Mar 2025 at 16:53, Peter Geoghegan <pg@bowt.ie> wrote:
> >
> > On Sat, Mar 8, 2025 at 11:43 AM Peter Geoghegan <pg@bowt.ie> wrote:
> > > I plan on committing this one soon. It's obviously pretty pointless to
> > > make the BTMaxItemSize operate off of a page header, and not requiring
> > > it is more flexible.
> >
> > Committed. And committed a revised version of "Show index search count
> > in EXPLAIN ANALYZE" that addresses the issues with non-parallel-aware
> > index scan executor nodes that run from a parallel worker.
> >
> > Attached is v28. This is just to keep the patch series applying
> > cleanly -- no real changes here.
>
> You asked off-list for my review of 0003. I'd already reviewed 0001
> before that, so that review also included. I'll see if I can spend
> some time on the other patches too

My comments on 0004:

> _bt_skiparray_strat_decrement
> _bt_skiparray_strat_increment

In both functions the generated value isn't used when the in/decrement
overflows (and thus invalidates the qual), or when the opclass somehow
doesn't have a <= or >= operator, respectively.
For byval types that's not much of an issue, but for by-ref types
(such as uuid, or bigint on 32-bit systems) that's not great, as btree
explicitly allows no leaks for the in/decrement functions, and now we
use those functions and leak the values.

Additionally, the code is essentially duplicated between the
functions, with as only differences which sksup function to call;
which opstrategies to check, and where to retrieve/put the value. It's
only 2 instances total, but if you figure out how to make a nice
single function from the two that'd be appreciated, as it reduces
duplication and chances for divergence.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

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

From

Peter Geoghegan

Date:

18 March, 22:15:20

On Mon, Mar 17, 2025 at 6:51 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> This hasn't changed meaningfully in this patch, but I noticed that
> pstate.finaltup is never set for the final page of the scan direction
> (i.e. P_RIGHTMOST or P_LEFTMOST for forward or backward,
> respectively). If it isn't used more than once after the first element
> of non-P_RIGHTMOST/LEFTMOST pages, why is it in pstate? Or, if it is
> used more than once, why shouldn't it be used in

We don't set pstate.finaltup on either the leftmost or rightmost page
(nothing new, this is all from the Postgres 17 SAOP patch) because we
cannot possibly need to start another primitive index scan from that
point. We only use pstate.finaltup to determine if we should start a
new primitive index scan, every time the scan's array keys advance
(except during "sktrig_required=false" array advancement, and barring
the case where we don't have to check pstate.finaltup because we see
that the new set of array keys are already an exact match for the
tuple passed to _bt_advance_array_keys). In short, pstate.finaltup is
used during a significant fraction of all calls to
_bt_advance_array_keys, and there is no useful limit on the number of
times that pstate.finaltup can be used per _bt_readpage.

Although you didn't say it in your email (you said it to me on our
most recent call), I believe that you're asking about pstate.finaltup
for reasons that are more related to 0003-* than to 0001-*. As I
recall, you asked me about why it was that the 0003-* patch avoids
_bt_readpage's call to _bt_skip_ikeyprefix on the leftmost or
rightmost leaf page (i.e. a page that lacks a pstate.finaltup). You
were skeptical about that -- understandably so.

To recap, 0003-* avoids calling _bt_skip_ikeyprefix on the rightmost
(and leftmost) page because it reasons that activating that
optimization is only okay when we know that we'll be able to "recover"
afterwards, during the finaltup _bt_checkkeys call. By "recover", I
mean restore the invariant for required array keys: that they track
our progress through the key space. It felt safer and easier for
0003-* to just not call _bt_skip_ikeyprefix on a page that has no
finaltup -- that way we won't have anything that we need to recover
from, when we lack the pstate.finaltup that we generally expect to use
for this purpose. This approach allowed me to add the following
assertions a little bit later on, right at the end of _bt_readpage
(quoting 0003-* here):

@@ -1993,6 +2031,16 @@ _bt_readpage(IndexScanDesc scan, ScanDirection
dir, OffsetNumber offnum,
        so->currPos.itemIndex = MaxTIDsPerBTreePage - 1;
    }

+   /*
+    * As far as our caller is concerned, the scan's arrays always track its
+    * progress through the index's key space.
+    *
+    * If _bt_skip_ikeyprefix told us to temporarily treat all scan keys as
+    * nonrequired (during a skip scan), then we must recover afterwards by
+    * advancing our arrays using finaltup (with !pstate.forcenonrequired).
+    */
+   Assert(pstate.ikey == 0 && !pstate.forcenonrequired);
+
    return (so->currPos.firstItem <= so->currPos.lastItem);
 }

I've actually come around to your point of view on this (or what I
thought was your PoV from our call). That is, I now *think* that it
would be better if the code added by 0003-* called
_bt_skip_ikeyprefix, without regard for whether or not we'll have a
finaltup _bt_checkkeys call to "recover" (i.e. whether we're on the
leftmost or rightmost page shouldn't matter).

My change in perspective on this question is related to another change
of perspective, on the question of whether we actually need to call
_bt_start_array_keys as part of "recovering/restoring the array
invariant", just ahead of the finaltup _bt_checkkeys call. As you
know, 0003-* calls _bt_start_array_keys in this way, but that now
seems like overkill. It can have undesirable side-effects when the
array keys spuriously appear to advance, when in fact they were
restarted via the _bt_start_array_keys call, only to have their
original values restored via the finaltup call that immediately
follows.

Here's what I mean about side-effects:

We shouldn't allow _bt_advance_array_keys' primitive index scan
scheduling logic to falsely believe that the array keys have advanced,
when they didn't really advance in any practical sense. The commit
message of 0003-* promises that its optimization cannot influence
primitive index scan scheduling at all, which seems like a good
general principle for us to follow. But I recently discovered that
that promise was subtly broken, which I tied to the way that 0003-*
calls _bt_start_array_keys (this didn't produce wrong answers, and
didn't even really hurt performance, but it seems wonky and hard to
test). So I now think that I need to expect more from
_bt_skip_ikeyprefix and its pstate.forcenonrequired optimization, so
that my promise about primscan scheduling is honored.

Tying it back to your concern, once I do that (once I stop calling
_bt_start_array_keys in 0003-* to "hard reset" the arrays), I can also
stop caring about finaltup being set on the rightmost page, at the
point where we decide if _bt_skip_ikeyprefix should be called.

Here's how I think that this will be safe:

Obviously, we can't expect _bt_skip_ikeyprefix/pstate.forcenonrequired
mode to maintain the scan's required arrays in the usual way -- the
whole idea in 0003-* is to stop properly maintaining the arrays, until
right at the end of the _bt_readpage call, so as to save cycles.
However, it should be possible to teach _bt_skip_ikeyprefix to not
leave the array keys in an irredeemably bad state -- even when no
finaltup call is possible during the same _bt_readpage. And, even when
the scan direction changes at an inconvenient time. The next revision
(v29) is likely to strengthen the guarantees that _bt_skip_ikeyprefix
makes about the state that it'll leave the scan's array keys in, so
that its _bt_readpage caller can be laxer about "fully undoing" its
call to _bt_skip_ikeyprefix. The invariants we need to restore only
really apply when the scan needs to continue in the same scan
direction, at least one more page.

In short, as long as the array keys can never "go backwards" (relative
to the current scan direction), then we'll be able to recover during
the next conventional call to _bt_checkkeys (meaning the next
!pstate.forcenonrequired call) -- even if that next call should happen
on some other page (in practice it is very unlikely that it will, but
we can still be prepared for that). While it's true that
_bt_advance_array_keys (with sktrig_required=true) always promises to
advance the array keys to the maximum possible extent that it can know
to be safe, based on the caller's tuple alone, that in itself doesn't
obligate _bt_readpage to make sure that _bt_advance_array_keys will be
called when the top-level scan is over. We have never expected
_bt_advance_array_keys to *reliably* reach the final set of array keys
at the end of the scan (e.g., this won't happen when the index is
completely empty, since we'll never call _bt_readpage in the first
place).

> In forward scan mode, recovery from forcenonrequired happens after the
> main loop over all page items. In backward mode, it's in the loop:
>
> > +            if (offnum == minoff && pstate.forcenonrequired)
> > +            {
> > +                Assert(so->skipScan);
>
> I think there's a comment missing that details _why_ we do this;
> probably something like:
>
> /*
>  * We're about to process the final item on the page.
>  * Un-set forcenonrequired, so the next _bt_checkkeys will
>  * evaluate required scankeys and signal an end to this
>  * primitive scan if we've reached a stopping point.
>  */

I think that the right place to talk about this is above
_bt_skip_ikeyprefix itself.

> In line with that, could you explain a bit more about the
> pstate.forcenonrequired optimization? I _think_ it's got something to
> do with "required" scankeys adding some overhead per scankey, which
> can be significant with skipscan evaluations and ignoring the
> requiredness can thus save some cycles, but the exact method doesn't
> seem to be very well articulated.

The main benefit of the _bt_skip_ikeyprefix optimization is that it
allows us to skip a pstate.ikey prefix of scan keys in many important
cases. But that is not compatible with certain existing
_bt_advance_array_keys "sktrig_required=true" optimizations.

Most notably, we cannot assume that the array keys perfectly track our
progress through the index's key space when calling
_bt_advance_array_keys with "sktrig_required=false". In particular, it
would be wrong to allow the SAOP array binary search
cur_elem_trig=true optimization (see _bt_binsrch_array_skey) to be
used. We also don't want to attempt to end the primscan during
"sktrig_required=false" calls to _bt_advance_array_keys (nothing about
that is new here, it's just that _bt_skip_ikeyprefix now temporarily
forces the scan to behave this way, dynamically, rather than it being
static behavior that is fixed for the whole scan).

The underlying problem is that "sktrig_required=false" array
advancement cannot precisely reason about the relationship between the
scan's progress and the current required array key positions. For
example, with a query "WHERE a BETWEEN 0 AND 100 AND b in (42, 44)",
on a page whose "a" attribute values all satisfy the range qual on "a"
(i.e. with pstate.ikey = 1), our "a" skip array won't advance at all
(if we didn't use the _bt_skip_ikeyprefix optimization then we'd only
ever do "sktrig_required=false" advancement, and the skip array might
advance several times within a page, but we're ignoring "a" here). We
cannot reuse work across "b" SAOP binary searches, because in general
we're not paying attention to "a" at all -- and so we won't even try
to roll over "b" when the value of "a" advances (we're just looking at
"b", never "a").

> > _bt_skip_ikeyprefix
>
> I _think_ it's worth special-casing firstchangingattnum=1, as in that
> case we know in advance there is no (immediate) common ground between
> the index tuples and thus any additional work we do towards parsing
> the scankeys would be wasted - except for matching inequality bounds
> for firstchangingatt, or matching "open" skip arrays for a prefix of
> attributes starting at firstchangingattnum (as per the
> array->null_elem case).

Not sure what you mean by "special-casing firstchangingattnum=1"? What
"additional work we do towards parsing the scankeys" are you concerned
about?

It's fairly common for firstchangingattnum=1, even when the
_bt_skip_ikeyprefix optimization is working well. For example, that's
what'd happen with the example query I just gave (a query "WHERE a
BETWEEN 0 AND 100 AND b in (42, 44)" can skip "a" by setting
pstate.ikey=1, provided all of the "a" attribute values on the page
are within the range of the skip array).

> I also notice somed some other missed opportunities for optimizing
> page accesses:
>
> > +        if (key->sk_strategy != BTEqualStrategyNumber)
>
> The code halts optimizing "prefix prechecks" when we notice a
> non-equality key. It seems to me that we can do the precheck on shared
> prefixes with non-equality keys just the same as with equality keys;
> and it'd improve performance in those cases, too.

Yeah, I was thinking of doing this already (though not for RowCompare
inequalities, which would be hard to evaluate from here). It makes
sense because it's exactly the same case as the range skip array case,
really -- why not just do it the same way?

> > +        if (!(key->sk_flags & SK_SEARCHARRAY))
> > +            if (key->sk_attno < firstchangingattnum)
> > +            {
> > +                if (result == 0)
> > +                    continue;    /* safe, = key satisfied by every tuple */
> > +            }
> > +            break;                /* pstate.ikey to be set to scalar key's ikey */
>
> This code finds out that no tuple on the page can possibly match the
> scankey (idxtup=scalar returns non-0 value) but doesn't (can't) use it
> to exit the scan. I think that's a missed opportunity for
> optimization; now we have to figure that out for every tuple in the
> scan. Same applies to the SAOP -array case (i.e. non-skiparray).

Maybe, but it's not much of a missed opportunity. It doesn't guarantee
that the scan can end in the case of a SAOP (the very next leaf page
could satisfy the same scan key, given a SAOP array with "gaps" in the
elements). So it can only really end the scan with a scalar = key --
though never when it is preceded by a skip array (doesn't matter if
the skip array is definitely satisfied/has only one distinct attribute
value on the page). Is this idea related to your previous idea
involving "special-casing firstchangingattnum=1"?

If I was going to do something like this, I think that it'd work by
backing out of applying the optimization entirely. Right now, 0003-*
applies the optimization whenever _bt_readpage decides to call
_bt_skip_ikeyprefix, regardless of the details after that (it would be
easy to teach _bt_skip_ikeyprefix to decide against applying its
optimization entirely, but testing seems to show that it always makes
sense to go ahead when _bt_skip_ikeyprefix is called, regardless of
what _bt_skip_ikeyprefix sees on the page).

> Thank you for working on this.

Thanks for the review!

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

18 March, 22:31:41

On Tue, Mar 18, 2025 at 1:01 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> My comments on 0004:
>
> > _bt_skiparray_strat_decrement
> > _bt_skiparray_strat_increment
>
> In both functions the generated value isn't used when the in/decrement
> overflows (and thus invalidates the qual), or when the opclass somehow
> doesn't have a <= or >= operator, respectively.
> For byval types that's not much of an issue, but for by-ref types
> (such as uuid, or bigint on 32-bit systems) that's not great, as btree
> explicitly allows no leaks for the in/decrement functions, and now we
> use those functions and leak the values.

We don't leak any memory here. We temporarily switch over to using
so->arrayContext, for the duration of these calls. And so the memory
will be freed on rescan -- there's a MemoryContextReset call at the
top of _bt_preprocess_array_keys to take care of this, which is hit on
rescan.

> Additionally, the code is essentially duplicated between the
> functions, with as only differences which sksup function to call;
> which opstrategies to check, and where to retrieve/put the value. It's
> only 2 instances total, but if you figure out how to make a nice
> single function from the two that'd be appreciated, as it reduces
> duplication and chances for divergence.

I'll see if I can do something like that for the next revision, but I
think that it might be more awkward than it's worth.

The duplication isn't quite duplication, so much as it's two functions
that are mirror images of each other. The details/direction of things
is flipped in a number of places. The strategy number differs, even
though the same function is called.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

20 March, 00:08:38

On Tue, Mar 18, 2025 at 3:15 PM Peter Geoghegan <pg@bowt.ie> wrote:
> I've actually come around to your point of view on this (or what I
> thought was your PoV from our call). That is, I now *think* that it
> would be better if the code added by 0003-* called
> _bt_skip_ikeyprefix, without regard for whether or not we'll have a
> finaltup _bt_checkkeys call to "recover" (i.e. whether we're on the
> leftmost or rightmost page shouldn't matter).
>
> My change in perspective on this question is related to another change
> of perspective, on the question of whether we actually need to call
> _bt_start_array_keys as part of "recovering/restoring the array
> invariant", just ahead of the finaltup _bt_checkkeys call. As you
> know, 0003-* calls _bt_start_array_keys in this way, but that now
> seems like overkill. It can have undesirable side-effects when the
> array keys spuriously appear to advance, when in fact they were
> restarted via the _bt_start_array_keys call, only to have their
> original values restored via the finaltup call that immediately
> follows.

> Tying it back to your concern, once I do that (once I stop calling
> _bt_start_array_keys in 0003-* to "hard reset" the arrays), I can also
> stop caring about finaltup being set on the rightmost page, at the
> point where we decide if _bt_skip_ikeyprefix should be called.

Attached is v29, which teaches _bt_skip_ikeyprefix to do things along
these lines (_bt_skip_ikeyprefix is added by 0003-*, same as last
time) . That's the first notable change for v29.

> > The code halts optimizing "prefix prechecks" when we notice a
> > non-equality key. It seems to me that we can do the precheck on shared
> > prefixes with non-equality keys just the same as with equality keys;
> > and it'd improve performance in those cases, too.
>
> Yeah, I was thinking of doing this already (though not for RowCompare
> inequalities, which would be hard to evaluate from here). It makes
> sense because it's exactly the same case as the range skip array case,
> really -- why not just do it the same way?

Second notable change for v29:

v29 also teaches 0003-* to handle plain inequalities (not just range
skip arrays) within _bt_skip_ikeyprefix, as I outlined to Matthias
here.

FWIW this doesn't really help much in practice, because scans that
benefit only do so to a limited degree, under fairly narrow
circumstances (I can explain what I mean by that if you're interested,
but it's not all that interesting). Even still, as I said the other
day, I think that it's worth doing this on consistency grounds. The
underlying rules that make this safe are literally identical to the
rules for range skip arrays (where determining if a key can be skipped
in _bt_skip_ikeyprefix tends to be much more important), so not doing
it with simple lower-order inequalities could confuse the reader.

Third notable change for v29:

Quite a few small improvements have been made to our new cost model,
in selfuncs.c/btcostestimate (see 0002-*, the main commit/patch that
introduces skip scan). The code is much better commented, and is more
idiomatic.

Most notably, I'm now using clauselist_selectivity() to adjust
ndistinct, as part of estimating the scan's num_sa_scans (I'm no
longer doing that in an ad-hoc way). The control flow is a lot easier
to understand. There are now a couple of new cases where we
conservatively fall back on using the old costing (i.e. we cost the
scan as if it was a Postgres 17 full index scan) for lack of a better
idea about what to do. We do this when we detect a default/generic
ndistinct estimate (we chicken out there), and we do it when we see a
range of values/a set of RestringInfos against a single column whose
selectivity is already relatively high (specifically, under
DEFAULT_RANGE_INEQ_SEL, meaning a selectivity that's under half a
percentage point).

Here are my plans around committing the patches:

* 0001-* can be committed within a matter of days. Probably before the
week is out.

It is commitable now, and is independently useful work.

* The remaining patches in the patch series (0002-* through to 0004-*)
are very close to being committable, but are still not quite ready.

I'm going to hold off on committing the big patches until late next
week, at the earliest. My current best estimate is that the bulk of
this work (0002-* through to 0004-*) will be committed together, on or
about April 2 (I suppose that I could commit 0004-* a few days later,
just to give things time to settle, but it wouldn't make sense to
commit 0002-* without also committing 0003-* immediately afterwards).

The tricky logic added by 0003-* is my single biggest outstanding
concern about the patch series. Particularly its potential to confuse
the existing invariants for required arrays. And particularly in light
of the changes that I made to 0003-* in the past few days. In short, I
need to think long and hard about the stuff I described under "Here's
how I think that this will be safe:" in my email to Matthias from
yesterday. The precondition and postcondition assertions in
_bt_advance_array_keys (added to Postgres 17) remain effective, which
gives me a certain amount of confidence in the changes made by 0003-*.

Thanks
--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

21 March, 18:36:18

On Wed, Mar 19, 2025 at 5:08 PM Peter Geoghegan <pg@bowt.ie> wrote:
> The tricky logic added by 0003-* is my single biggest outstanding
> concern about the patch series. Particularly its potential to confuse
> the existing invariants for required arrays. And particularly in light
> of the changes that I made to 0003-* in the past few days.

A big part of the concern here is with the existing pstate.prechecked
optimization (the one added to Postgres 17 by Alexander Korotkov's
commit e0b1ee17). It now seems quite redundant -- the new
_bt_skip_ikeyprefix mechanism added by my 0003-* patch does the same
thing, but does it better (especially since I taught
_bt_skip_ikeyprefix to deal with simple inequalities in v29). I now
think that it makes most sense to totally replace pstate.prechecked
with _bt_skip_ikeyprefix -- we should use _bt_skip_ikeyprefix during
every scan (not just during skip scans, not just during scans with
SAOP array keys), and be done with it.

To recap, right now the so->scanBehind flag serves two roles:

1. It lets us know that it is unsafe to apply the pstate.prechecked
optimization when _bt_readpage gets to the next page.

2. It lets us know that a recheck of the finaltup tuple is required on
the next page (right now that is limited to forwards scans that
encounter a truncated high key, but I intend to expand it in the
0001-* patch to other cases where we want to move onto the next page
without being 100% sure that it's the right thing to do).

Role #1 is related to the fact that pstate.prechecked works in a way
that doesn't really know anything about SAOP array keys. My Postgres
17 commit 5bf748b8 added role #1, to work around the problem of the
precheck being confused in cases where the scan's array keys are
advanced before we reach the final tuple on the page (the precheck
tuple). That way, scans with array keys were still able to safely use
the pstate.prechecked optimization, at least in simpler cases.

The new, similar _bt_skip_ikeyprefix mechanism has no need to check
scanBehind like this. That's because it is directly aware of both SAOP
arrays and skip arrays (it doesn't actually examine the sk_argument
from a scan key associated with an array, it just looks at the array
itself). That's a big advantage -- especially in light of the
scheduling improvements from 0001-*, which will make many more
_bt_readpage calls see the so->scanBehind flag as set (making us not
use pstate.prechecked). The new scheduling stuff from 0001-* affects
scans with skip arrays and SAOP arrays in just the same way, and yet
right now there's an unhelpful disconnect between what each case will
do once it reaches the next page. This is probably the single biggest
point that makes pstate.prechecked seem like it clashes with
_bt_skip_ikeyprefix: it undermines the principle that array type (SAOP
array vs skip array) should not matter anywhere outside of the lowest
level nbtutils.c code, which is a principle that now seems important.

Another key advantage of the _bt_skip_ikeyprefix mechanism is that it
can plausibly work in many cases that pstate.prechecked currently
can't handle at all. The design of pstate.prechecked makes it an "all
or nothing" thing -- it either works for every scan key required in
the scan direction, or it works for none at all. Not so for
_bt_skip_ikeyprefix; it can set pstate.ikey to skip a prefix of = scan
keys (a prefix of keys known to satisfy all tuples on pstate.page),
without the prefix necessarily including every = scan key. That
flexibility could matter a lot.

Furthermore, it can do this (set pstate.ikey to a value greater than
0) *without* needing to set pstate.forcenonrequired to make it safe
(pstate.forcenonrequired must be set during scans with array keys to
set pstate.ikey to a non-zero value, but otherwise doesn't need to be
set). In other words, it's possible for most scans to use
_bt_skip_ikeyprefix without having to commit themselves to scan all of
the tuples on the page (unlike pstate.prechecked).

I'm pretty sure that this is the right direction already, for the
reasons given, but also because I already have a draft version that
passes all tests. It significantly improves performance in many of my
most important microbenchmarks: unsympathetic cases that previously
had 5%-10% regression in query execution time end up with only 2% - 5%
regressions. I think that that's because the draft patch completely
removes the "prechecked" code path from _bt_check_compare, which is a
very hot function -- especially during these adversarial
microbenchmarks.

Under this new scheme, so->scanBehind is strictly a flag that
indicates that a recheck is scheduled, to be performed once the scan
calls _bt_readpage for the next page. It no longer serves role #1,
only role #2. That seems significantly simpler.

Note that I'm *not* proposing to remove/replace the similar
pstate.firstmatch optimization (also added by Alexander Korotkov's
commit e0b1ee17). That's still independently useful (it'll complement
_bt_skip_ikeyprefix in just the same way as it complemented
pstate.prechecked).

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

22 March, 20:47:41

On Fri, Mar 21, 2025 at 11:36 AM Peter Geoghegan <pg@bowt.ie> wrote:
> A big part of the concern here is with the existing pstate.prechecked
> optimization (the one added to Postgres 17 by Alexander Korotkov's
> commit e0b1ee17). It now seems quite redundant -- the new
> _bt_skip_ikeyprefix mechanism added by my 0003-* patch does the same
> thing, but does it better (especially since I taught
> _bt_skip_ikeyprefix to deal with simple inequalities in v29). I now
> think that it makes most sense to totally replace pstate.prechecked
> with _bt_skip_ikeyprefix -- we should use _bt_skip_ikeyprefix during
> every scan (not just during skip scans, not just during scans with
> SAOP array keys), and be done with it.

I just committed "Improve nbtree array primitive scan scheduling".

Attached is v30, which fully replaces the pstate.prechecked
optimization with the new _bt_skip_ikeyprefix optimization (which now
appears in v30-0002-Lower-nbtree-skip-array-maintenance-overhead.patch,
and not in 0003-*, due to my committing the primscan scheduling patch
just now).

I'm now absolutely convinced that fully generalizing
_bt_skip_ikeyprefix (as described in yesterday's email) is the right
direction to take things in. It seems to have no possible downside.

> Under this new scheme, so->scanBehind is strictly a flag that
> indicates that a recheck is scheduled, to be performed once the scan
> calls _bt_readpage for the next page. It no longer serves role #1,
> only role #2. That seems significantly simpler.

I especially like this about the new _bt_skip_ikeyprefix scheme.
Having so->scanBehind strictly be a flag (that tracks if we need a
recheck at the start of reading the next page) substantially lowers
the cognitive burden for somebody trying to understand how the
primitive scan scheduling stuff works.

The newly expanded _bt_skip_ikeyprefix needs quite a bit more testing
and polishing to be committable. I didn't even update the relevant
commit message for v30. Plus I'm not completely sure what to do about
RowCompare keys just yet, which have some funny rules when dealing
with NULLs.

--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

26 March, 02:45:16

On Sat, Mar 22, 2025 at 1:47 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v30, which fully replaces the pstate.prechecked
> optimization with the new _bt_skip_ikeyprefix optimization (which now
> appears in v30-0002-Lower-nbtree-skip-array-maintenance-overhead.patch,
> and not in 0003-*, due to my committing the primscan scheduling patch
> just now).

Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
I've once again renamed, this time to _bt_set_startikey).

There are some bug fixes here (nothing very interesting), and the
heuristics have been tuned to take into account the requirements of
conventional SAOP scans with dense/contiguous array keys (we should
mostly just be preserving existing performance characteristics here).

> The newly expanded _bt_skip_ikeyprefix needs quite a bit more testing
> and polishing to be committable. I didn't even update the relevant
> commit message for v30. Plus I'm not completely sure what to do about
> RowCompare keys just yet, which have some funny rules when dealing
> with NULLs.

v31 fixes all these problems, too.

Most notably, v31 differs from v30 in that it removes *both* of the
optimizations added to Postgres 17 by Alexander Korotkov's commit
e0b1ee17 -- including the pstate.firstmatch optimization. I didn't
expect things to go this way. I recently said that pstate.firstmatch
is something that can and should be kept (and v30 only removed
pstate.prechecked). Obviously, I've since changed my mind.

I changed my mind because lots of things are noticeably faster this
way, across most of my microbenchmarks. These performance validation
tests/microbenchmarks are really sensitive to the number of branches
added to _bt_check_compare; removing anything nonessential from that
hot code path really matters here.

Notably, removing the pstate.firstmatch optimization (along with
removing pstate.prechecked) is enough to fully eliminate what I've
long considered to be the most important microbenchmark regressions. I
refer to the microbenchmark suite originally written by Masahiro
Ikeda, and later enhanced/expanded by me to use a wider variety of
data cardinalities and datatypes. For the last several months, I
thought we'd need to live with a 5% - 10% regression with such cases
(those were the numbers I've thrown around when giving a high-level
summary of the extent of the regressions in unfavorable cases). Now
these microbenchmarks show that the queries are all about ~2% *faster*
instead. What's more, there may even be a similar small improvement
for important standard benchmarks (not microbenchmarks), such as the
standard pgbench SELECT benchmark. (I think simple pgbench is that
much faster, which is enough to matter, but not enough that it's easy
to prove under time pressure.)

There is at least a theoretical downside to replacing
pstate.firstmatch with the new _bt_set_startikey path, that I must
acknowledge: we only actually call _bt_set_startikey on the second or
subsequent leaf page, so that's the earliest possible point that it
can help speed things up (exactly like pstate.prechecked). Whereas
pstate.firstmatch is usually effective right away, on the first page
(effective at allowing us to avoid evaluating > or >= keys in the
common case where we're scanning the index forwards). It's fair to
wonder how much we'd be missing out, by giving up on that advantage.
It's very difficult to actually see any benefit that can be tied to
that theoretical advantage for pstate.firstmatch, though.

What I actually see when I run my range microbenchmark suite with v31
(not the aforementioned main microbenchmark suite) is that simple
cases involving no skip arrays (only simple scalar inequalities), with
quals like "WHERE col BETWEEN 0 and 1_000_000" are now *also* about 2%
faster. Any slowdown is more than made up for. Granted, if I worked
hard enough I might find a counter-example, where it actually is
slower overall, but I just can't see that ever mattering enough to
make me reconsider getting rid of pstate.firstmatch.

--
Peter Geoghegan

Attachment

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

From

Alena Rybakina

Date:

28 March, 01:03:53

Hi!

On 26.03.2025 02:45, Peter Geoghegan wrote:

On Sat, Mar 22, 2025 at 1:47 PM Peter Geoghegan <pg@bowt.ie> wrote:

Attached is v30, which fully replaces the pstate.prechecked
optimization with the new _bt_skip_ikeyprefix optimization (which now
appears in v30-0002-Lower-nbtree-skip-array-maintenance-overhead.patch,
and not in 0003-*, due to my committing the primscan scheduling patch
just now).

Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
I've once again renamed, this time to _bt_set_startikey).

I reviewed your first patch and noticed that you added the ability to define new quals if the first column isn't used in the query.

I replied an example like this:

CREATE TABLE sales ( id SERIAL PRIMARY KEY, region TEXT, product TEXT, year INT );

INSERT INTO sales (region, product, year) SELECT CASE WHEN i % 4 <= 1 THEN 'North' WHEN i % 4 <= 2 THEN 'South' WHEN i % 4 <= 3 THEN 'East' ELSE 'West' END, CASE WHEN random() > 0.5 THEN 'Laptop' ELSE 'Phone' END, 2023 FROM generate_series(1, 100000) AS i;

vacuum analyze;

CREATE INDEX sales_idx ON sales (region, product, year);

EXPLAIN ANALYZE SELECT * FROM sales WHERE product = 'Laptop' AND year = 2023;

master gives the query plan with SeqScan:

QUERY PLAN --------------------------------------------------------------------------------------------------------------- Seq Scan on sales (cost=0.00..2137.00 rows=49703 width=19) (actual time=0.035..31.438 rows=50212.00 loops=1) Filter: ((product = 'Laptop'::text) AND (year = 2023)) Rows Removed by Filter: 49788 Buffers: shared hit=637 Planning: Buffers: shared hit=35 Planning Time: 0.695 ms Execution Time: 33.942 ms (8 rows)

Your patch sets fair costs for it and it helps take into account index scan path and in my opinion it is perfect!)

QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on sales (cost=652.46..2031.86 rows=49493 width=19) (actual time=18.039..33.723 rows=49767.00 loops=1) Recheck Cond: ((product = 'Laptop'::text) AND (year = 2023)) Heap Blocks: exact=637 Buffers: shared hit=642 read=50 -> Bitmap Index Scan on sales_idx (cost=0.00..640.09 rows=49493 width=0) (actual time=17.756..17.756 rows=49767.00 loops=1) Index Cond: ((product = 'Laptop'::text) AND (year = 2023)) Index Searches: 4 Buffers: shared hit=5 read=50 Planning: Buffers: shared hit=55 read=1 Planning Time: 0.984 ms Execution Time: 36.940 ms

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)":

QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on sales (cost=652.46..2031.86 rows=49493 width=19) (actual time=18.039..33.723 rows=49767.00 loops=1) Recheck Cond: ((product = 'Laptop'::text) AND (year = 2023)) Heap Blocks: exact=637 Buffers: shared hit=642 read=50 -> Bitmap Index Scan on sales_idx (cost=0.00..640.09 rows=49493 width=0) (actual time=17.756..17.756 rows=49767.00 loops=1) Index Cond: ((product = 'Laptop'::text) AND (year = 2023)) Skip Scan on region (4 distinct values) Index Searches: 4 Buffers: shared hit=5 read=50 Planning: Buffers: shared hit=55 read=1 Planning Time: 0.984 ms Execution Time: 36.940 ms

What do you think?

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.

-- 
Regards,
Alena Rybakina
Postgres Professional

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

From

Peter Geoghegan

Date:

28 March, 23:15:19

On Thu, Mar 27, 2025 at 6:03 PM Alena Rybakina
<a.rybakina@postgrespro.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.

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

* 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).

* 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). 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.

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.

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 didn't see any regression tests. Maybe we should add some tests? To be honest I didn't see it mentioned in the
commitmessage 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!
--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

29 March, 00:59:22

On Tue, Mar 25, 2025 at 7:45 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
> I've once again renamed, this time to _bt_set_startikey).

Attached is v32, which has very few changes, but does add a new patch:
a patch that adds skip-array-specific primitive index scan heuristics
to _bt_advance_array_keys (this is
v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).

I feel compelled to do something about cases like the ones highlighted
by the attached test case, heikki-testcase-variant.sql. This shows how
the new heuristic added by my recent commit 9a2e2a28 can still
sometimes fail to ever be reached, in cases rather like the ones that
that was supposed to address [1]. This test case I'm posting now is
based on Heikki's adversarial test case (the one he posted back in
January). I've pushed it a bit further, demonstrating a remaining need
to tweak the primscan scheduling heuristics in light of skip scan. If
you run heikki-testcase-variant.sql against a patched server, without
v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch, you'll see
exactly what I'm concerned about .

I am somewhat breaking my own rule about not inventing heuristics that
specifically care about which type of array (skip vs SAOP array) are
involved here. In my defense, the new heuristic isn't particularly
likely to influence primscan scheduling. It will seldom be needed or
have any noticeable influence, but just might be crucial with cases
like the one from the test case. It seems a little too hard for skip
scans to actually get the behavior from commit 9a2e2a28 -- which is
something that we really shouldn't leave to chance.

The plan around committing this work hasn't changed: I still intend to
commit everything next Wednesday or Thursday. Hope to get a review of
the new scan heuristic before then, but it's a small adjunct to what I
did in commit 9a2e2a28, so not too concerned about it adding risk.

Thanks

[1] https://postgr.es/m/aa55adf3-6466-4324-92e6-5ef54e7c3918@iki.fi

--
Peter Geoghegan

Attachment

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

From

Peter Geoghegan

Date:

01 April, 05:02:25

On Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v32, which has very few changes, but does add a new patch:
> a patch that adds skip-array-specific primitive index scan heuristics
> to _bt_advance_array_keys (this is
> v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).

Attached is v33, which:

* Polishes the recently introduced
0003-Improve-skip-scan-primitive-scan-scheduling.patch logic, and
tweaks related code in _bt_advance_array_keys.

This includes one bug fix affecting backwards scans, which no longer
reuse pstate.skip to stop reading tuples when so->scanBehind was set.
Now _bt_readpage's backwards scan loop tests so.scanBehind directly
and explicitly, instead (there's no such change to its forwards scan
loop, though).

In v32 we could accidentally set pstate.skip (which is mostly intended
to be used by the "look-ahead" optimization added by the Postgres 17
SAOP project) to 0 (InvalidOffsetNumber), which actually represents
"don't skip at all" -- that was wrong. This happened when the
"pstate.skip = pstate.minoffnum - 1" statement gave us
InvalidOffsetNumber because pstate.minoffnum was already 1
(FirstOffsetNumber).

(FWIW, this only affected backwards scans at the point that they read
the index's rightmost leaf page, since any other leaf page has to have
a high key at FirstOffSetNumber, which implies a pstate.minoffnum of
FirstOffsetNumber+1, which meant we set pstate.skip = 1
(FirstOffsetNumber) by subtraction, which accidentally failed to
fail).

* v33 also makes small tweaks and comment clean-ups to the logic in
and around _bt_set_startikey, added by 0002-*, with the goal
simplifying the code, and in particular making the possible impact of
pstate.forcenonrequired on maintenance of the scan's arrays clearer.

We must not break the rule established by the Postgres 17 SAOP work:
the scan's array keys should always track the scan's progress through
the index's key space (I refer to the rule explained by the 17 SAOP
commit's message, see commit
5bf748b86bc6786a3fc57fc7ce296c37da6564b0). While we do "temporarily
stop following that rule" within a given pstate.forcenonrequired call
to _bt_readpage (to save some cycles), that should never have lasting
side-effects; there should be no observable effect outside of
_bt_readpage itself. In other words, the use of
pstate.forcenonrequired by _bt_readpage should leave the scan's arrays
in exactly the same state as _bt_readpage would have left them had it
never used pstate.forcenonrequired mode to begin with.

(FWIW, I have no reason to believe that v32 had any bugs pertaining to
this. AFAICT it didn't actually break "the general rule established by
the Postgres 17 SAOP work", but the explanation for why that was so
was needlessly complicated.)

I'm now very close to committing everything. Though I do still want
another pair of eyes on the newer
0003-Improve-skip-scan-primitive-scan-scheduling.patch stuff before
commiting (since I still intend to commit all the remaining patches
together).

--
Peter Geoghegan

On 01.04.2025 17:39, Matthias van de Meent wrote:

On Fri, 28 Mar 2025 at 22:59, Peter Geoghegan <pg@bowt.ie> wrote:

On Tue, Mar 25, 2025 at 7:45 PM Peter Geoghegan <pg@bowt.ie> wrote:

Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
I've once again renamed, this time to _bt_set_startikey).

Attached is v32

+static bool _bt_s**parray_shrink

I'd like to understand the "shrink" here, as it's not entirely clear to me.
The functions are exclusively called through dispatch in
_bt_compare_array_scankey_args, and I'd expected that naming to be
extended to these functions.

I understood _bt_skiparray_shrink() as the function that refines the range of values that a skip array will consider,
by interpreting existing scalar inequality conditions and applying them to limit the bounds of the skip scan.
I understood "shrink" to mean narrowing the range of values that the skip array will consider during the index scan.

-- 
Regards,
Alena Rybakina
Postgres Professional

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

From

Peter Geoghegan

Date:

01 April, 22:01:38

On Tue, Apr 1, 2025 at 10:40 AM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> The review below was started for v31, then adapted to v32 when that
> arrived. I haven't cross-checked this with v33.

There's been hardly any changes to 0001- in quite a while, so that's fine.

> > Teach nbtree composite index scans to opportunistically skip over
> > irrelevant sections of composite indexes given a query with an omitted
> > prefix column.
>
> AFAIK, this is only the second reference to "composite" indexes, after
> a single mention in a comment in nbtsplitloc.c's _bt_strategy. IIUC,
> this refers to multi-column indexes, which is more frequently and more
> consistently used across the code base.

I don't think it makes much difference, but sure, I'll use the
multi-column index terminology. In both code comments, and in commit
messages.

> > When nbtree is passed input scan keys derived from a
> > query predicate "WHERE b = 5", new nbtree preprocessing steps now output
> > "WHERE a = ANY(<every possible 'a' value>) AND b = 5" scan keys.
>
> [...] new nbtree preprocessing steps now output +the equivalent of+ [...]
>
> > Preprocessing can freely add a skip array before or after any input
> > ScalarArrayOp arrays.
>
> This implies skip arrays won't be generated for WHERE b = 5 (a
> non-SAOP scankey) or WHERE b < 3 (not SAOP either), which is probably
> not intentional, so a rewording would be appreciated.

I don't agree. Yes, that sentence (taken in isolation) does not make
it 100% unambiguous. But, would anybody ever actually be misled? Even
once, ever? The misinterpretation of my words that you're concerned
about is directly contradicted by the whole opening paragraph. Plus,
it just doesn't make any sense. Obviously, you yourself never actually
interpreted it that way. Right?

The paragraph that this sentence appears in is all about the various
ways in which SAOP arrays and skip arrays are the same thing, except
at the very lowest level of the _bt_advance_array_keys code. I think
that that context makes it particularly unlikely that anybody would
ever think that I mean to imply something about the ways in which
non-array keys can be composed alongside skip arrays.

I'm pushing back here because I think that there's a real cost to
using overly defensive language, aimed at some imaginary person. The
problem with catering to such a person is that, overall, the
clarifications do more harm than good. What seems to end up happening
(I speak from experience with writing overly defensive comments) is
that the superfluous clarifications are read (by actual readers) the
wrong way -- they're read as if we must have meant quite a lot more
than what we actually intended.

More generally, I feel that it's a mistake to try to interpret your
words on behalf of the reader. While it's definitely useful to try to
anticipate the ways in which your reader might misunderstand, you
cannot reasonably do the work for them. It's usually (though not
always) best to deal with anticipated points of confusion by subtly
constructing examples that suggest that some plausible wrong
interpretation is in fact wrong, without drawing attention to it.
Coming right out and telling the reader what to not think *is* an
important tool, but it should be reserved for cases where it's truly
necessary.

> // nbtpreprocesskeys.c
>
> > +static bool _bt_s**parray_shrink
>
> I'd like to understand the "shrink" here, as it's not entirely clear to me.
> The functions are exclusively called through dispatch in
> _bt_compare_array_scankey_args, and I'd expected that naming to be
> extended to these functions.

I don't see the problem? As Alena pointed out, we're shrinking the
arrays here (or are likely to), meaning that we're usually going to
eliminate some subset of array elements. It's possible that this will
happen more than once for a given array (since there could be more
than one "contradictory" key on input). An array can only shrink
within _bt_compare_array_scankey_args -- it can never have new array
elements added.

> > + * This qual now becomes "WHERE x = ANY('{every possible x value}') and y = 4"
>
> I understand what you're going for, but a reference that indexed NULLs
> are still handled correctly (rather than removed by the filter) would
> be appreciated, as the indicated substitution would remove NULL
> values. (This doesn't have to be much more than a footnote.)

Why, though? Obviously, '{every possible x value}' isn't a valid array
literal. Doesn't that establish that this isn't a 100% literal
statement of fact?

There are a handful of places where I make a similar statement (the
commit message is another one, as is selfuncs.c). I do make this same
point about NULLs being just another value in selfuncs.c, though only
because it's relevant there. I don't want to talk about NULLs here,
because they just aren't relevant to this high-level overview at the
top of _bt_preprocess_keys. We do talk about the issue of skip arrays
and IS NOT NULL constraints elsewhere in nbtree: we talk about those
issues in _bt_first (shortly after _bt_preprocess_keys is called).

Again, it comes down to what the reader might actually be confused by,
in the real world. Is it really plausible that I could ever commit a
skip scan patch that wholly forgot to deal with NULLs sensibly? Would
you personally ever think that I could make such an obvious blunder in
a committed patch? And if you did, how long would it take you to
figure out that there was no such oversight?

> > + * Also sets *numSkipArrayKeys to # of skip arrays _bt_preprocess_array_keys
> > + * caller must add to the scan keys it'll output.  Caller must add this many
> > + * skip arrays to each of the most significant attributes lacking any keys
>
> I don't think that's a good description; as any value other than 0 or
> 1 would mean more than one skip array per such attribute, which is
> obviously incorrect. I think I'd word it like:
>
> + * Also sets *numSkipArrayKeys to # of skip arrays _bt_preprocess_array_keys
> + * caller must add to the scan keys it'll output.  Caller will have to add
> + * this many skip arrays: one for each of the most significant attributes
> + * lacking any keys that use the = strategy [...]

I agree that it's better your way. Will fix.

> > +#if 0
> > +                /* Could be a redundant input scan key, so can't do this: */
> > +                Assert(inkey->sk_strategy == BTEqualStrategyNumber ||
> > +                       (inkey->sk_flags & SK_SEARCHNULL));
> > +#endif
>
> I think this should be removed?

Why? This is me expressing that I wish I could write this assertion,
but it won't quite work. I cannot rule out rare corner-cases involving
a contradictory pair of input keys, only one of which is a = key (the
other might be some kind of inequality, which makes this would-be
assertion not quite work). (You'll see similar "almost assertions"
from time to time, in different parts of the codebase.)

> > +#ifdef DEBUG_DISABLE_SKIP_SCAN
>
> I noticed this one and only reference to DEBUG_DISABLE_SKIP_SCAN. Are
> you planning on keeping that around, or is this a leftover?

I deliberately left this in place, just in case somebody wants to see
what happens when preprocessing stops generating skip arrays entirely.
Without this, it's not too obvious that it can just be turned off by
forcing _bt_num_array_keys to return early.

> > +        ScanKey        inkey = scan->keyData + i;
> > +
> > +        /*
> > +         * Backfill skip arrays for any wholly omitted attributes prior to
> > +         * attno_inkey
> > +         */
> > +        while (attno_skip < attno_inkey)
>
> I don't understand why we're adding skip keys before looking at the
> contents of this scankey, nor why we're backfilling skip keys based on
> a now old value of attno_inkey. Please
> add some comments on how/why this is the right approach.

_bt_num_array_keys should add exactly the minimum number of skip
arrays that will allow the standard _bt_preprocess_keys logic to mark
every input scan key (copied from scan->keyData[]) as required to
continue the scan on output (when output to so->keyData[]). It just
makes sense to structure the loop in a way that adds skip arrays just
before moving on to some input scan key on some never-before-seen
index column -- that's just how this needs to work.

Very early versions of the patch added skip arrays in cases involving
inequalities that could already be marked required. That approach
could probably work, but has no advantages, and some downsides. Now we
avoid adding skip arrays given a simple case like "WHERE a BETWEEN 1
AND 10". We only want to do it in cases like "WHERE a BETWEEN 1 AND 10
AND b = 42" -- since adding a skip array on "a" is strictly necessary
to be able to mark the = key on "b" as required. In the latter case,
the loop inside _bt_num_array_keys will add a skip array on "a" once
it gets past the final "a" input key (i.e. once it sees that the next
key is the = key on "b"). In the former case, there is no key on "b",
and so we don't add any skip arrays at all (which is the correct
behavior).

BTW, this _bt_num_array_keys code was primarily tested by writing lots
of complicated cases that tickled every edge-case I could think of. I
wrote tests that relied on my nbtree scan instrumentation patch, which
can print the details of both input and output keys -- I didn't rely
on testing any runtime behavior for this (that wouldn't have worked as
well). This includes any key markings (markings such as
SK_BT_REQFWD/SK_BT_REQBKWD), which is what I expected to see on every
scan key output (barring a couple of special cases, such as the
RowCompare case). Again, that is all that the "where do we add skip
arrays?" logic in _bt_num_array_keys is concerned with.

> > prev_numSkipArrayKeys, *numSkipArrayKeys
>
> I'm a bit confused why we primarily operate on *numSkipArrayKeys,
> rather than a local variable that we store in *numSkipArrayKeys once
> we know we can generate skip keys. I.e., I'd expected something more
> in line with the following snippet (incomplete code blocks):
> I think this is easier for the compiler to push the store operation
> out of the loop (assuming it's optimizable at all; but even if it
> isn't it removes the load of *numSkipArrayKeys from the hot path).

What if I just had a local copy of numSkipArrayKeys, and copied back
into caller's arg when the function returns? We'll still need a
prev_numSkipArrayKeys under this scheme, but we won't have to set the
caller's pointer until right at the end anymore (which, I agree, seems
like it might be worth avoiding).

> I think the increment/decrement callbacks for skipsupport should
> explicitly check (by e.g. Assert) for NULL (or alternatively: same
> value) returns on overflow, and the API definition should make this
> explicit.

But the API definition *does* specifically address the opclass
author's responsibilities around NULLs? It specifically says that it's
not up to the opclass author to think about them at all.

> The current system is quite easy to build a leaking
> implementation for. Sure, there are other easy ways to break this, but
> I think it's an easy API modification that makes things just that bit
> safer.

How can I do that? The callbacks themselves (the callbacks for
functions that are called as the scan progresses) don't use the fmgr
interface.

They're simple C function pointers (rather like sort support
callbacks), and do not have any args related to NULLs. They accept a
raw Datum, which can never be a NULL. The convention followed by
similar functions that are passed a Datum that might just be a NULL is
for the function to also accept a separate "bool isnull" argument.
(Just not having such a separate bool arg is another existing
convention, and the one that I've followed here.)

> A renewed review for 0002+ will arrive at a later point.

Thanks for the review!

--
Peter Geoghegan

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

From

Alena Rybakina

Date:

01 April, 22:08:26

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.rybakina@postgrespro.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

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

From

Matthias van de Meent

Date:

01 April, 23:16:15

On Tue, 1 Apr 2025 at 21:02, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Tue, Apr 1, 2025 at 10:40 AM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
> > > When nbtree is passed input scan keys derived from a
> > > query predicate "WHERE b = 5", new nbtree preprocessing steps now output
> > > "WHERE a = ANY(<every possible 'a' value>) AND b = 5" scan keys.
> >
> > [...] new nbtree preprocessing steps now output +the equivalent of+ [...]
> >
> > > Preprocessing can freely add a skip array before or after any input
> > > ScalarArrayOp arrays.
> >
> > This implies skip arrays won't be generated for WHERE b = 5 (a
> > non-SAOP scankey) or WHERE b < 3 (not SAOP either), which is probably
> > not intentional, so a rewording would be appreciated.
>
> I don't agree. Yes, that sentence (taken in isolation) does not make
> it 100% unambiguous. But, would anybody ever actually be misled? Even
> once, ever? The misinterpretation of my words that you're concerned
> about is directly contradicted by the whole opening paragraph. Plus,
> it just doesn't make any sense. Obviously, you yourself never actually
> interpreted it that way. Right?

That's built on my knowledge about the internals of this patch ahead
of reading the message, not on a clean-sleet interpretation.

> The paragraph that this sentence appears in is all about the various
> ways in which SAOP arrays and skip arrays are the same thing, except
> at the very lowest level of the _bt_advance_array_keys code. I think
> that that context makes it particularly unlikely that anybody would
> ever think that I mean to imply something about the ways in which
> non-array keys can be composed alongside skip arrays.
>
> I'm pushing back here because I think that there's a real cost to
> using overly defensive language, aimed at some imaginary person.

While I agree that there is such a cost, I don't think that this is
too far fetched. They are not just added when we have SAOP scankeys,
and I think the non-SAOP case is one of the most important areas where
this patch improves performance. Yes, this patch improves performance
for queries with only SAOP on non-first keys, but I've seen more
non-SAOP queries where this patch would improve performance than
similar queries but with SAOP.

> > // nbtpreprocesskeys.c
> >
> > > +static bool _bt_s**parray_shrink
> >
> > I'd like to understand the "shrink" here, as it's not entirely clear to me.
> > The functions are exclusively called through dispatch in
> > _bt_compare_array_scankey_args, and I'd expected that naming to be
> > extended to these functions.
>
> I don't see the problem?

It's mostly as an observation (and not problem per se) that "compare"
(which sounds like a pure function that doens't modify anything, e.g.
_bt_compare) is used to dispatch to "shrink" (which does sound like
it'd modify something).

> > > + * This qual now becomes "WHERE x = ANY('{every possible x value}') and y = 4"
> >
> > I understand what you're going for, but a reference that indexed NULLs
> > are still handled correctly (rather than removed by the filter) would
> > be appreciated, as the indicated substitution would remove NULL
> > values. (This doesn't have to be much more than a footnote.)

> Again, it comes down to what the reader might actually be confused by,
> in the real world. Is it really plausible that I could ever commit a
> skip scan patch that wholly forgot to deal with NULLs sensibly? Would
> you personally ever think that I could make such an obvious blunder in
> a committed patch? And if you did, how long would it take you to
> figure out that there was no such oversight?

My comment is not about your potential future actions, but rather what
any future developer or committer working on this code might think and
worry about when reading this. = ANY {} constructs *always* have NOT
NULL behaviour, just like any other operator clause that isn't "IS
NULL", so clarifying that this is only similar -and does not behave
the same in important edge cases- is IMO important. Not specifically
for you, but for any other developer trying to get a correct
understanding of how this works and why it is correct.

> > > +#if 0
> > > +                /* Could be a redundant input scan key, so can't do this: */
> > > +                Assert(inkey->sk_strategy == BTEqualStrategyNumber ||
> > > +                       (inkey->sk_flags & SK_SEARCHNULL));
> > > +#endif
> >
> > I think this should be removed?
>
> Why? This is me expressing that I wish I could write this assertion,
> but it won't quite work. I cannot rule out rare corner-cases involving
> a contradictory pair of input keys, only one of which is a = key (the
> other might be some kind of inequality, which makes this would-be
> assertion not quite work). (You'll see similar "almost assertions"
> from time to time, in different parts of the codebase.)

It is my understanding that those are mostly historical artifacts of
the code base, and not systems in active development. Their rarety
makes it difficult to put numbers on, but IIRC at least one such case
was recently removed for bitrot and apparent lack of use in years.

> > > +#ifdef DEBUG_DISABLE_SKIP_SCAN
> >
> > I noticed this one and only reference to DEBUG_DISABLE_SKIP_SCAN. Are
> > you planning on keeping that around, or is this a leftover?
>
> I deliberately left this in place, just in case somebody wants to see
> what happens when preprocessing stops generating skip arrays entirely.
> Without this, it's not too obvious that it can just be turned off by
> forcing _bt_num_array_keys to return early.

Ah, I see.

> > > prev_numSkipArrayKeys, *numSkipArrayKeys
> >
> > I'm a bit confused why we primarily operate on *numSkipArrayKeys,
> > rather than a local variable that we store in *numSkipArrayKeys once
> > we know we can generate skip keys. I.e., I'd expected something more
> > in line with the following snippet (incomplete code blocks):
> > I think this is easier for the compiler to push the store operation
> > out of the loop (assuming it's optimizable at all; but even if it
> > isn't it removes the load of *numSkipArrayKeys from the hot path).
>
> What if I just had a local copy of numSkipArrayKeys, and copied back
> into caller's arg when the function returns? We'll still need a
> prev_numSkipArrayKeys under this scheme, but we won't have to set the
> caller's pointer until right at the end anymore (which, I agree, seems
> like it might be worth avoiding).

That's a nice alternative too, indeed.

> > I think the increment/decrement callbacks for skipsupport should
> > explicitly check (by e.g. Assert) for NULL (or alternatively: same
> > value) returns on overflow, and the API definition should make this
> > explicit.
>
> But the API definition *does* specifically address the opclass
> author's responsibilities around NULLs? It specifically says that it's
> not up to the opclass author to think about them at all.

Yes. What I'm suggesting is to make the contract enforceable to a
degree. If it was defined to "return (Datum) 0 on overflow", then that
could be Assert()ed; and code that does leak memory could get detected
by static analysis tools in the function scope because the allocation
didn't get returned, but with this definition returning an allocation
is never detected because that's not part of the contract.

> > The current system is quite easy to build a leaking
> > implementation for. Sure, there are other easy ways to break this, but
> > I think it's an easy API modification that makes things just that bit
> > safer.
>
> How can I do that? The callbacks themselves (the callbacks for
> functions that are called as the scan progresses) don't use the fmgr
> interface.

You could Assert(inc_sk_argument == (Datum) 0) in the oflow branch?
I'm certain that (Datum) 0 is an invalid representation of a pointer,
so we know that no allocated value is returned (be it new or
pre-existing).

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

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

From

Matthias van de Meent

Date:

02 April, 00:56:13

On Tue, 1 Apr 2025 at 04:02, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > Attached is v32, which has very few changes, but does add a new patch:
> > a patch that adds skip-array-specific primitive index scan heuristics
> > to _bt_advance_array_keys (this is
> > v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).
>
> Attached is v33

0001:

I just realised we never check whether skip keys' high/low_compare
values generate valid quals, like what you'd see generated for WHERE a
> 5 AND a < 3 AND b = 2;

This causes a performance regression in the patched version:

   ->  Index Only Scan using test_a_b_idx on test  (cost=0.14..8.16
rows=1 width=0) (actual time=0.240..0.241 rows=0.00 loops=1)
         Index Cond: ((a > 5) AND (a < 3) AND (b = 2))
         Heap Fetches: 0
         Index Searches: 1
         Buffers: shared hit=1

As you can see in this explain, we're doing an index search, while the
index searches attribute before this patch would've been 0 due to
conflicting conditions.

(This came up while reviewing 0004, when I thought about doing this
key consistency check after the increment/decrement optimization of
that patch and after looking couldn't find the skipscan bounds
consistency check at all)

0002:

// nbtutils.c

> +             * (safe even when "key->sk_attno <= firstchangingattnum")

Typo: should be "key->sk_attno >= firstchangingattnum".

I'd also refactor the final segment to something like the following,
to remove a redundant compare when the attribute we're checking is
equal between firsttup and lasttup:

+        firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc,
&firstnull);
+
+        /* Test firsttup */
+        _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
+                                   firstdatum, firstnull, array, key,
+                                   &result);
+        if (result != 0)
+            break;                /* unsafe */
+
+        /* both attributes are equal, so no need to check lasttup */
+        if (key->sk_attno < firstchangingattnum)
+            continue;
+
+        lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull);
+
+        /* Test lasttup */
+        _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
+                                   lastdatum, lastnull, array, key,
+                                   &result);
+        if (result != 0)
+            break;                /* unsafe */
+
+        /* Safe, range skip array satisfied by every tuple */

0003: LGTM

0004: LGTM, but note the current bug in 0001, which is probably best
solved with a fix that keeps this optimization in mind, too.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

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

From

Matthias van de Meent

Date:

02 April, 01:08:55

On Tue, 1 Apr 2025 at 23:56, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
>
> On Tue, 1 Apr 2025 at 04:02, Peter Geoghegan <pg@bowt.ie> wrote:
> >
> > On Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > > Attached is v32, which has very few changes, but does add a new patch:
> > > a patch that adds skip-array-specific primitive index scan heuristics
> > > to _bt_advance_array_keys (this is
> > > v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).
> >
> > Attached is v33
>
> 0001:
>
> I just realised we never check whether skip keys' high/low_compare
> values generate valid quals, like what you'd see generated for WHERE a
> > 5 AND a < 3 AND b = 2;
>
> This causes a performance regression in the patched version:

Apparently it's not a regression, as we don't have this check in place
in the master branch. So, that's an optimization for PG19.

Sorry for the noise.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

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

From

Peter Geoghegan

Date:

02 April, 02:02:54

On Tue, Apr 1, 2025 at 5:56 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> 0002:
>
> // nbtutils.c
>
> > +             * (safe even when "key->sk_attno <= firstchangingattnum")
>
> Typo: should be "key->sk_attno >= firstchangingattnum".

Good catch!

Though I think it should be "" safe even when "key->sk_attno >
firstchangingattnum" "", to highlight that the rule here is
significantly more permissive than even the nearby range skip array
case, which is still safe when (key->sk_attno == firstchangingattnum).

As I'm sure you realize, SAOP = keys and regular = keys are only safe
when "key->sk_attno < firstchangingattnum". So there are a total of 3
distinct rules about how firstchangingattnum affects whether it's safe
to advance pstate.startikey past a scan key (which of the 3 rules we
apply depends solely on the type of scan key).

In summary, simple = keys have the strictest firstchangingattnum rule,
range skip arrays/scalar inequalities have a somewhat less restrictive
rule, and non-range skip arrays have the least restrictive/most
permissive rule. As I think you understand already, it is generally
safe to set pstate.startikey to an offset that's past several earlier
simple skip arrays (against several prefix columns, all omitted from
the query) -- even when firstchangingattnum is the lowest possible
value (which is attnum 1).

> I'd also refactor the final segment to something like the following,
> to remove a redundant compare when the attribute we're checking is
> equal between firsttup and lasttup:

At one point the code did look like that, but I concluded that the
extra code wasn't really worth it. We can only save cycles within
_bt_set_startikey itself this way, which doesn't add up to much.
_bt_set_startikey is only called once per page.

Besides, in general it's fairly likely that a range skip array that
_bt_set_startikey sees won't be against a column that we already know
(from the _bt_keep_natts_fast precheck, which returns
firstchangingattnum) to only have one distinct value among all tuples
on the page.

> 0003: LGTM
>
> 0004: LGTM

Great, thanks!

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

03 April, 02:15:33

On Tue, Apr 1, 2025 at 4:16 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> While I agree that there is such a cost, I don't think that this is
> too far fetched. They are not just added when we have SAOP scankeys,
> and I think the non-SAOP case is one of the most important areas where
> this patch improves performance. Yes, this patch improves performance
> for queries with only SAOP on non-first keys, but I've seen more
> non-SAOP queries where this patch would improve performance than
> similar queries but with SAOP.

That's all likely to be true. I just don't think that the commit
message for the big commit (the part that you took issue with) said
anything that suggests otherwise.

To recap, the sentence in question says "Preprocessing can freely add
a skip array before or after any input ScalarArrayOp arrays". This is
mostly just making a high level point about the design itself -- so I
just don't get what you mean.

The "everything is an array" design is what allows skip arrays to work
with a qual like "WHERE b IN (1, 2, 3)", as you say. It's also what
allows things like "WHERE a IN (100, 500) AND c = 55" to work
efficiently, without introducing any special cases -- it works both
ways. And, a pair of skip arrays can also be composed together, in
just the same way as a pair of SAOP arrays. This all works in the same
way; _bt_advance_array_keys concepts like array roll over continue to
apply, with essentially zero changes to the high level design,
relative to Postgres 17. That's the core idea that the paragraph in
question conveys.

Recall that _bt_advance_array_keys likes to think of simple scalar =
keys as a degenerate single-value array. They are the same thing, for
the purposes of rolling over the scan's arrays. We need to use a 3-way
ORDER proc for scalar scan keys for this reason.

> It's mostly as an observation (and not problem per se) that "compare"
> (which sounds like a pure function that doens't modify anything, e.g.
> _bt_compare) is used to dispatch to "shrink" (which does sound like
> it'd modify something).

It sounds like it's modifying something because (as you must know) it
does just that. This has been the case since the Postgres 17 SAOP
patch, of course (only the use of the term "shrink" in a helper
function is new here).

I don't want to rename _bt_compare_scankey_args now (that name is well
over 20 years old). That would be what it would take to make this
consistent in the way you expect. I just don't think it matters very
much.

> My comment is not about your potential future actions, but rather what
> any future developer or committer working on this code might think and
> worry about when reading this. = ANY {} constructs *always* have NOT
> NULL behaviour, just like any other operator clause that isn't "IS
> NULL", so clarifying that this is only similar -and does not behave
> the same in important edge cases- is IMO important.

> Not specifically for you, but for any other developer trying to get a correct
> understanding of how this works and why it is correct.

How many times does it have to be clarified, though? Do I have to put
something about it anywhere I give a brief high-level description of
how skip arrays work, where it's natural to compare them to a
traditional SAOP that generates all possible matching elements?
Explaining the concepts in question is hard enough, without having to
always list all of the ways that my analogy isn't the full and literal
truth of the matter. It's already extremely obvious that it must be
far from a literal account of what happens.

> It is my understanding that those are mostly historical artifacts of
> the code base, and not systems in active development. Their rarety
> makes it difficult to put numbers on, but IIRC at least one such case
> was recently removed for bitrot and apparent lack of use in years.

It's effectively a comment (nobody is expected to ever uncomment it by
removing the "#ifdef 0"). Sometimes, comments become obsolete. It's a
trade-off.

> > What if I just had a local copy of numSkipArrayKeys, and copied back
> > into caller's arg when the function returns? We'll still need a
> > prev_numSkipArrayKeys under this scheme, but we won't have to set the
> > caller's pointer until right at the end anymore (which, I agree, seems
> > like it might be worth avoiding).
>
> That's a nice alternative too, indeed.

I'll do it that way in the commited patch. That's probably not going
to happen until Friday morning EST, to give me another full day to
work some more on the docs.

I don't see much point in posting another version of the patchset to the list.

> > But the API definition *does* specifically address the opclass
> > author's responsibilities around NULLs? It specifically says that it's
> > not up to the opclass author to think about them at all.
>
> Yes. What I'm suggesting is to make the contract enforceable to a
> degree. If it was defined to "return (Datum) 0 on overflow", then that
> could be Assert()ed; and code that does leak memory could get detected
> by static analysis tools in the function scope because the allocation
> didn't get returned, but with this definition returning an allocation
> is never detected because that's not part of the contract.

All B-Tree support functions aren't allowed to leak memory. Same with
all operators. This will be far from the only time that we expect
opclass authors to get that right. This mostly works just fine,
probably because an opclass that leaked memory like this would visibly
break quite quickly.

> You could Assert(inc_sk_argument == (Datum) 0) in the oflow branch?
> I'm certain that (Datum) 0 is an invalid representation of a pointer,
> so we know that no allocated value is returned (be it new or
> pre-existing).

I just don't see what the point would be. Nothing would stop a
decrement/increment callback that needs to allocate memory from
returning 0 and then leaking memory anyway.

--
Peter Geoghegan

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

From

Peter Geoghegan

Date:

03 April, 02:32:24

On Tue, Apr 1, 2025 at 3:08 PM Alena Rybakina <a.rybakina@postgrespro.ru> wrote:
> 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?

I don't see much value in that. We can sometimes have data skew that
makes the number of distinct values far from representative of how
many index searches were required. We can have 3 distinct prefix
column values within 90% of all leaf pages, while the remaining 10%
all have unique values. Skip scan will work quite well here (at least
compared to a traditional full index scan), but the number of distinct
values makes it look really bad.

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

I would also like this kind of stuff to appear in EXPLAIN. It's partly
hard because so much stuff happens outside of planning.

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

So, many types don't (and probably can't) offer skip support. Skip
scan still works there. The most common example of this is "text".

We're still using skip arrays when skipping using (say) a text column.
Conceptually, it's still "WHERE a = ANY(<every possible 'a' value>)",
even with these continuous data types. It is useful to "pretend that
we're using a discrete data type", so that everything can work in the
usual way (remember, I hate special cases). We need to invent another
way to "increment" a text datum, that works in the same way (but
doesn't really require understanding the semantics of text, or
whatever the data type may be).

See my explanation about this here:

https://postgr.es/m/CAH2-WznKyHq_W7heu87z80EHyZepQeWbGuAZebcxZHvOXWCU-w@mail.gmail.com

See the part of my email that begins with "I think that you're
probably still a bit confused because the terminology in this area is
a little confusing. There are two ways of explaining the situation
with types like text and numeric (types that lack skip support)...."

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

The benefit of using skip scan comes from all of the pages that we
*aren't* reading, that we'd usually have to read. Hard to show that.

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

Not for  Postgres 18.

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

Let's talk about it off list.

> 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 think that it's particularly worth adding something to EXPLAIN
ANALYZE that makes it obvious that the index in question might not be
what the user thinks that it is. It might be an index that does some
skipping, but is far from optimal. They might have simply overlooked
the fact that there is an "extra" column between the columns that
their query predicate actually uses, which is far slower than what is
possible with a separate index that also omits that column.

Basically, I think that the most important goal should be to try to
help the user to understand when they have completely the wrong idea
about the index. I think that it's much less important to help users
to understand exactly how well a skip scan performs, relative to some
theoretical ideal. The theoretical ideal is just too complicated.

> I'm not sure that I correctly understood about "separation optimizer index path/executor stage". Do you mean that
it'sbetter to do all the optimizations during index execution rather than during index execution? 

Yes. In general it's good if we can delay decisions about the scan's
behavior until runtime, when we have a more complete picture of what
the index actually looks like.

--
Peter Geoghegan

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

From

Alena Rybakina

Date:

04 April, 20:44:49

On 03.04.2025 02:32, Peter Geoghegan wrote:

On Tue, Apr 1, 2025 at 3:08 PM Alena Rybakina <a.rybakina@postgrespro.ru> wrote:

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?

I don't see much value in that. We can sometimes have data skew that
makes the number of distinct values far from representative of how
many index searches were required. We can have 3 distinct prefix
column values within 90% of all leaf pages, while the remaining 10%
all have unique values. Skip scan will work quite well here (at least
compared to a traditional full index scan), but the number of distinct
values makes it look really bad.

Yes, I agree — this could give a misleading impression when trying to evaluate the effectiveness of the feature.
I’ve spent quite some time thinking about whether there’s a better way to present this information, but I haven’t come up with a solid alternative.

To be honest, I’m starting to think that simply displaying the name of the skipped column might be sufficient.

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

So, many types don't (and probably can't) offer skip support. Skip
scan still works there. The most common example of this is "text".

We're still using skip arrays when skipping using (say) a text column.
Conceptually, it's still "WHERE a = ANY(<every possible 'a' value>)",
even with these continuous data types. It is useful to "pretend that
we're using a discrete data type", so that everything can work in the
usual way (remember, I hate special cases). We need to invent another
way to "increment" a text datum, that works in the same way (but
doesn't really require understanding the semantics of text, or
whatever the data type may be).

See my explanation about this here:

https://postgr.es/m/CAH2-WznKyHq_W7heu87z80EHyZepQeWbGuAZebcxZHvOXWCU-w@mail.gmail.com

See the part of my email that begins with "I think that you're
probably still a bit confused because the terminology in this area is
a little confusing. There are two ways of explaining the situation
with types like text and numeric (types that lack skip support)...."

I understand it. I agree with you that it should be extended to other types but I'm not sure how.

Maybe we can add an abstract iterator that will helps to get the next distinct value adapted to the type or
it needs to be added similar functions for each type. I think this topic is also for a separate thread)

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.

The benefit of using skip scan comes from all of the pages that we
*aren't* reading, that we'd usually have to read. Hard to show that.

I noticed statistics on the number of hit buffers, read buffers, for example, "Buffers: shared hit=3 read=52",
are you talking about this?

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.

Let's talk about it off list.

Okay. Thank you)

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 think that it's particularly worth adding something to EXPLAIN
ANALYZE that makes it obvious that the index in question might not be
what the user thinks that it is. It might be an index that does some
skipping, but is far from optimal. They might have simply overlooked
the fact that there is an "extra" column between the columns that
their query predicate actually uses, which is far slower than what is
possible with a separate index that also omits that column.

Basically, I think that the most important goal should be to try to
help the user to understand when they have completely the wrong idea
about the index. I think that it's much less important to help users
to understand exactly how well a skip scan performs, relative to some
theoretical ideal. The theoretical ideal is just too complicated.

Yes, I agree — this information can be valuable, especially for those investigating query performance issues.
In particular, for example, it helps in cases where the optimizer chooses a suboptimal index, and it's not obvious why.

I believe it’s important to display not just what expressions were used during planning, but also what was actually used during execution.
That information might be important when analyzing data skew, deciding whether extended statistics are needed, and
understanding how the planner's assumptions played out.

But this is a separate thread for discussion.

-- 
Regards,
Alena Rybakina
Postgres Professional