Horton

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

Chao Li <li.evan.chao@gmail.com>

View thread
From: Chao Li <li.evan.chao@gmail.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Andy Fan <zhihuifan1213@163.com>, Mircea Cadariu <cadariu.mircea@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2025-12-04T03:24:16Z
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. Clarify why _bt_killitems sorts its items array.

  2. Return TIDs in desc order during backwards scans.

  3. Optimize nbtree backwards scans.

  4. Optimize nbtree backward scan boundary cases.


> On Dec 4, 2025, at 01:31, Peter Geoghegan <pg@bowt.ie> wrote:
> 
> 
> Note also that we'll use much less memory for killedItems by
> representing it as a Bitmapset. We'll use at most one bit per
> so->currPos.items[] item, whereas before we used 4 bytes per item.
> 

That’s true, BitmapSet saves 7/8 of memory usage for killedItems. However, it also brings a little performance burden, because bms_next_member() does O(N) iteration. Say so->curPos.items[] = {0, 1000}, the old code directly gives 0 and 1000 to the “for” loop, but the new code needs to iterate over 999 bits to get next member 1000. Maybe that’s affordable.

Actually MaxTIDsPerBTreePage (max length of so->curPos.items[]) is a value around 1000, in the old code, killedItems could be “short *” instead of “int *”, which may also save a half of memory usage.

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