look-ma-no-sort.patch

diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index b6aa2af..73b73de 100644
*** a/src/backend/storage/page/bufpage.c
--- b/src/backend/storage/page/bufpage.c
*************** PageRestoreTempPage(Page tempPage, Page 
*** 415,471 ****
  }
  
  /*
-  * sorting support for PageRepairFragmentation and PageIndexMultiDelete
-  */
- typedef struct itemIdSortData
- {
- 	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;
- }
- 
- /*
-  * 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)
- {
- 	PageHeader	phdr = (PageHeader) page;
- 	Offset		upper;
- 	int			i;
- 
- 	/* sort itemIdSortData array into decreasing itemoff order */
- 	qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
- 		  itemoffcompare);
- 
- 	upper = phdr->pd_special;
- 	for (i = 0; i < nitems; i++)
- 	{
- 		itemIdSort	itemidptr = &itemidbase[i];
- 		ItemId		lp;
- 
- 		lp = PageGetItemId(page, itemidptr->offsetindex + 1);
- 		upper -= itemidptr->alignedlen;
- 		memmove((char *) page + upper,
- 				(char *) page + itemidptr->itemoff,
- 				itemidptr->alignedlen);
- 		lp->lp_off = upper;
- 	}
- 
- 	phdr->pd_upper = upper;
- }
- 
- /*
   * PageRepairFragmentation
   *
   * Frees fragmented space on a page.
--- 415,420 ----
*************** PageRepairFragmentation(Page page)
*** 481,494 ****
  	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;
! 	ItemId		lp;
! 	int			nline,
! 				nstorage,
! 				nunused;
! 	int			i;
! 	Size		totallen;
  
  	/*
  	 * It's worth the trouble to be more paranoid here than in most places,
--- 430,444 ----
  	Offset		pd_lower = ((PageHeader) page)->pd_lower;
  	Offset		pd_upper = ((PageHeader) page)->pd_upper;
  	Offset		pd_special = ((PageHeader) page)->pd_special;
! 	int			new_pd_upper,
! 				nline,
! 				nunused,
! 				i;
! 	union
! 	{
! 		char		page[BLCKSZ];
! 		double		align;		/* force workspace to be MAXALIGN'd */
! 	}			workspace;
  
  	/*
  	 * It's worth the trouble to be more paranoid here than in most places,
*************** PageRepairFragmentation(Page page)
*** 508,563 ****
  						pd_lower, pd_upper, pd_special)));
  
  	/*
! 	 * Run through the line pointer array and collect data about live items.
  	 */
  	nline = PageGetMaxOffsetNumber(page);
! 	itemidptr = itemidbase;
! 	nunused = totallen = 0;
  	for (i = FirstOffsetNumber; i <= nline; i++)
  	{
! 		lp = PageGetItemId(page, i);
  		if (ItemIdIsUsed(lp))
  		{
  			if (ItemIdHasStorage(lp))
  			{
! 				itemidptr->offsetindex = i - 1;
! 				itemidptr->itemoff = ItemIdGetOffset(lp);
! 				if (unlikely(itemidptr->itemoff < (int) pd_upper ||
! 							 itemidptr->itemoff >= (int) pd_special))
  					ereport(ERROR,
  							(errcode(ERRCODE_DATA_CORRUPTED),
! 							 errmsg("corrupted item pointer: %u",
! 									itemidptr->itemoff)));
! 				itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp));
! 				totallen += itemidptr->alignedlen;
! 				itemidptr++;
  			}
  		}
  		else
  		{
! 			/* Unused entries should have lp_len = 0, but make sure */
! 			ItemIdSetUnused(lp);
  			nunused++;
  		}
  	}
  
! 	nstorage = itemidptr - itemidbase;
! 	if (nstorage == 0)
! 	{
! 		/* Page is completely empty, so just reset it quickly */
! 		((PageHeader) page)->pd_upper = pd_special;
! 	}
! 	else
! 	{
! 		/* Need to compact the page the hard way */
! 		if (totallen > (Size) (pd_special - pd_lower))
! 			ereport(ERROR,
! 					(errcode(ERRCODE_DATA_CORRUPTED),
! 					 errmsg("corrupted item lengths: total %u, available space %u",
! 							(unsigned int) totallen, pd_special - pd_lower)));
  
! 		compactify_tuples(itemidbase, nstorage, page);
! 	}
  
  	/* Set hint bit for PageAddItem */
  	if (nunused > 0)
--- 458,526 ----
  						pd_lower, pd_upper, pd_special)));
  
  	/*
! 	 * We build updated copies of the line pointer array and tuple data area
! 	 * in workspace.page, and then copy them back to the real page when done.
! 	 * This ensures that if we error out partway through, we have not changed
! 	 * the real page.  It also lets us use memcpy rather than memmove for the
! 	 * data transfers, which is faster on some machines.
! 	 *
! 	 * A useful side effect of this approach is that the tuples are re-sorted
! 	 * so that their physical order matches their line pointer order, which
! 	 * should improve locality of access in future scans of the page.
  	 */
  	nline = PageGetMaxOffsetNumber(page);
! 	new_pd_upper = pd_special;
! 	nunused = 0;
  	for (i = FirstOffsetNumber; i <= nline; i++)
  	{
! 		ItemId		lp = PageGetItemId(page, i);
! 		ItemId		newlp = PageGetItemId(workspace.page, i);
! 
  		if (ItemIdIsUsed(lp))
  		{
+ 			*newlp = *lp;
  			if (ItemIdHasStorage(lp))
  			{
! 				int			offset = ItemIdGetOffset(lp);
! 				int			alignedlen = MAXALIGN(ItemIdGetLength(lp));
! 
! 				new_pd_upper -= alignedlen;
! 				newlp->lp_off = new_pd_upper;
! 				if (unlikely(offset < (int) pd_upper ||
! 							 (offset + alignedlen) > (int) pd_special ||
! 							 offset != MAXALIGN(offset) ||
! 							 new_pd_upper < (int) pd_lower))
  					ereport(ERROR,
  							(errcode(ERRCODE_DATA_CORRUPTED),
! 							 errmsg("corrupted item pointer: offset = %u, length = %u",
! 									offset, alignedlen)));
! 				memcpy(workspace.page + new_pd_upper,
! 					   (char *) page + offset,
! 					   alignedlen);
  			}
  		}
  		else
  		{
! 			/* We can just zero out all the fields in *newlp */
! 			ItemIdSetUnused(newlp);
  			nunused++;
  		}
  	}
  
! 	/*
! 	 * Okay, copy lower and upper workspace areas back to the real page.
! 	 */
! 	if (pd_lower > SizeOfPageHeaderData)
! 		memcpy((char *) page + SizeOfPageHeaderData,
! 			   workspace.page + SizeOfPageHeaderData,
! 			   pd_lower - SizeOfPageHeaderData);
! 	if (new_pd_upper < pd_special)
! 		memcpy((char *) page + new_pd_upper,
! 			   workspace.page + new_pd_upper,
! 			   pd_special - new_pd_upper);
  
! 	/* Page's pd_lower doesn't change, but pd_upper does */
! 	((PageHeader) page)->pd_upper = new_pd_upper;
  
  	/* Set hint bit for PageAddItem */
  	if (nunused > 0)
*************** PageIndexTupleDelete(Page page, OffsetNu
*** 831,853 ****
  void
  PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
  {
! 	PageHeader	phdr = (PageHeader) page;
! 	Offset		pd_lower = phdr->pd_lower;
! 	Offset		pd_upper = phdr->pd_upper;
! 	Offset		pd_special = phdr->pd_special;
! 	itemIdSortData itemidbase[MaxIndexTuplesPerPage];
! 	ItemIdData	newitemids[MaxIndexTuplesPerPage];
! 	itemIdSort	itemidptr;
! 	ItemId		lp;
! 	int			nline,
! 				nused;
! 	Size		totallen;
! 	Size		size;
! 	unsigned	offset;
! 	int			nextitm;
  	OffsetNumber offnum;
! 
! 	Assert(nitems <= MaxIndexTuplesPerPage);
  
  	/*
  	 * If there aren't very many items to delete, then retail
--- 794,813 ----
  void
  PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
  {
! 	Offset		pd_lower = ((PageHeader) page)->pd_lower;
! 	Offset		pd_upper = ((PageHeader) page)->pd_upper;
! 	Offset		pd_special = ((PageHeader) page)->pd_special;
! 	int			new_pd_upper,
! 				nline,
! 				nextnew,
! 				nextitm,
! 				lpalen;
  	OffsetNumber offnum;
! 	union
! 	{
! 		char		page[BLCKSZ];
! 		double		align;		/* force workspace to be MAXALIGN'd */
! 	}			workspace;
  
  	/*
  	 * If there aren't very many items to delete, then retail
*************** PageIndexMultiDelete(Page page, OffsetNu
*** 878,906 ****
  						pd_lower, pd_upper, pd_special)));
  
  	/*
! 	 * Scan the item pointer array and build a list of just the ones we are
! 	 * going to keep.  Notice we do not modify the page yet, since we are
! 	 * still validity-checking.
  	 */
  	nline = PageGetMaxOffsetNumber(page);
! 	itemidptr = itemidbase;
! 	totallen = 0;
! 	nused = 0;
  	nextitm = 0;
  	for (offnum = FirstOffsetNumber; offnum <= nline; offnum = OffsetNumberNext(offnum))
  	{
- 		lp = PageGetItemId(page, offnum);
- 		Assert(ItemIdHasStorage(lp));
- 		size = ItemIdGetLength(lp);
- 		offset = ItemIdGetOffset(lp);
- 		if (offset < pd_upper ||
- 			(offset + size) > pd_special ||
- 			offset != MAXALIGN(offset))
- 			ereport(ERROR,
- 					(errcode(ERRCODE_DATA_CORRUPTED),
- 					 errmsg("corrupted item pointer: offset = %u, length = %u",
- 							offset, (unsigned int) size)));
- 
  		if (nextitm < nitems && offnum == itemnos[nextitm])
  		{
  			/* skip item to be deleted */
--- 838,853 ----
  						pd_lower, pd_upper, pd_special)));
  
  	/*
! 	 * As in PageRepairFragmentation, we build new copies of the line pointer
! 	 * array and tuple data area in workspace.page, then transfer them back to
! 	 * the real page.
  	 */
  	nline = PageGetMaxOffsetNumber(page);
! 	new_pd_upper = pd_special;
! 	nextnew = FirstOffsetNumber;
  	nextitm = 0;
  	for (offnum = FirstOffsetNumber; offnum <= nline; offnum = OffsetNumberNext(offnum))
  	{
  		if (nextitm < nitems && offnum == itemnos[nextitm])
  		{
  			/* skip item to be deleted */
*************** PageIndexMultiDelete(Page page, OffsetNu
*** 908,920 ****
  		}
  		else
  		{
! 			itemidptr->offsetindex = nused; /* where it will go */
! 			itemidptr->itemoff = offset;
! 			itemidptr->alignedlen = MAXALIGN(size);
! 			totallen += itemidptr->alignedlen;
! 			newitemids[nused] = *lp;
! 			itemidptr++;
! 			nused++;
  		}
  	}
  
--- 855,884 ----
  		}
  		else
  		{
! 			ItemId		lp = PageGetItemId(page, offnum);
! 			ItemId		newlp;
! 			int			offset;
! 			int			alignedlen;
! 
! 			Assert(ItemIdHasStorage(lp));
! 			offset = ItemIdGetOffset(lp);
! 			alignedlen = MAXALIGN(ItemIdGetLength(lp));
! 			new_pd_upper -= alignedlen;
! 			if (unlikely(offset < (int) pd_upper ||
! 						 (offset + alignedlen) > (int) pd_special ||
! 						 offset != MAXALIGN(offset) ||
! 						 new_pd_upper < (int) pd_lower))
! 				ereport(ERROR,
! 						(errcode(ERRCODE_DATA_CORRUPTED),
! 						 errmsg("corrupted item pointer: offset = %u, length = %u",
! 								offset, alignedlen)));
! 			memcpy(workspace.page + new_pd_upper,
! 				   (char *) page + offset,
! 				   alignedlen);
! 			newlp = PageGetItemId(workspace.page, nextnew);
! 			*newlp = *lp;
! 			newlp->lp_off = new_pd_upper;
! 			nextnew++;
  		}
  	}
  
*************** PageIndexMultiDelete(Page page, OffsetNu
*** 922,942 ****
  	if (nextitm != nitems)
  		elog(ERROR, "incorrect index offsets supplied");
  
- 	if (totallen > (Size) (pd_special - pd_lower))
- 		ereport(ERROR,
- 				(errcode(ERRCODE_DATA_CORRUPTED),
- 				 errmsg("corrupted item lengths: total %u, available space %u",
- 						(unsigned int) totallen, pd_special - pd_lower)));
- 
  	/*
! 	 * Looks good. Overwrite the line pointers with the copy, from which we've
! 	 * removed all the unused items.
  	 */
! 	memcpy(phdr->pd_linp, newitemids, nused * sizeof(ItemIdData));
! 	phdr->pd_lower = SizeOfPageHeaderData + nused * sizeof(ItemIdData);
  
! 	/* and compactify the tuple data */
! 	compactify_tuples(itemidbase, nused, page);
  }
  
  
--- 886,906 ----
  	if (nextitm != nitems)
  		elog(ERROR, "incorrect index offsets supplied");
  
  	/*
! 	 * Okay, copy lower and upper workspace areas back to the real page.
  	 */
! 	lpalen = (nextnew - FirstOffsetNumber) * sizeof(ItemIdData);
! 	if (lpalen > 0)
! 		memcpy((char *) page + SizeOfPageHeaderData,
! 			   workspace.page + SizeOfPageHeaderData,
! 			   lpalen);
! 	if (new_pd_upper < pd_special)
! 		memcpy((char *) page + new_pd_upper,
! 			   workspace.page + new_pd_upper,
! 			   pd_special - new_pd_upper);
  
! 	((PageHeader) page)->pd_lower = SizeOfPageHeaderData + lpalen;
! 	((PageHeader) page)->pd_upper = new_pd_upper;
  }