diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index d708117a40..b20559230c 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -411,50 +411,67 @@ PageRestoreTempPage(Page tempPage, Page oldPage)
 }
 
 /*
- * sorting support for PageRepairFragmentation and PageIndexMultiDelete
+ * Item pruning 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.
  */
 static void
-compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
+compactify_tuples(itemIdCompact itemidbase, int nitems, Page page)
 {
 	PageHeader	phdr = (PageHeader) page;
 	Offset		upper;
+	PGAlignedBlock scratch;
+	char	   *scratchptr = scratch.data;
 	int			i;
 
-	/* sort itemIdSortData array into decreasing itemoff order */
-	qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
-		  itemoffcompare);
+	/*
+	 * 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 before we copy them back into the page at the new position.
+	 *
+	 * If a large number of the tuples have been pruned (>75%) then we'll copy
+	 * these into the temp buffer tuple-by-tuple, otherwise we'll just copy
+	 * the entire tuple section of the page in a single memcpy().  Doing this
+	 * saves us doing large copies when we're pruning most of the tuples.
+	 */
+	if (nitems < PageGetMaxOffsetNumber(page) / 4)
+	{
+		for (i = 0; i < nitems; i++)
+		{
+			itemIdCompact	itemidptr = &itemidbase[i];
+			memcpy(scratchptr + itemidptr->itemoff, page + itemidptr->itemoff,
+				   itemidptr->alignedlen);
+		}
+	}
+	else
+	{
+		/* Copy the entire tuple space */
+		memcpy(scratchptr + phdr->pd_upper,
+			   page + phdr->pd_upper,
+			   phdr->pd_special - phdr->pd_upper);
+	}
 
 	upper = phdr->pd_special;
 	for (i = 0; i < nitems; i++)
 	{
-		itemIdSort	itemidptr = &itemidbase[i];
+		itemIdCompact	itemidptr = &itemidbase[i];
 		ItemId		lp;
 
 		lp = PageGetItemId(page, itemidptr->offsetindex + 1);
 		upper -= itemidptr->alignedlen;
-		memmove((char *) page + upper,
-				(char *) page + itemidptr->itemoff,
-				itemidptr->alignedlen);
+		memcpy((char *) page + upper,
+			   scratchptr + itemidptr->itemoff,
+			   itemidptr->alignedlen);
 		lp->lp_off = upper;
 	}
 
@@ -477,8 +494,8 @@ 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;
+	itemIdCompactData itemidbase[MaxHeapTuplesPerPage];
+	itemIdCompact	itemidptr;
 	ItemId		lp;
 	int			nline,
 				nstorage,
@@ -831,9 +848,9 @@ 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];
+	itemIdCompactData itemidbase[MaxIndexTuplesPerPage];
 	ItemIdData	newitemids[MaxIndexTuplesPerPage];
-	itemIdSort	itemidptr;
+	itemIdCompact	itemidptr;
 	ItemId		lp;
 	int			nline,
 				nused;