Re: [WIP] [B-Tree] Retail IndexTuple deletion

From: "Andrey V(dot) Lepikhov" <a(dot)lepikhov(at)postgrespro(dot)ru>
To: Peter Geoghegan <pg(at)bowt(dot)ie>
Cc: Юрий Соколов <funny(dot)falcon(at)gmail(dot)com>, PostgreSQL-Dev <pgsql-hackers(at)postgresql(dot)org>, Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com>
Subject: Re: [WIP] [B-Tree] Retail IndexTuple deletion
Date: 2018-07-03 12:17:57
Message-ID: 7598602c-f329-a6aa-00e6-e3335ed06048@postgrespro.ru
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On 03.07.2018 00:40, Peter Geoghegan wrote:
> On Mon, Jul 2, 2018 at 9:28 AM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>>> Execution time of last "VACUUM test;" command on my notebook was:
>>>
>>> with bulk deletion: 1.6 s;
>>> with Quick Vacuum Strategy: 5.2 s;
>>> with Quick Vacuum Strategy & TID sorting: 0.6 s.
>>
>> I'm glad that you looked into this. You could make this faster still,
>> by actually passing the lowest heap TID in the list of TIDs to kill to
>> _bt_search() and _bt_binsrch(). You might have to work through several
>> extra B-Tree leaf pages per bttargetdelete() call without this (you'll
>> move right multiple times within bttargetdelete()).
>
> I should add: I think that this doesn't matter so much in your
> original test case with v1 of my patch, because you're naturally
> accessing the index tuples in almost the most efficient way already,
> since you VACUUM works its way from the start of the table until the
> end of the table. You'll definitely need to pass a heap TID to
> routines like _bt_search() once you start using my v2, though, since
> that puts the heap TIDs in DESC sort order. Otherwise, it'll be almost
> as slow as the plain "Quick Vacuum Strategy" case was.
>
> In general, the big idea with my patch is that heap TID is just
> another attribute. I am not "cheating" in any way; if it's not
> possible to descend the tree and arrive at the right leaf page without
> looking through several leaf pages, then my patch is broken.
>
> You might also use _bt_moveright() with my patch. That way, you can
> quickly detect that you need to move right immediately, without going
> through all the items on the page. This should only be an issue in the
> event of a concurrent page split, though. In my patch, I use
> _bt_moveright() in a special way for unique indexes: I need to start
> at the first leaf page a duplicate could be on for duplicate checking,
> but once that's over I want to "jump immediately" to the leaf page the
> index tuple actually needs to be inserted on. That's when
> _bt_moveright() is called. (Actually, that looks like it breaks unique
> index enforcement in the case of my patch, which I need to fix, but
> you might still do this.)
>

Done.
Attachment contains an update for use v.2 of the 'Ensure nbtree leaf
tuple keys are always unique' patch.

Apply order:
1. 0001-Retail-IndexTuple-Deletion-Access-Method.patch - from previous email
2. 0002-Quick-vacuum-strategy.patch - from previous email
3. v2-0001-Ensure-nbtree-leaf-tuple-keys-are-always-unique.patch - from [1]
4. 0004-Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf.patch

[1]
https://www.postgresql.org/message-id/CAH2-Wzm6D%3DKnV%2BP8bZE-ZtP4e%2BW64HtVTdOenqd1d7HjJL3xZQ%40mail.gmail.com

--
Andrey Lepikhov
Postgres Professional:
https://postgrespro.com
The Russian Postgres Company

Attachment Content-Type Size
0004-Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf.patch text/x-patch 6.7 KB

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Moon, Insung 2018-07-03 12:20:58 RE: [Proposal] Table-level Transparent Data Encryption (TDE) and Key Management Service (KMS)
Previous Message Ashutosh Bapat 2018-07-03 12:15:46 Re: pgsql: Clarify use of temporary tables within partition trees