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

On Mon, Jun 16, 2025 at 12:46 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Making this change in _bt_readpage creates a problem in _bt_killitems:
> it currently expects posting list TIDs in ascending order (the loop
> invariant relies on that), which is why the deduplication patch didn't
> just do things like this in _bt_readpage to begin with. The patch
> deals with that new problem by qsort'ing the so->killedItems[] array
> (at the top of _bt_killitems) such that the items always appear
> exactly once, in the expected ASC order.

Actually, we can just completely get rid of so->killedItems[]. We can
replace it with a new 1 bit itemDead field in the BTScanPosItem struct
(the struct used for so->currPos.items[] entries). That way, the patch
avoids a qsort. The patch doesn't need to change the order of anything
(except of course for the order that _bt_readpage initially saves
posting list tuple TIDs in, when scanning backwards).

The problem with so->killedItems[] is that it stores things in
whatever order successive btgettuple calls find most convenient in the
kill_prior_tuple path. It turns out that it's even more convenient for
btgettuple if its this kill_prior_tuple path simply sets the relevant
(prior/just-returned) item's so->currPos.items[].itemDead field. There
is no need to allocate memory for so->killedItems[], and no need to
worry about running out of space in so->killedItems[] in cases
involving scrollable cursors that happen to scroll back and forth,
triggering kill_prior_tuple for the same TID. We'll simply set the
TID/item's so->currPos.items[].itemDead field a second or a third
time, which can't complicate things, since my new approach makes that
idempotent.

Attached is v2 of the patch, which works that way. This seems like a
better direction to take things in within _bt_killitems.

In general we're quite sensitive to the size of the BTScanPosItem
struct, since (at least for now) we routinely allocate
MaxTIDsPerBTreePage-many of them (i.e. 1,358 of them). 1,358 * 10
bytes is already too much. But there's no need to make the relevant
allocation even larger. I can steal a bit from
BTScanPosItem.tupleOffset for these new
so->currPos.items[].itemDead/BTScanPosItem.itemDead fields. That's
safe, since we only really need 15 bits for each
BTScanPosItem.tupleOffset offset.

--
Peter Geoghegan