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: "Anton A. Melnikov" <a.melnikov@postgrespro.ru>
Cc: Matthias van de Meent <boekewurm+postgres@gmail.com>, 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-08-07T14:59:11Z
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 Wed, Jul 31, 2024 at 12:47 AM Anton A. Melnikov
<a.melnikov@postgrespro.ru> wrote:
>  From the 5bf748b86bc commit message:
>
> > There is a theoretical risk that removing restrictions on SAOP index
> > paths from the planner will break compatibility with amcanorder-based
> > index AMs maintained as extensions.  Such an index AM could have the
> > same limitations around ordered SAOP scans as nbtree had up until now.
> > Adding a pro forma incompatibility item about the issue to the Postgres
> > 17 release notes seems like a good idea.

Here you've quoted the commit message's description of the risks
around breaking third party index AMs maintained as extensions. FWIW
that seems like a rather different problem to the one that you ran
into with your KNN nbtree patch.

> Seems, this commit broke our posted knn_btree patch. [1]
> If the point from which ORDER BY goes by distance is greater than the elements of ScalarArrayOp,
> then knn_btree algorithm will give only the first tuple. It sorts the elements of ScalarArrayOp
> in descending order and starts searching from smaller to larger
> and always expects that for each element of ScalarArrayOp there will be a separate scan.
> And now it does not work. Reproduction is described in [2].
>
> Seems it is impossible to solve this problem only from the knn-btree patch side.
> Could you advise any ways how to deal with this. Would be very grateful.

Well, you're actually patching nbtree. Your patch isn't upstream of
the nbtree code. You're going to have to reconcile your design with
the design for advancing arrays that is primarily implemented by
_bt_advance_array_keys.

I'm not entirely sure what the best way to go about doing that is --
that would require a lot of context about the KNN patch. It wouldn't
be particularly hard to selectively reenable the old Postgres 16 SAOP
behavior, though. You could conditionally force "goto new_prim_scan"
whenever the KNN patch's mechanism was in use.

That kind of approach might have unintended consequences elsewhere,
though. For example it could break things like mark/restore processing
by merge joins, which assumes that the scan's current array keys can
always be reconstructed after restoring a marked position by resetting
the array's to their first elements (or final elements if it's a
backwards scan). On the other hand, I think that you already shouldn't
expect anything like that to work with your patch. After all, it
changes the order of the tuples returned by the scan, which is already
bound to break certain assumptions made by "regular" index scans.

-- 
Peter Geoghegan