v30-0001-Delay-extraction-of-TIDBitmap-per-page-offsets.patch

From 92eacd13d60c67eee9812171256026191d2356f6 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 19 Feb 2025 11:32:22 -0500
Subject: [PATCH v30 1/4] Delay extraction of TIDBitmap per page offsets

Each time the TIDBitmap iterator was advanced to an exact page (in
tbm_private|shared_iterate()), it extracted the tuple offsets into an
array in the TBMIterateResult for convenience.

As long as the TBMIterateResult contains a reference to the
PagetableEntry, this can be done later by the caller when using the
array of offsets. Doing so allows us to wait on allocating the memory
for the offsets until later, which helps reduce the memory footprint of
having multiple TBMIterateResults allocated at the same time. Future
commits will make bitmap heap scan use the read stream API. This
requires a TBMIterateResult per issued block.

The benefit in current code is that we no longer extract offsets for
prefetched blocks. Those were never used, so the overhead of extracting
and storing them was unnecessary.

Suggested-by: Thomas Munro
Discussion: https://postgr.es/m/CA%2BhUKGLHbKP3jwJ6_%2BhnGi37Pw3BD5j2amjV3oSk7j-KyCnY7Q%40mail.gmail.com
---
 src/backend/access/gin/ginget.c          | 11 +++++--
 src/backend/access/gin/ginscan.c         |  2 ++
 src/backend/access/heap/heapam_handler.c |  6 +++-
 src/backend/nodes/tidbitmap.c            | 37 ++++++++++--------------
 src/include/access/gin_private.h         |  2 ++
 src/include/nodes/tidbitmap.h            |  4 ++-
 6 files changed, 36 insertions(+), 26 deletions(-)

diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 63dd1f3679f..438fa936f11 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -845,6 +845,11 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
 					break;
 				}
 
+				/* If page is not lossy, extract tuple offsets */
+				if (entry->matchResult->ntuples > -1)
+					tbm_extract_page_tuple(entry->matchResult,
+										   entry->offsets);
+
 				/*
 				 * Reset counter to the beginning of entry->matchResult. Note:
 				 * entry->offset is still greater than matchResult->ntuples if
@@ -884,20 +889,20 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
 				 * page. If that's > advancePast, so are all the other
 				 * offsets, so just go back to the top to get the next page.
 				 */
-				if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
+				if (entry->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
 				{
 					entry->offset = entry->matchResult->ntuples;
 					continue;
 				}
 
 				/* Otherwise scan to find the first item > advancePast */
-				while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
+				while (entry->offsets[entry->offset] <= advancePastOff)
 					entry->offset++;
 			}
 
 			ItemPointerSet(&entry->curItem,
 						   entry->matchResult->blockno,
-						   entry->matchResult->offsets[entry->offset]);
+						   entry->offsets[entry->offset]);
 			entry->offset++;
 
 			/* Done unless we need to reduce the result */
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 7d1e6615260..ceca72d7123 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -107,6 +107,8 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
 	scanEntry->matchBitmap = NULL;
 	scanEntry->matchIterator = NULL;
 	scanEntry->matchResult = NULL;
+	memset(scanEntry->offsets, 0,
+		   sizeof(OffsetNumber) * MaxHeapTuplesPerPage);
 	scanEntry->list = NULL;
 	scanEntry->nlist = 0;
 	scanEntry->offset = InvalidOffsetNumber;
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index c0bec014154..45918bf1eb6 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -2127,6 +2127,7 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
 	Snapshot	snapshot;
 	int			ntup;
 	TBMIterateResult *tbmres;
+	OffsetNumber offsets[MaxHeapTuplesPerPage] = {0};
 
 	Assert(scan->rs_flags & SO_TYPE_BITMAPSCAN);
 
@@ -2145,6 +2146,9 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
 		if (tbmres == NULL)
 			return false;
 
+		if (tbmres->ntuples > -1)
+			tbm_extract_page_tuple(tbmres, offsets);
+
 		/*
 		 * Ignore any claimed entries past what we think is the end of the
 		 * relation. It may have been extended after the start of our scan (we
@@ -2218,7 +2222,7 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
 
 		for (curslot = 0; curslot < tbmres->ntuples; curslot++)
 		{
-			OffsetNumber offnum = tbmres->offsets[curslot];
+			OffsetNumber offnum = offsets[curslot];
 			ItemPointerData tid;
 			HeapTupleData heapTuple;
 
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index 66b3c387d53..052afd3e4c3 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -181,7 +181,7 @@ struct TBMPrivateIterator
 	int			spageptr;		/* next spages index */
 	int			schunkptr;		/* next schunks index */
 	int			schunkbit;		/* next bit to check in current schunk */
-	TBMIterateResult output;	/* MUST BE LAST (because variable-size) */
+	TBMIterateResult output;
 };
 
 /*
@@ -222,7 +222,7 @@ struct TBMSharedIterator
 	PTEntryArray *ptbase;		/* pagetable element array */
 	PTIterationArray *ptpages;	/* sorted exact page index list */
 	PTIterationArray *ptchunks; /* sorted lossy page index list */
