0003_convert_chains_v12.patch

diff --git a/contrib/bloom/blvacuum.c b/contrib/bloom/blvacuum.c
index 04abd0f..ff50361 100644
--- a/contrib/bloom/blvacuum.c
+++ b/contrib/bloom/blvacuum.c
@@ -88,7 +88,7 @@ blbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 		while (itup < itupEnd)
 		{
 			/* Do we have to delete this tuple? */
-			if (callback(&itup->heapPtr, callback_state))
+			if (callback(&itup->heapPtr, false, callback_state) == IBDCR_DELETE)
 			{
 				/* Yes; adjust count of tuples that will be left on page */
 				BloomPageGetOpaque(page)->maxoff--;
diff --git a/src/backend/access/gin/ginvacuum.c b/src/backend/access/gin/ginvacuum.c
index c9ccfee..8ed71c5 100644
--- a/src/backend/access/gin/ginvacuum.c
+++ b/src/backend/access/gin/ginvacuum.c
@@ -56,7 +56,8 @@ ginVacuumItemPointers(GinVacuumState *gvs, ItemPointerData *items,
 	 */
 	for (i = 0; i < nitem; i++)
 	{
-		if (gvs->callback(items + i, gvs->callback_state))
+		if (gvs->callback(items + i, false, gvs->callback_state) ==
+				IBDCR_DELETE)
 		{
 			gvs->result->tuples_removed += 1;
 			if (!tmpitems)
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.c
index 77d9d12..0955db6 100644
--- a/src/backend/access/gist/gistvacuum.c
+++ b/src/backend/access/gist/gistvacuum.c
@@ -202,7 +202,8 @@ gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 				iid = PageGetItemId(page, i);
 				idxtuple = (IndexTuple) PageGetItem(page, iid);
 
-				if (callback(&(idxtuple->t_tid), callback_state))
+				if (callback(&(idxtuple->t_tid), false, callback_state) ==
+						IBDCR_DELETE)
 					todelete[ntodelete++] = i;
 				else
 					stats->num_index_tuples += 1;
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c
index 6645160..8b7a8aa 100644
--- a/src/backend/access/hash/hash.c
+++ b/src/backend/access/hash/hash.c
@@ -764,7 +764,8 @@ hashbucketcleanup(Relation rel, Bucket cur_bucket, Buffer bucket_buf,
 			 * To remove the dead tuples, we strictly want to rely on results
 			 * of callback function.  refer btvacuumpage for detailed reason.
 			 */
-			if (callback && callback(htup, callback_state))
+			if (callback && callback(htup, false, callback_state) ==
+					IBDCR_DELETE)
 			{
 				kill_tuple = true;
 				if (tuples_removed)
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 9c4522a..1f8f3eb 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -1958,17 +1958,32 @@ heap_fetch(Relation relation,
 }
 
 /*
- * Check if the HOT chain containing this tid is actually a WARM chain.
- * Note that even if the WARM update ultimately aborted, we still must do a
- * recheck because the failing UPDATE when have inserted created index entries
- * which are now stale, but still referencing this chain.
+ * Check status of a (possibly) WARM chain.
+ *
+ * This function looks at a HOT/WARM chain starting at tid and return a bitmask
+ * of information. We only follow the chain as long as it's known to be valid
+ * HOT chain. Information returned by the function consists of:
+ *
+ *  HCWC_WARM_TUPLE - a warm tuple is found somewhere in the chain. Note that
+ *  				  when a tuple is WARM updated, both old and new versions
+ *  				  of the tuple are treated as WARM tuple
+ *
+ *  HCWC_RED_TUPLE  - a warm tuple part of the Red chain is found somewhere in
+ *					  the chain.
+ *
+ *  HCWC_BLUE_TUPLE - a warm tuple part of the Blue chain is found somewhere in
+ *					  the chain.
+ *
+ *	If stop_at_warm is true, we stop when the first WARM tuple is found and
+ *	return information collected so far.
  */
-static bool
-hot_check_warm_chain(Page dp, ItemPointer tid)
+HeapCheckWarmChainStatus
+heap_check_warm_chain(Page dp, ItemPointer tid, bool stop_at_warm)
 {
-	TransactionId prev_xmax = InvalidTransactionId;
-	OffsetNumber offnum;
-	HeapTupleData heapTuple;
+	TransactionId				prev_xmax = InvalidTransactionId;
+	OffsetNumber				offnum;
+	HeapTupleData				heapTuple;
+	HeapCheckWarmChainStatus	status = 0;
 
 	offnum = ItemPointerGetOffsetNumber(tid);
 	heapTuple.t_self = *tid;
@@ -1985,7 +2000,16 @@ hot_check_warm_chain(Page dp, ItemPointer tid)
 
 		/* check for unused, dead, or redirected items */
 		if (!ItemIdIsNormal(lp))
+		{
+			if (ItemIdIsRedirected(lp))
+			{
+				/* Follow the redirect */
+				offnum = ItemIdGetRedirect(lp);
+				continue;
+			}
+			/* else must be end of chain */
 			break;
+		}
 
 		heapTuple.t_data = (HeapTupleHeader) PageGetItem(dp, lp);
 		ItemPointerSetOffsetNumber(&heapTuple.t_self, offnum);
@@ -2000,13 +2024,113 @@ hot_check_warm_chain(Page dp, ItemPointer tid)
 			break;
 
 
+		if (HeapTupleHeaderIsHeapWarmTuple(heapTuple.t_data))
+		{
+			/* We found a WARM tuple */
+			status |= HCWC_WARM_TUPLE;
+
+			/* 
+			 * If we've been told to stop at the first WARM tuple, just return
+			 * whatever information collected so far.
+			 */
+			if (stop_at_warm)
+				return status;
+
+			/* We found a tuple belonging to the Red chain */
+			if (HeapTupleHeaderIsWarmRed(heapTuple.t_data))
+				status |= HCWC_RED_TUPLE;
+		}
+		else
+			/* Must be a tuple belonging to the Blue chain */
+			status |= HCWC_BLUE_TUPLE;
+
+		/*
+		 * Check to see if HOT chain continues past this tuple; if so fetch
+		 * the next offnum and loop around.
+		 */
+		if (!HeapTupleIsHotUpdated(&heapTuple))
+			break;
+
 		/*
-		 * Presence of either WARM or WARM updated tuple signals possible
-		 * breakage and the caller must recheck tuple returned from this chain
-		 * for index satisfaction
+		 * It can't be a HOT chain if the tuple contains root line pointer
+		 */
+		if (HeapTupleHeaderHasRootOffset(heapTuple.t_data))
+			break;
+
+		offnum = ItemPointerGetOffsetNumber(&heapTuple.t_data->t_ctid);
+		prev_xmax = HeapTupleHeaderGetUpdateXid(heapTuple.t_data);
+	}
+
+	/* All OK. No need to recheck */
+	return status;
+}
+
+/*
+ * Scan through the WARM chain starting at tid and reset all WARM related
+ * flags. At the end, the chain will have all characteristics of a regular HOT
+ * chain.
+ *
+ * Return the number of cleared offnums. Cleared offnums are returned in the
+ * passed-in cleared_offnums array. The caller must ensure that the array is
+ * large enough to hold maximum offnums that can be cleared by this invokation
+ * of heap_clear_warm_chain().
+ */
+int
+heap_clear_warm_chain(Page dp, ItemPointer tid, OffsetNumber *cleared_offnums)
+{
+	TransactionId				prev_xmax = InvalidTransactionId;
+	OffsetNumber				offnum;
+	HeapTupleData				heapTuple;
+	int							num_cleared = 0;
+
+	offnum = ItemPointerGetOffsetNumber(tid);
+	heapTuple.t_self = *tid;
+	/* Scan through possible multiple members of HOT-chain */
+	for (;;)
+	{
+		ItemId		lp;
+
+		/* check for bogus TID */
+		if (offnum < FirstOffsetNumber || offnum > PageGetMaxOffsetNumber(dp))
+			break;
+
+		lp = PageGetItemId(dp, offnum);
+
+		/* check for unused, dead, or redirected items */
+		if (!ItemIdIsNormal(lp))
+		{
+			if (ItemIdIsRedirected(lp))
+			{
+				/* Follow the redirect */
+				offnum = ItemIdGetRedirect(lp);
+				continue;
+			}
+			/* else must be end of chain */
+			break;
+		}
+
+		heapTuple.t_data = (HeapTupleHeader) PageGetItem(dp, lp);
+		ItemPointerSetOffsetNumber(&heapTuple.t_self, offnum);
+
+		/*
+		 * The xmin should match the previous xmax value, else chain is
+		 * broken.
+		 */
+		if (TransactionIdIsValid(prev_xmax) &&
+			!TransactionIdEquals(prev_xmax,
+								 HeapTupleHeaderGetXmin(heapTuple.t_data)))
+			break;
+
+
+		/*
+		 * Clear WARM and Red flags
 		 */
 		if (HeapTupleHeaderIsHeapWarmTuple(heapTuple.t_data))
-			return true;
+		{
+			HeapTupleHeaderClearHeapWarmTuple(heapTuple.t_data);
+			HeapTupleHeaderClearWarmRed(heapTuple.t_data);
+			cleared_offnums[num_cleared++] = offnum;
+		}
 
 		/*
 		 * Check to see if HOT chain continues past this tuple; if so fetch
@@ -2025,8 +2149,7 @@ hot_check_warm_chain(Page dp, ItemPointer tid)
 		prev_xmax = HeapTupleHeaderGetUpdateXid(heapTuple.t_data);
 	}
 
-	/* All OK. No need to recheck */
-	return false;
+	return num_cleared;
 }
 
 /*
@@ -2135,7 +2258,11 @@ heap_hot_search_buffer(ItemPointer tid, Relation relation, Buffer buffer,
 		 * possible improvements here
 		 */
 		if (recheck && *recheck == false)
-			*recheck = hot_check_warm_chain(dp, &heapTuple->t_self);
+		{
+			HeapCheckWarmChainStatus status;
+			status = heap_check_warm_chain(dp, &heapTuple->t_self, true);
+			*recheck = HCWC_IS_WARM(status);
+		}
 
 		/*
 		 * When first_call is true (and thus, skip is initially false) we'll
@@ -3409,7 +3536,9 @@ l1:
 	}
 
 	/* store transaction information of xact deleting the tuple */
-	tp.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+	tp.t_data->t_infomask &= ~HEAP_XMAX_BITS;
+   	if (HeapTupleHeaderIsMoved(tp.t_data))
+		tp.t_data->t_infomask &= ~HEAP_MOVED;
 	tp.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 	tp.t_data->t_infomask |= new_infomask;
 	tp.t_data->t_infomask2 |= new_infomask2;
@@ -4172,7 +4301,9 @@ l2:
 		START_CRIT_SECTION();
 
 		/* Clear obsolete visibility flags ... */
-		oldtup.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+		oldtup.t_data->t_infomask &= ~HEAP_XMAX_BITS;
+		if (HeapTupleHeaderIsMoved(oldtup.t_data))
+			oldtup.t_data->t_infomask &= ~HEAP_MOVED;
 		oldtup.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		HeapTupleClearHotUpdated(&oldtup);
 		/* ... and store info about transaction updating this tuple */
@@ -4419,6 +4550,16 @@ l2:
 		}
 
 		/*
+		 * If the old tuple is already a member of the Red chain, mark the new
+		 * tuple with the same flag
+		 */
+		if (HeapTupleIsHeapWarmTupleRed(&oldtup))
+		{
+			HeapTupleSetHeapWarmTupleRed(heaptup);
+			HeapTupleSetHeapWarmTupleRed(newtup);
+		}
+
+		/*
 		 * For HOT (or WARM) updated tuples, we store the offset of the root
 		 * line pointer of this chain in the ip_posid field of the new tuple.
 		 * Usually this information will be available in the corresponding
@@ -4435,12 +4576,20 @@ l2:
 		/* Mark the old tuple as HOT-updated */
 		HeapTupleSetHotUpdated(&oldtup);
 		HeapTupleSetHeapWarmTuple(&oldtup);
+		
 		/* And mark the new tuple as heap-only */
 		HeapTupleSetHeapOnly(heaptup);
+		/* Mark the new tuple as WARM tuple */ 
 		HeapTupleSetHeapWarmTuple(heaptup);
+		/* This update also starts a Red chain */
+		HeapTupleSetHeapWarmTupleRed(heaptup);
+		Assert(!HeapTupleIsHeapWarmTupleRed(&oldtup));
+
 		/* Mark the caller's copy too, in case different from heaptup */
 		HeapTupleSetHeapOnly(newtup);
 		HeapTupleSetHeapWarmTuple(newtup);
+		HeapTupleSetHeapWarmTupleRed(newtup);
+
 		if (HeapTupleHeaderHasRootOffset(oldtup.t_data))
 			root_offnum = HeapTupleHeaderGetRootOffset(oldtup.t_data);
 		else
@@ -4459,6 +4608,8 @@ l2:
 		HeapTupleClearHeapOnly(newtup);
 		HeapTupleClearHeapWarmTuple(heaptup);
 		HeapTupleClearHeapWarmTuple(newtup);
+		HeapTupleClearHeapWarmTupleRed(heaptup);
+		HeapTupleClearHeapWarmTupleRed(newtup);
 		root_offnum = InvalidOffsetNumber;
 	}
 
@@ -4477,7 +4628,9 @@ l2:
 	HeapTupleHeaderSetHeapLatest(newtup->t_data, root_offnum);
 
 	/* Clear obsolete visibility flags, possibly set by ourselves above... */
-	oldtup.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+	oldtup.t_data->t_infomask &= ~HEAP_XMAX_BITS;
+	if (HeapTupleHeaderIsMoved(oldtup.t_data))
+		oldtup.t_data->t_infomask &= ~HEAP_MOVED;
 	oldtup.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 	/* ... and store info about transaction updating this tuple */
 	Assert(TransactionIdIsValid(xmax_old_tuple));
@@ -6398,7 +6551,9 @@ heap_abort_speculative(Relation relation, HeapTuple tuple)
 	PageSetPrunable(page, RecentGlobalXmin);
 
 	/* store transaction information of xact deleting the tuple */
-	tp.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+	tp.t_data->t_infomask &= ~HEAP_XMAX_BITS;
+	if (HeapTupleHeaderIsMoved(tp.t_data))
+		tp.t_data->t_infomask &= ~HEAP_MOVED;
 	tp.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 
 	/*
@@ -6972,7 +7127,7 @@ heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
 	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
 	 */
-	if (tuple->t_infomask & HEAP_MOVED)
+	if (HeapTupleHeaderIsMoved(tuple))
 	{
 		xid = HeapTupleHeaderGetXvac(tuple);
 
@@ -6991,7 +7146,7 @@ heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 			 * have failed; whereas a non-dead MOVED_IN tuple must mean the
 			 * xvac transaction succeeded.
 			 */
-			if (tuple->t_infomask & HEAP_MOVED_OFF)
+			if (HeapTupleHeaderIsMovedOff(tuple))
 				frz->frzflags |= XLH_INVALID_XVAC;
 			else
 				frz->frzflags |= XLH_FREEZE_XVAC;
@@ -7461,7 +7616,7 @@ heap_tuple_needs_eventual_freeze(HeapTupleHeader tuple)
 			return true;
 	}
 
-	if (tuple->t_infomask & HEAP_MOVED)
+	if (HeapTupleHeaderIsMoved(tuple))
 	{
 		xid = HeapTupleHeaderGetXvac(tuple);
 		if (TransactionIdIsNormal(xid))
@@ -7544,7 +7699,7 @@ heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
 			return true;
 	}
 
-	if (tuple->t_infomask & HEAP_MOVED)
+	if (HeapTupleHeaderIsMoved(tuple))
 	{
 		xid = HeapTupleHeaderGetXvac(tuple);
 		if (TransactionIdIsNormal(xid) &&
@@ -7570,7 +7725,7 @@ HeapTupleHeaderAdvanceLatestRemovedXid(HeapTupleHeader tuple,
 	TransactionId xmax = HeapTupleHeaderGetUpdateXid(tuple);
 	TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
-	if (tuple->t_infomask & HEAP_MOVED)
+	if (HeapTupleHeaderIsMoved(tuple))
 	{
 		if (TransactionIdPrecedes(*latestRemovedXid, xvac))
 			*latestRemovedXid = xvac;
@@ -8523,7 +8678,9 @@ heap_xlog_delete(XLogReaderState *record)
 
 		htup = (HeapTupleHeader) PageGetItem(page, lp);
 
-		htup->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+		htup->t_infomask &= ~HEAP_XMAX_BITS;
+		if (HeapTupleHeaderIsMoved(htup))
+			htup->t_infomask &= ~HEAP_MOVED;
 		htup->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		HeapTupleHeaderClearHotUpdated(htup);
 		fix_infomask_from_infobits(xlrec->infobits_set,
@@ -9186,7 +9343,9 @@ heap_xlog_lock(XLogReaderState *record)
 
 		htup = (HeapTupleHeader) PageGetItem(page, lp);
 
-		htup->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+		htup->t_infomask &= ~HEAP_XMAX_BITS;
+		if (HeapTupleHeaderIsMoved(htup))
+			htup->t_infomask &= ~HEAP_MOVED;
 		htup->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		fix_infomask_from_infobits(xlrec->infobits_set, &htup->t_infomask,
 								   &htup->t_infomask2);
@@ -9265,7 +9424,9 @@ heap_xlog_lock_updated(XLogReaderState *record)
 
 		htup = (HeapTupleHeader) PageGetItem(page, lp);
 
-		htup->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
+		htup->t_infomask &= ~HEAP_XMAX_BITS;
+		if (HeapTupleHeaderIsMoved(htup))
+			htup->t_infomask &= ~HEAP_MOVED;
 		htup->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		fix_infomask_from_infobits(xlrec->infobits_set, &htup->t_infomask,
 								   &htup->t_infomask2);
diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 19e7048..47b01eb 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -1620,7 +1620,8 @@ toast_save_datum(Relation rel, Datum value,
 							 toastrel,
 							 toastidxs[i]->rd_index->indisunique ?
 							 UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
-							 NULL);
+							 NULL,
+							 false);
 		}
 
 		/*
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index f56c58f..e8027f8 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -199,7 +199,8 @@ index_insert(Relation indexRelation,
 			 ItemPointer heap_t_ctid,
 			 Relation heapRelation,
 			 IndexUniqueCheck checkUnique,
-			 IndexInfo *indexInfo)
+			 IndexInfo *indexInfo,
+			 bool warm_update)
 {
 	RELATION_CHECKS;
 	CHECK_REL_PROCEDURE(aminsert);
@@ -209,6 +210,12 @@ index_insert(Relation indexRelation,
 									   (HeapTuple) NULL,
 									   InvalidBuffer);
 
+	if (warm_update)
+	{
+		Assert(indexRelation->rd_amroutine->amwarminsert != NULL);
+		return indexRelation->rd_amroutine->amwarminsert(indexRelation, values,
+				isnull, heap_t_ctid, heapRelation, checkUnique, indexInfo);
+	}
 	return indexRelation->rd_amroutine->aminsert(indexRelation, values, isnull,
 												 heap_t_ctid, heapRelation,
 												 checkUnique, indexInfo);
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 952ed8f..4988f47 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -147,6 +147,7 @@ bthandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = btbuild;
 	amroutine->ambuildempty = btbuildempty;
 	amroutine->aminsert = btinsert;
+	amroutine->amwarminsert = btwarminsert;
 	amroutine->ambulkdelete = btbulkdelete;
 	amroutine->amvacuumcleanup = btvacuumcleanup;
 	amroutine->amcanreturn = btcanreturn;
@@ -317,11 +318,12 @@ btbuildempty(Relation index)
  *		Descend the tree recursively, find the appropriate location for our
  *		new tuple, and put it there.
  */
-bool
-btinsert(Relation rel, Datum *values, bool *isnull,
+static bool
+btinsert_internal(Relation rel, Datum *values, bool *isnull,
 		 ItemPointer ht_ctid, Relation heapRel,
 		 IndexUniqueCheck checkUnique,
-		 IndexInfo *indexInfo)
+		 IndexInfo *indexInfo,
+		 bool warm_update)
 {
 	bool		result;
 	IndexTuple	itup;
@@ -330,6 +332,11 @@ btinsert(Relation rel, Datum *values, bool *isnull,
 	itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
 	itup->t_tid = *ht_ctid;
 
+	if (warm_update)
+		itup->t_info |= INDEX_RED_CHAIN;
+	else
+		itup->t_info &= ~INDEX_RED_CHAIN;
+
 	result = _bt_doinsert(rel, itup, checkUnique, heapRel);
 
 	pfree(itup);
@@ -337,6 +344,26 @@ btinsert(Relation rel, Datum *values, bool *isnull,
 	return result;
 }
 
+bool
+btinsert(Relation rel, Datum *values, bool *isnull,
+		 ItemPointer ht_ctid, Relation heapRel,
+		 IndexUniqueCheck checkUnique,
+		 IndexInfo *indexInfo)
+{
+	return btinsert_internal(rel, values, isnull, ht_ctid, heapRel,
+			checkUnique, indexInfo, false);
+}
+
+bool
+btwarminsert(Relation rel, Datum *values, bool *isnull,
+		 ItemPointer ht_ctid, Relation heapRel,
+		 IndexUniqueCheck checkUnique,
+		 IndexInfo *indexInfo)
+{
+	return btinsert_internal(rel, values, isnull, ht_ctid, heapRel,
+			checkUnique, indexInfo, true);
+}
+
 /*
  *	btgettuple() -- Get the next tuple in the scan.
  */
@@ -1253,6 +1280,8 @@ restart:
 			{
 				IndexTuple	itup;
 				ItemPointer htup;
+				IndexBulkDeleteCallbackResult	result;
+				bool		is_red = false;
 
 				itup = (IndexTuple) PageGetItem(page,
 												PageGetItemId(page, offnum));
@@ -1279,8 +1308,29 @@ restart:
 				 * applies to *any* type of index that marks index tuples as
 				 * killed.
 				 */
-				if (callback(htup, callback_state))
+				if (itup->t_info & INDEX_RED_CHAIN)
+					is_red = true;
+
+				if (is_red)
+					stats->num_red_pointers++;
+				else
+					stats->num_blue_pointers++;
+
+				result = callback(htup, is_red, callback_state);
+				if (result == IBDCR_DELETE)
+				{
+					if (is_red)
+						stats->red_pointers_removed++;
+					else
+						stats->blue_pointers_removed++;
 					deletable[ndeletable++] = offnum;
+				}
+				else if (result == IBDCR_COLOR_BLUE)
+				{
+					stats->pointers_colored++;
+					itup->t_info &= ~INDEX_RED_CHAIN;
+				}
+				/* XXX XLOG stuff for converted pointers */
 			}
 		}
 
diff --git a/src/backend/access/spgist/spgvacuum.c b/src/backend/access/spgist/spgvacuum.c
index cce9b3f..5343b10 100644
--- a/src/backend/access/spgist/spgvacuum.c
+++ b/src/backend/access/spgist/spgvacuum.c
@@ -155,7 +155,8 @@ vacuumLeafPage(spgBulkDeleteState *bds, Relation index, Buffer buffer,
 		{
 			Assert(ItemPointerIsValid(&lt->heapPtr));
 
-			if (bds->callback(&lt->heapPtr, bds->callback_state))
+			if (bds->callback(&lt->heapPtr, false, bds->callback_state) ==
+					IBDCR_DELETE)
 			{
 				bds->stats->tuples_removed += 1;
 				deletable[i] = true;
@@ -425,7 +426,8 @@ vacuumLeafRoot(spgBulkDeleteState *bds, Relation index, Buffer buffer)
 		{
 			Assert(ItemPointerIsValid(&lt->heapPtr));
 
-			if (bds->callback(&lt->heapPtr, bds->callback_state))
+			if (bds->callback(&lt->heapPtr, false, bds->callback_state) ==
+					IBDCR_DELETE)
 			{
 				bds->stats->tuples_removed += 1;
 				toDelete[xlrec.nDelete] = i;
@@ -902,10 +904,10 @@ spgbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 }
 
 /* Dummy callback to delete no tuples during spgvacuumcleanup */
-static bool
-dummy_callback(ItemPointer itemptr, void *state)
+static IndexBulkDeleteCallbackResult
+dummy_callback(ItemPointer itemptr, bool is_red, void *state)
 {
-	return false;
+	return IBDCR_KEEP;
 }
 
 /*
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index bba52ec..ab37b43 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -115,7 +115,7 @@ static void IndexCheckExclusion(Relation heapRelation,
 					IndexInfo *indexInfo);
 static inline int64 itemptr_encode(ItemPointer itemptr);
 static inline void itemptr_decode(ItemPointer itemptr, int64 encoded);
-static bool validate_index_callback(ItemPointer itemptr, void *opaque);
+static IndexBulkDeleteCallbackResult validate_index_callback(ItemPointer itemptr, bool is_red, void *opaque);
 static void validate_index_heapscan(Relation heapRelation,
 						Relation indexRelation,
 						IndexInfo *indexInfo,
@@ -2949,15 +2949,15 @@ itemptr_decode(ItemPointer itemptr, int64 encoded)
 /*
  * validate_index_callback - bulkdelete callback to collect the index TIDs
  */
-static bool
-validate_index_callback(ItemPointer itemptr, void *opaque)
+static IndexBulkDeleteCallbackResult
+validate_index_callback(ItemPointer itemptr, bool is_red, void *opaque)
 {
 	v_i_state  *state = (v_i_state *) opaque;
 	int64		encoded = itemptr_encode(itemptr);
 
 	tuplesort_putdatum(state->tuplesort, Int64GetDatum(encoded), false);
 	state->itups += 1;
-	return false;				/* never actually delete anything */
+	return IBDCR_KEEP;				/* never actually delete anything */
 }
 
 /*
@@ -3178,7 +3178,8 @@ validate_index_heapscan(Relation heapRelation,
 						 heapRelation,
 						 indexInfo->ii_Unique ?
 						 UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
-						 indexInfo);
+						 indexInfo,
+						 false);
 
 			state->tups_inserted += 1;
 		}
diff --git a/src/backend/catalog/indexing.c b/src/backend/catalog/indexing.c
index e5355a8..5b6efcf 100644
--- a/src/backend/catalog/indexing.c
+++ b/src/backend/catalog/indexing.c
@@ -172,7 +172,8 @@ CatalogIndexInsert(CatalogIndexState indstate, HeapTuple heapTuple,
 					 heapRelation,
 					 relationDescs[i]->rd_index->indisunique ?
 					 UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
-					 indexInfo);
+					 indexInfo,
+					 warm_update);
 	}
 
 	ExecDropSingleTupleTableSlot(slot);
@@ -222,7 +223,7 @@ CatalogTupleInsertWithInfo(Relation heapRel, HeapTuple tup,
 
 	oid = simple_heap_insert(heapRel, tup);
 
-	CatalogIndexInsert(indstate, tup, false, NULL);
+	CatalogIndexInsert(indstate, tup, NULL, false);
 
 	return oid;
 }
diff --git a/src/backend/commands/constraint.c b/src/backend/commands/constraint.c
index d9c0fe7..330b661 100644
--- a/src/backend/commands/constraint.c
+++ b/src/backend/commands/constraint.c
@@ -168,7 +168,8 @@ unique_key_recheck(PG_FUNCTION_ARGS)
 		 */
 		index_insert(indexRel, values, isnull, &(new_row->t_self),
 					 trigdata->tg_relation, UNIQUE_CHECK_EXISTING,
-					 indexInfo);
+					 indexInfo,
+					 false);
 	}
 	else
 	{
diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c
index 1388be1..33b1ac3 100644
--- a/src/backend/commands/vacuumlazy.c
+++ b/src/backend/commands/vacuumlazy.c
@@ -104,6 +104,25 @@
  */
 #define PREFETCH_SIZE			((BlockNumber) 32)
 
+/*
+ * Structure to track WARM chains that can be converted into HOT chains during
+ * this run.
+ * 
+ * To reduce space requirement, we're using bitfields. But the way things are
+ * laid down, we're still wasting 1-byte per candidate chain.
+ */
+typedef struct LVRedBlueChain
+{
+	ItemPointerData	chain_tid;			/* root of the chain */
+	uint8			is_red_chain:1;		/* is the WARM chain complete red ? */
+	uint8			keep_warm_chain:1;	/* this chain can't be cleared of WARM
+										 * tuples */
+	uint8			num_blue_pointers:2;/* number of blue pointers found so
+										 * far */
+	uint8			num_red_pointers:2; /* number of red pointers found so far
+										 * in the current index */
+} LVRedBlueChain;
+
 typedef struct LVRelStats
 {
 	/* hasindex = true means two-pass strategy; false means one-pass */
@@ -121,6 +140,16 @@ typedef struct LVRelStats
 	BlockNumber pages_removed;
 	double		tuples_deleted;
 	BlockNumber nonempty_pages; /* actually, last nonempty page + 1 */
+	
+	double			num_warm_chains; /* number of warm chains seen so far */
+
+	/* List of WARM chains that can be converted into HOT chains */
+	/* NB: this list is ordered by TID of the root pointers */
+	int				num_redblue_chains;	/* current # of entries */
+	int				max_redblue_chains;	/* # slots allocated in array */
+	LVRedBlueChain *redblue_chains;	/* array of LVRedBlueChain */
+	double			num_non_convertible_warm_chains;
+
 	/* List of TIDs of tuples we intend to delete */
 	/* NB: this list is ordered by TID address */
 	int			num_dead_tuples;	/* current # of entries */
@@ -149,6 +178,7 @@ static void lazy_scan_heap(Relation onerel, int options,
 static void lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats);
 static bool lazy_check_needs_freeze(Buffer buf, bool *hastup);
 static void lazy_vacuum_index(Relation indrel,
+				  bool clear_warm,
 				  IndexBulkDeleteResult **stats,
 				  LVRelStats *vacrelstats);
 static void lazy_cleanup_index(Relation indrel,
@@ -156,6 +186,10 @@ static void lazy_cleanup_index(Relation indrel,
 				   LVRelStats *vacrelstats);
 static int lazy_vacuum_page(Relation onerel, BlockNumber blkno, Buffer buffer,
 				 int tupindex, LVRelStats *vacrelstats, Buffer *vmbuffer);
+static int lazy_warmclear_page(Relation onerel, BlockNumber blkno,
+				 Buffer buffer, int chainindex, LVRelStats *vacrelstats,
+				 Buffer *vmbuffer);
+static void lazy_reset_redblue_pointer_count(LVRelStats *vacrelstats);
 static bool should_attempt_truncation(LVRelStats *vacrelstats);
 static void lazy_truncate_heap(Relation onerel, LVRelStats *vacrelstats);
 static BlockNumber count_nondeletable_pages(Relation onerel,
@@ -163,8 +197,15 @@ 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 bool lazy_tid_reaped(ItemPointer itemptr, void *state);
+static void lazy_record_red_chain(LVRelStats *vacrelstats,
+					   ItemPointer itemptr);
+static void lazy_record_blue_chain(LVRelStats *vacrelstats,
+					   ItemPointer itemptr);
+static IndexBulkDeleteCallbackResult lazy_tid_reaped(ItemPointer itemptr, bool is_red, void *state);
+static IndexBulkDeleteCallbackResult lazy_indexvac_phase1(ItemPointer itemptr, bool is_red, void *state);
+static IndexBulkDeleteCallbackResult lazy_indexvac_phase2(ItemPointer itemptr, bool is_red, void *state);
 static int	vac_cmp_itemptr(const void *left, const void *right);
+static int vac_cmp_redblue_chain(const void *left, const void *right);
 static bool heap_page_is_all_visible(Relation rel, Buffer buf,
 					 TransactionId *visibility_cutoff_xid, bool *all_frozen);
 
@@ -683,8 +724,10 @@ 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->max_dead_tuples - vacrelstats->num_dead_tuples) < MaxHeapTuplesPerPage &&
+			vacrelstats->num_dead_tuples > 0) ||
+			((vacrelstats->max_redblue_chains - vacrelstats->num_redblue_chains) < MaxHeapTuplesPerPage &&
+			 vacrelstats->num_redblue_chains > 0))
 		{
 			const int	hvp_index[] = {
 				PROGRESS_VACUUM_PHASE,
@@ -714,6 +757,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 			/* Remove index entries */
 			for (i = 0; i < nindexes; i++)
 				lazy_vacuum_index(Irel[i],
+								  (vacrelstats->num_redblue_chains > 0),
 								  &indstats[i],
 								  vacrelstats);
 
@@ -736,6 +780,9 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 			 * valid.
 			 */
 			vacrelstats->num_dead_tuples = 0;
+			vacrelstats->num_redblue_chains = 0;
+			memset(vacrelstats->redblue_chains, 0,
+					vacrelstats->max_redblue_chains * sizeof (LVRedBlueChain));
 			vacrelstats->num_index_scans++;
 
 			/* Report that we are once again scanning the heap */
@@ -939,15 +986,33 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 				continue;
 			}
 
+			ItemPointerSet(&(tuple.t_self), blkno, offnum);
+
 			/* Redirect items mustn't be touched */
 			if (ItemIdIsRedirected(itemid))
 			{
+				HeapCheckWarmChainStatus status = heap_check_warm_chain(page,
+						&tuple.t_self, false);
+				if (HCWC_IS_WARM(status))
+				{
+					vacrelstats->num_warm_chains++;
+
+					/*
+					 * A chain which is either complete Red or Blue is a
+					 * candidate for chain conversion. Remember the chain and
+					 * its color.
+					 */
+					if (HCWC_IS_ALL_RED(status))
+						lazy_record_red_chain(vacrelstats, &tuple.t_self);
+					else if (HCWC_IS_ALL_BLUE(status))
+						lazy_record_blue_chain(vacrelstats, &tuple.t_self);
+					else
+						vacrelstats->num_non_convertible_warm_chains++;
+				}
 				hastup = true;	/* this page won't be truncatable */
 				continue;
 			}
 
-			ItemPointerSet(&(tuple.t_self), blkno, offnum);
-
 			/*
 			 * DEAD item pointers are to be vacuumed normally; but we don't
 			 * count them in tups_vacuumed, else we'd be double-counting (at
@@ -967,6 +1032,28 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 			tuple.t_len = ItemIdGetLength(itemid);
 			tuple.t_tableOid = RelationGetRelid(onerel);
 
+			if (!HeapTupleIsHeapOnly(&tuple))
+			{
+				HeapCheckWarmChainStatus status = heap_check_warm_chain(page,
+						&tuple.t_self, false);
+				if (HCWC_IS_WARM(status))
+				{
+					vacrelstats->num_warm_chains++;
+
+					/*
+					 * A chain which is either complete Red or Blue is a
+					 * candidate for chain conversion. Remember the chain and
+					 * its color.
+					 */
+					if (HCWC_IS_ALL_RED(status))
+						lazy_record_red_chain(vacrelstats, &tuple.t_self);
+					else if (HCWC_IS_ALL_BLUE(status))
+						lazy_record_blue_chain(vacrelstats, &tuple.t_self);
+					else
+						vacrelstats->num_non_convertible_warm_chains++;
+				}
+			}
+
 			tupgone = false;
 
 			switch (HeapTupleSatisfiesVacuum(&tuple, OldestXmin, buf))
@@ -1287,7 +1374,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->num_dead_tuples > 0 || vacrelstats->num_redblue_chains > 0)
 	{
 		const int	hvp_index[] = {
 			PROGRESS_VACUUM_PHASE,
@@ -1305,6 +1392,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 		/* Remove index entries */
 		for (i = 0; i < nindexes; i++)
 			lazy_vacuum_index(Irel[i],
+							  (vacrelstats->num_redblue_chains > 0),
 							  &indstats[i],
 							  vacrelstats);
 
@@ -1372,7 +1460,10 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
  *
  *		This routine marks dead tuples as unused and compacts out free
  *		space on their pages.  Pages not having dead tuples recorded from
- *		lazy_scan_heap are not visited at all.
+ *		lazy_scan_heap are not visited at all. This routine also converts
+ *		candidate WARM chains to HOT chains by clearing WARM related flags. The
+ *		candidate chains are determined by the preceeding index scans after
+ *		looking at the data collected by the first heap scan.
  *
  * Note: the reason for doing this as a second pass is we cannot remove
  * the tuples until we've removed their index entries, and we want to
@@ -1381,7 +1472,7 @@ lazy_scan_heap(Relation onerel, int options, LVRelStats *vacrelstats,
 static void
 lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 {
-	int			tupindex;
+	int			tupindex, chainindex;
 	int			npages;
 	PGRUsage	ru0;
 	Buffer		vmbuffer = InvalidBuffer;
@@ -1390,33 +1481,66 @@ lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 	npages = 0;
 
 	tupindex = 0;
-	while (tupindex < vacrelstats->num_dead_tuples)
+	chainindex = 0;
+	while (tupindex < vacrelstats->num_dead_tuples ||
+		   chainindex < vacrelstats->num_redblue_chains)
 	{
-		BlockNumber tblk;
+		BlockNumber tblk, chainblk, vacblk;
 		Buffer		buf;
 		Page		page;
 		Size		freespace;
 
 		vacuum_delay_point();
 
-		tblk = ItemPointerGetBlockNumber(&vacrelstats->dead_tuples[tupindex]);
-		buf = ReadBufferExtended(onerel, MAIN_FORKNUM, tblk, RBM_NORMAL,
+		tblk = chainblk = InvalidBlockNumber;
+		if (chainindex < vacrelstats->num_redblue_chains)
+			chainblk =
+				ItemPointerGetBlockNumber(&(vacrelstats->redblue_chains[chainindex].chain_tid));
+		
+		if (tupindex < vacrelstats->num_dead_tuples)
+			tblk = ItemPointerGetBlockNumber(&vacrelstats->dead_tuples[tupindex]);
+
+		if (tblk == InvalidBlockNumber)
+			vacblk = chainblk;
+		else if (chainblk == InvalidBlockNumber)
+			vacblk = tblk;
+		else
+			vacblk = Min(chainblk, tblk);
+
+		Assert(vacblk != InvalidBlockNumber);
+
+		buf = ReadBufferExtended(onerel, MAIN_FORKNUM, vacblk, RBM_NORMAL,
 								 vac_strategy);
-		if (!ConditionalLockBufferForCleanup(buf))
+
+
+		if (vacblk == chainblk)
+			LockBufferForCleanup(buf);
+		else if (!ConditionalLockBufferForCleanup(buf))
 		{
 			ReleaseBuffer(buf);
 			++tupindex;
 			continue;
 		}
-		tupindex = lazy_vacuum_page(onerel, tblk, buf, tupindex, vacrelstats,
-									&vmbuffer);
+
+		/* 
+		 * Convert WARM chains on this page. This should be done before
+		 * vacuuming the page to ensure that we can correctly set visibility
+		 * bits after clearing WARM chains
+		*/
+		if (vacblk == chainblk)
+			chainindex = lazy_warmclear_page(onerel, chainblk, buf, chainindex,
+					vacrelstats, &vmbuffer);
+
+		if (vacblk == tblk)
+			tupindex = lazy_vacuum_page(onerel, tblk, buf, tupindex, vacrelstats,
+					&vmbuffer);
 
 		/* Now that we've compacted the page, record its available space */
 		page = BufferGetPage(buf);
 		freespace = PageGetHeapFreeSpace(page);
 
 		UnlockReleaseBuffer(buf);
-		RecordPageWithFreeSpace(onerel, tblk, freespace);
+		RecordPageWithFreeSpace(onerel, vacblk, freespace);
 		npages++;
 	}
 
@@ -1435,6 +1559,63 @@ lazy_vacuum_heap(Relation onerel, LVRelStats *vacrelstats)
 }
 
 /*
+ *	lazy_warmclear_page() -- clear WARM flag and mark chains blue when possible
+ *
+ * Caller must hold pin and buffer cleanup lock on the buffer.
+ *
+ * chainindex is the index in vacrelstats->redblue_chains 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_warmclear_page(Relation onerel, BlockNumber blkno, Buffer buffer,
+				 int chainindex, LVRelStats *vacrelstats, Buffer *vmbuffer)
+{
+	Page			page = BufferGetPage(buffer);
+	OffsetNumber	cleared_offnums[MaxHeapTuplesPerPage];
+	int				num_cleared = 0;
+
+	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_WARMCLEARED, blkno);
+
+	START_CRIT_SECTION();
+
+	for (; chainindex < vacrelstats->num_redblue_chains ; chainindex++)
+	{
+		BlockNumber tblk;
+		LVRedBlueChain	*chain;
+
+		chain = &vacrelstats->redblue_chains[chainindex];
+
+		tblk = ItemPointerGetBlockNumber(&chain->chain_tid);
+		if (tblk != blkno)
+			break;				/* past end of tuples for this block */
+
+		/*
+		 * Since a heap page can have no more than MaxHeapTuplesPerPage
+		 * offnums and we process each offnum only once, MaxHeapTuplesPerPage
+		 * size array should be enough to hold all cleared tuples in this page.
+		 */
+		if (!chain->keep_warm_chain)
+			num_cleared += heap_clear_warm_chain(page, &chain->chain_tid,
+					cleared_offnums + num_cleared);
+	}
+
+	/*
+	 * Mark buffer dirty before we write WAL.
+	 */
+	MarkBufferDirty(buffer);
+
+	/* XLOG stuff */
+	if (RelationNeedsWAL(onerel))
+	{
+	}
+
+	END_CRIT_SECTION();
+
+	return chainindex;
+}
+
+/*
  *	lazy_vacuum_page() -- free dead tuples on a page
  *					 and repair its fragmentation.
  *
@@ -1587,6 +1768,16 @@ lazy_check_needs_freeze(Buffer buf, bool *hastup)
 	return false;
 }
 
+static void
+lazy_reset_redblue_pointer_count(LVRelStats *vacrelstats)
+{
+	int i;
+	for (i = 0; i < vacrelstats->num_redblue_chains; i++)
+	{
+		LVRedBlueChain *chain = &vacrelstats->redblue_chains[i];
+		chain->num_blue_pointers = chain->num_red_pointers = 0;
+	}
+}
 
 /*
  *	lazy_vacuum_index() -- vacuum one index relation.
@@ -1596,6 +1787,7 @@ lazy_check_needs_freeze(Buffer buf, bool *hastup)
  */
 static void
 lazy_vacuum_index(Relation indrel,
+				  bool clear_warm,
 				  IndexBulkDeleteResult **stats,
 				  LVRelStats *vacrelstats)
 {
@@ -1611,15 +1803,81 @@ lazy_vacuum_index(Relation indrel,
 	ivinfo.num_heap_tuples = vacrelstats->old_rel_tuples;
 	ivinfo.strategy = vac_strategy;
 
-	/* Do bulk deletion */
-	*stats = index_bulk_delete(&ivinfo, *stats,
-							   lazy_tid_reaped, (void *) vacrelstats);
+	/*
+	 * If told, convert WARM chains into HOT chains.
+	 *
+	 * We must have already collected candidate WARM chains i.e. chains which
+	 * has either has only Red or only Blue tuples, but not a mix of both.
+	 *
+	 * This works in two phases. In the first phase, we do a complete index
+	 * scan and collect information about index pointers to the candidate
+	 * chains, but we don't do conversion. To be precise, we count the number
+	 * of Blue and Red index pointers to each candidate chain and use that
+	 * knowledge to arrive at a decision and do the actual conversion during
+	 * the second phase (we kill known dead pointers though in this phase).
+	 *
+	 * In the second phase, for each Red chain we check if we have seen a Red
+	 * index pointer. For such chains, we kill the Blue pointer and color the
+	 * Red pointer Blue. the heap tuples are marked Blue in the second heap
+	 * scan. If we did not find any Red pointer to a Red chain, that means that
+	 * the chain is reachable from the Blue pointer (because say WARM update
+	 * did not added a new entry for this index). In that case, we do nothing.
+	 * There is a third case where we find more than one Blue pointers to a Red
+	 * chain. This can happen because of aborted vacuums. We don't handle that
+	 * case yet, but it should be possible to apply the same recheck logic and
+	 * find which of the Blue pointers is redundant and should be removed.
+	 *
+	 * For Blue chains, we just kill the Red pointer, if it exists and keep the
+	 * Blue pointer.
+	 */
+	if (clear_warm)
+	{
+		lazy_reset_redblue_pointer_count(vacrelstats);
+		*stats = index_bulk_delete(&ivinfo, *stats,
+				lazy_indexvac_phase1, (void *) vacrelstats);
+		ereport(elevel,
+				(errmsg("scanned index \"%s\" to remove %d row version, found "
+						"%0.f red pointers, %0.f blue pointers, removed "
+						"%0.f red pointers, removed %0.f blue pointers",
+						RelationGetRelationName(indrel),
+						vacrelstats->num_dead_tuples,
+						(*stats)->num_red_pointers,
+						(*stats)->num_blue_pointers,
+						(*stats)->red_pointers_removed,
+						(*stats)->blue_pointers_removed)));
+
+		(*stats)->num_red_pointers = 0;
+		(*stats)->num_blue_pointers = 0;
+		(*stats)->red_pointers_removed = 0;
+		(*stats)->blue_pointers_removed = 0;
+		(*stats)->pointers_colored = 0;
+
+		*stats = index_bulk_delete(&ivinfo, *stats,
+				lazy_indexvac_phase2, (void *) vacrelstats);
+		ereport(elevel,
+				(errmsg("scanned index \"%s\" to convert red pointers, found "
+						"%0.f red pointers, %0.f blue pointers, removed "
+						"%0.f red pointers, removed %0.f blue pointers, "
+						"colored %0.f red pointers blue",
+						RelationGetRelationName(indrel),
+						(*stats)->num_red_pointers,
+						(*stats)->num_blue_pointers,
+						(*stats)->red_pointers_removed,
+						(*stats)->blue_pointers_removed,
+						(*stats)->pointers_colored)));
+	}
+	else
+	{
+		/* Do bulk deletion */
+		*stats = index_bulk_delete(&ivinfo, *stats,
+				lazy_tid_reaped, (void *) vacrelstats);
+		ereport(elevel,
+				(errmsg("scanned index \"%s\" to remove %d row versions",
+						RelationGetRelationName(indrel),
+						vacrelstats->num_dead_tuples),
+				 errdetail("%s.", pg_rusage_show(&ru0))));
+	}
 
-	ereport(elevel,
-			(errmsg("scanned index \"%s\" to remove %d row versions",
-					RelationGetRelationName(indrel),
-					vacrelstats->num_dead_tuples),
-			 errdetail("%s.", pg_rusage_show(&ru0))));
 }
 
 /*
@@ -1993,9 +2251,11 @@ lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
 
 	if (vacrelstats->hasindex)
 	{
-		maxtuples = (vac_work_mem * 1024L) / sizeof(ItemPointerData);
+		maxtuples = (vac_work_mem * 1024L) / (sizeof(ItemPointerData) +
+				sizeof(LVRedBlueChain));
 		maxtuples = Min(maxtuples, INT_MAX);
-		maxtuples = Min(maxtuples, MaxAllocSize / sizeof(ItemPointerData));
+		maxtuples = Min(maxtuples, MaxAllocSize / (sizeof(ItemPointerData) +
+					sizeof(LVRedBlueChain)));
 
 		/* curious coding here to ensure the multiplication can't overflow */
 		if ((BlockNumber) (maxtuples / LAZY_ALLOC_TUPLES) > relblocks)
@@ -2013,6 +2273,57 @@ lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks)
 	vacrelstats->max_dead_tuples = (int) maxtuples;
 	vacrelstats->dead_tuples = (ItemPointer)
 		palloc(maxtuples * sizeof(ItemPointerData));
+
+	/* 
+	 * XXX Cheat for now and allocate the same size array for tracking blue and
+	 * red chains. maxtuples must have been already adjusted above to ensure we
+	 * don't cross vac_work_mem.
+	 */
+	vacrelstats->num_redblue_chains = 0;
+	vacrelstats->max_redblue_chains = (int) maxtuples;
+	vacrelstats->redblue_chains = (LVRedBlueChain *)
+		palloc0(maxtuples * sizeof(LVRedBlueChain));
+
+}
+
+/*
+ * lazy_record_blue_chain - remember one blue chain
+ */
+static void
+lazy_record_blue_chain(LVRelStats *vacrelstats,
+					   ItemPointer itemptr)
+{
+	/*
+	 * The array shouldn't overflow under normal behavior, but perhaps it
+	 * 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_redblue_chains < vacrelstats->max_redblue_chains)
+	{
+		vacrelstats->redblue_chains[vacrelstats->num_redblue_chains].chain_tid = *itemptr;
+		vacrelstats->redblue_chains[vacrelstats->num_redblue_chains].is_red_chain = 0;
+		vacrelstats->num_redblue_chains++;
+	}
+}
+
+/*
+ * lazy_record_red_chain - remember one red chain
+ */
+static void
+lazy_record_red_chain(LVRelStats *vacrelstats,
+					   ItemPointer itemptr)
+{
+	/*
+	 * The array shouldn't overflow under normal behavior, but perhaps it
+	 * 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_redblue_chains < vacrelstats->max_redblue_chains)
+	{
+		vacrelstats->redblue_chains[vacrelstats->num_redblue_chains].chain_tid = *itemptr;
+		vacrelstats->redblue_chains[vacrelstats->num_redblue_chains].is_red_chain = 1;
+		vacrelstats->num_redblue_chains++;
+	}
 }
 
 /*
@@ -2043,8 +2354,8 @@ lazy_record_dead_tuple(LVRelStats *vacrelstats,
  *
  *		Assumes dead_tuples array is in sorted order.
  */
-static bool
-lazy_tid_reaped(ItemPointer itemptr, void *state)
+static IndexBulkDeleteCallbackResult
+lazy_tid_reaped(ItemPointer itemptr, bool is_red, void *state)
 {
 	LVRelStats *vacrelstats = (LVRelStats *) state;
 	ItemPointer res;
@@ -2055,7 +2366,152 @@ lazy_tid_reaped(ItemPointer itemptr, void *state)
 								sizeof(ItemPointerData),
 								vac_cmp_itemptr);
 
-	return (res != NULL);
+	return (res != NULL) ? IBDCR_DELETE : IBDCR_KEEP;
+}
+
+/*
+ *	lazy_indexvac_phase1() -- run first pass of index vacuum
+ *
+ *		This has the right signature to be an IndexBulkDeleteCallback.
+ */
+static IndexBulkDeleteCallbackResult
+lazy_indexvac_phase1(ItemPointer itemptr, bool is_red, void *state)
+{
+	LVRelStats		*vacrelstats = (LVRelStats *) state;
+	ItemPointer		res;
+	LVRedBlueChain	*chain;
+
+	res = (ItemPointer) bsearch((void *) itemptr,
+								(void *) vacrelstats->dead_tuples,
+								vacrelstats->num_dead_tuples,
+								sizeof(ItemPointerData),
+								vac_cmp_itemptr);
+
+	if (res != NULL)
+		return IBDCR_DELETE;
+
+	chain = (LVRedBlueChain *) bsearch((void *) itemptr,
+								(void *) vacrelstats->redblue_chains,
+								vacrelstats->num_redblue_chains,
+								sizeof(LVRedBlueChain),
+								vac_cmp_redblue_chain);
+	if (chain != NULL)
+	{
+		if (is_red)
+			chain->num_red_pointers++;
+		else
+			chain->num_blue_pointers++;
+	}
+	return IBDCR_KEEP;
+}
+
+/*
+ *	lazy_indexvac_phase2() -- run first pass of index vacuum
+ *
+ *		This has the right signature to be an IndexBulkDeleteCallback.
+ */
+static IndexBulkDeleteCallbackResult
+lazy_indexvac_phase2(ItemPointer itemptr, bool is_red, void *state)
+{
+	LVRelStats		*vacrelstats = (LVRelStats *) state;
+	LVRedBlueChain	*chain;
+
+	chain = (LVRedBlueChain *) bsearch((void *) itemptr,
+								(void *) vacrelstats->redblue_chains,
+								vacrelstats->num_redblue_chains,
+								sizeof(LVRedBlueChain),
+								vac_cmp_redblue_chain);
+
+	if (chain != NULL && (chain->keep_warm_chain != 1))
+	{
+		if (chain->is_red_chain == 1)
+		{
+			/*
+			 * For Red chains, color Red index pointer Blue and kill the Blue
+			 * pointer if we have a Red index pointer.
+			 */
+			if (is_red)
+			{
+				Assert(chain->num_red_pointers == 1);
+				chain->keep_warm_chain = 0;
+				return IBDCR_COLOR_BLUE;
+			}
+			else
+			{
+				if (chain->num_red_pointers > 0)
+				{
+					chain->keep_warm_chain = 0;
+					return IBDCR_DELETE;
+				}
+				else if (chain->num_blue_pointers == 1)
+				{
+					chain->keep_warm_chain = 0;
+					return IBDCR_KEEP;
+				}
+			}
+		}
+		else
+		{
+			/*
+			 * For Blue chains, kill the Red pointer
+			 */
+			if (chain->num_red_pointers > 0)
+			{
+				chain->keep_warm_chain = 0;
+				return IBDCR_DELETE;
+			}
+			
+			/*
+			 * If this is the only surviving Blue pointer, keep it but convert
+			 * the chain.
+			 */
+			if (chain->num_blue_pointers == 1)
+			{
+				chain->keep_warm_chain = 0;
+				return IBDCR_KEEP;
+			}
+
+			/*
+			 * If there are more than 1 Blue pointers to this chain, we can
+			 * apply the recheck logic and kill the redudant Blue pointer and
+			 * convert the chain. But that's not yet done.
+			 */
+		}
+		chain->keep_warm_chain = 1;
+		return IBDCR_KEEP;
+	}
+	return IBDCR_KEEP;
+}
+
+/*
+ * Comparator routines for use with qsort() and bsearch(). Similar to
+ * vac_cmp_itemptr, but right hand argument is LVRedBlueChain struct pointer.
+ */
+static int
+vac_cmp_redblue_chain(const void *left, const void *right)
+{
+	BlockNumber lblk,
+				rblk;
+	OffsetNumber loff,
+				roff;
+
+	lblk = ItemPointerGetBlockNumber((ItemPointer) left);
+	rblk = ItemPointerGetBlockNumber(&((LVRedBlueChain *) right)->chain_tid);
+
+	if (lblk < rblk)
+		return -1;
+	if (lblk > rblk)
+		return 1;
+
+	loff = ItemPointerGetOffsetNumber((ItemPointer) left);
+	roff = ItemPointerGetOffsetNumber(&((LVRedBlueChain *) right)->chain_tid);
+
+	if (loff < roff)
+		return -1;
+	if (loff > roff)
+		return 1;
+
+	return 0;
 }
 
 /*
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index d62d2de..3e49a8f 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -405,7 +405,8 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 						 root_tid,		/* tid of heap or root tuple */
 						 heapRelation,	/* heap relation */
 						 checkUnique,	/* type of uniqueness check to do */
-						 indexInfo);	/* index AM may need this */
+						 indexInfo,	/* index AM may need this */
+						 (modified_attrs != NULL));	/* type of uniqueness check to do */
 
 		/*
 		 * If the index has an associated exclusion constraint, check that.
diff --git a/src/backend/utils/time/combocid.c b/src/backend/utils/time/combocid.c
index baff998..6a2e2f2 100644
--- a/src/backend/utils/time/combocid.c
+++ b/src/backend/utils/time/combocid.c
@@ -106,7 +106,7 @@ HeapTupleHeaderGetCmin(HeapTupleHeader tup)
 {
 	CommandId	cid = HeapTupleHeaderGetRawCommandId(tup);
 
-	Assert(!(tup->t_infomask & HEAP_MOVED));
+	Assert(!(HeapTupleHeaderIsMoved(tup)));
 	Assert(TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tup)));
 
 	if (tup->t_infomask & HEAP_COMBOCID)
@@ -120,7 +120,7 @@ HeapTupleHeaderGetCmax(HeapTupleHeader tup)
 {
 	CommandId	cid = HeapTupleHeaderGetRawCommandId(tup);
 
-	Assert(!(tup->t_infomask & HEAP_MOVED));
+	Assert(!(HeapTupleHeaderIsMoved(tup)));
 
 	/*
 	 * Because GetUpdateXid() performs memory allocations if xmax is a
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index 703bdce..0df5a44 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -186,7 +186,7 @@ HeapTupleSatisfiesSelf(HeapTuple htup, Snapshot snapshot, Buffer buffer)
 			return false;
 
 		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
+		if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -205,7 +205,7 @@ HeapTupleSatisfiesSelf(HeapTuple htup, Snapshot snapshot, Buffer buffer)
 			}
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -377,7 +377,7 @@ HeapTupleSatisfiesToast(HeapTuple htup, Snapshot snapshot,
 			return false;
 
 		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
+		if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -396,7 +396,7 @@ HeapTupleSatisfiesToast(HeapTuple htup, Snapshot snapshot,
 			}
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -471,7 +471,7 @@ HeapTupleSatisfiesUpdate(HeapTuple htup, CommandId curcid,
 			return HeapTupleInvisible;
 
 		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
+		if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -490,7 +490,7 @@ HeapTupleSatisfiesUpdate(HeapTuple htup, CommandId curcid,
 			}
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -753,7 +753,7 @@ HeapTupleSatisfiesDirty(HeapTuple htup, Snapshot snapshot,
 			return false;
 
 		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
+		if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -772,7 +772,7 @@ HeapTupleSatisfiesDirty(HeapTuple htup, Snapshot snapshot,
 			}
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -974,7 +974,7 @@ HeapTupleSatisfiesMVCC(HeapTuple htup, Snapshot snapshot,
 			return false;
 
 		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
+		if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -993,7 +993,7 @@ HeapTupleSatisfiesMVCC(HeapTuple htup, Snapshot snapshot,
 			}
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -1180,7 +1180,7 @@ HeapTupleSatisfiesVacuum(HeapTuple htup, TransactionId OldestXmin,
 		if (HeapTupleHeaderXminInvalid(tuple))
 			return HEAPTUPLE_DEAD;
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_OFF)
+		else if (HeapTupleHeaderIsMovedOff(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
@@ -1198,7 +1198,7 @@ HeapTupleSatisfiesVacuum(HeapTuple htup, TransactionId OldestXmin,
 						InvalidTransactionId);
 		}
 		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (HeapTupleHeaderIsMovedIn(tuple))
 		{
 			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h
index d7702e5..68859f2 100644
--- a/src/include/access/amapi.h
+++ b/src/include/access/amapi.h
@@ -75,6 +75,14 @@ typedef bool (*aminsert_function) (Relation indexRelation,
 											   Relation heapRelation,
 											   IndexUniqueCheck checkUnique,
 											   struct IndexInfo *indexInfo);
+/* insert this WARM tuple */
+typedef bool (*amwarminsert_function) (Relation indexRelation,
+											   Datum *values,
+											   bool *isnull,
+											   ItemPointer heap_tid,
+											   Relation heapRelation,
+											   IndexUniqueCheck checkUnique,
+											   struct IndexInfo *indexInfo);
 
 /* bulk delete */
 typedef IndexBulkDeleteResult *(*ambulkdelete_function) (IndexVacuumInfo *info,
@@ -203,6 +211,7 @@ typedef struct IndexAmRoutine
 	ambuild_function ambuild;
 	ambuildempty_function ambuildempty;
 	aminsert_function aminsert;
+	amwarminsert_function amwarminsert;
 	ambulkdelete_function ambulkdelete;
 	amvacuumcleanup_function amvacuumcleanup;
 	amcanreturn_function amcanreturn;	/* can be NULL */
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index f467b18..bf1e6bd 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -75,12 +75,29 @@ typedef struct IndexBulkDeleteResult
 	bool		estimated_count;	/* num_index_tuples is an estimate */
 	double		num_index_tuples;		/* tuples remaining */
 	double		tuples_removed; /* # removed during vacuum operation */
+	double		num_red_pointers;	/* # red pointers found */
+	double		num_blue_pointers;	/* # blue pointers found */
+	double		pointers_colored;	/* # red pointers colored blue */
+	double		red_pointers_removed;	/* # red pointers removed */
+	double		blue_pointers_removed;	/* # blue pointers removed */
 	BlockNumber pages_deleted;	/* # unused pages in index */
 	BlockNumber pages_free;		/* # pages available for reuse */
 } IndexBulkDeleteResult;
 
+/*
+ * IndexBulkDeleteCallback should return one of the following
+ */
+typedef enum IndexBulkDeleteCallbackResult
+{
+	IBDCR_KEEP,			/* index tuple should be preserved */
+	IBDCR_DELETE,		/* index tuple should be deleted */
+	IBDCR_COLOR_BLUE	/* index tuple should be colored blue */
+} IndexBulkDeleteCallbackResult;
+
 /* Typedef for callback function to determine if a tuple is bulk-deletable */
-typedef bool (*IndexBulkDeleteCallback) (ItemPointer itemptr, void *state);
+typedef IndexBulkDeleteCallbackResult (*IndexBulkDeleteCallback) (
+										 ItemPointer itemptr,
+										 bool is_red, void *state);
 
 /* struct definitions appear in relscan.h */
 typedef struct IndexScanDescData *IndexScanDesc;
@@ -135,7 +152,8 @@ extern bool index_insert(Relation indexRelation,
 			 ItemPointer heap_t_ctid,
 			 Relation heapRelation,
 			 IndexUniqueCheck checkUnique,
-			 struct IndexInfo *indexInfo);
+			 struct IndexInfo *indexInfo,
+			 bool warm_update);
 
 extern IndexScanDesc index_beginscan(Relation heapRelation,
 				Relation indexRelation,
diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 9412c3a..719a725 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -72,6 +72,20 @@ typedef struct HeapUpdateFailureData
 	CommandId	cmax;
 } HeapUpdateFailureData;
 
+typedef int HeapCheckWarmChainStatus;
+
+#define HCWC_BLUE_TUPLE	0x0001
+#define	HCWC_RED_TUPLE	0x0002
+#define HCWC_WARM_TUPLE	0x0004
+
+#define HCWC_IS_MIXED(status) \
+	(((status) & (HCWC_BLUE_TUPLE | HCWC_RED_TUPLE)) != 0)
+#define HCWC_IS_ALL_RED(status) \
+	(((status) & HCWC_BLUE_TUPLE) == 0)
+#define HCWC_IS_ALL_BLUE(status) \
+	(((status) & HCWC_RED_TUPLE) == 0)
+#define HCWC_IS_WARM(status) \
+	(((status) & HCWC_WARM_TUPLE) != 0)
 
 /* ----------------
  *		function prototypes for heap access method
@@ -183,6 +197,10 @@ extern void simple_heap_update(Relation relation, ItemPointer otid,
 				   bool *warm_update);
 
 extern void heap_sync(Relation relation);
+extern HeapCheckWarmChainStatus heap_check_warm_chain(Page dp,
+				   ItemPointer tid, bool stop_at_warm);
+extern int heap_clear_warm_chain(Page dp, ItemPointer tid,
+				   OffsetNumber *cleared_offnums);
 
 /* in heap/pruneheap.c */
 extern void heap_page_prune_opt(Relation relation, Buffer buffer);
diff --git a/src/include/access/htup_details.h b/src/include/access/htup_details.h
index ddbdbcd..45fe12c 100644
--- a/src/include/access/htup_details.h
+++ b/src/include/access/htup_details.h
@@ -201,6 +201,21 @@ struct HeapTupleHeaderData
 										 * upgrade support */
 #define HEAP_MOVED (HEAP_MOVED_OFF | HEAP_MOVED_IN)
 
+/*
+ * A WARM chain usually consists of two parts. Each of these parts are HOT
+ * chains in themselves i.e. all indexed columns has the same value, but a WARM
+ * update separates these parts. We call these two parts as Blue chain and Red
+ * chain. We need a mechanism to identify which part a tuple belongs to. We
+ * can't just look at if it's a HeapTupleHeaderIsHeapWarmTuple() because during
+ * WARM update, both old and new tuples are marked as WARM tuples.
+ * 
+ * We need another infomask bit for this. But we use the same infomask bit that
+ * was earlier used for by old-style VACUUM FULL. This is safe because
+ * HEAP_WARM_TUPLE flag will always be set along with HEAP_WARM_RED. So if
+ * HEAP_WARM_TUPLE and HEAP_WARM_RED is set then we know that it's referring to
+ * red part of the WARM chain.
+ */
+#define HEAP_WARM_RED			0x4000
 #define HEAP_XACT_MASK			0xFFF0	/* visibility-related bits */
 
 /*
@@ -397,7 +412,7 @@ struct HeapTupleHeaderData
 /* SetCmin is reasonably simple since we never need a combo CID */
 #define HeapTupleHeaderSetCmin(tup, cid) \
 do { \
-	Assert(!((tup)->t_infomask & HEAP_MOVED)); \
+	Assert(!HeapTupleHeaderIsMoved(tup)); \
 	(tup)->t_choice.t_heap.t_field3.t_cid = (cid); \
 	(tup)->t_infomask &= ~HEAP_COMBOCID; \
 } while (0)
@@ -405,7 +420,7 @@ do { \
 /* SetCmax must be used after HeapTupleHeaderAdjustCmax; see combocid.c */
 #define HeapTupleHeaderSetCmax(tup, cid, iscombo) \
 do { \
-	Assert(!((tup)->t_infomask & HEAP_MOVED)); \
+	Assert(!HeapTupleHeaderIsMoved(tup)); \
 	(tup)->t_choice.t_heap.t_field3.t_cid = (cid); \
 	if (iscombo) \
 		(tup)->t_infomask |= HEAP_COMBOCID; \
@@ -415,7 +430,7 @@ do { \
 
 #define HeapTupleHeaderGetXvac(tup) \
 ( \
-	((tup)->t_infomask & HEAP_MOVED) ? \
+	HeapTupleHeaderIsMoved(tup) ? \
 		(tup)->t_choice.t_heap.t_field3.t_xvac \
 	: \
 		InvalidTransactionId \
@@ -423,7 +438,7 @@ do { \
 
 #define HeapTupleHeaderSetXvac(tup, xid) \
 do { \
-	Assert((tup)->t_infomask & HEAP_MOVED); \
+	Assert(HeapTupleHeaderIsMoved(tup)); \
 	(tup)->t_choice.t_heap.t_field3.t_xvac = (xid); \
 } while (0)
 
@@ -651,6 +666,58 @@ do { \
 )
 
 /*
+ * Macros to check if tuple is a moved-off/in tuple by VACUUM FULL in from
+ * pre-9.0 era. Such tuple must not have HEAP_WARM_TUPLE flag set.
+ *
+ * Beware of multiple evaluations of the argument.
+ */ 
+#define HeapTupleHeaderIsMovedOff(tuple) \
+( \
+ 	!HeapTupleHeaderIsHeapWarmTuple((tuple)) && \
+  	((tuple)->t_infomask & HEAP_MOVED_OFF) \
+)
+
+#define HeapTupleHeaderIsMovedIn(tuple) \
+( \
+ 	!HeapTupleHeaderIsHeapWarmTuple((tuple)) && \
+  	((tuple)->t_infomask & HEAP_MOVED_IN) \
+)
+
+#define HeapTupleHeaderIsMoved(tuple) \
+( \
+ 	!HeapTupleHeaderIsHeapWarmTuple((tuple)) && \
+  	((tuple)->t_infomask & HEAP_MOVED) \
+)
+
+/*
+ * Check if tuple belongs to the Red part of the WARM chain.
+ *
+ * Beware of multiple evaluations of the argument.
+ */
+#define HeapTupleHeaderIsWarmRed(tuple) \
+( \
+	HeapTupleHeaderIsHeapWarmTuple(tuple) && \
+    (((tuple)->t_infomask & HEAP_WARM_RED) != 0) \
+)
+
+/*
+ * Mark tuple as a member of the Red chain. Must only be done on a tuple which
+ * is already marked a WARM-tuple.
+ *
+ * Beware of multiple evaluations of the argument.
+ */
+#define HeapTupleHeaderSetWarmRed(tuple) \
+( \
+  	AssertMacro(HeapTupleHeaderIsHeapWarmTuple(tuple)), \
+	(tuple)->t_infomask |= HEAP_WARM_RED \
+)
+
+#define HeapTupleHeaderClearWarmRed(tuple) \
+( \
+	(tuple)->t_infomask &= ~HEAP_WARM_RED \
+)
+
+/*
  * BITMAPLEN(NATTS) -
  *		Computes size of null bitmap given number of data columns.
  */
@@ -810,6 +877,15 @@ struct MinimalTupleData
 #define HeapTupleClearHeapWarmTuple(tuple) \
 		HeapTupleHeaderClearHeapWarmTuple((tuple)->t_data)
 
+#define HeapTupleIsHeapWarmTupleRed(tuple) \
+		HeapTupleHeaderIsWarmRed((tuple)->t_data)
+
+#define HeapTupleSetHeapWarmTupleRed(tuple) \
+		HeapTupleHeaderSetWarmRed((tuple)->t_data)
+
+#define HeapTupleClearHeapWarmTupleRed(tuple) \
+		HeapTupleHeaderClearWarmRed((tuple)->t_data)
+
 #define HeapTupleGetOid(tuple) \
 		HeapTupleHeaderGetOid((tuple)->t_data)
 
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 08d056d..40be895 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -427,6 +427,9 @@ typedef BTScanOpaqueData *BTScanOpaque;
 #define SK_BT_DESC			(INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)
 #define SK_BT_NULLS_FIRST	(INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)
 
+/* This index tuple points to the red part of the WARM chain */
+#define INDEX_RED_CHAIN	0x2000
+
 /*
  * external entry points for btree, in nbtree.c
  */
@@ -437,6 +440,10 @@ extern bool btinsert(Relation rel, Datum *values, bool *isnull,
 		 ItemPointer ht_ctid, Relation heapRel,
 		 IndexUniqueCheck checkUnique,
 		 struct IndexInfo *indexInfo);
+extern bool btwarminsert(Relation rel, Datum *values, bool *isnull,
+		 ItemPointer ht_ctid, Relation heapRel,
+		 IndexUniqueCheck checkUnique,
+		 struct IndexInfo *indexInfo);
 extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
 extern Size btestimateparallelscan(void);
 extern void btinitparallelscan(void *target);
diff --git a/src/include/commands/progress.h b/src/include/commands/progress.h
index 9472ecc..b355b61 100644
--- a/src/include/commands/progress.h
+++ b/src/include/commands/progress.h
@@ -25,6 +25,7 @@
 #define PROGRESS_VACUUM_NUM_INDEX_VACUUMS		4
 #define PROGRESS_VACUUM_MAX_DEAD_TUPLES			5
 #define PROGRESS_VACUUM_NUM_DEAD_TUPLES			6
+#define PROGRESS_VACUUM_HEAP_BLKS_WARMCLEARED	7
 
 /* Phases of vacuum (as advertised via PROGRESS_VACUUM_PHASE) */
 #define PROGRESS_VACUUM_PHASE_SCAN_HEAP			1
diff --git a/src/test/regress/expected/warm.out b/src/test/regress/expected/warm.out
index 0aa3bb7..6391891 100644
--- a/src/test/regress/expected/warm.out
+++ b/src/test/regress/expected/warm.out
@@ -26,12 +26,12 @@ SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 -- Even when seqscan is disabled and indexscan is forced
 SET enable_seqscan = false;
-EXPLAIN SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
-                                 QUERY PLAN                                 
-----------------------------------------------------------------------------
- Bitmap Heap Scan on updtst_tab1  (cost=4.45..47.23 rows=22 width=72)
+EXPLAIN (costs off) SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
+               QUERY PLAN                
+-----------------------------------------
+ Bitmap Heap Scan on updtst_tab1
    Recheck Cond: (b = 140001)
-   ->  Bitmap Index Scan on updtst_indx1  (cost=0.00..4.45 rows=22 width=0)
+   ->  Bitmap Index Scan on updtst_indx1
          Index Cond: (b = 140001)
 (4 rows)
 
@@ -42,12 +42,12 @@ SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
 (1 row)
 
 -- Check if index only scan works correctly
-EXPLAIN SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
-                                 QUERY PLAN                                 
-----------------------------------------------------------------------------
- Bitmap Heap Scan on updtst_tab1  (cost=4.45..47.23 rows=22 width=4)
+EXPLAIN (costs off) SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
+               QUERY PLAN                
+-----------------------------------------
+ Bitmap Heap Scan on updtst_tab1
    Recheck Cond: (b = 140001)
-   ->  Bitmap Index Scan on updtst_indx1  (cost=0.00..4.45 rows=22 width=0)
+   ->  Bitmap Index Scan on updtst_indx1
          Index Cond: (b = 140001)
 (4 rows)
 
@@ -59,10 +59,10 @@ SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 -- Table must be vacuumed to force index-only scan
 VACUUM updtst_tab1;
-EXPLAIN SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
-                                      QUERY PLAN                                      
---------------------------------------------------------------------------------------
- Index Only Scan using updtst_indx1 on updtst_tab1  (cost=0.29..9.16 rows=50 width=4)
+EXPLAIN (costs off) SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
+                    QUERY PLAN                     
+---------------------------------------------------
+ Index Only Scan using updtst_indx1 on updtst_tab1
    Index Cond: (b = 140001)
 (2 rows)
 
@@ -99,12 +99,12 @@ SELECT * FROM updtst_tab2 WHERE c = 'foo6';
  1 | 701 | foo6 | bar
 (1 row)
 
-EXPLAIN SELECT * FROM updtst_tab2 WHERE b = 701;
-                                QUERY PLAN                                 
----------------------------------------------------------------------------
- Bitmap Heap Scan on updtst_tab2  (cost=4.18..12.64 rows=4 width=72)
+EXPLAIN (costs off) SELECT * FROM updtst_tab2 WHERE b = 701;
+               QUERY PLAN                
+-----------------------------------------
+ Bitmap Heap Scan on updtst_tab2
    Recheck Cond: (b = 701)
-   ->  Bitmap Index Scan on updtst_indx2  (cost=0.00..4.18 rows=4 width=0)
+   ->  Bitmap Index Scan on updtst_indx2
          Index Cond: (b = 701)
 (4 rows)
 
@@ -115,12 +115,12 @@ SELECT * FROM updtst_tab2 WHERE a = 1;
 (1 row)
 
 SET enable_seqscan = false;
-EXPLAIN SELECT * FROM updtst_tab2 WHERE b = 701;
-                                QUERY PLAN                                 
----------------------------------------------------------------------------
- Bitmap Heap Scan on updtst_tab2  (cost=4.18..12.64 rows=4 width=72)
+EXPLAIN (costs off) SELECT * FROM updtst_tab2 WHERE b = 701;
+               QUERY PLAN                
+-----------------------------------------
+ Bitmap Heap Scan on updtst_tab2
    Recheck Cond: (b = 701)
-   ->  Bitmap Index Scan on updtst_indx2  (cost=0.00..4.18 rows=4 width=0)
+   ->  Bitmap Index Scan on updtst_indx2
          Index Cond: (b = 701)
 (4 rows)
 
@@ -131,10 +131,10 @@ SELECT * FROM updtst_tab2 WHERE b = 701;
 (1 row)
 
 VACUUM updtst_tab2;
-EXPLAIN SELECT b FROM updtst_tab2 WHERE b = 701;
-                                     QUERY PLAN                                      
--------------------------------------------------------------------------------------
- Index Only Scan using updtst_indx2 on updtst_tab2  (cost=0.14..4.16 rows=1 width=4)
+EXPLAIN (costs off) SELECT b FROM updtst_tab2 WHERE b = 701;
+                    QUERY PLAN                     
+---------------------------------------------------
+ Index Only Scan using updtst_indx2 on updtst_tab2
    Index Cond: (b = 701)
 (2 rows)
 
@@ -212,10 +212,10 @@ SELECT * FROM updtst_tab3 WHERE b = 1421;
 (1 row)
 
 VACUUM updtst_tab3;
-EXPLAIN SELECT b FROM updtst_tab3 WHERE b = 701;
-                        QUERY PLAN                         
------------------------------------------------------------
- Seq Scan on updtst_tab3  (cost=0.00..2.25 rows=1 width=4)
+EXPLAIN (costs off) SELECT b FROM updtst_tab3 WHERE b = 701;
+       QUERY PLAN        
+-------------------------
+ Seq Scan on updtst_tab3
    Filter: (b = 701)
 (2 rows)
 
@@ -293,10 +293,10 @@ SELECT * FROM updtst_tab3 WHERE b = 1422;
 (1 row)
 
 VACUUM updtst_tab3;
-EXPLAIN SELECT b FROM updtst_tab3 WHERE b = 702;
-                                     QUERY PLAN                                      
--------------------------------------------------------------------------------------
- Index Only Scan using updtst_indx3 on updtst_tab3  (cost=0.14..8.16 rows=1 width=4)
+EXPLAIN (costs off) SELECT b FROM updtst_tab3 WHERE b = 702;
+                    QUERY PLAN                     
+---------------------------------------------------
+ Index Only Scan using updtst_indx3 on updtst_tab3
    Index Cond: (b = 702)
 (2 rows)
 
diff --git a/src/test/regress/sql/warm.sql b/src/test/regress/sql/warm.sql
index b73c278..f31127c 100644
--- a/src/test/regress/sql/warm.sql
+++ b/src/test/regress/sql/warm.sql
@@ -23,16 +23,16 @@ SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 -- Even when seqscan is disabled and indexscan is forced
 SET enable_seqscan = false;
-EXPLAIN SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
+EXPLAIN (costs off) SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
 SELECT * FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 -- Check if index only scan works correctly
-EXPLAIN SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
+EXPLAIN (costs off) SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
 SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 -- Table must be vacuumed to force index-only scan
 VACUUM updtst_tab1;
-EXPLAIN SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
+EXPLAIN (costs off) SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
 SELECT b FROM updtst_tab1 WHERE b = 70001 + 70000;
 
 SET enable_seqscan = true;
@@ -58,15 +58,15 @@ UPDATE updtst_tab2 SET c = 'foo6'  WHERE a = 1;
 SELECT count(*) FROM updtst_tab2 WHERE c = 'foo';
 SELECT * FROM updtst_tab2 WHERE c = 'foo6';
 
-EXPLAIN SELECT * FROM updtst_tab2 WHERE b = 701;
+EXPLAIN (costs off) SELECT * FROM updtst_tab2 WHERE b = 701;
 SELECT * FROM updtst_tab2 WHERE a = 1;
 
 SET enable_seqscan = false;
-EXPLAIN SELECT * FROM updtst_tab2 WHERE b = 701;
+EXPLAIN (costs off) SELECT * FROM updtst_tab2 WHERE b = 701;
 SELECT * FROM updtst_tab2 WHERE b = 701;
 
 VACUUM updtst_tab2;
-EXPLAIN SELECT b FROM updtst_tab2 WHERE b = 701;
+EXPLAIN (costs off) SELECT b FROM updtst_tab2 WHERE b = 701;
 SELECT b FROM updtst_tab2 WHERE b = 701;
 
 SET enable_seqscan = true;
@@ -109,7 +109,7 @@ SELECT * FROM updtst_tab3 WHERE b = 701;
 SELECT * FROM updtst_tab3 WHERE b = 1421;
 
 VACUUM updtst_tab3;
-EXPLAIN SELECT b FROM updtst_tab3 WHERE b = 701;
+EXPLAIN (costs off) SELECT b FROM updtst_tab3 WHERE b = 701;
 SELECT b FROM updtst_tab3 WHERE b = 701;
 SELECT b FROM updtst_tab3 WHERE b = 1421;
 
@@ -146,7 +146,7 @@ SELECT * FROM updtst_tab3 WHERE b = 702;
 SELECT * FROM updtst_tab3 WHERE b = 1422;
 
 VACUUM updtst_tab3;
-EXPLAIN SELECT b FROM updtst_tab3 WHERE b = 702;
+EXPLAIN (costs off) SELECT b FROM updtst_tab3 WHERE b = 702;
 SELECT b FROM updtst_tab3 WHERE b = 702;
 SELECT b FROM updtst_tab3 WHERE b = 1422;