v32-0012-tidstore-Use-concept-of-off_upper-and-off_lower.patch

From 3f38c7722deb260e5cc4ac003ab37cfe959b1954 Mon Sep 17 00:00:00 2001
From: Masahiko Sawada <sawada.mshk@gmail.com>
Date: Mon, 17 Apr 2023 17:54:49 +0900
Subject: [PATCH v32 12/18] tidstore: Use concept of off_upper and off_lower.

The key is block number + the upper of offset number, whereas the
value is the bitmap representation of the lower offset number.

Updated function and variable names accordingly.
---
 src/backend/access/common/tidstore.c | 191 ++++++++++++++-------------
 1 file changed, 99 insertions(+), 92 deletions(-)

diff --git a/src/backend/access/common/tidstore.c b/src/backend/access/common/tidstore.c
index 283a326d13..d9fe3d5f15 100644
--- a/src/backend/access/common/tidstore.c
+++ b/src/backend/access/common/tidstore.c
@@ -65,8 +65,10 @@
  *
  * The maximum height of the radix tree is 5 in this case.
  */
-#define TIDSTORE_VALUE_NBITS	6	/* log(64, 2) */
-#define TIDSTORE_OFFSET_MASK	((1 << TIDSTORE_VALUE_NBITS) - 1)
+typedef uint64 tidkey;
+typedef uint64 offsetbm;
+#define LOWER_OFFSET_NBITS	6	/* log(sizeof(offsetbm), 2) */
+#define LOWER_OFFSET_MASK	((1 << LOWER_OFFSET_NBITS) - 1)
 
 /* A magic value used to identify our TidStores. */
 #define TIDSTORE_MAGIC 0x826f6a10
@@ -75,7 +77,7 @@
 #define RT_SCOPE static
 #define RT_DECLARE
 #define RT_DEFINE
-#define RT_VALUE_TYPE uint64
+#define RT_VALUE_TYPE tidkey
 #include "lib/radixtree.h"
 
 #define RT_PREFIX shared_rt
@@ -83,7 +85,7 @@
 #define RT_SCOPE static
 #define RT_DECLARE
 #define RT_DEFINE
-#define RT_VALUE_TYPE uint64
+#define RT_VALUE_TYPE tidkey
 #include "lib/radixtree.h"
 
 /* The control object for a TidStore */
@@ -94,10 +96,10 @@ typedef struct TidStoreControl
 
 	/* These values are never changed after creation */
 	size_t	max_bytes;		/* the maximum bytes a TidStore can use */
-	int		max_offset;		/* the maximum offset number */
-	int		offset_nbits;	/* the number of bits required for an offset
-							 * number */
-	int		offset_key_nbits;	/* the number of bits of an offset number
+	int		max_off;		/* the maximum offset number */
+	int		max_off_nbits;	/* the number of bits required for offset
+							 * numbers */
+	int		upper_off_nbits;	/* the number of bits of offset numbers
 								 * used in a key */
 
 	/* The below fields are used only in shared case */
@@ -147,17 +149,18 @@ typedef struct TidStoreIter
 	bool		finished;
 
 	/* save for the next iteration */
-	uint64		next_key;
-	uint64		next_val;
+	tidkey		next_tidkey;
+	offsetbm	next_off_bitmap;
 
 	/* output for the caller */
 	TidStoreIterResult result;
 } TidStoreIter;
 
