Date: Wed, 31 Dec 2025 19:21:24 +0900
From: Yugo Nagata <nagata@sraoss.co.jp>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Pgsql Hackers <pgsql-hackers@postgresql.org>
Subject: Re: Add a berief general comment on BTScanInsertData's nextkey and
 backward
Message-Id: <20251231192124.9aeda68f5518d78483bd84e7@sraoss.co.jp>
In-Reply-To: 
 <CAH2-Wzk3VivXOSDz-e9fhATUwzxOpmkHGUN=u9gX-j6b8urfwQ@mail.gmail.com>
References: <20251118162801.27cb13408cb3c9dd3a72cf7d@sraoss.co.jp>
	<CAH2-Wzk3VivXOSDz-e9fhATUwzxOpmkHGUN=u9gX-j6b8urfwQ@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?utf-8?B?bkQ1OVJ0UTBKdThRTjdMamFlR2MvVk5kUXdXVE9pYlUvRDN4YzIzYXJYMUJ4?=
 =?utf-8?B?QjFQNUhUTGZoQS9jWnR3dVZIakhOMXR1Q0VMaEcvd3ZvNGswNjdyVDRBeTR2?=
 =?utf-8?B?WmFEek42YmppZU9mSENSVWl1YXEzS1pkNWprSFlVUGhOL29kZHYwNUpNUU1z?=
 =?utf-8?B?QXpaN2tPdzVyQ1Z6VmVIMjFhOE10ajFPaDlpTHVCSlBCVUJFalEyVWVYVExQ?=
 =?utf-8?B?TkE4WHVFSGczOHlCcjdFam45K1RxaDFYQ3ZzMkhCM0tDR25tUHJrTUVVZkpS?=
 =?utf-8?B?V3RVRUZOWUdJWS9JY3FRNElTV25tT09uOVRPZ05MRkZqMjF5TUlXdzRVbTFY?=
 =?utf-8?B?NnBVeW5DaXo3TXd5ZXpMeFV4VEw4K1ZBS1N1TUNkR1FGT2xQTmZiZndlNjUz?=
 =?utf-8?B?UzZpU3pWMkRIVnZONmdYR05WcUMyUlB2SDltRFYzeHFsY1hHNjEySU12Zmx3?=
 =?utf-8?B?Q242K3U2bitsZlRPL1ZZcFpRT240Z1RLTldJYnFTc200b20wQ0dmQTNIaHlz?=
 =?utf-8?B?L2ZXUFI3eVVBNHV2UEN2VDlzazFyRmtIR1VSTWhKNXlxcVozVjdmaUwvMVY3?=
 =?utf-8?B?bnBPZ3F6bGZ6dm5MaGFVQXQvQlRZQzZZeXk2VUtTdVh6UGRvVjJmVERrRDg0?=
 =?utf-8?B?WEI5bEZaY1FPMWVmQ2Vka25Fb2F1WndqdHhOUk1rQ0dyTlB2bHA3aGtwbWRJ?=
 =?utf-8?B?TEo4MVdRMmExL2pWb3k4MDZlZHphc3c1Qk9TOEJpQVc3bzE3bWNSeXpoeHdR?=
 =?utf-8?B?cDM0R0QrSElMZllEWDlNMjE3WkF5RktDclVRVzA3bktKc2NCVUx0UzJFTC8x?=
 =?utf-8?B?TFVTS1ZkVjh3NW82VEtsbDVzbi91RjVYbmMzSXZwVnFndUYvUkxUVmRWVkY5?=
 =?utf-8?B?SXFuQk9wV3NQRTBHb1FEM3ZvVi9hK3pUUzFUOVJhZkl5eE5IUnd4MGJ6MlBV?=
 =?utf-8?B?RW9JTnNiNW83ckNTSyt4RkFHaXoxRHBWVkNMTFRCSFozei9MazM2QUE1WERJ?=
 =?utf-8?B?MEs0ejk0ZHhwL2JFdENaL29uVm5wTXh5OHU2Z1VIbS9FZUN0VUg1Szg1WklG?=
 =?utf-8?B?YjB3VkhGLzUwZy9CUDlZUHMvS2p5bWtEaGtWWmE1WXZmdm1HRThPbENwaWQ1?=
 =?utf-8?B?QlRCS1FqMmw1SmhDdDZHTE1ib1U2MVBTY24vSjlFZTZqdTYxbE1wWGI5NFpS?=
 =?utf-8?B?MlZ4M1h2d0RWZUFCZ3F4L3NpVG1qei9Jc3pPVElJT0xHc0lGMHRiaGJmdEUr?=
 =?utf-8?B?cWNHckZmelkweXFPSEhRUVBoUnRQNWFWcmJkWjMydnVCeWpseTRBUllib1Z6?=
 =?utf-8?B?ellVQTVPVVZEaDFwL0NiakRCWHRBMVdkVFVRY1JSbFFqdE91OGpocVpUMWtT?=
 =?utf-8?B?MS9KS3dsejFuWFVTdFpiY0hIQTYrVzN2SXV1SzFaaDVxR3o2VzV2QURtWnpO?=
 =?utf-8?B?MlZKakgxbG4rbEhETVA2UjVDSVY4aVZpblVtT3YzenpwUjVzTnN3WERHYkc4?=
 =?utf-8?B?azNMQm1vL0V2NnZqZkRwamRKaGFnOEk5aUh5YUxKK2c2YVBUOUZQL1N5anBw?=
 =?utf-8?B?eHNsYWRvWnluT1ZqcnJMcUExU1lyVmF4TGlkeHRNTW9kbEhQbDY5SVV6bEVG?=
 =?utf-8?B?cUwvQXZFWWxHc1ZQZ1ZESzh1YVBxMFZQV0N4djc1YlkzbXNkVlM2cU05ZndV?=
 =?utf-8?B?eFJmVC82WFNaUFNWblhNdkYvS1oyak95VEZNYmtvRnlkUE94dmtSazFDbXhi?=
 =?utf-8?B?TE9wVEV3VDN1Zmt6UHJOQWp3bDE4dkFIbkdGTXNaay9VVW9OV010ayt5RHlG?=
 =?utf-8?B?MldTRUFEVlA5cC9ydDQ5V1pXNmU0TU1vQ3RyNG9UYjdPY2pzWThQZmFnVEd1?=
 =?utf-8?B?MnNUcXduYTlMREx6MWJzdXNhZFliWmJKQ2hQWEtuZy8xdE1NdVBDNGxmdHJi?=
 =?utf-8?B?RGhBS2I2SDBOSTNUc3FDOFN5VUNlM3dEdyt3QXo4TDVTQkRxZjU2Sjc3SFJo?=
 =?utf-8?B?NEdRM2t5MDdzUmp1NG9wVEwvZTV4RUVUNEZzZzZVYVJqS1V1dlJDcjd0dVNl?=
 =?utf-8?B?STNBVzlnK2dOVDVoK1JVa2RXdDg5VXVjcnBiSm00ZGNXNmY2SjVSdUZKK2s1?=
 =?utf-8?B?ZUFrdUVVT3FCTGpJSmg4OXZxMHV6L1hxZUZaejcxU3Fpdng0TEo5WUd0bFRJ?=
 =?utf-8?B?RWVhbHJRMHFhRzBZODRPL3hCdnpaMERQN0kyeW9EYzJlWTBIaC9iYytCZ1Nw?=
 =?utf-8?B?OWxiNmpnaG1VNUNSOGVQOUJnbEhwd1huUDhORzF2TlhPZHJWME5Tdm9YRVNu?=
 =?utf-8?B?Tk5lSHdONG8yY3MzQ1dTamFPS2dnV1pra2NPVTlyM2hPME5nMVo0dz09?=
X-OriginatorOrg: sraoss.co.jp
X-MS-Exchange-CrossTenant-Network-Message-Id: 
 188641b8-2ef2-4d1d-a1a6-08de48565a17
X-MS-Exchange-CrossTenant-AuthSource: OSZP286MB2160.JPNP286.PROD.OUTLOOK.COM
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Dec 2025 10:21:25.0552
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 75db6c32-352e-4063-ae79-cafb8623f6db
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 
 WBTMyH9P0rExh0xWfuz315riMQpdCn8E5WGxEIqCdH16grzrppx9SEiDLYeT4jHvJgGSnO+JT+6k2CJ+OMgw3Q==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: OS7P286MB7773
List-Id: <pgsql-hackers.lists.postgresql.org>
List-Help: <https://lists.postgresql.org/manage/>
List-Subscribe: <https://lists.postgresql.org/manage/>
List-Post: <mailto:pgsql-hackers@lists.postgresql.org>
List-Owner: <mailto:pgsql-hackers-owner@lists.postgresql.org>
List-Archive: <https://www.postgresql.org/list/pgsql-hackers>
Archived-At: 
 <https://www.postgresql.org/message-id/20251231192124.9aeda68f5518d78483bd84e7%40sraoss.co.jp>
Precedence: bulk

On Tue, 18 Nov 2025 20:15:40 -0500
Peter Geoghegan <pg@bowt.ie> wrote:

