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

On 2024-11-21 04:40, Peter Geoghegan wrote:
> On Wed, Nov 20, 2024 at 4:04 AM Masahiro Ikeda
> <ikedamsh(at)oss(dot)nttdata(dot)com> wrote:
>> Thanks for your quick response!
>
> Attached is v16. This is similar to v15, but the new
> v16-0003-Fix-regressions* patch to fix the regressions is much less
> buggy, and easier to understand.
>
> Unlike v15, the experimental patch in v16 doesn't change anything
> about which index pages are read by the scan -- not even in corner
> cases. It is 100% limited to fixing the CPU overhead of maintaining
> skip arrays uselessly *within* a leaf page. My extensive test suite
> passes; it no longer shows any changes in "Buffers: N" for any of the
> EXPLAIN (ANALYZE, BUFFERS) ... output that the tests look at. This is
> what I'd expect.
>
> I think that it will make sense to commit this patch as a separate
> commit, immediately after skip scan itself is committed. It makes it
> clear that, at least in theory, the new v16-0003-Fix-regressions*
> patch doesn't change any behavior that's visible to code outside of
> _bt_readpage/_bt_checkkeys/_bt_advance_array_keys.

Thanks for the update! I'll look into the details and understand the
approach to the commit.

>> I didn't come up with the idea. At first glance, your idea seems good
>> for all cases.
>
> My approach of conditioning the new "beyondskip" behavior on
> "has_skip_array && beyond_end_advance" is at least a good start.
>
> The idea behind conditioning this behavior on having at least one
> beyond_end_advance array advancement is pretty simple: in practice
> that almost never happens during skip scans that actually end up
> skipping (either via another _bt_first that redesends the index, or
> via skipping "within the page" using the
> _bt_checkkeys_look_ahead/pstate->skip mechanism). So that definitely
> seems like a good general heuristic. It just isn't sufficient on its
> own, as you have shown.

Yes, I think so. This idea can make the worst-case execution time of a
skip scan almost the same as that of a full index scan.

>> Actually, test.sql shows a performance improvement, and the
>> performance
>> is almost the same as the master's seqscan. To be precise, the
>> master's
>> performance is 10-20% better than the v15 patch because the seqscan is
>> executed in parallel. However, the v15 patch is twice as fast as when
>> seqscan is not executed in parallel.
>
> I think that that's a good result, overall.
>
> Bear in mind that a case such as this might receive a big performance
> benefit if it can skip only once or twice. It's almost impossible to
> model those kinds of effects within the optimizer's cost model, but
> they're still important effects.
>
> FWIW, I notice that your "t" test table is 35 MB, whereas its t_idx
> index is 21 MB. That's not very realistic (the index size is usually a
> smaller fraction of the table size than we see here), which probably
> partly explains why the planner likes parallel sequential scan for
> this.

Yes, I agree that the above case is not realistic. If anything, the
purpose of this case might be to simply find regression scenarios.

One possible use case I can think of is enforcing a unique constraint
on all columns. However, such cases are probably very rare.

> I have an experimental fix in mind for this case. One not-very-good
> way to fix this new problem seems to work:
>
> diff --git a/src/backend/access/nbtree/nbtutils.c
> b/src/backend/access/nbtree/nbtutils.c
> index b70b58e0c..ddae5f2a1 100644
> --- a/src/backend/access/nbtree/nbtutils.c
> +++ b/src/backend/access/nbtree/nbtutils.c
> @@ -3640,7 +3640,7 @@ _bt_advance_array_keys(IndexScanDesc scan,
> BTReadPageState *pstate,
> * for skip scan, and stop maintaining the scan's skip arrays
> until we
> * reach the page's finaltup, if any.
> */
> - if (has_skip_array && beyond_end_advance &&
> + if (has_skip_array && !all_required_satisfied &&
> !has_required_opposite_direction_skip && pstate->finaltup)
> pstate->beyondskip = true;
>
> However, a small number of my test cases now fail. And (I assume) this
> approach has certain downsides on leaf pages where we're now too quick
> to stop maintaining skip arrays.

Since I've built with the above change and executed make check, I found
that there is an assertion error, which may not be related to what you
pointed
out.

* the reproducible simple query (you can see the original query in
opr_sanity.sql).
select * from pg_proc
where proname in (
'lo_lseek64',
'lo_truncate',
'lo_truncate64')
and pronamespace = 11;

* the assertion error
TRAP: failed Assert("sktrig_required && required"), File:
"nbtutils.c", Line: 3375, PID: 362411

While investigating the error, I thought we might need to consider
whether key->sk_flags does not have SK_BT_SKIP. The assertion error
occurs because
requiredSameDir doesn't become true since proname does not have
SK_BT_SKIP.

+ if (beyondskip)
+ {
+ /*
+ * "Beyond end advancement" skip scan optimization.
+ *
+ * Just skip over any skip array scan keys. Treat all other scan
+ * keys as not required for the scan to continue.
+ */
+ Assert(!prechecked);
+
+ if (key->sk_flags & SK_BT_SKIP)
+ continue;
+ }
+ else if (((key->sk_flags & SK_BT_REQFWD) &&
ScanDirectionIsForward(dir)) ||
+ ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
requiredSameDir = true;

> What I really need to do next is to provide a vigorous argument for
> why the new pstate->beyondskip behavior is correct. I'm already
> imposing restrictions on range skip arrays in v16 of the patch --
> that's what the "!has_required_opposite_direction_skip" portion of the
> test is about. But it still feels too ad-hoc.
>
> I'm a little worried that these restrictions on range skip arrays will
> themselves be the problem for some other kind of query. Imagine a
> query like this:
>
> SELECT * FROM t WHERE id1 BETWEEN 0 AND 1_000_000 AND id2 = 1
>
> This is probably going to be regressed due to the aforementioned
> "!has_required_opposite_direction_skip" restriction. Right now I don't
> fully understand what restrictions are truly necessary, though. More
> research is needed.
>
> I think for v17 I'll properly fix all of the regressions that you've
> complained about so far, including the most recent "SELECT * FROM t
> WHERE id2 = 1_000_000" regression. Hopefully the best fix for this
> other "WHERE id1 BETWEEN 0 AND 1_000_000 AND id2 = 1" regression will
> become clearer once I get that far. What do you think?

To be honest, I don't fully understand
has_required_opposite_direction_skip
and its context at the moment. Please give me some time to understand
it,
and I'd like to provide feedback afterward.

FWIW, the optimization is especially important for types that don't
support
'skipsupport', like 'real'. Although the example case I provided uses
integer
types, they (like 'real') tend to have many different values and high
cardinality, which means the possibility of skip scan working
efficiently
can be low.

>> There may be a better way, such as the new idea you suggested, and I
>> think there
>> is room for discussion regarding how far we should go in handling
>> regressions,
>> regardless of whether we choose to accept regressions or sacrifice the
>> benefits of
>> skip scan to address them.
>
> There are definitely lots more options to address these regressions.
> For example, we could have the planner hint that it thinks that skip
> scan won't be a good idea, without that actually changing the basic
> choices that nbtree makes about which pages it needs to scan (only how
> to scan each individual leaf page). Or, we could remember that the
> previous page used "pstate-> beyondskip" each time _bt_readpage reads
> another page. I could probably think of 2 or 3 more ideas like that,
> if I had to.
>
> However, the problem is not a lack of ideas IMV. The important
> trade-off is likely to be the trade-off between how effectively we can
> avoid these regressions versus how much complexity each approach
> imposes. My guess is that complexity is more likely to impose limits
> on us than overall feasibility.

OK, I think you're right.

Regards,
--
Masahiro Ikeda
NTT DATA CORPORATION