Message-ID: <5fc8f150-f350-4cb3-b6b7-ffcc21ed7bc2@enterprisedb.com>
Date: Wed, 14 Feb 2024 15:13:12 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: index prefetching
Content-Language: en-US
To: Robert Haas <robertmhaas@gmail.com>,
 Melanie Plageman <melanieplageman@gmail.com>
Cc: Andres Freund <andres@anarazel.de>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
 Georgios <gkokolatos@protonmail.com>, Thomas Munro <thomas.munro@gmail.com>,
 Konstantin Knizhnik <knizhnik@garret.ru>, Dilip Kumar <dilipbalaut@gmail.com>
References: <8ec36f51-b863-60e3-20e2-b9c981c5ce5e@enterprisedb.com>
 <CA+Tgmob5Nh7sQO8GENzEDSjYJQuKCgfhWtwDLjMtdueFMCh05A@mail.gmail.com>
 <98ba4b25-fae8-c1f4-1597-8093375a1986@enterprisedb.com>
 <20231221134314.wf2rs62d37u62j7t@alap3.anarazel.de>
 <afd17f3c-d496-5583-e93a-5a162d37235f@enterprisedb.com>
 <20231221154352.ijtg6wloa3nowivh@alap3.anarazel.de>
 <e00dac57-0181-4d9c-9eae-71346383e69b@enterprisedb.com>
 <CA+TgmoacmxNQBZsgMPSn9b7oE6QQLOqr_EP=YZTzdfHrqa5dqw@mail.gmail.com>
 <482ec3ff-52ad-415d-96fd-f3832a894023@enterprisedb.com>
 <CAAKRu_ZPDhNwwFxQwS8NdeTFkycM1c=tNLKdU0J-M6KxCjdEmQ@mail.gmail.com>
 <56176b8d-956c-487e-ab09-310db4581c07@enterprisedb.com>
 <CAAKRu_ad8cywU4_X+5e4A9Wy_PZmrCx2aoLpdHPBRvb9inGDgQ@mail.gmail.com>
 <4867452a-b853-4813-a6da-9bb06a336f8b@enterprisedb.com>
 <CAAKRu_Y=go4u99udRaj3k0vuF6EAfWqM86BONhxB4MV9X4FRpQ@mail.gmail.com>
 <CAAKRu_ZPuaO5XwXfM7wowf4sSmPSJ2LT9+zfmD5=LQ=WhV_j=Q@mail.gmail.com>
 <CA+TgmoZemqR60MoiPN+R0qMe2XDYtOe=Tr1+3rX7S1Uua_C6wA@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
In-Reply-To: <CA+TgmoZemqR60MoiPN+R0qMe2XDYtOe=Tr1+3rX7S1Uua_C6wA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Archived-At: <https://www.postgresql.org/message-id/5fc8f150-f350-4cb3-b6b7-ffcc21ed7bc2%40enterprisedb.com>
Precedence: bulk


On 2/14/24 08:10, Robert Haas wrote:
> On Thu, Feb 8, 2024 at 3:18 AM Melanie Plageman
> <melanieplageman@gmail.com> wrote:
>> - kill prior tuple
>>
>> This optimization doesn't work with index prefetching with the current
>> design. Kill prior tuple relies on alternating between fetching a
>> single index tuple and visiting the heap. After visiting the heap we
>> can potentially kill the immediately preceding index tuple. Once we
>> fetch multiple index tuples, enqueue their TIDs, and later visit the
>> heap, the next index page we visit may not contain all of the index
>> tuples deemed killable by our visit to the heap.
> 
> Is this maybe just a bookkeeping problem? A Boolean that says "you can
> kill the prior tuple" is well-suited if and only if the prior tuple is
> well-defined. But perhaps it could be replaced with something more
> sophisticated that tells you which tuples are eligible to be killed.
> 

I don't think it's just a bookkeeping problem. In a way, nbtree already
does keep an array of tuples to kill (see btgettuple), but it's always
for the current index page. So it's not that we immediately go and kill
the prior tuple - nbtree already stashes it in an array, and kills all
those tuples when moving to the next index page.

The way I understand the problem is that with prefetching we're bound to
determine the kill_prior_tuple flag with a delay, in which case we might
have already moved to the next index page ...


So to make this work, we'd need to:

1) keep index pages pinned for all "in flight" TIDs (read from the
index, not yet consumed by the index scan)

2) keep a separate array of "to be killed" index tuples for each page

3) have a more sophisticated way to decide when to kill tuples and unpin
the index page (instead of just doing it when moving to the next index page)

Maybe that's what you meant by "more sophisticated bookkeeping", ofc.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company