diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index 3ef0112..ddb6ee5 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -80,6 +80,8 @@
 /* number of active words for a lossy chunk: */
 #define WORDS_PER_CHUNK  ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
 
+#define MAXOFFSETS		10
+
 /*
  * The hashtable entries are represented by this data structure.  For
  * an exact page, blockno is the page number and bit k of the bitmap
@@ -99,9 +101,17 @@ typedef struct PagetableEntry
 	BlockNumber blockno;		/* page number (hashtable key) */
 	bool		ischunk;		/* T = lossy storage, F = exact */
 	bool		recheck;		/* should the tuples be rechecked? */
-	bitmapword	words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
+	int8		noffsets;		/* number of offsets in boffsets, or -1 if bitmap */
+	union
+	{
+		bitmapword	bwords[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
+		OffsetNumber boffsets[MAXOFFSETS];
+	} wo;
 } PagetableEntry;
 
+#define words wo.bwords
+#define boffsets wo.boffsets
+
 /*
  * dynahash.c is optimized for relatively large, long-lived hash tables.
  * This is not ideal for TIDBitMap, particularly when we are using a bitmap
@@ -244,6 +254,27 @@ tbm_create_pagetable(TIDBitmap *tbm)
 	tbm->status = TBM_HASH;
 }
 
+static void
+tbm_page_to_bitmap(PagetableEntry *page)
+{
+	int i;
+	OffsetNumber offsets[MAXOFFSETS];
+	int noffsets;
+
+	noffsets = page->noffsets;
+	memcpy(offsets, page->boffsets, sizeof(OffsetNumber) * noffsets);
+	memset(page->boffsets, 0, sizeof(page->boffsets));
+	for (i = 0; i < noffsets; i++)
+	{
+		OffsetNumber off = offsets[i];
+		int wordnum = WORDNUM(off - 1);
+		int bitnum = BITNUM(off - 1);
+		page->words[wordnum] |= ((bitmapword) 1 << bitnum);
+	}
+
+	page->noffsets = -1;
+}
+
 /*
  * tbm_free - free a TIDBitmap
  */
@@ -270,13 +301,14 @@ tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids,
 			   bool recheck)
 {
 	int			i;
+	BlockNumber prevblk = InvalidBlockNumber;
+	PagetableEntry *page = NULL;
 
 	Assert(!tbm->iterating);
 	for (i = 0; i < ntids; i++)
 	{
 		BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
 		OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
-		PagetableEntry *page;
 		int			wordnum,
 					bitnum;
 
@@ -287,20 +319,52 @@ tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids,
 		if (tbm_page_is_lossy(tbm, blk))
 			continue;			/* whole page is already marked */
 
-		page = tbm_get_pageentry(tbm, blk);
+		if (prevblk != blk)
+			page = tbm_get_pageentry(tbm, blk);
 
 		if (page->ischunk)
 		{
 			/* The page is a lossy chunk header, set bit for itself */
 			wordnum = bitnum = 0;
+			page->words[0] |= 1;
 		}
 		else
 		{
 			/* Page is exact, so set bit for individual tuple */
-			wordnum = WORDNUM(off - 1);
-			bitnum = BITNUM(off - 1);
+			if (page->noffsets >= MAXOFFSETS)
+			{
+				/* switch to bitmap */
+				tbm_page_to_bitmap(page);
+			}
+			if (page->noffsets >= 0)
+			{
+				int j;
+				/* Find the right place for the new offset */
+				for (j = 0; j < page->noffsets; j++)
+				{
+					if (page->boffsets[j] == off)
+						return;
+					if (page->boffsets[j] < off)
+					{
+						for (; j < page->noffsets; j++)
+						{
+							OffsetNumber swp = off;
+							off = page->boffsets[j];
+							page->boffsets[j] = swp;
+						}
+						page->boffsets[j] = off;
+						page->noffsets++;
+						break;
+					}
+				}
+			}
+			else
+			{
+				wordnum = WORDNUM(off - 1);
+				bitnum = BITNUM(off - 1);
+				page->words[wordnum] |= ((bitmapword) 1 << bitnum);
+			}
 		}
-		page->words[wordnum] |= ((bitmapword) 1 << bitnum);
 		page->recheck |= recheck;
 
 		if (tbm->nentries > tbm->maxentries)
@@ -711,21 +775,29 @@ tbm_iterate(TBMIterator *iterator)
 			page = tbm->spages[iterator->spageptr];
 
 		/* scan bitmap to extract individual offset numbers */
-		ntuples = 0;
-		for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
+		if (page->noffsets >= 0)
 		{
-			bitmapword	w = page->words[wordnum];
-
-			if (w != 0)
+			ntuples = page->noffsets;
+			memcpy(output->offsets, page->boffsets, sizeof(OffsetNumber) * page->noffsets);
+		}
+		else
+		{
+			ntuples = 0;
+			for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
 			{
-				int			off = wordnum * BITS_PER_BITMAPWORD + 1;
+				bitmapword	w = page->words[wordnum];
 
-				while (w != 0)
+				if (w != 0)
 				{
-					if (w & 1)
-						output->offsets[ntuples++] = (OffsetNumber) off;
-					off++;
-					w >>= 1;
+					int			off = wordnum * BITS_PER_BITMAPWORD + 1;
+
+					while (w != 0)
+					{
+						if (w & 1)
+							output->offsets[ntuples++] = (OffsetNumber) off;
+						off++;
+						w >>= 1;
+					}
 				}
 			}
 		}