On Wed, Dec 28, 2016 at 3:41 PM, Claudio Freire <klaussfre...@gmail.com> wrote:
>> Anyway, I found the problem that had caused segfault.
>>
>> for (segindex = 0; segindex <= vacrelstats->dead_tuples.last_seg; tupindex =
>> 0, segindex++)
>> {
>>     DeadTuplesSegment *seg =
>> &(vacrelstats->dead_tuples.dead_tuples[segindex]);
>>     int            num_dead_tuples = seg->num_dead_tuples;
>>
>>     while (tupindex < num_dead_tuples)
>>     ...
>>
>> You rely on the value of tupindex here, while during the very first pass the
>> 'tupindex' variable
>> may contain any garbage. And it happend that on my system there was negative
>> value
>> as I found inspecting core dump:
>>
>> (gdb) info locals
>> num_dead_tuples = 5
>> tottuples = 0
>> tupindex = -1819017215
>>
>> Which leads to failure in the next line
>>     tblk = ItemPointerGetBlockNumber(&seg->dead_tuples[tupindex]);
>>
>> The solution is to move this assignment inside the cycle.
>
> Good catch. I read that line suspecting that very same thing but
> somehow I was blind to it.

Attached v4 patches with the requested fixes.
From 988527b49ec0f48ea7fc85c7533e8eaa07d6fc3b Mon Sep 17 00:00:00 2001
From: Claudio Freire <klaussfre...@gmail.com>
Date: Fri, 2 Sep 2016 23:33:48 -0300
Subject: [PATCH 1/2] Vacuum: prefetch buffers on backward scan

This patch speeds up truncation by prefetching buffers during
the backward scan phase just prior to truncation. This optimization
helps rotating media because disk rotation induces a buffer-to-buffer
latency of roughly a whole rotation when reading backwards, such
disks are usually optimized for forward scans. Prefetching buffers
in larger chunks ameliorates the issue considerably and is otherwise
harmless. The prefetch amount should also not be an issue on SSD,
which won't benefit from the optimization, but won't be hurt either.
---
 src/backend/commands/vacuumlazy.c | 21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c
index b5fb325..854bce3 100644
--- a/src/backend/commands/vacuumlazy.c
+++ b/src/backend/commands/vacuumlazy.c
@@ -1825,7 +1825,7 @@ lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats)
 static BlockNumber
 count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 {
-	BlockNumber blkno;
+	BlockNumber blkno, prefetchBlkno;
 	instr_time	starttime;
 
 	/* Initialize the starttime if we check for conflicting lock requests */
@@ -1833,6 +1833,8 @@ count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 
 	/* Strange coding of loop control is needed because blkno is unsigned */
 	blkno = vacrelstats->rel_pages;
+	prefetchBlkno = blkno & ~0x1f;
+	prefetchBlkno = (prefetchBlkno > 32) ? prefetchBlkno - 32 : 0;
 	while (blkno > vacrelstats->nonempty_pages)
 	{
 		Buffer		buf;
@@ -1882,6 +1884,23 @@ count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 
 		blkno--;
 
+		/*
+		 * Speed up reads on rotating rust by prefetching a few blocks ahead.
+		 * Backward scans on rotary disks are slow if done one buffer at a time
+		 * because readahead won't kick in on most OSes, and each buffer will
+		 * have to wait for the platter to do a full rotation.
+		 * Should be harmless on SSD.
+		 */
+		if (blkno <= prefetchBlkno) {
+			BlockNumber pblkno;
+			if (prefetchBlkno >= 32)
+				prefetchBlkno -= 32;
+			else
+				prefetchBlkno = 0;
+			for (pblkno = prefetchBlkno; pblkno < blkno; pblkno++)
+				PrefetchBuffer(onerel, MAIN_FORKNUM, pblkno);
+		}
+
 		buf = ReadBufferExtended(onerel, MAIN_FORKNUM, blkno,
 								 RBM_NORMAL, vac_strategy);
 
-- 
1.8.4.5

From d360720415a2db5d5285a757c9a06e7ed854c5c5 Mon Sep 17 00:00:00 2001
From: Claudio Freire <klaussfre...@gmail.com>
Date: Mon, 12 Sep 2016 23:36:42 -0300
Subject: [PATCH 2/2] Vacuum: allow using more than 1GB work mem

Turn the dead_tuples array into a structure composed of several
exponentially bigger arrays, to enable usage of more than 1GB
of work mem during vacuum and thus reduce the number of full
index scans necessary to remove all dead tids when the memory is
available.
---
 src/backend/commands/vacuumlazy.c | 302 ++++++++++++++++++++++++++++++--------
 1 file changed, 237 insertions(+), 65 deletions(-)

diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c
index 854bce3..8b714e0 100644
--- a/src/backend/commands/vacuumlazy.c
+++ b/src/backend/commands/vacuumlazy.c
@@ -93,11 +93,40 @@
 #define LAZY_ALLOC_TUPLES		MaxHeapTuplesPerPage
 
 /*
+ * Minimum (starting) size of the dead_tuples array segments. Will allocate
+ * space for 128MB worth of tid pointers in the first segment, further segments
+ * will grow in size exponentially. Don't make it too small or the segment list
+ * will grow bigger than the sweetspot for search efficiency on big vacuums.
+ */
+#define LAZY_MIN_TUPLES		Max(MaxHeapTuplesPerPage, (128<<20) / sizeof(ItemPointerData))
+
+/*
  * Before we consider skipping a page that's marked as clean in
  * visibility map, we must've seen at least this many clean pages.
  */
 #define SKIP_PAGES_THRESHOLD	((BlockNumber) 32)
 
+typedef struct DeadTuplesSegment
+{
+	int			num_dead_tuples;	/* # of entries in the segment */
+	int			max_dead_tuples;	/* # of entries allocated in the segment */
+	ItemPointerData last_dead_tuple;	/* Copy of the last dead tuple (unset
+										 * until the segment is fully
+										 * populated) */
+	unsigned short padding;
+	ItemPointer dead_tuples;	/* Array of dead tuples */
+}	DeadTuplesSegment;
+
+typedef struct DeadTuplesMultiArray
+{
+	int			num_entries;	/* current # of entries */
+	int			max_entries;	/* total # of slots that can be allocated in
+								 * array */
+	int			num_segs;		/* number of dead tuple segments allocated */
+	int			last_seg;		/* last dead tuple segment with data (or 0) */
+	DeadTuplesSegment *dead_tuples;		/* array of num_segs segments */
+}	DeadTuplesMultiArray;
+
 typedef struct LVRelStats
 {
 	/* hasindex = true means two-pass strategy; false means one-pass */
@@ -117,14 +146,14 @@ typedef struct LVRelStats
 	BlockNumber nonempty_pages; /* actually, last nonempty page + 1 */
 	/* List of TIDs of tuples we intend to delete */
 	/* NB: this list is ordered by TID address */
-	int			num_dead_tuples;	/* current # of entries */
-	int			max_dead_tuples;	/* # slots allocated in array */
-	ItemPointer dead_tuples;	/* array of ItemPointerData */
+	DeadTuplesMultiArray dead_tuples;
 	int			num_index_scans;
 	TransactionId latestRemovedXid;
 	bool		lock_waiter_detected;
 } LVRelStats;
 
+#define DeadTuplesCurrentSegment(lvrelstats) (&((lvrelstats)->dead_tuples.dead_tuples[ \
+	(lvrelstats)->dead_tuples.last_seg ]))
 
 /* A few variables that don't seem worth passing around as parameters */
 static int	elevel = -1;
