commit 18407962e96ccec6c9aeeba97412edd762a5a4fe
Author: John Naylor <john.naylor@postgresql.org>
Date:   Wed Sep 21 11:44:43 2022 +0700

    Add special benchmark function to test effect of fanout

diff --git a/contrib/bench_radix_tree/Makefile b/contrib/bench_radix_tree/Makefile
index b8f70e12d1..952bb0ceae 100644
--- a/contrib/bench_radix_tree/Makefile
+++ b/contrib/bench_radix_tree/Makefile
@@ -7,7 +7,7 @@ OBJS = \
 EXTENSION = bench_radix_tree
 DATA = bench_radix_tree--1.0.sql
 
-REGRESS = bench
+REGRESS = bench_fixed_height
 
 ifdef USE_PGXS
 PG_CONFIG = pg_config
diff --git a/contrib/bench_radix_tree/bench_radix_tree--1.0.sql b/contrib/bench_radix_tree/bench_radix_tree--1.0.sql
index 6663abe6a4..f2fee15b17 100644
--- a/contrib/bench_radix_tree/bench_radix_tree--1.0.sql
+++ b/contrib/bench_radix_tree/bench_radix_tree--1.0.sql
@@ -40,3 +40,15 @@ OUT load_ms int8)
 returns record
 as 'MODULE_PATHNAME'
 LANGUAGE C STRICT VOLATILE PARALLEL UNSAFE;
+
+create function bench_fixed_height_search(
+fanout int4,
+OUT fanout int4,
+OUT nkeys int8,
+OUT rt_mem_allocated int8,
+OUT rt_load_ms int8,
+OUT rt_search_ms int8
+)
+returns record
+as 'MODULE_PATHNAME'
+LANGUAGE C STRICT VOLATILE PARALLEL UNSAFE;
diff --git a/contrib/bench_radix_tree/bench_radix_tree.c b/contrib/bench_radix_tree/bench_radix_tree.c
index 5806ef7519..0778da2d7b 100644
--- a/contrib/bench_radix_tree/bench_radix_tree.c
+++ b/contrib/bench_radix_tree/bench_radix_tree.c
@@ -13,6 +13,7 @@
 #include "fmgr.h"
 #include "funcapi.h"
 #include "lib/radixtree.h"
+#include <math.h>
 #include "miscadmin.h"
 #include "utils/timestamp.h"
 
@@ -24,6 +25,7 @@ PG_MODULE_MAGIC;
 PG_FUNCTION_INFO_V1(bench_seq_search);
 PG_FUNCTION_INFO_V1(bench_shuffle_search);
 PG_FUNCTION_INFO_V1(bench_load_random_int);
+PG_FUNCTION_INFO_V1(bench_fixed_height_search);
 
 static radix_tree *rt = NULL;
 static ItemPointer itemptrs = NULL;
@@ -299,3 +301,108 @@ bench_load_random_int(PG_FUNCTION_ARGS)
 	rt_free(rt);
 	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc, values, nulls)));
 }
