Horton

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

Matthias van de Meent <boekewurm+postgres@gmail.com>

View thread
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>, Tom Lane <tgl@sss.pgh.pa.us>, Tomas Vondra <tomas.vondra@enterprisedb.com>, Jeff Davis <pgsql@j-davis.com>, benoit <benoit@hopsandfork.com>, Alexander Korotkov <aekorotkov@gmail.com>, Heikki Linnakangas <hlinnaka@iki.fi>
Date: 2024-03-20T19:26:38Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Move nbtree preprocessing into new .c file.

  2. Fix nbtree lookahead overflow bug.

  3. Remove unneeded nbtree array preprocessing assert.

  4. Don't try to fix eliminated nbtree array scan keys.

  5. Remove redundant nbtree preprocessing assertions.

  6. Avoid extra lookups with nbtree array inequalities.

  7. Enhance nbtree ScalarArrayOp execution.

  8. Improvements and fixes for e0b1ee17dc

  9. Skip checking of scan keys required for directional scan in B-tree

  10. Fix btmarkpos/btrestrpos array key wraparound bug.

  11. Add nbtree high key "continuescan" optimization.

  12. Consider secondary factors during nbtree splits.

  13. Make heap TID a tiebreaker nbtree index column.

  14. Fix planning of btree index scans using ScalarArrayOpExpr quals.

  15. Fix btree stop-at-nulls logic properly.

  16. Teach btree to handle ScalarArrayOpExpr quals natively.

Attachments

On Sat, 16 Mar 2024 at 01:12, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Fri, Mar 8, 2024 at 9:00 AM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
> > 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.
>
> This is part of my next revision, v15, which I've attached (along with
> a test case that you might find useful, explained below).
>
> v15 makes the difference between the non-required scan key trigger and
> required scan key trigger cases clearer within _bt_advance_array_keys.

OK, here's a small additional review, with a suggestion for additional
changes to _bt_preprocess:

> @@ -1117,6 +3160,46 @@ _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
>      /*
>      * The opfamily we need to worry about is identified by the index column.
>      */
>     Assert(leftarg->sk_attno == rightarg->sk_attno);
>
> +    /*
> +     * If either leftarg or rightarg are equality-type array scankeys, we need
> +     * specialized handling (since by now we know that IS NULL wasn't used)
> +     */
> [...]
> +    }
> +
>     opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];

Here, you insert your code between the comment about which opfamily to
choose and the code assigning the opfamily. I think this needs some
cleanup.

> +             * Don't call _bt_preprocess_array_keys_final in this fast path
> +             * (we'll miss out on the single value array transformation, but
> +             * that's not nearly as important when there's only one scan key)

Why is it OK to ignore it? Or, why don't we apply it here?

---

Attached 2 patches for further optimization of the _bt_preprocess_keys
path (on top of your v15), according to the following idea:

Right now, we do "expensive" processing with xform merging for all
keys when we have more than 1 keys in the scan. However, we only do
per-attribute merging of these keys, so if there is only one key for
any attribute, the many cycles spent in that loop are mostly wasted.
By checking for single-scankey attributes, we can short-track many
multi-column index scans because they usually have only a single scan
key per attribute.
The first implements that idea, the second reduces the scope of
various variables so as to improve compiler optimizability.

I'll try to work a bit more on merging the _bt_preprocess steps into a
single main iterator, but this is about as far as I got with clean
patches. Merging the steps for array preprocessing with per-key
processing and post-processing is proving a bit more complex than I'd
anticipated, so I don't think I'll be able to finish that before the
feature freeze, especially with other things that keep distracting me.

Matthias van de Meent