-static void tidstore_iter_extract_tids(TidStoreIter *iter, uint64 key, uint64 val);
-static inline BlockNumber key_get_blkno(TidStore *ts, uint64 key);
-static inline uint64 encode_key_off(TidStore *ts, BlockNumber block, uint32 offset, uint64 *off_bit);
-static inline uint64 tid_to_key_off(TidStore *ts, ItemPointer tid, uint64 *off_bit);
+static void iter_decode_key_off(TidStoreIter *iter, tidkey key, offsetbm off_bitmap);
+static inline BlockNumber key_get_blkno(TidStore *ts, tidkey key);
+static inline tidkey encode_blk_off(TidStore *ts, BlockNumber block,
+									OffsetNumber offset, offsetbm *off_bit);
+static inline tidkey encode_tid(TidStore *ts, ItemPointer tid, offsetbm *off_bit);
 
 /*
  * Create a TidStore. The returned object is allocated in backend-local memory.
@@ -218,14 +221,14 @@ TidStoreCreate(size_t max_bytes, int max_off, dsa_area *area)
 		ts->control->max_bytes = max_bytes - (70 * 1024);
 	}
 
-	ts->control->max_offset = max_offset;
-	ts->control->offset_nbits = pg_ceil_log2_32(max_offset);
+	ts->control->max_off = max_off;
+	ts->control->max_off_nbits = pg_ceil_log2_32(max_off);
 
-	if (ts->control->offset_nbits < TIDSTORE_VALUE_NBITS)
-		ts->control->offset_nbits = TIDSTORE_VALUE_NBITS;
+	if (ts->control->max_off_nbits < LOWER_OFFSET_NBITS)
+		ts->control->max_off_nbits = LOWER_OFFSET_NBITS;
 
-	ts->control->offset_key_nbits =
-		ts->control->offset_nbits - TIDSTORE_VALUE_NBITS;
+	ts->control->upper_off_nbits =
+		ts->control->max_off_nbits - LOWER_OFFSET_NBITS;
 
 	return ts;
 }
@@ -355,25 +358,25 @@ void
 TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 						int num_offsets)
 {
-	uint64	*values;
-	uint64	key;
-	uint64	prev_key;
-	uint64	off_bitmap = 0;
+	offsetbm	*bitmaps;
+	tidkey		key;
+	tidkey		prev_key;
+	offsetbm	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;
+	const tidkey key_base = ((uint64) blkno) << ts->control->upper_off_nbits;
+	const int nkeys = UINT64CONST(1) << ts->control->upper_off_nbits;
 
 	Assert(!TidStoreIsShared(ts) || ts->control->magic == TIDSTORE_MAGIC);
 
-	values = palloc(sizeof(uint64) * nkeys);
+	bitmaps = palloc(sizeof(offsetbm) * nkeys);
 	key = prev_key = key_base;
 
 	for (int i = 0; i < num_offsets; i++)
 	{
-		uint64	off_bit;
+		offsetbm	off_bit;
 
 		/* encode the tid to a key and partial offset */
-		key = encode_key_off(ts, blkno, offsets[i], &off_bit);
+		key = encode_blk_off(ts, blkno, offsets[i], &off_bit);
 
 		/* make sure we scanned the line pointer array in order */
 		Assert(key >= prev_key);
@@ -384,11 +387,11 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 			Assert(idx >= 0 && idx < nkeys);
 
 			/* write out offset bitmap for this key */
