From: Andrey V. Lepikhov <a.lepikhov@postgrespro.ru>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Юрий Соколов <funny.falcon@gmail.com>
Cc: PostgreSQL-Dev <pgsql-hackers@postgresql.org>
Cc: Masahiko Sawada <sawada.mshk@gmail.com>
Subject: Re: [WIP] [B-Tree] Retail IndexTuple deletion
Date: Tue, 3 Jul 2018 17:17:57 +0500
Message-ID: <7598602c-f329-a6aa-00e6-e3335ed06048@postgrespro.ru> (raw)
In-Reply-To: <CAH2-WzmPf0pmnS4go9+MmqQMA0MijsZ9XR+zdMy9J2gkEzadxA@mail.gmail.com>
References: <425db134-8bba-005c-b59d-56e50de3b41e@postgrespro.ru>
<CAH2-WzkOmpQ30nRy6=fdQ8Um8MKBRZ9yU6MwEFDQnWcVb3dY8Q@mail.gmail.com>
<CAH2-Wz=bhuwATGhiQVACbEcVrdGJ-TKyTCg7rZtm1ncRzSuGfw@mail.gmail.com>
<CAD21AoC-31Fr2JGmCpQPjJNZb-bvH38gURAC7256aJg3jO2C7w@mail.gmail.com>
<CAH2-Wz=U-m6rDUdj2JcGycX3OT+0588ZCsauCfC7Fdv3_UmKGQ@mail.gmail.com>
<5affa50e-72a9-aef5-d71f-f5f551e01aaf@postgrespro.ru>
<CAH2-WzmpjdeU77aJf1gtte3QhWrnwMffx3pPJQpEDHA1zbx3gw@mail.gmail.com>
<e4cec53a-ab12-4858-d9d8-5fac9948a4c7@postgrespro.ru>
<CAH2-Wz=mkrkQJJxHjDgiTv25yk0yqrx0EOn5exAHvPyQRR6iNQ@mail.gmail.com>
<9a008ab3-f591-e5e9-8e03-c0dd1dc13579@postgrespro.ru>
<CAL-rCA0BkRJgEfkQdDkii6kt0L-_8xcYqraaSmrrn_jzTFx-Pg@mail.gmail.com>
<2ada5790-dffa-a41a-ef84-10f60a525ba6@postgrespro.ru>
<CAH2-Wz=mnW+8+oZ9vh45+WEzt4dinYrz5f5acqn8mRjVY=YXqg@mail.gmail.com>
<CAH2-WzmPf0pmnS4go9+MmqQMA0MijsZ9XR+zdMy9J2gkEzadxA@mail.gmail.com>
On 03.07.2018 00:40, Peter Geoghegan wrote:
> On Mon, Jul 2, 2018 at 9:28 AM, Peter Geoghegan <pg@bowt.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%40ma...
--
Andrey Lepikhov
Postgres Professional:
https://postgrespro.com
The Russian Postgres Company
Attachments:0004-Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf.patch (text/x-patch, 6.7K) download
From 1c8569abe9479e547911ec3079633f79056eff96 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
Date: Tue, 3 Jul 2018 16:54:46 +0500
Subject: [PATCH 4/4] Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf
---
src/backend/access/nbtree/nbtree.c | 75 +++++++++++++++++++++++++-------------
src/backend/commands/vacuumlazy.c | 8 ++--
src/include/access/genam.h | 2 +-
3 files changed, 55 insertions(+), 30 deletions(-)
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.cindex c54aeac..7c617e9 100644--- a/src/backend/access/nbtree/nbtree.c+++ b/src/backend/access/nbtree/nbtree.c@@ -887,15 +887,19 @@ btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
return stats;
}
-static int-tid_list_search(ItemPointer tid, ItemPointer tid_list, int ntid)-{- for (int i = 0; i < ntid; i++)- if (ItemPointerEquals(tid, &(tid_list[i])))- return i;- return -1;-}-+/*+ * Deletion of index entries pointing to heap tuples.+ *+ * Constraints:+ * 1. TID list info->dead_tuples arranged in ASC order.+ * 2. Logical duplicates of index tuples stored in DESC order.+ *+ * The function generates an insertion scan key and descent by btree for first+ * index tuple what satisfies scan key and last TID in info->dead_tuples list.+ * For the scan results it deletes all index entries, matched to the TID list.+ *+ * Result: a palloc'd struct containing statistical info.+ */
IndexTargetDeleteResult*
bttargetdelete(IndexTargetDeleteInfo *info,
IndexTargetDeleteResult *stats,
@@ -914,20 +918,21 @@ bttargetdelete(IndexTargetDeleteInfo *info,
int ndeletable = 0;
OffsetNumber deletable[MaxOffsetNumber];
IndexTuple itup;
+ int pos = info->last_dead_tuple;
if (stats == NULL)
stats = (IndexTargetDeleteResult *) palloc0(sizeof(IndexTargetDeleteResult));
+ /* Assemble scankey */
itup = index_form_tuple(RelationGetDescr(irel), values, isnull);
skey = _bt_mkscankey(irel, itup);
/* Descend the tree and position ourselves on the target leaf page. */
- stack = _bt_search(irel, keysCount, skey, false, &buf, BT_READ, NULL);- _bt_freestack(stack);+ stack = _bt_search(irel, keysCount, skey, &info->dead_tuples[pos], false, &buf, BT_READ, NULL);
/* To prepare tuple entries search across index pages */
Assert(BufferIsValid(buf));
- offnum = _bt_binsrch(irel, buf, keysCount, skey, false);+ offnum = _bt_binsrch(irel, buf, keysCount, skey, &info->dead_tuples[pos], false);
page = BufferGetPage(buf);
_bt_checkpage(irel, buf);
opaque = (BTPageOpaque) PageGetSpecialPointer(page);
@@ -937,10 +942,9 @@ bttargetdelete(IndexTargetDeleteInfo *info,
int32 cmpval;
ItemId itemid;
IndexTuple itup;
- int pos;
/* Switch to the next page */
- if (P_IGNORE(opaque) || (offnum > PageGetMaxOffsetNumber(page)))+ if (offnum > PageGetMaxOffsetNumber(page))
{
/*
* Before unlocking index page we need to delete
@@ -965,20 +969,27 @@ bttargetdelete(IndexTargetDeleteInfo *info,
break;
/*
- * Switch to the next index page+ * Traverse to a next reliable index page
*/
- buf = _bt_relandgetbuf(irel, buf, opaque->btpo_next, BT_READ);+ buf = _bt_moveright(irel, buf, keysCount, skey, &info->dead_tuples[pos],+ false, true, stack, BT_READ, NULL);
page = BufferGetPage(buf);
_bt_checkpage(irel, buf);
opaque = (BTPageOpaque) PageGetSpecialPointer(page);
- offnum = P_FIRSTDATAKEY(opaque);- continue;+ Assert(!P_IGNORE(opaque));+ /* Set offnum to first potentially interesting item */+ offnum = _bt_binsrch(irel, buf, keysCount, skey, &info->dead_tuples[pos], false);++ if (offnum > PageGetMaxOffsetNumber(page))+ break;+ else+ continue;
}
/*
* This index entry satisfied to the scan key?
*/
- cmpval = _bt_compare(irel, keysCount, skey, page, offnum);+ cmpval = _bt_compare(irel, keysCount, skey, NULL, page, offnum);
if (cmpval != 0)
/* End of index entries, satisfied to the scan key */
@@ -990,15 +1001,28 @@ bttargetdelete(IndexTargetDeleteInfo *info,
*/
itemid = PageGetItemId(page, offnum);
itup = (IndexTuple) PageGetItem(page, itemid);
- pos = tid_list_search(&(itup->t_tid), info->dead_tuples, info->num_dead_tuples);- if ((pos >= 0) && (!info->found_dead_tuples[pos]))+ /*+ * Search for next TID from presorted btree result comparable+ * to TID from presorted dead_tuples tid list+ */+ while (pos >= 0)
{
- /* index entry for TID of dead tuple is found */- deletable[ndeletable++] = offnum;- info->found_dead_tuples[pos] = true;+ int res = ItemPointerCompare(&(itup->t_tid), &info->dead_tuples[pos]);+ if ((res == 0) && (!info->found_dead_tuples[pos]))+ {+ /* index entry for TID of dead tuple is found */+ deletable[ndeletable++] = offnum;+ info->found_dead_tuples[pos] = true;+ }+ else if (res > 0)+ break;+ pos--;
}
+ if (pos < 0)+ break;+
offnum = OffsetNumberNext(offnum);
}
@@ -1015,7 +1039,8 @@ bttargetdelete(IndexTargetDeleteInfo *info,
stats->tuples_removed += ndeletable;
}
- /* Release scan key, unpin and unlock buffer */+ /* Release stack, scan key, unpin and unlock buffer */+ _bt_freestack(stack);
_bt_freeskey(skey);
_bt_relbuf(irel, buf);
diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.cindex 0bb8abb..2fca7be 100644--- a/src/backend/commands/vacuumlazy.c+++ b/src/backend/commands/vacuumlazy.c@@ -1770,7 +1770,7 @@ quick_vacuum_index(Relation irel, Relation hrel,
econtext->ecxt_scantuple = slot;
/* Get tuple from heap */
- for (tnum = 0; tnum < vacrelstats->num_dead_tuples; tnum++)+ for (tnum = vacrelstats->num_dead_tuples-1; tnum >= 0; tnum--)
{
HeapTuple tuple;
Datum values[INDEX_MAX_KEYS];
@@ -1814,9 +1814,9 @@ quick_vacuum_index(Relation irel, Relation hrel,
* Make attempt to delete some index entries by one tree descent.
* We use only a part of TID list, which contains not found TID's.
*/
- ivinfo.dead_tuples = &(vacrelstats->dead_tuples[tnum]);- ivinfo.num_dead_tuples = vacrelstats->num_dead_tuples - tnum;- ivinfo.found_dead_tuples = found + tnum;+ ivinfo.dead_tuples = vacrelstats->dead_tuples;+ ivinfo.last_dead_tuple = tnum;+ ivinfo.found_dead_tuples = found;
index_target_delete(&ivinfo, &stats, values, isnull);
}
diff --git a/src/include/access/genam.h b/src/include/access/genam.hindex 79b386e..297d357 100644--- a/src/include/access/genam.h+++ b/src/include/access/genam.h@@ -55,7 +55,7 @@ typedef struct IndexTargetDeleteInfo
{
Relation heapRelation;
Relation indexRelation; /* the index being vacuumed */
- int num_dead_tuples;+ int last_dead_tuple;
ItemPointer dead_tuples;
bool* found_dead_tuples;
} IndexTargetDeleteInfo;
--
2.7.4
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: a.lepikhov@postgrespro.ru, pg@bowt.ie, funny.falcon@gmail.com, sawada.mshk@gmail.com
Subject: Re: [WIP] [B-Tree] Retail IndexTuple deletion
In-Reply-To: <7598602c-f329-a6aa-00e6-e3335ed06048@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox