From c0bc497f50318c8e31ccdf0c2a9186ffc736abeb Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Fri, 10 Feb 2023 19:56:01 +0700
Subject: [PATCH v2699 1/3] Miscellaneous optimizations for tidstore_add_tids()

- remove palloc0; it's expensive for lengths not known at compile-time
- optimize for case with only one key per heap block
- make some intializations const and branch-free
- when writing to the radix tree, stop at the last non-zero bitmap
---
 src/backend/access/common/tidstore.c | 56 ++++++++++++++++++----------
 1 file changed, 36 insertions(+), 20 deletions(-)

diff --git a/src/backend/access/common/tidstore.c b/src/backend/access/common/tidstore.c
index 4c72673ce9..5d24680737 100644
--- a/src/backend/access/common/tidstore.c
+++ b/src/backend/access/common/tidstore.c
@@ -368,51 +368,67 @@ tidstore_add_tids(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 				  int num_offsets)
 {
 	ItemPointerData tid;
-	uint64	key_base;
 	uint64	*values;
-	int	nkeys;
+	uint64	key;
+	uint64	prev_key;
+	uint64	off_bitmap = 0;
+	int idx;
+	const uint64 key_base = ((uint64) blkno) << ts->control->offset_key_nbits;
+	const int nkeys = UINT64CONST(1) << ts->control->offset_key_nbits;
 
 	Assert(!TidStoreIsShared(ts) || ts->control->magic == TIDSTORE_MAGIC);
 
-	if (ts->control->encode_tids)
-	{
-		key_base = ((uint64) blkno) << ts->control->offset_key_nbits;
-		nkeys = UINT64CONST(1) << ts->control->offset_key_nbits;
-	}
-	else
-	{
-		key_base = (uint64) blkno;
-		nkeys = 1;
-	}
-	values = palloc0(sizeof(uint64) * nkeys);
+	values = palloc(sizeof(uint64) * nkeys);
+	key = prev_key = key_base;
 
 	ItemPointerSetBlockNumber(&tid, blkno);
+
 	for (int i = 0; i < num_offsets; i++)
 	{
-		uint64	key;
 		uint32	off;
-		int idx;
 
 		ItemPointerSetOffsetNumber(&tid, offsets[i]);
 
 		/* encode the tid to key and val */
 		key = tid_to_key_off(ts, &tid, &off);
 
-		idx = key - key_base;
-		Assert(idx >= 0 && idx < nkeys);
+		/* make sure we scanned the line pointer array in order */
+		Assert(key >= prev_key);
 
-		values[idx] |= UINT64CONST(1) << off;
+		if (key > prev_key)
+		{
+			idx = prev_key - key_base;
+			Assert(idx >= 0 && idx < nkeys);
+
+			/* write out offset bitmap for this key */
+			values[idx] = off_bitmap;
+
+			/* zero out any gaps up to the current key */
+			for (int empty_idx = idx + 1; empty_idx < key - key_base; empty_idx++)
+				values[empty_idx] = 0;
+
+			/* reset for current key -- the current offset will be handled below */
+			off_bitmap = 0;
+			prev_key = key;
+		}
+
+		off_bitmap |= UINT64CONST(1) << off;
 	}
 
+	/* save the final index for later */
+	idx = key - key_base;
+	/* write out last offset bitmap */
+	values[idx] = off_bitmap;
+
 	if (TidStoreIsShared(ts))
 		LWLockAcquire(&ts->control->lock, LW_EXCLUSIVE);
 
 	/* insert the calculated key-values to the tree */
-	for (int i = 0; i < nkeys; i++)
+	for (int i = 0; i <= idx; i++)
 	{
 		if (values[i])
 		{
-			uint64 key = key_base + i;
+			key = key_base + i;
 
 			if (TidStoreIsShared(ts))
 				shared_rt_set(ts->tree.shared, key, &values[i]);
-- 
2.39.1