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

On Tue, Apr 1, 2025 at 9:26 AM Aleksander Alekseev
<aleksander@timescale.com> wrote:
> Can you think of any tests specifically for 0003, or relying on the
> added Asserts() is best we can do? Same question for 0002.

There are many more tests than those that are included in the patch. I
wrote and debugged all patches using TDD. This is also how I wrote the
Postgres 17 SAOP patch. (My test suite is actually a greatly expanded
version of the earlier SAOP patch's test suite, since this project is
a direct follow-up.)

These tests are not nearly stable enough to commit; they have
something like a 5% chance of spuriously failing when I run them,
generally due to concurrent autoanalyze activity that prevents VACUUM
from setting all VM bits. Almost all of the tests expect specific
index page accesses, which is captured by "Buffers:" output. I find
that the full test suite takes over 10 seconds to run with a debug
build. So they're really not too maintainable.

Every little behavioral detail has been memorialized by some test.
Many of the tests present some adversarial scenario where
_bt_advance_array_keys runs out of array keys before reaching the end
of a given page, where it must then decide how to get to the next leaf
page (the page whose key space matches the next distinct set of array
keys). We want to consistently make good decisions about whether we
should step to the next sibling page, or whether starting another
primscan to get to the next relevant leaf page makes more sense. That
comes up again and again (only a minority of these tests were written
to test general correctness).

I did write almost all of these tests before writing the code that
they test, but most of the tests never failed by giving wrong answers
to queries. They initially failed by not meeting some expectation that
I had in mind about how best to schedule primitive index scans.

What "the right decision" means when scheduling primitive index scans
is somewhat open to interpretation -- I do sometimes revise my opinion
in light of new information, or new requirements (SAOP scans have
basically the same issues as skip scans, but in practice skip scans
are more sensitive to these details). It's inherently necessary to
manage the uncertainty around which approach is best, in any given
situation, on any given page. Having a large and varied set of
scenarios seems to help to keep things in balance (it avoids unduly
favoring one type of scan or index over another).

> I can confirm that v33 applies and passes the test.
>
> 0002 adds _bt_set_startikey() to nbtutils.c but it is not well-covered
> by tests, many branches of the new code are never executed.

It's hard to get test coverage for these cases into the standard
regression tests, since the function is only called when on the second
or subsequent page of a given primscan -- you need quite a few
relatively big indexes. There are quite a few far-removed
implementation details that any test will inevitably have to rely on,
such as BLCKSZ, the influence of suffix truncation.

Just having test coverage of these branches wouldn't test much on its
own. In practice it's very likely that not testing the key directly
(incorrectly assuming that the _bt_keep_natts_fast precheck is enough,
just removing the uncovered branches) won't break queries at all. The
_bt_keep_natts_fast precheck tells us which columns have no more than
one distinct value on the page. If there's only one value, and if we
just left a page that definitely satisfied its keys, it's quite likely
that those same keys will also be satisfied on this new page (it's
just not certain, which is why _bt_set_startikey can't just rely on
the precheck, it has to test each key separately).

> ```
> @@ -2554,9 +2865,20 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
>               */
>              if (requiredSameDir)
>                  *continuescan = false;
> +            else if (unlikely(key->sk_flags & SK_BT_SKIP))
> +            {
> +                /*
> +                 * If we're treating scan keys as nonrequired, and encounter a
> +                 * skip array scan key whose current element is NULL, then it
> +                 * must be a non-range skip array
> +                 */
> +                Assert(forcenonrequired && *ikey > 0);
> +                return _bt_advance_array_keys(scan, NULL, tuple, tupnatts,
> +                                              tupdesc, *ikey, false);
> +            }
> ```
>
> This branch is also never executed during the test run.

FWIW I have a test case that breaks when this particular code is
removed, given a wrong answer.

This is just another way that _bt_check_compare can find that it needs
to advance the array keys in the context of forcenonrequired mode --
it's just like the other calls to _bt_advance_array_keys from
_bt_check_compare. This particular code path is only hit when a skip
array's current element is NULL, which is unlikely to coincide with
the use of forcenonrequired mode (NULL is just another array element).
We just need another _bt_advance_array_keys callsite because of how
things are laid out in _bt_check_compare, which deals with
ISNULL-marked keys separately.

> For your convenience I uploaded a complete HTML code coverage report
> (~36 Mb) [1].

Thanks. I actually generated a similar coverage report myself
yesterday. I'm keeping an eye on this, but I don't think that it's
worth aiming for very high test coverage for these code paths. Writing
a failing test case for that one ISNULL _bt_advance_array_keys code
path was quite difficult, and required quite a big index. That isn't
going to be acceptable within the standard regression tests.

-- 
Peter Geoghegan