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

Hi Peter,

The patch v4 looks carefully written and technically solid, and the core logic (switching killedItems[] to Bitmapset and reworking backwards posting list scans) is coherent.

I just got a few comments/questions:

> On Dec 3, 2025, at 11:08, Peter Geoghegan <pg@bowt.ie> wrote:
> 
> Attached is v4, which does it that way.
> 
> My plan is to commit this improved version in the next couple of days.
> 
> --
> Peter Geoghegan
> <v4-0001-Return-TIDs-in-desc-order-during-backwards-scans.patch>


1
```
-	/* Always invalidate so->killedItems[] before leaving so->currPos */
-	so->numKilled = 0;
```

The old code only sets so->numKilled to 0 and reuse memory of so->killedItems[], now the new code always bms_free(so->killedItems) and re-alloc memory when next time adding a member to bms.

I am think that, if there were bms_clear(), then we could have just cleared the bitmap and reused the memory next time. But unfortunately, there is no such a bms_clear() now. What do you think to add bms_clear() and use it here? I don’t want to do that, I can try that once you push this patch.

2
```
+					/* Set up posting list state (and remember last TID) */
 					itemIndex--;
 					tupleOffset =
 						_bt_setuppostingitems(so, itemIndex, offnum,
-											  BTreeTupleGetPostingN(itup, 0),
+											  BTreeTupleGetPostingN(itup, nitems - 1),
 											  itup);
-					/* Remember additional TIDs */
-					for (int i = 1; i < BTreeTupleGetNPosting(itup); i++)
+
+					/* Remember all prior TIDs (must be at least one) */
+					for (int i = nitems - 2; i >= 0; i--)
 					{
 						itemIndex--;
 						_bt_savepostingitem(so, itemIndex, offnum,
```

I wonder if the comment “must be at lease one” should apply to the assignment of tupleOffset? The “for” loop starts from nitems-2, will it still must be at lease one item?

3
```
 				/*
-				 * Don't bother advancing the outermost loop's int iterator to
-				 * avoid processing killed items that relate to the same
-				 * offnum/posting list tuple.  This micro-optimization hardly
-				 * seems worth it.  (Further iterations of the outermost loop
-				 * will fail to match on this same posting list's first heap
-				 * TID instead, so we'll advance to the next offnum/index
-				 * tuple pretty quickly.)
+				 * Don't advance itemIndex for outermost loop, no matter how
+				 * nextIndex was advanced.  It's possible that items whose
+				 * TIDs weren't matched in posting list can still be killed
+				 * (there might be a later tuple whose TID is a match).
 				 */
 				if (j == nposting)
 					killtuple = true;
```

I really don’t get what "Don't bother advancing the outermost loop's int iterator” means? Here we only set killtuple to true, then if (killtuple && !ItemIdIsDead(iid)), it breaks the inner while loop, in that case, outer while loop "while ((itemIndex = bms_next_member(so->killedItems, itemIndex)) >= 0)” will advance itemIndex.

I know this is a legacy comment, if you can explain a little bit, that will be very appreciated.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/