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

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

Thanks!

The review below was started for v31, then adapted to v32 when that
arrived. I haven't cross-checked this with v33.

Review for 0001:

I have some comments on the commit message, following below.  _Note:
For smaller patches I would let small things like this go, but given
the complexity of the feature I think it is important to make sure
there can be no misunderstanding about how it works and why it's
correct. Hence, these comments._

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

FYI, I think "composite index" would be more likely to refer to GIN,
given its double-btree structure. If we are about to use this term
more often, an entry in the glossary would be in place.

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

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

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

> + * 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 [...]


> +#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?


> +#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?

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

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

+            if (!OidIsValid(skip_eq_ops[attno_skip - 1]))
+            {
+                /*
+                 * Cannot generate a skip array for this or later attributes
+                 * (input opclass lacks an equality strategy operator)
+                 */
+                return numArrayKeys + *numSkipArrayKeys;
+            }
+
+            /* plan on adding a backfill skip array for this attribute */
+            loc_numSkipArrayKeys++;
+            attno_skip++;
+        }
+
+        *numSkipArrayKeys = loc_numSkipArrayKeys;

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

// utils/skipsupport.h, nbtutils.c

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

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


Kind regards,

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