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-04-01T22:33:22Z
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 Tue, Mar 26, 2024 at 2:01 PM Peter Geoghegan <pg@bowt.ie> wrote:
> v17 replaces _bt_parallel_advance_array_keys with a new function,
> called _bt_parallel_primscan_advance, which is now called from
> _bt_advance_array_keys. The new function doesn't need to increment
> btscan->btps_arrayKeyCount (nor does it increment a local copy in
> BTScanOpaqueData.arrayKeyCount). It is called at the specific point
> that array key advancement *tries* to start another primitive index
> scan. The difference (relative to the serial case) is that it might
> not succeed in doing so. It might not be possible to start another
> primitive index scan, since it might turn out that some other backend
> (one page ahead, or even one page behind) already did it for
> everybody.

There was a bug in v17 around how we deal with parallel index scans.
Under the right circumstances, a parallel scan with array keys put all
of its worker processes to sleep, without subsequently waking them up
(so the scan would hang indefinitely). The underlying problem was that
v17 assumed that the backend that scheduled the next primitive index
scan would also be the one that actually performs that same primitive
scan. While it is natural and desirable for the backend that schedules
the primitive scan to be the one that actually calls _bt_search, v17
tacitly relied on that to successfully finish the scan. It's
particularly important that the leader process always be able to stop
participating as a worker immediately, whenever it needs to, and for
as long as it needs to.

Attached is v18, which adds an additional layer of indirection to fix
the bug: worker processes now schedule primitive index scans
explicitly. They store their current array keys in shared memory when
primitive scans are scheduled (during a parallel scan), allowing other
backends to pick things up where the scheduling backend left off. And
so with v18, any other backend can be the one that performs the actual
descent of the index within _bt_search.

The design is essentially the same as before, though. We'd still
prefer that it be the backend that scheduled the primitive index scan.
Other backends might well be busy finishing off their scan of
immediately preceding leaf pages.

Separately, v18 also adds many new regression tests. This greatly
improves the general situation around test coverage, which I'd put off
before now. Now there is coverage for parallel scans with array keys,
as well as coverage for the new array-specific preprocessing code.

Note: v18 doesn't have any adjustments to the costing, as originally
planned. I'll probably need to post a revised patch with improved (or
at least polished) costing in the next few days, so that others will
have the opportunity to comment before I commit the patch.

--
Peter Geoghegan