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

Tomas Vondra <tomas.vondra@enterprisedb.com>

From: Tomas Vondra <tomas.vondra@enterprisedb.com>

To: Peter Geoghegan <pg@bowt.ie>, Matthias van de Meent <boekewurm+postgres@gmail.com>

Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>, Tom Lane <tgl@sss.pgh.pa.us>, Jeff Davis <pgsql@j-davis.com>, benoit <benoit@hopsandfork.com>, Alexander Korotkov <aekorotkov@gmail.com>

Date: 2023-11-28T12:29:27Z

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 →

Move nbtree preprocessing into new .c file.
- 597b1ffbf123 18.0 landed
Fix nbtree lookahead overflow bug.
- 09a8407dbfd8 18.0 landed
- 6749d4aabe74 17.0 landed
Remove unneeded nbtree array preprocessing assert.
- 480bc6e3ed3a 17.0 landed
Don't try to fix eliminated nbtree array scan keys.
- f22e17f76cf5 17.0 landed
Remove redundant nbtree preprocessing assertions.
- 3b08133cd13c 17.0 landed
Avoid extra lookups with nbtree array inequalities.
- 473411fc5115 17.0 landed
Enhance nbtree ScalarArrayOp execution.
- 5bf748b86bc6 17.0 landed
Improvements and fixes for e0b1ee17dc
- 7e6fb5da41d8 17.0 cited
Skip checking of scan keys required for directional scan in B-tree
- e0b1ee17dc3a 17.0 cited
Fix btmarkpos/btrestrpos array key wraparound bug.
- 714780dcddf0 17.0 cited
Add nbtree high key "continuescan" optimization.
- 29b64d1de7c7 12.0 cited
Consider secondary factors during nbtree splits.
- fab250243387 12.0 cited
Make heap TID a tiebreaker nbtree index column.
- dd299df8189b 12.0 cited
Fix planning of btree index scans using ScalarArrayOpExpr quals.
- 807a40c551dd 9.3.0 cited
Fix btree stop-at-nulls logic properly.
- 882368e854b6 9.2.0 cited
Teach btree to handle ScalarArrayOpExpr quals natively.
- 9e8da0f75731 9.2.0 cited

Attachments

saop-benchmark.pdf (application/pdf)
run-all.sh (application/x-shellscript)
run.sh (application/x-shellscript)

On 11/21/23 03:52, Peter Geoghegan wrote:
> On Sat, Nov 11, 2023 at 1:08 PM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
>> Thanks. Here's my review of the btree-related code:
> 
> Attached is v7.
> 

I haven't looked at the code, but I decided to do a bit of blackbox perf
and stress testing, to get some feeling of what to expect in terms of
performance improvements, and see if there happen to be some unexpected
regressions. Attached is a couple simple bash scripts doing a
brute-force test with tables of different size / data distribution,
number of values in the SAOP expression, etc.

And a PDF visualizing the comparing the results between master and build
with the patch applied. First group of columns is master, then patched,
and then (patched/master) comparison, with green=faster, red=slower. The
columns are for different number of values in the SAOP condition.

Overall, the results look pretty good, with consistent speedups of up to
~30% for large number of values (SAOP with 1000 elements). There's a
couple blips where the performance regresses, also by up to ~30%. It's
too regular to be a random variation (it affects different combinations
of parameters, tablesizes), but it seems to only affect one of the two
machines I used for testing. Interestingly enough, it's the newer one.

I'm not convinced this is a problem we have to solve. It's possible it
only affects cases that are implausible in practice (the script forces a
particular scan type, and maybe it would not be picked in practice). But
maybe it's fixable ...

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company