PostgreSQL 14通过改进compactify_tuples函数，去掉了O(nlogn)的qsort操作，使得Recovery和VACUUM操作有明显的性能提升。 ### 一、数据结构 **itemIdCompactData** ``` /* * Tuple defrag support for PageRepairFragmentation and PageIndexMultiDelete */ typedef struct itemIdCompactData { uint16 offsetindex; /* 行指针数组索引,linp array index */ int16 itemoff; /* 数据在页中的偏移,page offset of item data */ uint16 alignedlen; /* 对齐后的长度,MAXALIGN(item data len) */ } itemIdCompactData; typedef itemIdCompactData *itemIdCompact; typedef signed int Offset; ``` **ItemId** ``` //头文件：src/include/storage/itemid.h /* * An item pointer (also called line pointer) on a buffer page * * In some cases an item pointer is "in use" but does not have any associated * storage on the page. By convention, lp_len == 0 in every item pointer * that does not have storage, independently of its lp_flags state. */ typedef struct ItemIdData { unsigned lp_off:15,/* offset to tuple (from start of page) */ lp_flags:2,/* state of item pointer, see below */ lp_len:15;/* byte length of tuple */ } ItemIdData; typedef ItemIdData *ItemId; /* * lp_flags has these possible states. An UNUSED line pointer is available * for immediate re-use, the other states are not. */ #define LP_UNUSED 0 /* unused (should always have lp_len=0) */ #define LP_NORMAL 1 /* used (should always have lp_len>0) */ #define LP_REDIRECT 2 /* HOT redirect (should have lp_len=0) */ #define LP_DEAD 3 /* dead, may or may not have storage */ /* * Item offsets and lengths are represented by these types when * they're not actually stored in an ItemIdData. */ typedef uint16 ItemOffset; typedef uint16 ItemLength; ``` ### 二、源码解读 ```diff diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index d708117a4067e0464172663e5d54b1e0ec011b51..4bc2bf955dfd5aa1d4b2c4f0dc606b442da57d34 100644 (file) --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -411,51 +411,250 @@ PageRestoreTempPage(Page tempPage, Page oldPage) } /* - * sorting support for PageRepairFragmentation and PageIndexMultiDelete + * Tuple defrag support for PageRepairFragmentation and PageIndexMultiDelete */ //参见数据结构 -typedef struct itemIdSortData +typedef struct itemIdCompactData { uint16 offsetindex; /* linp array index */ int16 itemoff; /* page offset of item data */ uint16 alignedlen; /* MAXALIGN(item data len) */ -} itemIdSortData; -typedef itemIdSortData *itemIdSort; - -static int -itemoffcompare(const void *itemidp1, const void *itemidp2) -{ - /* Sort in decreasing itemoff order */ - return ((itemIdSort) itemidp2)->itemoff - - ((itemIdSort) itemidp1)->itemoff; -} +} itemIdCompactData; +typedef itemIdCompactData *itemIdCompact; /* * After removing or marking some line pointers unused, move the tuples to - * remove the gaps caused by the removed items. + * remove the gaps caused by the removed items and reorder them back into + * reverse line pointer order in the page. 删除或者标记行指针为无用后,消除因为删除出现的"裂缝"并按行指针顺序重排 + * + * This function can often be fairly hot, so it pays to take some measures to + * make it as optimal as possible. 该函数频繁调用,因此应尽可能的进行优化 + * + * Callers may pass 'presorted' as true if the 'itemidbase' array is sorted in + * descending order of itemoff. When this is true we can just memmove() + * tuples towards the end of the page. This is quite a common case as it's + * the order that tuples are initially inserted into pages. When we call this + * function to defragment the tuples in the page then any new line pointers + * added to the page will keep that presorted order, so hitting this case is + * still very common for tables that are commonly updated. 如果itemidbase数组已按itemoff降序排序,则调用方设置presorted为true. 在这种情况下,只需要调用memmove移动元组到page中合适的位置即可,就跟一开始插入到表的时候一样. + * + * When the 'itemidbase' array is not presorted then we're unable to just + * memmove() tuples around freely. Doing so could cause us to overwrite the + * memory belonging to a tuple we've not moved yet. In this case, we copy all + * the tuples that need to be moved into a temporary buffer. We can then + * simply memcpy() out of that temp buffer back into the page at the correct + * location. Tuples are copied back into the page in the same order as the + * 'itemidbase' array, so we end up reordering the tuples back into reverse + * line pointer order. This will increase the chances of hitting the + * presorted case the next time around. 如果itemidbase数组没有按itemoff排序,那么不能简单的调用memmove,因为会导致覆盖尚未移动的元组. 在这种情况下,拷贝需要移动的元组到临时缓存中.我们只需要简单的拷贝所有需要移动的元组到临时缓存中即可. 然后再把临时缓存中的数据通过memcpy拷贝回page的合适位置上,下次调用时很可能会使presorted为true. + * + * Callers must ensure that nitems is > 0 调用方必须确保nitems大于0 */ static void -compactify_tuples(itemIdSort itemidbase, int nitems, Page page) +compactify_tuples(itemIdCompact itemidbase, int nitems, Page page, bool presorted) { PageHeader phdr = (PageHeader) page; Offset upper;//目标位置:用于标记从哪开始拷贝数据 + Offset copy_tail;//源位置:尾部 + Offset copy_head;//源位置:头部,copy_tail - copy_head = 需要拷贝的范围 + itemIdCompact itemidptr;//Item指针 int i; - /* sort itemIdSortData array into decreasing itemoff order */ - qsort((char *) itemidbase, nitems, sizeof(itemIdSortData), - itemoffcompare); + /* Code within will not work correctly if nitems == 0 */ //必须大于0 + Assert(nitems > 0); - upper = phdr->pd_special; - for (i = 0; i < nitems; i++) //已按itemoff排序 + if (presorted) { - itemIdSort itemidptr = &itemidbase[i]; - ItemId lp; - lp = PageGetItemId(page, itemidptr->offsetindex + 1); - upper -= itemidptr->alignedlen; +#ifdef USE_ASSERT_CHECKING //检查是否合法(已按要求排序) + { + /* + * Verify we've not gotten any new callers that are incorrectly + * passing a true presorted value. + */ + Offset lastoff = phdr->pd_special; + + for (i = 0; i < nitems; i++) + { + itemidptr = &itemidbase[i]; + + Assert(lastoff > itemidptr->itemoff); + + lastoff = itemidptr->itemoff; + } + } +#endif /* USE_ASSERT_CHECKING */ + + /* + * 'itemidbase' is already in the optimal order, i.e, lower item + * pointers have a higher offset. This allows us to memmove() the + * tuples up to the end of the page without having to worry about + * overwriting other tuples that have not been moved yet. //已按要求排序,用memmove处理 + * + * There's a good chance that there are tuples already right at the + * end of the page that we can simply skip over because they're + * already in the correct location within the page. We'll do that + * first... //对于已处于page最后的哪些数据,无需处理 + */ + upper = phdr->pd_special; + i = 0; + do + { + itemidptr = &itemidbase[i]; //找到有"裂缝"的地方 + if (upper != itemidptr->itemoff + itemidptr->alignedlen) + break; + upper -= itemidptr->alignedlen; + + i++; + } while (i < nitems); + + /* + * Now that we've found the first tuple that needs to be moved, we can + * do the tuple compactification. We try and make the least number of + * memmove() calls and only call memmove() when there's a gap. When + * we see a gap we just move all tuples after the gap up until the + * point of the last move operation. + */ + copy_tail = copy_head = itemidptr->itemoff + itemidptr->alignedlen; + for (; i < nitems; i++) + { //继续往后遍历,直到出现下一个"裂缝"为止,这时候批量把裂缝之间的数据move到合适的位置 + ItemId lp; + + itemidptr = &itemidbase[i]; + lp = PageGetItemId(page, itemidptr->offsetindex + 1); + + if (copy_head != itemidptr->itemoff + itemidptr->alignedlen) + { + memmove((char *) page + upper, + page + copy_head, + copy_tail - copy_head); + + /* + * We've now moved all tuples already seen, but not the + * current tuple, so we set the copy_tail to the end of this + * tuple so it can be moved in another iteration of the loop. + */ + copy_tail = itemidptr->itemoff + itemidptr->alignedlen; + } + /* shift the target offset down by the length of this tuple */ //upper继续指向目标位置 + upper -= itemidptr->alignedlen; + /* point the copy_head to the start of this tuple */ + copy_head = itemidptr->itemoff; + + /* update the line pointer to reference the new offset */ //调整行指针偏移 + lp->lp_off = upper; + + } + + /* move the remaining tuples. */ //最后一批数据 memmove((char *) page + upper, - (char *) page + itemidptr->itemoff, - itemidptr->alignedlen); - lp->lp_off = upper; + page + copy_head, + copy_tail - copy_head); + } + else + { + PGAlignedBlock scratch; + char *scratchptr = scratch.data; + + /* + * Non-presorted case: The tuples in the itemidbase array may be in + * any order. So, in order to move these to the end of the page we + * must make a temp copy of each tuple that needs to be moved before + * we copy them back into the page at the new offset. //没有预排序的情况 : itemidbase数组中的元组顺序未知. //因此,使用临时缓存来存储需移动的tuples + * + * If a large percentage of tuples have been pruned (>75%) then we'll + * copy these into the temp buffer tuple-by-tuple, otherwise, we'll + * just do a single memcpy() for all tuples that need to be moved. + * When so many tuples have been removed there's likely to be a lot of + * gaps and it's unlikely that many non-movable tuples remain at the + * end of the page. //如果page中大量的元组已被清除(超过75%已被清除),逐个元组拷贝到缓存中, //否则使用memcpy拷贝所有元组 + */ + if (nitems < PageGetMaxOffsetNumber(page) / 4) + { //逐个元组拷贝到缓存中 + i = 0; + do + { + itemidptr = &itemidbase[i]; + memcpy(scratchptr + itemidptr->itemoff, page + itemidptr->itemoff, + itemidptr->alignedlen); + i++; + } while (i < nitems); + + /* Set things up for the compactification code below */ //进行整理前的准备工作 + i = 0; + itemidptr = &itemidbase[0]; + upper = phdr->pd_special; + } + else + { //全部拷贝到缓存(除了已按顺序那些元组) + upper = phdr->pd_special; + + /* + * Many tuples are likely to already be in the correct location. + * There's no need to copy these into the temp buffer. Instead + * we'll just skip forward in the itemidbase array to the position + * that we do need to move tuples from so that the code below just + * leaves these ones alone. + */ + i = 0; + do + { + itemidptr = &itemidbase[i]; + if (upper != itemidptr->itemoff + itemidptr->alignedlen) + break; + upper -= itemidptr->alignedlen; + + i++; + } while (i < nitems); + + /* Copy all tuples that need to be moved into the temp buffer */ //只需要拷贝需要整理的那些元组 + memcpy(scratchptr + phdr->pd_upper, + page + phdr->pd_upper, + upper - phdr->pd_upper); + } + + /* + * Do the tuple compactification. itemidptr is already pointing to + * the first tuple that we're going to move. Here we collapse the + * memcpy calls for adjacent tuples into a single call. This is done + * by delaying the memcpy call until we find a gap that needs to be + * closed. + */ //执行整理操作,逻辑与已排序的一致,调整行指针偏移,相当于重排序 + copy_tail = copy_head = itemidptr->itemoff + itemidptr->alignedlen; + for (; i < nitems; i++) + { + ItemId lp; + + itemidptr = &itemidbase[i]; + lp = PageGetItemId(page, itemidptr->offsetindex + 1); + + /* copy pending tuples when we detect a gap */ + if (copy_head != itemidptr->itemoff + itemidptr->alignedlen) + { + memcpy((char *) page + upper, + scratchptr + copy_head, + copy_tail - copy_head); + + /* + * We've now copied all tuples already seen, but not the + * current tuple, so we set the copy_tail to the end of this + * tuple. + */ + copy_tail = itemidptr->itemoff + itemidptr->alignedlen; + } + /* shift the target offset down by the length of this tuple */ + upper -= itemidptr->alignedlen; + /* point the copy_head to the start of this tuple */ + copy_head = itemidptr->itemoff; + + /* update the line pointer to reference the new offset */ + lp->lp_off = upper; + + } + + /* Copy the remaining chunk */ + memcpy((char *) page + upper, + scratchptr + copy_head, + copy_tail - copy_head); } phdr->pd_upper = upper; @@ -477,14 +676,16 @@ PageRepairFragmentation(Page page) Offset pd_lower = ((PageHeader) page)->pd_lower; Offset pd_upper = ((PageHeader) page)->pd_upper; Offset pd_special = ((PageHeader) page)->pd_special; - itemIdSortData itemidbase[MaxHeapTuplesPerPage]; - itemIdSort itemidptr; + Offset last_offset; + itemIdCompactData itemidbase[MaxHeapTuplesPerPage]; + itemIdCompact itemidptr; ItemId lp; int nline, nstorage, nunused; int i; Size totallen; + bool presorted = true; /* For now */ /* * It's worth the trouble to be more paranoid here than in most places, @@ -509,6 +710,7 @@ PageRepairFragmentation(Page page) nline = PageGetMaxOffsetNumber(page); itemidptr = itemidbase; nunused = totallen = 0; + last_offset = pd_special; for (i = FirstOffsetNumber; i <= nline; i++) { lp = PageGetItemId(page, i); @@ -518,6 +720,12 @@ PageRepairFragmentation(Page page) { itemidptr->offsetindex = i - 1; itemidptr->itemoff = ItemIdGetOffset(lp); + + if (last_offset > itemidptr->itemoff) + last_offset = itemidptr->itemoff; + else + presorted = false; + if (unlikely(itemidptr->itemoff < (int) pd_upper || itemidptr->itemoff >= (int) pd_special)) ereport(ERROR, @@ -552,7 +760,7 @@ PageRepairFragmentation(Page page) errmsg("corrupted item lengths: total %u, available space %u", (unsigned int) totallen, pd_special - pd_lower))); - compactify_tuples(itemidbase, nstorage, page); + compactify_tuples(itemidbase, nstorage, page, presorted); } /* Set hint bit for PageAddItem */ @@ -831,9 +1039,10 @@ PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems) Offset pd_lower = phdr->pd_lower; Offset pd_upper = phdr->pd_upper; Offset pd_special = phdr->pd_special; - itemIdSortData itemidbase[MaxIndexTuplesPerPage]; + Offset last_offset; + itemIdCompactData itemidbase[MaxIndexTuplesPerPage]; ItemIdData newitemids[MaxIndexTuplesPerPage]; - itemIdSort itemidptr; + itemIdCompact itemidptr; ItemId lp; int nline, nused; @@ -842,6 +1051,7 @@ PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems) unsigned offset; int nextitm; OffsetNumber offnum; + bool presorted = true; /* For now */ Assert(nitems <= MaxIndexTuplesPerPage); @@ -883,6 +1093,7 @@ PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems) totallen = 0; nused = 0; nextitm = 0; + last_offset = pd_special; for (offnum = FirstOffsetNumber; offnum <= nline; offnum = OffsetNumberNext(offnum)) { lp = PageGetItemId(page, offnum); @@ -906,6 +1117,12 @@ PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems) { itemidptr->offsetindex = nused; /* where it will go */ itemidptr->itemoff = offset; + + if (last_offset > itemidptr->itemoff) + last_offset = itemidptr->itemoff; + else + presorted = false; + itemidptr->alignedlen = MAXALIGN(size); totallen += itemidptr->alignedlen; newitemids[nused] = *lp; @@ -932,7 +1149,10 @@ PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems) phdr->pd_lower = SizeOfPageHeaderData + nused * sizeof(ItemIdData); /* and compactify the tuple data */ - compactify_tuples(itemidbase, nused, page); + if (nused > 0) + compactify_tuples(itemidbase, nused, page, presorted); + else + phdr->pd_upper = pd_special; } ``` ### 三、跟踪分析 N/A ### 四、参考资料 1.[Speeding up recovery and VACUUM in Postgres 14](https://techcommunity.microsoft.com/t5/azure-database-for-postgresql/speeding-up-recovery-and-vacuum-in-postgres-14/ba-p/2234071) 2.[Optimize compactify_tuples function](https://git.postgresql.org/gitweb/?p=postgresql.git;a=blobdiff;f=src/backend/storage/page/bufpage.c;h=4bc2bf955dfd5aa1d4b2c4f0dc606b442da57d34;hp=d708117a4067e0464172663e5d54b1e0ec011b51;hb=19c60ad69a91f346edf66996b2cf726f594d3d2b;hpb=ced138e8cbac7f5a840de8679e9882665478c680)