Horton

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

Peter Geoghegan <pg@bowt.ie>

View thread
From: Peter Geoghegan <pg@bowt.ie>
To: Matthias van de Meent <boekewurm+postgres@gmail.com>
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-02-15T23:01:50Z
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.

On Mon, Jan 22, 2024 at 4:13 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> Attached 2 patches: v11.patch-a and v11.patch-b. Both are incremental
> on top of your earlier set, and both don't allocate additional memory
> in the merge operation in non-assertion builds.
>
> patch-a is a trivial and clean implementation of mergesort, which
> tends to reduce the total number of compare operations if both arrays
> are of similar size and value range. It writes data directly back into
> the main array on non-assertion builds, and with assertions it reuses
> your binary search join on scratch space for algorithm validation.

This patch fails some of my tests on non-assert builds only (assert
builds pass all my tests, though). I'm using the first patch on its
own here.

While I tend to be relatively in favor of complicated assertions (I
tend to think the risk of introducing side-effects is worth it), it
looks like you're only performing certain steps in release builds.
This is evident from just looking at the code (there is an #else block
just for the release build in the loop). Note also that
"Assert(_bt_compare_array_elements(&merged[merged_nelems++], orig,
&cxt) == 0)" has side-effects in assert-enabled builds only (it
increments merged_nelems). While it's true that you *also* increment
merged_nelems *outside* of the assertion (or in an #else block used
during non-assert builds), that is conditioned on some other thing (so
it's in no way equivalent to the debug #ifdef USE_ASSERT_CHECKING
case). It's also just really hard to understand what's going on here.

If I was going to do this kind of thing, I'd use two completely
separate loops, that were obviously completely separate (maybe even
two functions). I'd then memcmp() each array at the end.

-- 
Peter Geoghegan