Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan

On Wed, 6 Mar 2024 at 22:46, Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
>
> On Wed, 6 Mar 2024 at 01:50, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> >
> > Are you still interested in working directly on the preprocessing
> > stuff?
>
> If you mean my proposed change to merging two equality AOPs, then yes.
> I'll try to fit it in tomorrow with the rest of the review.

I've attached v14, where 0001 is v13, 0002 is a patch with small
changes + some large comment suggestions, and 0003 which contains
sorted merge join code for _bt_merge_arrays.

I'll try to work a bit on v13/14's _bt_preprocess_keys, and see what I
can make of it.

> > I have a feeling that I was slightly too optimistic about how
> > likely we were to be able to get away with not having certain kinds of
> > array preprocessing, back when I posted v12. It's true that the
> > propensity of the patch to not recognize "partial
> > redundancies/contradictions" hardly matters with redundant equalities,
> > but inequalities are another matter. I'm slightly worried about cases
> > like this one:
> >
> > select * from multi_test where a in (1,99, 182, 183, 184) and a < 183;
> >
> > Maybe we need to do better with that. What do you think?
>
> Let me come back to that when I'm done reviewing the final part of nbtutils.
>
> > Attached is v13.
>
> It looks like there are few issues remaining outside the changes in
> nbtutils. I've reviewed the changes to those files, and ~half of
> nbtutils (up to _bt_advance_array_keys_increment) now. I think I can
> get the remainder done tomorrow.

> +_bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir)
[...]
> + if (!(cur->sk_flags & SK_SEARCHARRAY) &&
> + cur->sk_strategy != BTEqualStrategyNumber)
> + continue;

This should use ||, not &&: if it's not an array, or not an equality
array key, it's not using an array key slot and we're not interested.
Note that _bt_verify_arrays_bt_first does have the right condition already.

> + if (readpagetup || result != 0)
> + {
> + Assert(result != 0);
> + return false;
> + }

I'm confused about this. By asserting !readpagetup after this exit, we
could save a branch condition for the !readpagetup result != 0 path.
Can't we better assert the inverse just below, or is this specifically
for defense-in-depth against bug? E.g.

+ if (result != 0)
+ return false;
+
+ Assert(!readpagetup);

> + /*
> + * By here we have established that the scan's required arrays were
> + * advanced, and that they haven't become exhausted.
> + */
> + Assert(arrays_advanced || !arrays_exhausted);

Should use &&, based on the comment.

> + * We generally permit primitive index scans to continue onto the next
> + * sibling page when the page's finaltup satisfies all required scan keys
> + * at the point where we're between pages.

This should probably describe that we permit primitive scans with
array keys to continue until we get to the sibling page, rather than
this rather obvious and generic statement that would cover even the
index scan for id > 0 ORDER BY id asc; or this paragraph can be
removed.

+ if (!all_required_satisfied && pstate->finaltup &&
+ _bt_tuple_before_array_skeys(scan, dir, pstate->finaltup, false, 0,
+ &so->scanBehind))
+ goto new_prim_scan;

> +_bt_verify_arrays_bt_first(IndexScanDesc scan, ScanDirection dir)
[...]
> + if (((cur->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
> + ((cur->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
> + continue;

I think a simple check if any SK_BT_REQ flag is set should be OK here:
The key must be an equality key, and those must be required either in
both directions, or in neither direction.

-----

Further notes:

I have yet to fully grasp what so->scanBehind is supposed to mean. "/*
Scan might be behind arrays? */" doesn't give me enough hints here.

I find it weird that we call _bt_advance_array_keys for non-required
sktrig. Shouldn't that be as easy as doing a binary search through the
array? Why does this need to hit the difficult path?

Kind regards,

Matthias van de Meent