-	TBMIterateResult output;	/* MUST BE LAST (because variable-size) */
+	TBMIterateResult output;
 };
 
 /* Local function prototypes */
@@ -696,9 +696,7 @@ tbm_begin_private_iterate(TIDBitmap *tbm)
 	 * Create the TBMPrivateIterator struct, with enough trailing space to
 	 * serve the needs of the TBMIterateResult sub-struct.
 	 */
-	iterator = (TBMPrivateIterator *) palloc(sizeof(TBMPrivateIterator) +
-											 MAX_TUPLES_PER_PAGE *
-											 sizeof(OffsetNumber));
+	iterator = (TBMPrivateIterator *) palloc(sizeof(TBMPrivateIterator));
 	iterator->tbm = tbm;
 
 	/*
@@ -905,12 +903,12 @@ tbm_prepare_shared_iterate(TIDBitmap *tbm)
 
 /*
  * tbm_extract_page_tuple - extract the tuple offsets from a page
- *
- * The extracted offsets are stored into TBMIterateResult.
  */
-static inline int
-tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
+void
+tbm_extract_page_tuple(TBMIterateResult *iteritem,
+					   OffsetNumber *offsets)
 {
+	PagetableEntry *page = iteritem->internal_page;
 	int			wordnum;
 	int			ntuples = 0;
 
@@ -925,14 +923,14 @@ tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
 			while (w != 0)
 			{
 				if (w & 1)
-					output->offsets[ntuples++] = (OffsetNumber) off;
+					offsets[ntuples++] = (OffsetNumber) off;
 				off++;
 				w >>= 1;
 			}
 		}
 	}
 
-	return ntuples;
+	iteritem->ntuples = ntuples;
 }
 
 /*
@@ -1021,7 +1019,6 @@ tbm_private_iterate(TBMPrivateIterator *iterator)
 	if (iterator->spageptr < tbm->npages)
 	{
 		PagetableEntry *page;
-		int			ntuples;
 
 		/* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
 		if (tbm->status == TBM_ONE_PAGE)
@@ -1029,10 +1026,10 @@ tbm_private_iterate(TBMPrivateIterator *iterator)
 		else
 			page = tbm->spages[iterator->spageptr];
 
-		/* scan bitmap to extract individual offset numbers */
-		ntuples = tbm_extract_page_tuple(page, output);
+		output->internal_page = page;
+		/* ntuples will be calculated later */
+		output->ntuples = 0;
 		output->blockno = page->blockno;
-		output->ntuples = ntuples;
 		output->recheck = page->recheck;
 		iterator->spageptr++;
 		return output;
@@ -1116,12 +1113,11 @@ tbm_shared_iterate(TBMSharedIterator *iterator)
 	if (istate->spageptr < istate->npages)
 	{
 		PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
-		int			ntuples;
 
-		/* scan bitmap to extract individual offset numbers */
-		ntuples = tbm_extract_page_tuple(page, output);
+		output->internal_page = page;
+		/* ntuples will be calculated later */
+		output->ntuples = 0;
 		output->blockno = page->blockno;
-		output->ntuples = ntuples;
 		output->recheck = page->recheck;
 		istate->spageptr++;
 
@@ -1468,8 +1464,7 @@ tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
 	 * Create the TBMSharedIterator struct, with enough trailing space to
 	 * serve the needs of the TBMIterateResult sub-struct.
 	 */
-	iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
-											 MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
+	iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator));
 
 	istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
 
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index dcd1ae3fc34..f889e4f7d16 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -13,6 +13,7 @@
 #include "access/amapi.h"
 #include "access/gin.h"
 #include "access/ginblock.h"
+#include "access/htup_details.h"
 #include "access/itup.h"
 #include "common/int.h"
 #include "catalog/pg_am_d.h"
@@ -354,6 +355,7 @@ typedef struct GinScanEntryData
 	TIDBitmap  *matchBitmap;
 	TBMPrivateIterator *matchIterator;
 	TBMIterateResult *matchResult;
+	OffsetNumber offsets[MaxHeapTuplesPerPage];
 
 	/* used for Posting list and one page in Posting tree */
 	ItemPointerData *list;
diff --git a/src/include/nodes/tidbitmap.h b/src/include/nodes/tidbitmap.h
index a6ffeac90be..1a381595abe 100644
--- a/src/include/nodes/tidbitmap.h
+++ b/src/include/nodes/tidbitmap.h
@@ -56,12 +56,14 @@ typedef struct TBMIterateResult
 	BlockNumber blockno;		/* page number containing tuples */
 	int			ntuples;		/* -1 indicates lossy result */
 	bool		recheck;		/* should the tuples be rechecked? */
+	void	   *internal_page;	/* pointer to the PagetableEntry */
 	/* Note: recheck is always true if ntuples < 0 */
-	OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER];
 } TBMIterateResult;
 
 /* function prototypes in nodes/tidbitmap.c */
 
+extern void tbm_extract_page_tuple(TBMIterateResult *iteritem,
+								   OffsetNumber *offsets);
 extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa);
 extern void tbm_free(TIDBitmap *tbm);
 extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp);
-- 
2.34.1