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>
Date: 2023-07-27T13:59:51Z
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 Thu, 27 Jul 2023 at 06:14, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Wed, Jul 26, 2023 at 12:07 PM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
> > We could cache the last accessed leaf page across amrescan operations
> > to reduce the number of index traversals needed when the join key of
> > the left side is highly (but not necessarily strictly) correllated.
>
> That sounds like block nested loop join. It's possible that that could
> reuse some infrastructure from this patch, but I'm not sure.

My idea is not quite block nested loop join. It's more 'restart the
index scan at the location the previous index scan ended, if
heuristics say there's a good chance that might save us time'. I'd say
it is comparable to the fast tree descent optimization that we have
for endpoint queries, and comparable to this patch's scankey
optimization, but across AM-level rescans instead of internal rescans.

See also the attached prototype and loosely coded patch. It passes
tests, but it might not be without bugs.

The basic design of that patch is this: We keep track of how many
times we've rescanned, and the end location of the index scan. If a
new index scan hits the same page after _bt_search as the previous
scan ended, we register that. Those two values - num_rescans and
num_samepage - are used as heuristics for the following:

If 50% or more of rescans hit the same page as the end location of the
previous scan, we start saving the scan's end location's buffer into
the BTScanOpaque, so that the next _bt_first can check whether that
page might be the right leaf page, and if so, immediately go to that
buffer instead of descending the tree - saving one tree descent in the
process.

Further optimizations of this mechanism could easily be implemented by
e.g. only copying the min/max index tuples instead of the full index
page, reducing the overhead at scan end.

Kind regards,

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