-			values[idx] = off_bitmap;
+			bitmaps[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;
+				bitmaps[empty_idx] = 0;
 
 			/* reset for current key -- the current offset will be handled below */
 			off_bitmap = 0;
@@ -401,7 +404,7 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 	/* save the final index for later */
 	idx = key - key_base;
 	/* write out last offset bitmap */
-	values[idx] = off_bitmap;
+	bitmaps[idx] = off_bitmap;
 
 	if (TidStoreIsShared(ts))
 		LWLockAcquire(&ts->control->lock, LW_EXCLUSIVE);
@@ -409,14 +412,14 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 	/* insert the calculated key-values to the tree */
 	for (int i = 0; i <= idx; i++)
 	{
-		if (values[i])
+		if (bitmaps[i])
 		{
 			key = key_base + i;
 
 			if (TidStoreIsShared(ts))
-				shared_rt_set(ts->tree.shared, key, &values[i]);
+				shared_rt_set(ts->tree.shared, key, &bitmaps[i]);
 			else
-				local_rt_set(ts->tree.local, key, &values[i]);
+				local_rt_set(ts->tree.local, key, &bitmaps[i]);
 		}
 	}
 
@@ -426,29 +429,29 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
 	if (TidStoreIsShared(ts))
 		LWLockRelease(&ts->control->lock);
 
-	pfree(values);
+	pfree(bitmaps);
 }
 
 /* Return true if the given tid is present in the TidStore */
 bool
 TidStoreIsMember(TidStore *ts, ItemPointer tid)
 {
-	uint64 key;
-	uint64 val = 0;
-	uint64 off_bit;
+	tidkey key;
+	offsetbm off_bitmap = 0;
+	offsetbm off_bit;
 	bool found;
 
-	key = tid_to_key_off(ts, tid, &off_bit);
+	key = encode_tid(ts, tid, &off_bit);
 
 	if (TidStoreIsShared(ts))
-		found = shared_rt_search(ts->tree.shared, key, &val);
+		found = shared_rt_search(ts->tree.shared, key, &off_bitmap);
 	else
-		found = local_rt_search(ts->tree.local, key, &val);
+		found = local_rt_search(ts->tree.local, key, &off_bitmap);
 
 	if (!found)
 		return false;
 
-	return (val & off_bit) != 0;
+	return (off_bitmap & off_bit) != 0;
 }
 
 /*
@@ -486,12 +489,12 @@ TidStoreBeginIterate(TidStore *ts)
 }
 
 static inline bool
-tidstore_iter_kv(TidStoreIter *iter, uint64 *key, uint64 *val)
+tidstore_iter(TidStoreIter *iter, tidkey *key, offsetbm *off_bitmap)
 {
 	if (TidStoreIsShared(iter->ts))
-		return shared_rt_iterate_next(iter->tree_iter.shared, key, val);
+		return shared_rt_iterate_next(iter->tree_iter.shared, key, off_bitmap);
 
-	return local_rt_iterate_next(iter->tree_iter.local, key, val);
+	return local_rt_iterate_next(iter->tree_iter.local, key, off_bitmap);
 }
 
 /*
@@ -502,43 +505,46 @@ tidstore_iter_kv(TidStoreIter *iter, uint64 *key, uint64 *val)
 TidStoreIterResult *
 TidStoreIterateNext(TidStoreIter *iter)
 {
-	uint64 key;
-	uint64 val;
-	TidStoreIterResult *result = &(iter->result);
+	tidkey key;
+	offsetbm off_bitmap = 0;
+	TidStoreIterResult *output = &(iter->output);
 
 	if (iter->finished)
 		return NULL;
 
-	if (BlockNumberIsValid(result->blkno))
-	{
-		/* Process the previously collected key-value */
-		result->num_offsets = 0;
-		tidstore_iter_extract_tids(iter, iter->next_key, iter->next_val);
-	}
+	/* Initialize the outputs */
+	output->blkno = InvalidBlockNumber;
+	output->num_offsets = 0;
 
-	while (tidstore_iter_kv(iter, &key, &val))
-	{
-		BlockNumber blkno;
+	/*
+	 * Decode the key and offset bitmap that are collected in the previous
+	 * time, if exists.
+	 */
+	if (iter->next_off_bitmap > 0)
+		iter_decode_key_off(iter, iter->next_tidkey, iter->next_off_bitmap);
 
-		blkno = key_get_blkno(iter->ts, key);
+	while (tidstore_iter(iter, &key, &off_bitmap))
+	{
+		BlockNumber blkno = key_get_blkno(iter->ts, key);
 
-		if (BlockNumberIsValid(result->blkno) && result->blkno != blkno)
+		if (BlockNumberIsValid(output->blkno) && output->blkno != blkno)
 		{
 			/*
-			 * We got a key-value pair for a different block. So return the
-			 * collected tids, and remember the key-value for the next iteration.
+			 * We got tids for a different block. We return the collected
+			 * tids so far, and remember the key-value for the next
+			 * iteration.
 			 */
-			iter->next_key = key;
-			iter->next_val = val;
-			return result;
+			iter->next_tidkey = key;
+			iter->next_off_bitmap = off_bitmap;
+			return output;
 		}
 
-		/* Collect tids extracted from the key-value pair */
-		tidstore_iter_extract_tids(iter, key, val);
+		/* Collect tids decoded from the key and offset bitmap */
+		iter_decode_key_off(iter, key, off_bitmap);
 	}
 
 	iter->finished = true;
-	return result;
+	return output;
 }
 
 /*
@@ -623,61 +629,62 @@ TidStoreGetHandle(TidStore *ts)
 
 /* Extract tids from the given key-value pair */
 static void
