Subject: Re: Avoiding superfluous buffer locking during nbtree backwards scans

From: Peter Geoghegan <[email-masked]>
Date: Fri, 11 Oct 2024 19:29:12 -0400

On Thu, Oct 10, 2024 at 1:41 PM Peter Geoghegan <[email-masked]> wrote:
> The main simplification new to v4 is that v4 isolates the need to call
> _bt_drop_lock_and_maybe_pin to only 2 functions: _bt_readnextpage, and
> its new _bt_readfirstpage "sibling" function. The functions have
> similar preconditions, and identical postconditions -- all of which
> are now clearly documented.

Worked on this a little more today. Attached is v5, which goes even
further than v4 did. Highlights:

* Completely gets rid of _bt_initialize_more_data by moving its code
into the new _bt_readfirstpage function.

* Adds similar "initialize moreLeft/moreRight" code to the
corresponding point within _bt_readnextpage (that is, at the start of
_bt_readnextpage) -- meaning I moved a bit more code from _bt_steppage
into _bt_readnextpage.

Again, _bt_readnextpage and the new _bt_readfirstpage function are
intended to be "sibling" functions (while _bt_steppage is demoted to a
helper that sets up a call to _bt_readfirstpage). The matching
handling of currPos initialization within _bt_readnextpage and the
_bt_readfirstpage pushes this further than in v4.

* We now reset currPos state (including even its moreLeft/moreRight
fields) within _bt_parallel_seize, automatically and regardless of any
other details.

It doesn't really make sense that (up until now) we've trusted the
shared state that we seized from the parallel scan to kinda be in sync
with the local currPos state (at least its moreLeft/moreRight need to
be in sync, to avoid confusion within _bt_readnextpage). This allowed
me to remove several parallel-only BTScanPosInvalidate calls from
_bt_readnextpage.

This "currPos must be kept in sync with parallel scan state" confusion
is exemplified by the following code snippet (which FWIW was already
removed by earlier revisions of the patch), that appears in the
backwards scan block of _bt_readnextpage on master:

"""
        /*
         * Should only happen in parallel cases, when some other backend
         * advanced the scan.
         */
        if (so->currPos.currPage != blkno)
        {
            BTScanPosUnpinIfPinned(so->currPos);
            so->currPos.currPage = blkno;
        }
"""

Why should the parallel scan have any concern for what currPos is, in general?

* Now nbtree has only one PredicateLockPage call, inside _bt_readpage.
This saves us an extra BufferGetBlockNumber call. (v4 pushed
PredicateLockPage calls down one layer, v5 pushes them down another
layer still.)

* Improved precondition/postcondition comments, and generally cleaner
separation between _bt_steppage and _bt_readnextpage.

--
Peter Geoghegan

---

From: Masahiro Ikeda <[email-masked]>
Date: Thu, 07 Nov 2024 19:44:24 +0900

Hi, thanks for working on these improvements.

I noticed an unexpected behavior where the index scan continues instead 
of
stopping, even when it detects that there are no tuples that match the 
conditions.
(I observed this while reviewing the skip scan patch, though it isn't 
directly
related to this issue.)

> fields) within _bt_parallel_seize, automatically and regardless of any

IIUC, the above change is the root cause. The commit 1bd4bc8 adds a 
reset of
the currPos state in _bt_parallel_seize(). However, this change can 
overwrite
currPos.moreRight which should be preserved before calling 
_bt_readnextpage().

* Test case

-- Prepare
DROP TABLE IF EXISTS test;
CREATE TABLE test (smallint smallint, bool bool);
INSERT INTO test (SELECT -20000+i%40000, random()>0.5 FROM 
generate_series(1, 1_000_000) s(i));
CREATE INDEX test_smallint ON test (smallint);
VACUUM ANALYZE test;

-- Check the number of pages of the index
=# SELECT relpages FROM pg_class WHERE relname = 'test_smallint';
  relpages
----------
       937
(1 row)

-- Test
=# SET max_parallel_workers = 0;
=# EXPLAIN (ANALYZE, BUFFERS, VERBOSE) SELECT COUNT(*) FROM test WHERE 
smallint < -10000;
                                                                          
       QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Finalize Aggregate  (cost=5170.23..5170.24 rows=1 width=8) (actual 
time=71.352..71.402 rows=1 loops=1)
    Output: count(*)
    Buffers: shared hit=934
    ->  Gather  (cost=5170.01..5170.22 rows=2 width=8) (actual 
time=71.344..71.395 rows=1 loops=1)
          Output: (PARTIAL count(*))
          Workers Planned: 2
          Workers Launched: 0
          Buffers: shared hit=934
          ->  Partial Aggregate  (cost=4170.01..4170.02 rows=1 width=8) 
(actual time=71.199..71.199 rows=1 loops=1)
                Output: PARTIAL count(*)
                Buffers: shared hit=934
                ->  Parallel Index Only Scan using test_smallint on 
public.test  (cost=0.42..3906.27 rows=105495 width=0) (actual 
time=0.062..49.137 rows=250000 loops=1)
                      Output: "smallint"
                      Index Cond: (test."smallint" < '-10000'::integer)
                      Heap Fetches: 0
                      Buffers: shared hit=934  -- This is not the result 
I expected. Almost all relpages are being read to retrieve only 25% of 
the tuples.
                                               -- Without commit 1bd4bc8, 
the number was '236' in my environment.
  Planning Time: 0.105 ms
  Execution Time: 71.454 ms
(18 rows)

Regards,
-- 
Masahiro Ikeda
NTT DATA CORPORATION