Received: from malur.postgresql.org ([2a02:16a8:dc51::56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1faKG4-0000UE-Eg for pgsql-hackers@arkaria.postgresql.org; Tue, 03 Jul 2018 12:18:13 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1faKG2-000207-S8 for pgsql-hackers@arkaria.postgresql.org; Tue, 03 Jul 2018 12:18:10 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1faKG2-0001zw-0E for pgsql-hackers@lists.postgresql.org; Tue, 03 Jul 2018 12:18:10 +0000 Received: from mail.postgrespro.ru ([93.174.131.138]) by makus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1faKFt-0007pV-FS for pgsql-hackers@postgresql.org; Tue, 03 Jul 2018 12:18:08 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id CBD8821C4589; Tue, 3 Jul 2018 15:17:58 +0300 (MSK) X-Virus-Scanned: Debian amavisd-new at postgrespro.ru X-Spam-Flag: NO X-Spam-Score: 0 X-Spam-Level: X-Spam-Status: No, score=x tagged_above=-99 required=4 WHITELISTED tests=[] autolearn=unavailable Received: from [192.168.0.106] (unknown [5.79.141.77]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mail.postgrespro.ru (Postfix) with ESMTPSA id 7595E21C35BB; Tue, 3 Jul 2018 15:17:58 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1530620278; bh=saFKdHrGF2BZlUC5puehOpbZksQQN5FlXdTHNxSHoLI=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=Loklp7R0pvLkCANcqsp8O9pU9lMXXf5yz4HTToFmf4RIeKU306t4tQoFnZLmUj2Ep s+RevwhfbLgnjqNVhKDnTY7Mb29JBXBI6Mqtrx63wUtiDhN0lP/lglxiBZwSf9G68/ 9SeLik4Spn4+ycG6p+a713K+QFD1/GbnXRoQiLP8= Subject: Re: [WIP] [B-Tree] Retail IndexTuple deletion To: Peter Geoghegan Cc: =?UTF-8?B?0K7RgNC40Lkg0KHQvtC60L7Qu9C+0LI=?= , PostgreSQL-Dev , Masahiko Sawada References: <425db134-8bba-005c-b59d-56e50de3b41e@postgrespro.ru> <5affa50e-72a9-aef5-d71f-f5f551e01aaf@postgrespro.ru> <9a008ab3-f591-e5e9-8e03-c0dd1dc13579@postgrespro.ru> <2ada5790-dffa-a41a-ef84-10f60a525ba6@postgrespro.ru> From: "Andrey V. Lepikhov" Message-ID: <7598602c-f329-a6aa-00e6-e3335ed06048@postgrespro.ru> Date: Tue, 3 Jul 2018 17:17:57 +0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------ECD60EC66B61115720D6C240" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multi-part message in MIME format. --------------ECD60EC66B61115720D6C240 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit On 03.07.2018 00:40, Peter Geoghegan wrote: > On Mon, Jul 2, 2018 at 9:28 AM, Peter Geoghegan 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 --------------ECD60EC66B61115720D6C240 Content-Type: text/x-patch; name="0004-Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0004-Retail-IndexTuple-Deletion-with-TID-sorting-in-leaf.pat"; filename*1="ch" From 1c8569abe9479e547911ec3079633f79056eff96 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" 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.c index 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.c index 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.h index 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 --------------ECD60EC66B61115720D6C240--