@@ -149,7 +178,7 @@ static void lazy_cleanup_index(Relation indrel,
 				   IndexBulkDeleteResult *stats,
 				   LVRelStats *vacrelstats);
 static int lazy_vacuum_page(Relation onerel, BlockNumber blkno, Buffer buffer,
-				 int tupindex, LVRelStats *vacrelstats, Buffer *vmbuffer);
+				 int tupindex, LVRelStats *vacrelstats, DeadTuplesSegment * seg, Buffer *vmbuffer);
 static bool should_attempt_truncation(LVRelStats *vacrelstats);
 static void lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats);
 static BlockNumber count_nondeletable_pages(Relation onerel,
@@ -157,8 +186,9 @@ static BlockNumber count_nondeletable_pages(Relation onerel,
 static void lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks);
 static void lazy_record_dead_tuple(LVRelStats *vacrelstats,
 					   ItemPointer itemptr);
+static void lazy_clear_dead_tuples(LVRelStats *vacrelstats);
 static bool lazy_tid_reaped(ItemPointer itemptr, void *state);
-static int	vac_cmp_itemptr(const void *left, const void *right);
+static inline int vac_cmp_itemptr(const void *left, const void *right);
 static bool heap_page_is_all_visible(Relation rel, Buffer buf,
 					 TransactionId *visibility_cutoff_xid, bool *all_frozen);
 
@@ -498,7 +528,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 	/* Report that we're scanning the heap, advertising total # of blocks */
 	initprog_val[0] = PROGRESS_VACUUM_PHASE_SCAN_HEAP;
 	initprog_val[1] = nblocks;
-	initprog_val[2] = vacrelstats->max_dead_tuples;
+	initprog_val[2] = vacrelstats->dead_tuples.max_entries;
 	pgstat_progress_update_multi_param(3, initprog_index, initprog_val);
 
 	/*
@@ -677,8 +707,8 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 		 * If we are close to overrunning the available space for dead-tuple
 		 * TIDs, pause and do a cycle of vacuuming before we tackle this page.
 		 */
-		if ((vacrelstats->max_dead_tuples - vacrelstats->num_dead_tuples) < MaxHeapTuplesPerPage &&
-			vacrelstats->num_dead_tuples > 0)
+		if ((vacrelstats->dead_tuples.max_entries - vacrelstats->dead_tuples.num_entries) < MaxHeapTuplesPerPage &&
+			vacrelstats->dead_tuples.num_entries > 0)
 		{
 			const int	hvp_index[] = {
 				PROGRESS_VACUUM_PHASE,
@@ -729,7 +759,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 			 * not to reset latestRemovedXid since we want that value to be
 			 * valid.
 			 */
-			vacrelstats->num_dead_tuples = 0;
+			lazy_clear_dead_tuples(vacrelstats);
 			vacrelstats->num_index_scans++;
 
 			/* Report that we are once again scanning the heap */
@@ -911,7 +941,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 		has_dead_tuples = false;
 		nfrozen = 0;
 		hastup = false;
-		prev_dead_count = vacrelstats->num_dead_tuples;
+		prev_dead_count = vacrelstats->dead_tuples.num_entries;
 		maxoff = PageGetMaxOffsetNumber(page);
 
 		/*
@@ -1123,10 +1153,13 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 		 * instead of doing a second scan.
 		 */
 		if (nindexes == 0 &&
-			vacrelstats->num_dead_tuples > 0)
+			vacrelstats->dead_tuples.num_entries > 0)
 		{
 			/* Remove tuples from heap */
-			lazy_vacuum_page(onerel, blkno, buf, 0, vacrelstats, &vmbuffer);
+			Assert(vacrelstats->dead_tuples.last_seg == 0);		/* Should not need more
+																 * than one segment per
+																 * page */
+			lazy_vacuum_page(onerel, blkno, buf, 0, vacrelstats, DeadTuplesCurrentSegment(vacrelstats), &vmbuffer);
 			has_dead_tuples = false;
 
 			/*
@@ -1134,7 +1167,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 			 * not to reset latestRemovedXid since we want that value to be
 			 * valid.
 			 */
-			vacrelstats->num_dead_tuples = 0;
+			lazy_clear_dead_tuples(vacrelstats);
 			vacuumed_pages++;
 		}
 
@@ -1237,7 +1270,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 		 * page, so remember its free space as-is.  (This path will always be
 		 * taken if there are no indexes.)
 		 */
-		if (vacrelstats->num_dead_tuples == prev_dead_count)
+		if (vacrelstats->dead_tuples.num_entries == prev_dead_count)
 			RecordPageWithFreeSpace(onerel, blkno, freespace);
 	}
 
@@ -1268,7 +1301,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 
 	/* If any tuples need to be deleted, perform final vacuum cycle */
 	/* XXX put a threshold on min number of tuples here? */
-	if (vacrelstats->num_dead_tuples > 0)
+	if (vacrelstats->dead_tuples.num_entries > 0)
 	{
 		const int	hvp_index[] = {
 			PROGRESS_VACUUM_PHASE,
@@ -1362,7 +1395,9 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 static void
 lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 {
+	int			tottuples;
 	int			tupindex;
+	int			segindex;
 	int			npages;
 	PGRUsage	ru0;
 	Buffer		vmbuffer = InvalidBuffer;
@@ -1370,35 +1405,43 @@ lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 	pg_rusage_init(&ru0);
 	npages = 0;
 
-	tupindex = 0;
-	while (tupindex < vacrelstats->num_dead_tuples)
+	segindex = 0;
+	tottuples = 0;
+	for (segindex = tupindex = 0; segindex <= vacrelstats->dead_tuples.last_seg; tupindex = 0, segindex++)
 	{
-		BlockNumber tblk;
-		Buffer		buf;
-		Page		page;
-		Size		freespace;
-
-		vacuum_delay_point();
+		DeadTuplesSegment *seg = &(vacrelstats->dead_tuples.dead_tuples[segindex]);
+		int			num_dead_tuples = seg->num_dead_tuples;
 
-		tblk = ItemPointerGetBlockNumber(&vacrelstats->dead_tuples[tupindex]);
-		buf = ReadBufferExtended(onerel, MAIN_FORKNUM, tblk, RBM_NORMAL,
-								 vac_strategy);
-		if (!ConditionalLockBufferForCleanup(buf))
+		while (tupindex < num_dead_tuples)
 		{
-			ReleaseBuffer(buf);
-			++tupindex;
-			continue;
-		}
-		tupindex = lazy_vacuum_page(onerel, tblk, buf, tupindex, vacrelstats,
-									&vmbuffer);
+			BlockNumber tblk;
+			Buffer		buf;
+			Page		page;
+			Size		freespace;
 
-		/* Now that we've compacted the page, record its available space */
-		page = BufferGetPage(buf);
-		freespace = PageGetHeapFreeSpace(page);
+			vacuum_delay_point();
 
-		UnlockReleaseBuffer(buf);
-		RecordPageWithFreeSpace(onerel, tblk, freespace);
-		npages++;
+			tblk = ItemPointerGetBlockNumber(&seg->dead_tuples[tupindex]);
+			buf = ReadBufferExtended(onerel, MAIN_FORKNUM, tblk, RBM_NORMAL,
+									 vac_strategy);
+			if (!ConditionalLockBufferForCleanup(buf))
+			{
+				ReleaseBuffer(buf);
+				++tupindex;
+				continue;
+			}
+			tupindex = lazy_vacuum_page(onerel, tblk, buf, tupindex, vacrelstats,
+										seg, &vmbuffer);
+
+			/* Now that we've compacted the page, record its available space */
+			page = BufferGetPage(buf);
+			freespace = PageGetHeapFreeSpace(page);
+
+			UnlockReleaseBuffer(buf);
+			RecordPageWithFreeSpace(onerel, tblk, freespace);
+			npages++;
+		}
+		tottuples += tupindex;
 	}
 
 	if (BufferIsValid(vmbuffer))
@@ -1410,7 +1453,7 @@ lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 	ereport(elevel,
 			(errmsg("\"%s\": removed %d row versions in %d pages",
 					RelationGetRelationName(onerel),
-					tupindex, npages),
+					tottuples, npages),
 			 errdetail("%s.",
 					   pg_rusage_show(&ru0))));
 }
@@ -1421,34 +1464,36 @@ lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
  *
  * Caller must hold pin and buffer cleanup lock on the buffer.
  *
- * tupindex is the index in vacrelstats->dead_tuples of the first dead
+ * tupindex is the index in seg->dead_tuples of the first dead
  * tuple for this page.  We assume the rest follow sequentially.
  * The return value is the first tupindex after the tuples of this page.
  */
 static int
 lazy_vacuum_page(Relation onerel, BlockNumber blkno, Buffer buffer,
-				 int tupindex, LVRelStats *vacrelstats, Buffer *vmbuffer)
+				 int tupindex, LVRelStats *vacrelstats, DeadTuplesSegment * seg, Buffer *vmbuffer)
 {
 	Page		page = BufferGetPage(buffer);
 	OffsetNumber unused[MaxOffsetNumber];
 	int			uncnt = 0;
 	TransactionId visibility_cutoff_xid;
 	bool		all_frozen;
+	ItemPointer dead_tuples = seg->dead_tuples;
+	int			num_dead_tuples = seg->num_dead_tuples;
 
 	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_VACUUMED, blkno);
 
 	START_CRIT_SECTION();
 