> On Tue, Nov 18, 2025 at 2:28 AM Yugo Nagata <nagata@sraoss.co.jp> wrote:
> > I've attached a patch that adds the following comment:
> >
> > + * nextkey determines how the scankey's boundary is interpreted, and backward
> > + * indicates a backward scan.  See comments in _bt_first for a more detailed
> > + * explanation of these fields.
> >
> > What do think?
> 
> Seems reasonable to me.

Thank you for your review.

> 
> I wonder if we also do something about these existing _bt_binsrch comments:
> 
>  * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
>  * of the last key < given scankey, or last key <= given scankey if nextkey
>  * is true.  (Since _bt_compare treats the first data key of such a page as
>  * minus infinity, there will be at least one key < scankey, so the result
>  * always points at one of the keys on the page.)
> 
> Here we describe what happens on an internal page. This is correct,
> but *seems* to contradict the higher level comments at the end of
> _bt_first. There is actually no contradiction between the two -- not
> when you understand that _bt_first describes the whole end-to-end
> process of calling _bt_search and then calling _bt_binsrch on the leaf
> page (not of calling _bt_binsrch once, against an internal page).
> 
> One could think of this _bt_binsrch internal page behavior as
> compensating for the fact that internal pages have pivot tuples that
> consist of a separator key (except for the first key, which is just
> has a -inf key/no key), plus a downlink that points to the *next* page
> after that separator key one level down (except for the internal page
> high key, which has no downlink at all). Might be useful to say
> something like that instead.
> 
> This is hard to explain without an example. Right now, an internal
> page might have pivot tuples that look like this:
> 
> Separator: -inf, Downlink: 1
> Separator: 'a', Downlink: 2
> Separator: 'c', Downlink: 3
> Separator: 'f', Downlink: (none, this is the high key)
> 
> But _bt_binsrch "pretends" that our internal page actually contains:
> 
> Downlink: 1
> Separator: 'a'
> Downlink: 2
> Separator: 'c'
> Downlink: 3
> Separator: 'f'
> 
> So if our = scan key is (say) 'c', we should descend using the
> downlink that points to block 2 (not the one that points to block 3,
> as might be expected from looking at the real physical representation
> consisting of pivot tuples). That is what the scan needs to do to get
> to the page one level down whose high key is also 'c' -- that's where
> the scan needs to look. (If the next level down is the leaf level,
> then the leaf page we descend to might also contain a *non*-pivot
> tuple with the key value 'c', "right before" the high key with 'c',
> which the scan will need to return in _bt_readpage. Lehman & Yao allow
> the key before a leaf page's high key to be equal to the high key, but
> otherwise forbid all duplicate keys.)
> 
> I find it very hard to know what explanation will be the least
> confusing to other people, at least in this area. Since you're
> interested in this area, I thought I'd ask what you think.

I do not see any contradiction between the comment on _bt_binsrch and
the comments at the end of _bt_first. The former explicitly states that
it refers to internal (non-leaf) pages, and I understand the latter to
describe loading data from a leaf page.

That said, we could make this clearer by explicitly mentioning the leaf
page in the first sentence, for example:

      * Now load data from the first leaf page of the scan (usually the
      *page currently in so->currPos.buf).

Regards,
Yugo Nagata

-- 
Yugo Nagata <nagata@sraoss.co.jp>