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 1g2qh0-00084w-FN for pgsql-hackers@arkaria.postgresql.org; Thu, 20 Sep 2018 04:35:55 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1g2qgy-0007t8-Qw for pgsql-hackers@arkaria.postgresql.org; Thu, 20 Sep 2018 04:35:52 +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 1g2qgy-0007sv-6y for pgsql-hackers@lists.postgresql.org; Thu, 20 Sep 2018 04:35:52 +0000 Received: from mail.postgrespro.ru ([93.174.131.138]) by makus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1g2qgu-0004Wp-34 for pgsql-hackers@postgresql.org; Thu, 20 Sep 2018 04:35:51 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id 2710321C26EB for ; Thu, 20 Sep 2018 07:35:45 +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 CE4AC21C26E2 for ; Thu, 20 Sep 2018 07:35:44 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1537418144; bh=FZV5AmtWqV0BLhDSHXgjmPl4vWRQcshgAbw5Iho/A6M=; h=Subject:To:References:From:Date:In-Reply-To; b=qpCWvyHAacGW2BLVwT1tuItPfYVsFEramTldE34xvuE1fjbD0w+I22n4VFFwXaSSe oBwryS8M7hWd9o/JuQUZKMOSgPJPnd4tqtTnXhPOV9zTGg2Qst8RPU5whVQ3ereTzl A5auTEd+cBNKdvczRT31AhAVEk8IQkqbGhl6HhhI= Subject: Re: [WIP] [B-Tree] Retail IndexTuple deletion To: PostgreSQL-Dev References: <425db134-8bba-005c-b59d-56e50de3b41e@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 Organization: Postgres Professional Message-ID: <11d32604-c0b9-7c05-edee-76582374404c@postgrespro.ru> Date: Thu, 20 Sep 2018 09:35:43 +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="------------3937AD4A21B7866FB6C98F92" 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. --------------3937AD4A21B7866FB6C98F92 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit The next version of amtargetdelete() interface and its implementation for nbtree, devoted to the problem of retail indextuple deletion. Uses 'v5-0001-Make-nbtree-indexes-have-unique-keys-in-tuples' patch [1] to delete all logical duplicates by one tree descent. [1] https://www.postgresql.org/message-id/CAH2-WzkfK=JVHjkd17TLDvsFb6psduTt5WYiT8dg+-UFc+rSSQ@mail.gmail.com -- Andrey Lepikhov Postgres Professional https://postgrespro.com The Russian Postgres Company --------------3937AD4A21B7866FB6C98F92 Content-Type: text/x-patch; name="v6-0001-Retail-IndexTuple-Deletion-Access-Method.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="v6-0001-Retail-IndexTuple-Deletion-Access-Method.patch" From 99c9bc340a730a85328549165ae8023a0716e147 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" Date: Thu, 20 Sep 2018 07:56:18 +0500 Subject: [PATCH] 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 | 160 +++++++++++++++++++++++++++ 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, 209 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 eade540ef5..20d9acddad 100644 --- a/src/backend/access/index/indexam.c +++ b/src/backend/access/index/indexam.c @@ -731,6 +731,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..a5d8ad4aa2 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -127,6 +127,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 +887,165 @@ btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, return stats; } +/* + * Deletion of index entries corresponding to heap TIDs. + * + * 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 the 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, + 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]; + int pos = info->last_dead_tuple; + IndexTuple itup; + + 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, &info->dead_tuples[pos], false, &buf, BT_WRITE, NULL); + + /* trade in our read lock for a write lock */ + LockBuffer(buf, BUFFER_LOCK_UNLOCK); + LockBuffer(buf, BT_WRITE); + + buf = _bt_moveright(irel, buf, keysCount, skey, &info->dead_tuples[pos], + false, true, stack, BT_WRITE, NULL); + + /* To prepare tuple entries search across index pages */ + Assert(BufferIsValid(buf)); + 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; + + /* Switch to the next page */ + if (offnum > PageGetMaxOffsetNumber(page)) + { + /* + * Before unlocking index page we need to delete + * all currently found tuples + */ + if (ndeletable > 0) + { + _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; + + /* + * Traverse to a next reliable index page if current page do not + * includes the (scan key; TID) value at the range. + */ + buf = _bt_moveright(irel, buf, keysCount, skey, &info->dead_tuples[pos], + false, true, stack, BT_WRITE, NULL); + page = BufferGetPage(buf); + _bt_checkpage(irel, buf); + opaque = (BTPageOpaque) PageGetSpecialPointer(page); + 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)) + /* Index relation do not contain TID of this DEAD tuple. */ + break; + } + + /* This index entry satisfied to the scan key? */ + cmpval = _bt_compare(irel, keysCount, skey, NULL, page, offnum); + + if (cmpval != 0) + /* End of the logical duplicates chain */ + 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); + + /* + * Search for next TID from presorted btree result comparable + * to TID from presorted dead_tuples tid list + */ + while (pos >= 0) + { + 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) + /* End of DEAD TIDs list was reached */ + break; + + offnum = OffsetNumberNext(offnum); + } + + /* + * Delete rest of dead index entries + */ + if (ndeletable > 0) + { + _bt_delitems_delete(irel, buf, deletable, ndeletable, hrel); + stats->tuples_removed += ndeletable; + } + + /* Release stack, scan key, unpin and unlock buffer */ + if (stack) + _bt_freestack(stack); + _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 9919e6f0d7..bdf1fdc472 100644 --- a/src/backend/access/spgist/spgutils.c +++ b/src/backend/access/spgist/spgutils.c @@ -65,6 +65,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 534fac7bf2..ee005891d2 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 last_dead_tuple; + 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 12f57773e7..59f8456e0b 100644 --- a/src/include/access/nbtree.h +++ b/src/include/access/nbtree.h @@ -557,6 +557,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 --------------3937AD4A21B7866FB6C98F92--