Re: Saving stack space in nbtree's _bt_first function

On Tue, Jul 15, 2025 at 4:50 PM Mircea Cadariu <cadariu.mircea@gmail.com> wrote:
> As an experiment, I added an elog(WARNING,...) just above the main changed line in the patch, and then ran the tests
(makeinstallcheck). This resulted in lines logged next to some of the SELECT statements in the following files in
src/test/regress/sql:
>
> create_index.sql
> inherit.sql
>
> I saw the log line only once per query, showing that at least for the scenarios in the tests, the claim checks out.

I'm relying on the fact that we'll inevitably break out of the
relevant _bt_first loop over so->keyData[] (the loop that finds our
initial position keys/builds our insertion scan key by storing ScanKey pointers
in startKeys[]) immediately after we generate an IS NOT NULL boundary
key in this way. Such a generated IS NOT NULL key must use the
BTGreaterStrategyNumber strategy (or the BTLessStrategyNumber strategy
when scanning backwards/when the index is NULLS LAST). That's why it's
inherently impossible to need more than a single notnullkey.

It's a little hard to see why this is from the loop itself, since
there is no "break" in the relevant code block (the block that
actually uses notnullkey). Rather, we rely on the generic logic that
builds our startKeys[] entries. It will inevitably "break" before ever
moving on to the next index attribute/next so->keyData[] key because
strat_total will inevitably become
BTGreaterStrategyNumber/BTLessStrategyNumber. In other words, the
generic BTGreaterStrategyNumber/BTLessStrategyNumber test will
inevitably cause the loop to "break" right after our first (and only)
use of notnullkey.

I've tried to make that clearer in the attached v2 revision's commit
message. v2 also slightly simplifies the logic that the notnullkey
code block uses to select the key's strategy (which is also the
strategy that'll be used as _bt_first's strat_total later on), since
that seems like it'll make my explanation slightly clearer to anybody
that reads the code.

Thanks
--
Peter Geoghegan