v11-0001-nbtree-merge-array-scankeys-s-arrays-more-effici.patch-a

From 35dfa0a8aee457423d702001d2a437b2eaff0146 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: Tue, 16 Jan 2024 18:34:09 +0100
Subject: [PATCH v11] nbtree: merge array scankeys's arrays more efficiently

Instead of n * log(m), we use mergejoin to merge the arrays in
O(n + m) time. We further use exponential search to improve
mergejoin's O(n+m) complexity to O(log(n | m)) in cases where one
array's data range is completely disjunct from the other.

While technically this last case could be further improved to O(1),
it'd be only a marginal speedup when compared to this one's.
---
 src/backend/access/nbtree/nbtutils.c | 60 +++++++++++++++++++++++++++-
 1 file changed, 58 insertions(+), 2 deletions(-)

diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 78d16d3330..3565e33cd7 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -48,6 +48,9 @@ static int	_bt_sort_array_elements(IndexScanDesc scan, ScanKey skey,
 static int	_bt_merge_arrays(IndexScanDesc scan, ScanKey skey, bool reverse,
 							 Datum *elems_orig, int nelems_orig,
 							 Datum *elems_next, int nelems_next);
+static int _bt_merge_arrays_search_next(Datum *elems, int nelems, int start_index,
+										Datum *key, BTSortArrayContext *cxt,
+										int *compare_result);
 static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
 static inline int32 _bt_compare_array_skey(FmgrInfo *orderproc,
 										   Datum tupdatum, bool tupnull,
@@ -644,8 +647,9 @@ _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, bool reverse,
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	BTSortArrayContext cxt;
-	Datum	   *merged = palloc(sizeof(Datum) * Min(nelems_orig, nelems_next));
+	Datum	   *merged PG_USED_FOR_ASSERTS_ONLY;
 	int			merged_nelems = 0;
+	int			merged_nelems_check PG_USED_FOR_ASSERTS_ONLY = 0;
 
 	/*
 	 * Incrementally copy the original array into a temp buffer, skipping over
@@ -654,21 +658,73 @@ _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, bool reverse,
 	cxt.orderproc = &so->orderProcs[skey->sk_attno - 1];
 	cxt.collation = skey->sk_collation;
 	cxt.reverse = reverse;
+
+	/*
+	 * When assertions are enabled, use binary searches to create an array of
+	 * matches that we'll use to validate our merge join + exponential search
+	 * algorithm below.
+	 *
+	 * Note that this scratch space is only used in assert-enabled builds; we
+	 * write directly to elems_orig when we don't have assertions enabled,
+	 * saving one palloc/pfree.
+	 */
+#ifdef USE_ASSERT_CHECKING
+	merged = palloc(sizeof(Datum) * Min(nelems_orig, nelems_next));
+
 	for (int i = 0; i < nelems_orig; i++)
 	{
 		Datum	   *elem = elems_orig + i;
 
 		if (bsearch_arg(elem, elems_next, nelems_next, sizeof(Datum),
 						_bt_compare_array_elements, &cxt))
-			merged[merged_nelems++] = *elem;
+			merged[merged_nelems_check++] = *elem;
+	}
+#endif
+
+	for (int i = 0, j = 0; i < nelems_orig && j < nelems_next;)
+	{
+		Datum	   *orig = &elems_orig[i];
+		Datum	   *next = &elems_next[j];
+		int			res;
+
+		res = _bt_compare_array_elements(orig, next, &cxt);
+
+		if (res < 0)
+			i++;
+		else if (res > 0)
+			j++;
+		else /* res == 0 */
+		{
+#ifdef USE_ASSERT_CHECKING
+			/*
+			 * Make sure that the current index in elems_orig is not smaller
+			 * than the number of merged elements: if that were the case, we'd
+			 * have double-counted at least one element, which would break
+			 * the assumption we use in non-assertion builds to directly write
+			 * to elems_orig.
+			 */
+			Assert(merged_nelems <= i);
+			Assert(_bt_compare_array_elements(&merged[merged_nelems++], orig, &cxt) == 0);
+#else
+			/* Move the element to the merged section, if needed */
+			if (merged_nelems != i)
+				elems_orig[merged_nelems++] = *orig;
+#endif
+			i++;
+			j++;
+		}
 	}
 
+	Assert(merged_nelems == merged_nelems_check);
+
+#ifdef USE_ASSERT_CHECKING
 	/*
 	 * Overwrite the original array with temp buffer so that we're only left
 	 * with intersecting array elements
 	 */
 	memcpy(elems_orig, merged, merged_nelems * sizeof(Datum));
 	pfree(merged);
+#endif
 
 	return merged_nelems;
 }
-- 
2.40.1