Re: Returning nbtree posting list TIDs in DESC order during backwards scans

Hi,

On 18/07/2025 05:37, Peter Geoghegan wrote:

> I think that this patch isn't too far off being committable.

Agreed. I just tried v3, and got 23 buffer hits, same as in the original 
demonstrative example.


> +                    /* Remember all prior TIDs (must be at least one) */
> +                    for (int i = nitems - 2; i >= 0; i--)

This loop has to start from the end, in order to return TIDs in DESC order?


> I'm not really worried about _bt_killitems; more so about the routines
> called by _bt_readpage, which must make sure that the bit is unset
> every time a TID is saved in so->currPos.items[].

I did a search through the code for "so->" and had a look at the results 
for functions I'd expect to see changes in, at the minimum:

   *  btbeginscan
  * btrescan
  * btendscan
  * btrestrpos
  * _bt_steppage
  * _bt_readfirstpage

I could find all of the above being touched in v3.


> Modern CPUs are likely to skip over
> non-itemDead entries very quickly.

Okay, yeah. A sequential iteration through an array will be fast, and we 
expect the branch predictor to do its job properly with the "if 
(!kitem->itemDead)".


> I'll need
> to think about issues around adding the new kitem->itemDead bitfield.

It's probably not a concern here, but got reminded of this ABI break: 
https://www.postgresql.org/message-id/flat/CABOikdNmVBC1LL6pY26dyxAS2f%2BgLZvTsNt%3D2XbcyG7WxXVBBQ%40mail.gmail.com


Kind regards,

Mircea Cadariu