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 1fhUIB-0007BM-94 for pgsql-hackers@arkaria.postgresql.org; Mon, 23 Jul 2018 06:26:00 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1fhUI9-00054I-SX for pgsql-hackers@arkaria.postgresql.org; Mon, 23 Jul 2018 06:25:57 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1fhUI9-00054B-Gk for pgsql-hackers@lists.postgresql.org; Mon, 23 Jul 2018 06:25:57 +0000 Received: from mail.postgrespro.ru ([93.174.131.138]) by magus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1fhUHy-0008QY-0f for pgsql-hackers@postgresql.org; Mon, 23 Jul 2018 06:25:56 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id CE31721C1CD0; Mon, 23 Jul 2018 09:25:44 +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.103] (unknown [5.79.139.210]) (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 4EB4121C1CCE; Mon, 23 Jul 2018 09:25:44 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1532327144; bh=Ksd59G/Q91VpCPMnAfSLkq1DDSg3/OBs/6DJ2K+UGAo=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=J1e/h0rhzxkI9G9WazTEm5DY4uAEKkA4IhtJihBCKnySJukj95tPNAGiAOGdRwCgV 7LrogqVcjMyN/fIRrV43QvPzip5DdOrGxjOfX0Pv7QuQwfeDjO3tPBH45vxolthANA uP2fcgLJUpXHUkFEBojW4vTQHpmv1i7+U50JGHXc= 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> <7598602c-f329-a6aa-00e6-e3335ed06048@postgrespro.ru> From: Andrey Lepikhov Message-ID: <9f73727c-da00-c50e-7193-64b199c964d2@postgrespro.ru> Date: Mon, 23 Jul 2018 11:25:42 +0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------75D312DAFAE4FD0A374BCA4F" 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. --------------75D312DAFAE4FD0A374BCA4F Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit This v5 version of the patch is intended to use with v3-0001-Make-all-nbtree-index-tuples-have-unique-keys patch [1]. [1] https://www.postgresql.org/message-id/CAH2-WzkmTRXh%3DzyMAUHyG3%3DO-QQip6CJc2VyNijRO-vzgPxmoQ%40mail.gmail.com 13.07.2018 00:00, Peter Geoghegan пишет: > On Tue, Jul 3, 2018 at 5:17 AM, Andrey V. Lepikhov > wrote: >> Done. >> Attachment contains an update for use v.2 of the 'Ensure nbtree leaf tuple >> keys are always unique' patch. > My v3 is still pending, but is now a lot better than v2. There were > bugs in v2 that were fixed. > > One area that might be worth investigating is retail index tuple > deletion performed within the executor in the event of non-HOT > updates. Maybe LP_REDIRECT could be repurposed to mean "ghost record", > at least in unique index tuples with no NULL values. The idea is that > MVCC index scans can skip over those if they've already found a > visible tuple with the same value. Also, when there was about to be a > page split, they could be treated a little bit like LP_DEAD items. Of > course, the ghost bit would have to be treated as a hint that could be > "wrong" (e.g. because the transaction hasn't committed yet), so you'd > have to go to the heap in the context of a page split, to double > check. Also, you'd need heuristics that let you give up on this > strategy when it didn't help. > > I think that this could work well enough for OLTP workloads, and might > be more future-proof than doing it in VACUUM. Though, of course, it's > still very complicated. > -- --- Andrey Lepikhov Postgres Professional https://postgrespro.com The Russian Postgres Company --------------75D312DAFAE4FD0A374BCA4F Content-Type: text/x-patch; name="0001-v5-Retail-IndexTuple-Deletion-Access-Method.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-v5-Retail-IndexTuple-Deletion-Access-Method.patch" From 022338178180b9968e365ed4157d35be7fb4c664 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" Date: Mon, 23 Jul 2018 09:35:17 +0500 Subject: [PATCH 1/4] v5 Retail IndexTuple Deletion Access Method --- contrib/bloom/blutils.c | 1 + src/backend/access/brin/brin.c | 1 + src/backend/access/gin/ginutil.c | 1 + src/backend/access/gist/gist.c | 1 + src/backend/access/hash/hash.c | 1 + src/backend/access/index/indexam.c | 15 +++ src/backend/access/nbtree/nbtree.c | 138 +++++++++++++++++++++++++++ src/backend/access/spgist/spgutils.c | 1 + src/include/access/amapi.h | 6 ++ src/include/access/genam.h | 18 ++++ src/include/access/nbtree.h | 4 + 11 files changed, 187 insertions(+) diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.c index 6b2b9e3742..96f1d47c70 100644 --- a/contrib/bloom/blutils.c +++ b/contrib/bloom/blutils.c @@ -126,6 +126,7 @@ blhandler(PG_FUNCTION_ARGS) amroutine->ambuild = blbuild; amroutine->ambuildempty = blbuildempty; amroutine->aminsert = blinsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = blbulkdelete; amroutine->amvacuumcleanup = blvacuumcleanup; amroutine->amcanreturn = NULL; diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.c index e95fbbcea7..a0e06bd868 100644 --- a/src/backend/access/brin/brin.c +++ b/src/backend/access/brin/brin.c @@ -103,6 +103,7 @@ brinhandler(PG_FUNCTION_ARGS) amroutine->ambuild = brinbuild; amroutine->ambuildempty = brinbuildempty; amroutine->aminsert = brininsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = brinbulkdelete; amroutine->amvacuumcleanup = brinvacuumcleanup; amroutine->amcanreturn = NULL; diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c index 0a32182dd7..acf14e7bec 100644 --- a/src/backend/access/gin/ginutil.c +++ b/src/backend/access/gin/ginutil.c @@ -58,6 +58,7 @@ ginhandler(PG_FUNCTION_ARGS) amroutine->ambuild = ginbuild; amroutine->ambuildempty = ginbuildempty; amroutine->aminsert = gininsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = ginbulkdelete; amroutine->amvacuumcleanup = ginvacuumcleanup; amroutine->amcanreturn = NULL; diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c index 8a42effdf7..d7a53d2ca9 100644 --- a/src/backend/access/gist/gist.c +++ b/src/backend/access/gist/gist.c @@ -80,6 +80,7 @@ gisthandler(PG_FUNCTION_ARGS) amroutine->ambuild = gistbuild; amroutine->ambuildempty = gistbuildempty; amroutine->aminsert = gistinsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = gistbulkdelete; amroutine->amvacuumcleanup = gistvacuumcleanup; amroutine->amcanreturn = gistcanreturn; diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c index 0002df30c0..5fb32d6eba 100644 --- a/src/backend/access/hash/hash.c +++ b/src/backend/access/hash/hash.c @@ -76,6 +76,7 @@ hashhandler(PG_FUNCTION_ARGS) amroutine->ambuild = hashbuild; amroutine->ambuildempty = hashbuildempty; amroutine->aminsert = hashinsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = hashbulkdelete; amroutine->amvacuumcleanup = hashvacuumcleanup; amroutine->amcanreturn = NULL; diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c index 22b5cc921f..9ebeb789fb 100644 --- a/src/backend/access/index/indexam.c +++ b/src/backend/access/index/indexam.c @@ -730,6 +730,21 @@ index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap) return ntids; } +IndexTargetDeleteResult * +index_target_delete(IndexTargetDeleteInfo *info, + IndexTargetDeleteResult *stats, + Datum *values, + bool *isnull) +{ + Relation indexRelation = info->indexRelation; + + RELATION_CHECKS; + + CHECK_REL_PROCEDURE(amtargetdelete); + + return indexRelation->rd_amroutine->amtargetdelete(info, stats, values, isnull); +} + /* ---------------- * index_bulk_delete - do mass deletion of index entries * diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c index e8725fbbe1..44f4d0dc9f 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -34,7 +34,9 @@ #include "storage/smgr.h" #include "utils/builtins.h" #include "utils/index_selfuncs.h" +#include "utils/lsyscache.h" #include "utils/memutils.h" +#include "utils/syscache.h" /* Working state needed by btvacuumpage */ @@ -127,6 +129,7 @@ bthandler(PG_FUNCTION_ARGS) amroutine->ambuild = btbuild; amroutine->ambuildempty = btbuildempty; amroutine->aminsert = btinsert; + amroutine->amtargetdelete = bttargetdelete; amroutine->ambulkdelete = btbulkdelete; amroutine->amvacuumcleanup = btvacuumcleanup; amroutine->amcanreturn = btcanreturn; @@ -886,6 +889,141 @@ 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; +} + +IndexTargetDeleteResult* +bttargetdelete(IndexTargetDeleteInfo *info, + IndexTargetDeleteResult *stats, + Datum *values, + bool *isnull) +{ + Relation irel = info->indexRelation; + Relation hrel = info->heapRelation; + ScanKey skey; + int keysCount = IndexRelationGetNumberOfKeyAttributes(irel); + BTStack stack; + Buffer buf; + Page page; + BTPageOpaque opaque; + OffsetNumber offnum; + int ndeletable = 0; + OffsetNumber deletable[MaxOffsetNumber]; + IndexTuple itup; + + if (stats == NULL) + stats = (IndexTargetDeleteResult *) palloc0(sizeof(IndexTargetDeleteResult)); + + 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); + + /* To prepare tuple entries search across index pages */ + Assert(BufferIsValid(buf)); + offnum = _bt_binsrch(irel, buf, keysCount, skey, false); + page = BufferGetPage(buf); + _bt_checkpage(irel, buf); + opaque = (BTPageOpaque) PageGetSpecialPointer(page); + + for (;;) + { + int32 cmpval; + ItemId itemid; + IndexTuple itup; + int pos; + + /* Switch to the next page */ + if (P_IGNORE(opaque) || (offnum > PageGetMaxOffsetNumber(page))) + { + /* + * Before unlocking index page we need to delete + * all currently found tuples + */ + if (ndeletable > 0) + { + LockBuffer(buf, BUFFER_LOCK_UNLOCK); + LockBufferForCleanup(buf); + + _bt_delitems_delete(irel, buf, deletable, ndeletable, hrel); + + stats->tuples_removed += ndeletable; + ndeletable = 0; + } + + /* + * Check for end-of-index + */ + if (P_RIGHTMOST(opaque)) + /* it is rightmost leaf */ + break; + + /* + * Switch to the next index page + */ + buf = _bt_relandgetbuf(irel, buf, opaque->btpo_next, BT_READ); + page = BufferGetPage(buf); + _bt_checkpage(irel, buf); + opaque = (BTPageOpaque) PageGetSpecialPointer(page); + offnum = P_FIRSTDATAKEY(opaque); + continue; + } + + /* + * This index entry satisfied to the scan key? + */ + cmpval = _bt_compare(irel, keysCount, skey, page, offnum); + + if (cmpval != 0) + /* End of index entries, satisfied to the scan key */ + break; + + /* + * To load index tuple and look for matches in the TID list of + * dead heap tuples + */ + 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])) + { + /* index entry for TID of dead tuple is found */ + deletable[ndeletable++] = offnum; + info->found_dead_tuples[pos] = true; + } + + offnum = OffsetNumberNext(offnum); + } + + /* + * Delete all found index tuples + */ + if (ndeletable > 0) + { + LockBuffer(buf, BUFFER_LOCK_UNLOCK); + LockBufferForCleanup(buf); + + _bt_delitems_delete(irel, buf, deletable, ndeletable, hrel); + + stats->tuples_removed += ndeletable; + } + + /* Release scan key, unpin and unlock buffer */ + _bt_freeskey(skey); + _bt_relbuf(irel, buf); + + return stats; +} + /* * Post-VACUUM cleanup. * diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c index 4a9b5da268..325728122b 100644 --- a/src/backend/access/spgist/spgutils.c +++ b/src/backend/access/spgist/spgutils.c @@ -56,6 +56,7 @@ spghandler(PG_FUNCTION_ARGS) amroutine->ambuild = spgbuild; amroutine->ambuildempty = spgbuildempty; amroutine->aminsert = spginsert; + amroutine->amtargetdelete = NULL; amroutine->ambulkdelete = spgbulkdelete; amroutine->amvacuumcleanup = spgvacuumcleanup; amroutine->amcanreturn = spgcanreturn; diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h index 14526a6bb2..497b54e8a8 100644 --- a/src/include/access/amapi.h +++ b/src/include/access/amapi.h @@ -76,6 +76,11 @@ typedef bool (*aminsert_function) (Relation indexRelation, IndexUniqueCheck checkUnique, struct IndexInfo *indexInfo); +/* target delete */ +typedef IndexTargetDeleteResult *(*amtargetdelete_function) (IndexTargetDeleteInfo *info, + IndexTargetDeleteResult *stats, + Datum *values, + bool *isnull); /* bulk delete */ typedef IndexBulkDeleteResult *(*ambulkdelete_function) (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, @@ -207,6 +212,7 @@ typedef struct IndexAmRoutine ambuild_function ambuild; ambuildempty_function ambuildempty; aminsert_function aminsert; + amtargetdelete_function amtargetdelete; ambulkdelete_function ambulkdelete; amvacuumcleanup_function amvacuumcleanup; amcanreturn_function amcanreturn; /* can be NULL */ diff --git a/src/include/access/genam.h b/src/include/access/genam.h index 24c720bf42..79b386eebd 100644 --- a/src/include/access/genam.h +++ b/src/include/access/genam.h @@ -51,6 +51,15 @@ typedef struct IndexVacuumInfo BufferAccessStrategy strategy; /* access strategy for reads */ } IndexVacuumInfo; +typedef struct IndexTargetDeleteInfo +{ + Relation heapRelation; + Relation indexRelation; /* the index being vacuumed */ + int num_dead_tuples; + ItemPointer dead_tuples; + bool* found_dead_tuples; +} IndexTargetDeleteInfo; + /* * Struct for statistics returned by ambulkdelete and amvacuumcleanup * @@ -79,6 +88,11 @@ typedef struct IndexBulkDeleteResult BlockNumber pages_free; /* # pages available for reuse */ } IndexBulkDeleteResult; +typedef struct IndexTargetDeleteResult +{ + int tuples_removed; /* # removed during vacuum operation */ +} IndexTargetDeleteResult; + /* Typedef for callback function to determine if a tuple is bulk-deletable */ typedef bool (*IndexBulkDeleteCallback) (ItemPointer itemptr, void *state); @@ -163,6 +177,10 @@ extern HeapTuple index_fetch_heap(IndexScanDesc scan); extern HeapTuple index_getnext(IndexScanDesc scan, ScanDirection direction); extern int64 index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap); +extern IndexTargetDeleteResult *index_target_delete(IndexTargetDeleteInfo *info, + IndexTargetDeleteResult *stats, + Datum *values, + bool *isnull); extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h index 04ecb4cbc0..3b9461c3b4 100644 --- a/src/include/access/nbtree.h +++ b/src/include/access/nbtree.h @@ -508,6 +508,10 @@ extern void btparallelrescan(IndexScanDesc scan); extern void btendscan(IndexScanDesc scan); extern void btmarkpos(IndexScanDesc scan); extern void btrestrpos(IndexScanDesc scan); +extern IndexTargetDeleteResult *bttargetdelete(IndexTargetDeleteInfo *info, + IndexTargetDeleteResult *stats, + Datum *values, + bool *isnull); extern IndexBulkDeleteResult *btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, -- 2.17.1 --------------75D312DAFAE4FD0A374BCA4F Content-Type: text/x-patch; name="0002-v5-Quick-Vacuum-Strategy.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-v5-Quick-Vacuum-Strategy.patch" From 7b56036ea5f6817c1f81e3d53a197c50911ec69a Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" Date: Mon, 23 Jul 2018 09:36:23 +0500 Subject: [PATCH 2/4] v5 Quick Vacuum Strategy --- src/backend/access/heap/heapam.c | 31 ++++++ src/backend/access/heap/pruneheap.c | 40 ++++++- src/backend/commands/vacuumlazy.c | 161 +++++++++++++++++++++++++++- src/backend/utils/misc/guc.c | 10 +- src/include/access/heapam.h | 1 + 5 files changed, 234 insertions(+), 9 deletions(-) diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c index 72395a50b8..dd033668b6 100644 --- a/src/backend/access/heap/heapam.c +++ b/src/backend/access/heap/heapam.c @@ -9392,6 +9392,36 @@ heap_sync(Relation rel) } } +/* + * Mask DEAD tuples at a HEAP page + * + * We introduce this function for wal_consistency_checking satisfaction at + * Hot Standby node. + * + * DEAD tuple on a master node has t_cid and t_infomask, which can not be + * obtained by WAL records applying on a Hot Standby node. + */ +static void +mask_dead_tuples(Page page) +{ + OffsetNumber offnum; + + for (offnum = FirstOffsetNumber; offnum <= PageGetMaxOffsetNumber(page); offnum = OffsetNumberNext(offnum)) + { + ItemId lp = PageGetItemId(page, offnum); + char* htup_begin; + + if (!ItemIdIsDead(lp)) + continue; + + if (!ItemIdHasStorage(lp)) + continue; + + htup_begin = (char *) PageGetItem(page, lp); + memset(htup_begin, MASK_MARKER, ItemIdGetLength(lp)); + } +} + /* * Mask a heap page before performing consistency checks on it. */ @@ -9405,6 +9435,7 @@ heap_mask(char *pagedata, BlockNumber blkno) mask_page_hint_bits(page); mask_unused_space(page); + mask_dead_tuples(page); for (off = 1; off <= PageGetMaxOffsetNumber(page); off++) { diff --git a/src/backend/access/heap/pruneheap.c b/src/backend/access/heap/pruneheap.c index c2f5343dac..ebbafe3275 100644 --- a/src/backend/access/heap/pruneheap.c +++ b/src/backend/access/heap/pruneheap.c @@ -43,6 +43,9 @@ typedef struct bool marked[MaxHeapTuplesPerPage + 1]; } PruneState; +/* Parameter for target deletion strategy in lazy vacuum */ +double target_index_deletion_factor = 0.01; + /* Local functions */ static int heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, @@ -405,7 +408,7 @@ heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, if (HeapTupleSatisfiesVacuum(&tup, OldestXmin, buffer) == HEAPTUPLE_DEAD && !HeapTupleHeaderIsHotUpdated(htup)) { - heap_prune_record_unused(prstate, rootoffnum); + heap_prune_record_dead(prstate, rootoffnum); HeapTupleHeaderAdvanceLatestRemovedXid(htup, &prstate->latestRemovedXid); ndeleted++; @@ -580,8 +583,10 @@ heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, */ for (i = 1; (i < nchain) && (chainitems[i - 1] != latestdead); i++) { - heap_prune_record_unused(prstate, chainitems[i]); ndeleted++; + if (chainitems[i] == latestdead) + continue; + heap_prune_record_unused(prstate, chainitems[i]); } /* @@ -598,9 +603,28 @@ heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, * redirect the root to the correct chain member. */ if (i >= nchain) + { + if (rootoffnum != latestdead) + { + if (ItemIdIsNormal(rootlp)) + heap_prune_record_unused(prstate, latestdead); + else + { + /* + * We allow overlapping of redirected and dead items + */ + heap_prune_record_redirect(prstate, rootoffnum, latestdead); + heap_prune_record_dead(prstate, latestdead); + } + } heap_prune_record_dead(prstate, rootoffnum); + } else + { + if (rootoffnum != latestdead) + heap_prune_record_unused(prstate, latestdead); heap_prune_record_redirect(prstate, rootoffnum, chainitems[i]); + } } else if (nchain < 2 && ItemIdIsRedirected(rootlp)) { @@ -653,7 +677,12 @@ heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum) Assert(prstate->ndead < MaxHeapTuplesPerPage); prstate->nowdead[prstate->ndead] = offnum; prstate->ndead++; - Assert(!prstate->marked[offnum]); + + /* + * We suppress checking prstate->marked[offnum]. It is not the best idea, + * but this is most simplistic way to enable Dead Redirecting by + * overlapping Dead and Redirected states. + */ prstate->marked[offnum] = true; } @@ -706,7 +735,10 @@ heap_page_prune_execute(Buffer buffer, OffsetNumber off = *offnum++; ItemId lp = PageGetItemId(page, off); - ItemIdSetDead(lp); + if (target_index_deletion_factor > 0) + ItemIdMarkDead(lp); + else + ItemIdSetDead(lp); } /* Update all now-unused line pointers */ diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c index 5649a70800..9a625b8dba 100644 --- a/src/backend/commands/vacuumlazy.c +++ b/src/backend/commands/vacuumlazy.c @@ -41,13 +41,16 @@ #include "access/heapam_xlog.h" #include "access/htup_details.h" #include "access/multixact.h" +#include "access/nbtree.h" #include "access/transam.h" #include "access/visibilitymap.h" #include "access/xlog.h" +#include "catalog/index.h" #include "catalog/storage.h" #include "commands/dbcommands.h" #include "commands/progress.h" #include "commands/vacuum.h" +#include "executor/executor.h" #include "miscadmin.h" #include "pgstat.h" #include "portability/instr_time.h" @@ -139,7 +142,6 @@ typedef struct LVRelStats bool lock_waiter_detected; } LVRelStats; - /* A few variables that don't seem worth passing around as parameters */ static int elevel = -1; @@ -156,6 +158,8 @@ static void lazy_scan_heap(Relation onerel, int options, bool aggressive); static void lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats); static bool lazy_check_needs_freeze(Buffer buf, bool *hastup); +static void quick_vacuum_index(Relation irel, Relation hrel, + LVRelStats *vacrelstats); static void lazy_vacuum_index(Relation indrel, IndexBulkDeleteResult **stats, LVRelStats *vacrelstats); @@ -734,10 +738,17 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats, /* Remove index entries */ for (i = 0; i < nindexes; i++) - lazy_vacuum_index(Irel[i], + { + bool use_quick_strategy = (vacrelstats->num_dead_tuples/vacrelstats->old_live_tuples < target_index_deletion_factor); + + if (use_quick_strategy && (Irel[i]->rd_amroutine->amtargetdelete != NULL)) + quick_vacuum_index(Irel[i], onerel, vacrelstats); + else + lazy_vacuum_index(Irel[i], &indstats[i], vacrelstats); + } /* * Report that we are now vacuuming the heap. We also increase * the number of index scans here; note that by using @@ -1379,10 +1390,16 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats, /* Remove index entries */ for (i = 0; i < nindexes; i++) - lazy_vacuum_index(Irel[i], + { + bool use_quick_strategy = (vacrelstats->num_dead_tuples/vacrelstats->old_live_tuples < target_index_deletion_factor); + + if (use_quick_strategy && (Irel[i]->rd_amroutine->amtargetdelete != NULL)) + quick_vacuum_index(Irel[i], onerel, vacrelstats); + else + lazy_vacuum_index(Irel[i], &indstats[i], vacrelstats); - + } /* Report that we are now vacuuming the heap */ hvp_val[0] = PROGRESS_VACUUM_PHASE_VACUUM_HEAP; hvp_val[1] = vacrelstats->num_index_scans + 1; @@ -1671,6 +1688,142 @@ lazy_check_needs_freeze(Buffer buf, bool *hastup) return false; } +/* + * Get tuple from heap for a scan key building. + */ +static HeapTuple +get_tuple_by_tid(Relation rel, ItemPointer tid) +{ + Buffer buffer; + Page page; + OffsetNumber offnum; + ItemId lp; + HeapTuple tuple; + bool needLock = !RELATION_IS_LOCAL(rel); + BlockNumber npages; + + if (needLock) + LockRelationForExtension(rel, ExclusiveLock); + npages = RelationGetNumberOfBlocks(rel); + if (needLock) + UnlockRelationForExtension(rel, ExclusiveLock); + if (ItemPointerGetBlockNumber(tid) > npages) + return NULL; + + buffer = ReadBufferExtended(rel, MAIN_FORKNUM, ItemPointerGetBlockNumber(tid), RBM_NORMAL, NULL); + LockBuffer(buffer, BUFFER_LOCK_SHARE); + + page = (Page) BufferGetPage(buffer); + offnum = ItemPointerGetOffsetNumber(tid); + lp = PageGetItemId(page, offnum); + + /* + * VACUUM Races: someone already remove the tuple from HEAP. Ignore it. + */ + if (!ItemIdIsUsed(lp)) + { + UnlockReleaseBuffer(buffer); + return NULL; + } + /* Walk along the chain */ + while (!ItemIdHasStorage(lp)) + { + offnum = ItemIdGetRedirect(lp); + lp = PageGetItemId(page, offnum); + Assert(ItemIdIsUsed(lp)); + } + + /* Form a tuple */ + tuple = palloc(sizeof(HeapTupleData)); + ItemPointerSet(&(tuple->t_self), BufferGetBlockNumber(buffer), offnum); + tuple->t_tableOid = RelationGetRelid(rel); + tuple->t_data = (HeapTupleHeader) PageGetItem(page, lp); + tuple->t_len = ItemIdGetLength(lp); + UnlockReleaseBuffer(buffer); + return tuple; +} + +/* + * quick_vacuum_index() -- quick vacuum one index relation. + * + * Delete all the index entries pointing to tuples listed in + * vacrelstats->dead_tuples. + */ +static void +quick_vacuum_index(Relation irel, Relation hrel, + LVRelStats *vacrelstats) +{ + int tnum; + bool* found = palloc0(vacrelstats->num_dead_tuples*sizeof(bool)); + IndexInfo* indexInfo = BuildIndexInfo(irel); + EState* estate = CreateExecutorState(); + ExprContext* econtext = GetPerTupleExprContext(estate); + ExprState* predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate); + TupleTableSlot* slot = MakeSingleTupleTableSlot(RelationGetDescr(hrel)); + + IndexTargetDeleteResult stats; + IndexTargetDeleteInfo ivinfo; + + ivinfo.indexRelation = irel; + ivinfo.heapRelation = hrel; + + econtext->ecxt_scantuple = slot; + + /* Get tuple from heap */ + for (tnum = 0; tnum < vacrelstats->num_dead_tuples; tnum++) + { + HeapTuple tuple; + Datum values[INDEX_MAX_KEYS]; + bool isnull[INDEX_MAX_KEYS]; + + /* Index entry for the TID was deleted early */ + if (found[tnum]) + continue; + + /* Get a tuple from heap */ + if ((tuple = get_tuple_by_tid(hrel, &(vacrelstats->dead_tuples[tnum]))) == NULL) + { + /* + * Tuple has 'not used' status. + */ + found[tnum] = true; + continue; + } + + /* + * Form values[] and isnull[] arrays from for index tuple + * by heap tuple + */ + MemoryContextReset(econtext->ecxt_per_tuple_memory); + + ExecStoreTuple(tuple, slot, InvalidBuffer, false); + + /* + * In a partial index, ignore tuples that don't satisfy the + * predicate. + */ + if ((predicate != NULL) && (!ExecQual(predicate, econtext))) + { + found[tnum] = true; + continue; + } + + FormIndexDatum(indexInfo, slot, estate, values, isnull); + + /* + * 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; + index_target_delete(&ivinfo, &stats, values, isnull); + } + + pfree(found); + ExecDropSingleTupleTableSlot(slot); + FreeExecutorState(estate); +} /* * lazy_vacuum_index() -- vacuum one index relation. diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c index a88ea6cfc9..e9e953ece6 100644 --- a/src/backend/utils/misc/guc.c +++ b/src/backend/utils/misc/guc.c @@ -3243,7 +3243,15 @@ static struct config_real ConfigureNamesReal[] = 0.1, 0.0, 100.0, NULL, NULL, NULL }, - + { + {"target_index_deletion_factor", PGC_SIGHUP, AUTOVACUUM, + gettext_noop("Maximum number of vacuumed tuples as a fraction of reltuples where we can use target index vacuum strategy."), + NULL + }, + &target_index_deletion_factor, + 0.01, 0.0, 1.0, + NULL, NULL, NULL + }, { {"checkpoint_completion_target", PGC_SIGHUP, WAL_CHECKPOINTS, gettext_noop("Time spent flushing dirty buffers during checkpoint, as fraction of checkpoint interval."), diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h index ca5cad7497..c5a7bc8361 100644 --- a/src/include/access/heapam.h +++ b/src/include/access/heapam.h @@ -100,6 +100,7 @@ extern Relation heap_openrv_extended(const RangeVar *relation, typedef struct HeapScanDescData *HeapScanDesc; typedef struct ParallelHeapScanDescData *ParallelHeapScanDesc; +extern double target_index_deletion_factor; /* * HeapScanIsValid * True iff the heap scan is valid. -- 2.17.1 --------------75D312DAFAE4FD0A374BCA4F Content-Type: text/x-patch; name="0004-v5-Retail-IndexTuple-Deletion-with-TID-sorting-in-Leaf.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0004-v5-Retail-IndexTuple-Deletion-with-TID-sorting-in-Leaf."; filename*1="patch" From ec49e3c00d21b5aa3ff9bca382cd8d745c5fe7f5 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" Date: Mon, 23 Jul 2018 09:38:45 +0500 Subject: [PATCH 4/4] v5 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 44f4d0dc9f..50378e0f51 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -889,15 +889,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, @@ -916,33 +920,33 @@ 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); page = BufferGetPage(buf); _bt_checkpage(irel, buf); opaque = (BTPageOpaque) PageGetSpecialPointer(page); + offnum = _bt_binsrch(irel, buf, keysCount, skey, &info->dead_tuples[pos], P_FIRSTDATAKEY(opaque), false); for (;;) { 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 @@ -967,20 +971,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], P_FIRSTDATAKEY(opaque), 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 */ @@ -992,15 +1003,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); } @@ -1017,7 +1041,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 9a625b8dba..1b952fedd9 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 79b386eebd..297d357a7d 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.17.1 --------------75D312DAFAE4FD0A374BCA4F--