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

On Tue, 1 Apr 2025 at 04:02, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>
> On Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg(at)bowt(dot)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)