add-random-node-search-test.patch.txt

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 0874201d7e..e0205b364e 100644
--- a/contrib/bench_radix_tree/bench_radix_tree--1.0.sql
+++ b/contrib/bench_radix_tree/bench_radix_tree--1.0.sql
@@ -43,6 +43,14 @@ returns record
 as 'MODULE_PATHNAME'
 LANGUAGE C STRICT VOLATILE PARALLEL UNSAFE;
 
+create function bench_search_random_nodes(
+cnt int8,
+OUT mem_allocated int8,
+OUT search_ms int8)
+returns record
+as 'MODULE_PATHNAME'
+LANGUAGE C STRICT VOLATILE PARALLEL UNSAFE;
+
 create function bench_fixed_height_search(
 fanout int4,
 OUT fanout int4,
diff --git a/contrib/bench_radix_tree/bench_radix_tree.c b/contrib/bench_radix_tree/bench_radix_tree.c
index 7abb237e96..a43fc61c2d 100644
--- a/contrib/bench_radix_tree/bench_radix_tree.c
+++ b/contrib/bench_radix_tree/bench_radix_tree.c
@@ -29,6 +29,7 @@ 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);
+PG_FUNCTION_INFO_V1(bench_search_random_nodes);
 
 static uint64
 tid_to_key_off(ItemPointer tid, uint32 *off)
@@ -347,6 +348,77 @@ bench_load_random_int(PG_FUNCTION_ARGS)
 	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc, values, nulls)));
 }
 
+/* copy of splitmix64() */
+static uint64
+hash64(uint64 x)
+{
+	x ^= x >> 30;
+	x *= UINT64CONST(0xbf58476d1ce4e5b9);
+	x ^= x >> 27;
+	x *= UINT64CONST(0x94d049bb133111eb);
+	x ^= x >> 31;
+	return x;
+}
+
+/* attempts to have a relatively even population of node kinds */
+Datum
+bench_search_random_nodes(PG_FUNCTION_ARGS)
+{
+	uint64		cnt = (uint64) PG_GETARG_INT64(0);
+	radix_tree *rt;
+	TupleDesc	tupdesc;
+	TimestampTz start_time,
+				end_time;
+	long		secs;
+	int			usecs;
+	int64		search_time_ms;
+	Datum		values[2] = {0};
+	bool		nulls[2] = {0};
+	/* from trial and error */
+	const uint64 filter = (((uint64) 0x7F<<32) | (0x07<<24) | (0xFF<<16) | 0xFF);
+
+	/* 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);
+
+	for (uint64 i = 0; i < cnt; i++)
+	{
+		const uint64 hash = hash64(i);
+		const uint64 key = hash & filter;
+
+		rt_set(rt, key, key);
+	}
+
+	start_time = GetCurrentTimestamp();
+	for (uint64 i = 0; i < cnt; i++)
+	{
+		const uint64 hash = hash64(i);
+		const uint64 key = hash & filter;
+		uint64		val;
+		volatile bool ret;		/* prevent calling rt_search from being
+								 * optimized out */
+
+		CHECK_FOR_INTERRUPTS();
+
+		ret = rt_search(rt, key, &val);
+		(void) ret;
+	}
+	end_time = GetCurrentTimestamp();
+
+	TimestampDifference(start_time, end_time, &secs, &usecs);
+	search_time_ms = secs * 1000 + usecs / 1000;
+
+	rt_stats(rt);
+
+	values[0] = Int64GetDatum(rt_memory_usage(rt));
+	values[1] = Int64GetDatum(search_time_ms);
+
+	rt_free(rt);
+	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc, values, nulls)));
+}
+
 Datum
 bench_fixed_height_search(PG_FUNCTION_ARGS)
 {