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
andreworking 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.
Butunfortunately, there is no such a bms_clear() now. What do you think to add bms_clear() and use it here? I don’t
wantto 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
fromnitems-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/