-	for (; tupindex < vacrelstats->num_dead_tuples; tupindex++)
+	for (; tupindex < num_dead_tuples; tupindex++)
 	{
 		BlockNumber tblk;
 		OffsetNumber toff;
 		ItemId		itemid;
 
-		tblk = ItemPointerGetBlockNumber(&vacrelstats->dead_tuples[tupindex]);
+		tblk = ItemPointerGetBlockNumber(&dead_tuples[tupindex]);
 		if (tblk != blkno)
 			break;				/* past end of tuples for this block */
-		toff = ItemPointerGetOffsetNumber(&vacrelstats->dead_tuples[tupindex]);
+		toff = ItemPointerGetOffsetNumber(&dead_tuples[tupindex]);
 		itemid = PageGetItemId(page, toff);
 		ItemIdSetUnused(itemid);
 		unused[uncnt++] = toff;
@@ -1582,6 +1627,7 @@ lazy_vacuum_index(Relation indrel,
 {
 	IndexVacuumInfo ivinfo;
 	PGRUsage	ru0;
+	DeadTuplesSegment *seg;
 
 	pg_rusage_init(&ru0);
 
@@ -1592,6 +1638,11 @@ lazy_vacuum_index(Relation indrel,
 	ivinfo.num_heap_tuples = vacrelstats->old_rel_tuples;
 	ivinfo.strategy = vac_strategy;
 
+	/* Finalize the current segment by setting its upper bound dead tuple */
+	seg = DeadTuplesCurrentSegment(vacrelstats);
+	if (seg->num_dead_tuples > 0)
+		seg->last_dead_tuple = seg->dead_tuples[seg->num_dead_tuples - 1];
+
 	/* Do bulk deletion */
 	*stats = index_bulk_delete(&ivinfo, *stats,
 							   lazy_tid_reaped, (void *) vacrelstats);
@@ -1599,7 +1650,7 @@ lazy_vacuum_index(Relation indrel,
 	ereport(elevel,
 			(errmsg("scanned index \"%s\" to remove %d row versions",
 					RelationGetRelationName(indrel),
-					vacrelstats->num_dead_tuples),
+					vacrelstats->dead_tuples.num_entries),
 			 errdetail("%s.", pg_rusage_show(&ru0))));
 }
 
@@ -1825,7 +1876,8 @@ lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats)
 static BlockNumber
 count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 {
-	BlockNumber blkno, prefetchBlkno;
+	BlockNumber blkno,
+				prefetchBlkno;
 	instr_time	starttime;
 
 	/* Initialize the starttime if we check for conflicting lock requests */
@@ -1886,13 +1938,15 @@ count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 
 		/*
 		 * Speed up reads on rotating rust by prefetching a few blocks ahead.
-		 * Backward scans on rotary disks are slow if done one buffer at a time
-		 * because readahead won't kick in on most OSes, and each buffer will
-		 * have to wait for the platter to do a full rotation.
-		 * Should be harmless on SSD.
+		 * Backward scans on rotary disks are slow if done one buffer at a
+		 * time because readahead won't kick in on most OSes, and each buffer
+		 * will have to wait for the platter to do a full rotation. Should be
+		 * harmless on SSD.
 		 */
-		if (blkno <= prefetchBlkno) {
+		if (blkno <= prefetchBlkno)
+		{
 			BlockNumber pblkno;
+
 			if (prefetchBlkno >= 32)
 				prefetchBlkno -= 32;
 			else
@@ -1962,7 +2016,8 @@ count_nondeletable_pages(Relation onerel, LVRelStats *vacrelstats)
 static void
 lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
 {
-	long		maxtuples;
+	long		maxtuples,
+				mintuples;
 	int			vac_work_mem = IsAutoVacuumWorkerProcess() &&
 	autovacuum_work_mem != -1 ?
 	autovacuum_work_mem : maintenance_work_mem;
@@ -1971,7 +2026,6 @@ lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
 	{
 		maxtuples = (vac_work_mem * 1024L) / sizeof(ItemPointerData);
 		maxtuples = Min(maxtuples, INT_MAX);
-		maxtuples = Min(maxtuples, MaxAllocSize / sizeof(ItemPointerData));
 
 		/* curious coding here to ensure the multiplication can't overflow */
 		if ((BlockNumber) (maxtuples / LAZY_ALLOC_TUPLES) > relblocks)
@@ -1985,10 +2039,18 @@ lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
 		maxtuples = MaxHeapTuplesPerPage;
 	}
 
-	vacrelstats->num_dead_tuples = 0;
-	vacrelstats->max_dead_tuples = (int) maxtuples;
-	vacrelstats->dead_tuples = (ItemPointer)
-		palloc(maxtuples * sizeof(ItemPointerData));
+	mintuples = Min(LAZY_MIN_TUPLES, maxtuples);
+
+	vacrelstats->dead_tuples.num_entries = 0;
+	vacrelstats->dead_tuples.max_entries = (int) maxtuples;
+	vacrelstats->dead_tuples.num_segs = 1;
+	vacrelstats->dead_tuples.last_seg = 0;
+	vacrelstats->dead_tuples.dead_tuples = (DeadTuplesSegment *)
+		palloc(sizeof(DeadTuplesSegment));
+	vacrelstats->dead_tuples.dead_tuples[0].dead_tuples = (ItemPointer)
+		palloc(mintuples * sizeof(ItemPointerData));
+	vacrelstats->dead_tuples.dead_tuples[0].max_dead_tuples = mintuples;
+	vacrelstats->dead_tuples.dead_tuples[0].num_dead_tuples = 0;
 }
 
 /*
@@ -2003,16 +2065,85 @@ lazy_record_dead_tuple(LVRelStats *vacrelstats,
 	 * could if we are given a really small maintenance_work_mem. In that
 	 * case, just forget the last few tuples (we'll get 'em next time).
 	 */
-	if (vacrelstats->num_dead_tuples < vacrelstats->max_dead_tuples)
+	if (vacrelstats->dead_tuples.num_entries < vacrelstats->dead_tuples.max_entries)
 	{
-		vacrelstats->dead_tuples[vacrelstats->num_dead_tuples] = *itemptr;
-		vacrelstats->num_dead_tuples++;
+		DeadTuplesSegment *seg = DeadTuplesCurrentSegment(vacrelstats);
+
+		if (seg->num_dead_tuples >= seg->max_dead_tuples)
+		{
+			/*
+			 * The segment is overflowing, so we must allocate a new segment.
+			 * We could have a preallocated segment descriptor already, in
+			 * which case we just reinitialize it, or we may need to repalloc
+			 * the vacrelstats->dead_tuples array. In that case, seg will no
+			 * longer be valid, so we must be careful about that. In any case,
+			 * we must update the last_dead_tuple copy in the overflowing
+			 * segment descriptor.
+			 */
+			Assert(seg->num_dead_tuples == seg->max_dead_tuples);
+			seg->last_dead_tuple = seg->dead_tuples[seg->num_dead_tuples - 1];
+			if (vacrelstats->dead_tuples.last_seg + 1 >= vacrelstats->dead_tuples.num_segs)
+			{
+				int			new_num_segs = vacrelstats->dead_tuples.num_segs * 2;
+
+				vacrelstats->dead_tuples.dead_tuples = (DeadTuplesSegment *) repalloc(
+							   (void *) vacrelstats->dead_tuples.dead_tuples,
+								   new_num_segs * sizeof(DeadTuplesSegment));
+				while (vacrelstats->dead_tuples.num_segs < new_num_segs)
+				{
+					/* Initialize as "unallocated" */
+					DeadTuplesSegment *nseg = &(vacrelstats->dead_tuples.dead_tuples[
+										 vacrelstats->dead_tuples.num_segs]);
+
+					nseg->num_dead_tuples = 0;
+					nseg->max_dead_tuples = 0;
+					nseg->dead_tuples = NULL;
+					vacrelstats->dead_tuples.num_segs++;
+				}
+				seg = DeadTuplesCurrentSegment(vacrelstats);
+			}
+			vacrelstats->dead_tuples.last_seg++;
+			seg = DeadTuplesCurrentSegment(vacrelstats);
+			if (seg->dead_tuples == NULL)
+			{
+				/*
+				 * If unallocated, allocate up to twice the amount of the
+				 * previous segment
+				 */
+				DeadTuplesSegment *pseg = seg - 1;
+				int			numtuples = vacrelstats->dead_tuples.max_entries - vacrelstats->dead_tuples.num_entries;
+
+				numtuples = Max(numtuples, MaxHeapTuplesPerPage);
+				numtuples = Min(numtuples, INT_MAX / 2);
+				numtuples = Min(numtuples, 2 * pseg->max_dead_tuples);
+				numtuples = Min(numtuples, MaxAllocSize / sizeof(ItemPointerData));
+				seg->dead_tuples = (ItemPointer) palloc(sizeof(ItemPointerData) * numtuples);
+				seg->max_dead_tuples = numtuples;
+			}
+			seg->num_dead_tuples = 0;
+		}
+		seg->dead_tuples[seg->num_dead_tuples] = *itemptr;
+		vacrelstats->dead_tuples.num_entries++;
+		seg->num_dead_tuples++;
 		pgstat_progress_update_param(PROGRESS_VACUUM_NUM_DEAD_TUPLES,
-									 vacrelstats->num_dead_tuples);
+									 vacrelstats->dead_tuples.num_entries);
 	}
 }
 
 /*
+ * lazy_clear_dead_tuples - reset all dead tuples segments
+ */
+static void
+lazy_clear_dead_tuples(LVRelStats *vacrelstats)
+{
+	int			nseg;
+
+	for (nseg = 0; nseg < vacrelstats->dead_tuples.last_seg; nseg++)
+		vacrelstats->dead_tuples.dead_tuples[nseg].num_dead_tuples = 0;
+	vacrelstats->dead_tuples.last_seg = 0;
+}
+
+/*
  *	lazy_tid_reaped() -- is a particular tid deletable?
  *
  *		This has the right signature to be an IndexBulkDeleteCallback.
@@ -2024,10 +2155,51 @@ lazy_tid_reaped(ItemPointer itemptr, void *state)
 {
 	LVRelStats *vacrelstats = (LVRelStats *) state;
 	ItemPointer res;
+	DeadTuplesSegment *seg,
+			   *rseg;
+	int			nseg,
+				last_seg;
+
+	if (vacrelstats->dead_tuples.num_segs == 0)
+		return false;
+
+	/*
+	 * Do a sequential search to find the first segment that could contain the
+	 * item pointer. Given the number of segments involved, binary search
+	 * would be pointless.
+	 */
+	seg = vacrelstats->dead_tuples.dead_tuples;
+	rseg = NULL;
+	last_seg = vacrelstats->dead_tuples.last_seg;
+	for (nseg = 0; nseg <= last_seg; nseg++, seg++)
+	{
+		int			rcomp = vac_cmp_itemptr((void *) itemptr, (void *) &(seg->last_dead_tuple));
+
+		if (rcomp == 0)
+		{
+			/* Found it, what are the chances! */
+			return true;
+		}
+		else if (rcomp < 0)
+		{
+			/* Found the right segment, further segments won't overlap */
+			rseg = seg;
+			break;
+		}
+	}
+	if (rseg == NULL || rseg->num_dead_tuples == 0)
+		return false;
+
+	/*
+	 * Quickly rule out by lower bound (should happen a lot) Upper bound was
+	 * already checked by segment search
+	 */
+	if (vac_cmp_itemptr((void *) itemptr, (void *) rseg->dead_tuples) < 0)
+		return false;
 
 	res = (ItemPointer) bsearch((void *) itemptr,
-								(void *) vacrelstats->dead_tuples,
-								vacrelstats->num_dead_tuples,
+								(void *) rseg->dead_tuples,
+								rseg->num_dead_tuples,
 								sizeof(ItemPointerData),
 								vac_cmp_itemptr);
 
@@ -2037,7 +2209,7 @@ lazy_tid_reaped(ItemPointer itemptr, void *state)
 /*
  * Comparator routines for use with qsort() and bsearch().
  */
-static int
+static inline int
 vac_cmp_itemptr(const void *left, const void *right)
 {
 	BlockNumber lblk,
-- 
1.8.4.5

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Reply via email to