+
+Datum
+bench_fixed_height_search(PG_FUNCTION_ARGS)
+{
+	int	fanout = PG_GETARG_INT32(0);
+	radix_tree *rt;
+	TupleDesc	tupdesc;
+	TimestampTz	start_time,	end_time;
+	long	secs;
+	int		usecs;
+	int64	rt_load_ms, rt_search_ms;
+	Datum	values[5];
+	bool	nulls[5];
+
+	/* test boundary between vector and iteration */
+	const int		n_keys = 5 * 16 * 16 * 16 * 16;
+	uint64		r, h, i, j, k;
+	int key_id;
+
+	/* Build a tuple descriptor for our result type */
+	if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
+		elog(ERROR, "return type must be a row type");
+
+	rt = rt_create(CurrentMemoryContext);
+
+	start_time = GetCurrentTimestamp();
+
+	key_id = 0;
+	/*  lower nodes have limited fanout, the top is only limited by bits-per-byte */
+	for (r=1;;r++)
+	{
+		for (h = 1; h <= fanout; h++)
+		{
+			for (i = 1; i <= fanout; i++)
+			{
+				for (j = 1; j <= fanout; j++)
+				{
+					for (k = 1; k <= fanout; k++)
+					{
+						uint64	key;
+						key = (r<<32) | (h<<24) | (i<<16) | (j<<8) | (k);
+
+						CHECK_FOR_INTERRUPTS();
+
+						key_id++;
+						if (key_id > n_keys)
+							goto finish_set;
+
+						rt_set(rt, key, key_id);
+					}
+				}
+			}
+		}
+	}
+finish_set:
+	end_time = GetCurrentTimestamp();
+	TimestampDifference(start_time, end_time, &secs, &usecs);
+	rt_load_ms = secs * 1000 + usecs / 1000;
+
+	rt_stats(rt);
+
+	/* meaure the search time of the radix tree */
+	start_time = GetCurrentTimestamp();
+
+	key_id = 0;
+	for (r=1;;r++)
+	{
+		for (h = 1; h <= fanout; h++)
+		{
+			for (i = 1; i <= fanout; i++)
+			{
+				for (j = 1; j <= fanout; j++)
+				{
+					for (k = 1; k <= fanout; k++)
+					{
+						uint64	key, val;
+						key = (r<<32) | (h<<24) | (i<<16) | (j<<8) | (k);
+
+						CHECK_FOR_INTERRUPTS();
+
+						key_id++;
+						if (key_id > n_keys)
+							goto finish_search;
+
+						rt_search(rt, key, &val);
+					}
+				}
+			}
+		}
+	}
+finish_search:
+	end_time = GetCurrentTimestamp();
+	TimestampDifference(start_time, end_time, &secs, &usecs);
+	rt_search_ms = secs * 1000 + usecs / 1000;
+
+	MemSet(nulls, false, sizeof(nulls));
+	values[0] = Int32GetDatum(fanout);
+	values[1] = Int64GetDatum(rt_num_entries(rt));
+	values[2] = Int64GetDatum(rt_memory_usage(rt));
+	values[3] = Int64GetDatum(rt_load_ms);
+	values[4] = Int64GetDatum(rt_search_ms);
+
+	rt_free(rt);
+	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc, values, nulls)));
+}
diff --git a/contrib/bench_radix_tree/expected/bench_fixed_height.out b/contrib/bench_radix_tree/expected/bench_fixed_height.out
new file mode 100644
index 0000000000..c4995afc13
--- /dev/null
+++ b/contrib/bench_radix_tree/expected/bench_fixed_height.out
@@ -0,0 +1,6 @@
+create extension bench_radix_tree;
+\o fixed_height_search.data
+begin;
+select * from bench_fixed_height_search(15);
+select * from bench_fixed_height_search(16);
+commit;
diff --git a/contrib/bench_radix_tree/sql/bench_fixed_height.sql b/contrib/bench_radix_tree/sql/bench_fixed_height.sql
new file mode 100644
index 0000000000..0c06570e9a
--- /dev/null
+++ b/contrib/bench_radix_tree/sql/bench_fixed_height.sql
@@ -0,0 +1,7 @@
+create extension bench_radix_tree;
+
+\o fixed_height_search.data
+begin;
+select * from bench_fixed_height_search(15);
+select * from bench_fixed_height_search(16);
+commit;
diff --git a/src/backend/lib/radixtree.c b/src/backend/lib/radixtree.c
index b163eac480..4ce8e9ad9d 100644
--- a/src/backend/lib/radixtree.c
+++ b/src/backend/lib/radixtree.c
@@ -1980,7 +1980,7 @@ rt_verify_node(rt_node *node)
 void
 rt_stats(radix_tree *tree)
 {
-	fprintf(stderr, "num_keys = %lu, height = %u, n4 = %u, n16 = %u,n32 = %u, n128 = %u, n256 = %u",
+	fprintf(stderr, "num_keys = %lu, height = %u, n4 = %u, n16 = %u,n32 = %u, n128 = %u, n256 = %u\n",
 			tree->num_keys,
 			tree->root->shift / RT_NODE_SPAN,
 			tree->cnt[0],
diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index 38cc6abf4c..6016d593ee 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -15,7 +15,7 @@
 
 #include "postgres.h"
 
-/* #define RT_DEBUG 1 */
+#define RT_DEBUG 1 
 
 typedef struct radix_tree radix_tree;
 typedef struct rt_iter rt_iter;