-tidstore_iter_extract_tids(TidStoreIter *iter, uint64 key, uint64 val)
+iter_decode_key_off(TidStoreIter *iter, tidkey key, offsetbm off_bitmap)
 {
 	TidStoreIterResult *result = (&iter->result);
 
-	while (val)
+	while (off_bitmap)
 	{
-		uint64	tid_i;
+		uint64	compressed_tid;
 		OffsetNumber	off;
 
-		tid_i = key << TIDSTORE_VALUE_NBITS;
-		tid_i |= pg_rightmost_one_pos64(val);
+		compressed_tid = key << LOWER_OFFSET_NBITS;
+		compressed_tid |= pg_rightmost_one_pos64(off_bitmap);
 
-		off = tid_i & ((UINT64CONST(1) << iter->ts->control->offset_nbits) - 1);
+		off = compressed_tid & ((UINT64CONST(1) << iter->ts->control->max_off_nbits) - 1);
 
-		Assert(result->num_offsets < iter->ts->control->max_offset);
-		result->offsets[result->num_offsets++] = off;
+		Assert(output->num_offsets < iter->ts->control->max_off);
+		output->offsets[output->num_offsets++] = off;
 
 		/* unset the rightmost bit */
-		val &= ~pg_rightmost_one64(val);
+		off_bitmap &= ~pg_rightmost_one64(off_bitmap);
 	}
 
-	result->blkno = key_get_blkno(iter->ts, key);
+	output->blkno = key_get_blkno(iter->ts, key);
 }
 
 /* Get block number from the given key */
 static inline BlockNumber
-key_get_blkno(TidStore *ts, uint64 key)
+key_get_blkno(TidStore *ts, tidkey key)
 {
-	return (BlockNumber) (key >> ts->control->offset_key_nbits);
+	return (BlockNumber) (key >> ts->control->upper_off_nbits);
 }
 
-/* Encode a tid to key and offset */
-static inline uint64
-tid_to_key_off(TidStore *ts, ItemPointer tid, uint64 *off_bit)
+/* Encode a tid to key and partial offset */
+static inline tidkey
+encode_tid(TidStore *ts, ItemPointer tid, offsetbm *off_bit)
 {
 	uint32 offset = ItemPointerGetOffsetNumber(tid);
 	BlockNumber block = ItemPointerGetBlockNumber(tid);
 
-	return encode_key_off(ts, block, offset, off_bit);
+	return encode_blk_off(ts, block, offset, off_bit);
 }
 
 /* encode a block and offset to a key and partial offset */
-static inline uint64
-encode_key_off(TidStore *ts, BlockNumber block, uint32 offset, uint64 *off_bit)
+static inline tidkey
+encode_blk_off(TidStore *ts, BlockNumber block, OffsetNumber offset,
+			   offsetbm *off_bit)
 {
-	uint64 key;
-	uint64 tid_i;
+	tidkey key;
+	uint64 compressed_tid;
 	uint32 off_lower;
 
-	off_lower = offset & TIDSTORE_OFFSET_MASK;
-	Assert(off_lower < (sizeof(uint64) * BITS_PER_BYTE));
+	off_lower = offset & LOWER_OFFSET_MASK;
+	Assert(off_lower < (sizeof(offsetbm) * BITS_PER_BYTE));
 
 	*off_bit = UINT64CONST(1) << off_lower;
-	tid_i = offset | ((uint64) block << ts->control->offset_nbits);
-	key = tid_i >> TIDSTORE_VALUE_NBITS;
+	compressed_tid = offset | ((uint64) block << ts->control->max_off_nbits);
+	key = compressed_tid >> LOWER_OFFSET_NBITS;
 
 	return key;
 }
-- 
2.31.1