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 --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
2.
Optimize compactify_tuples function