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

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