v14-0003-_bt_merge_arrays-Use-sort-merge-join-algorithm.patch
application/octet-stream
Filename: v14-0003-_bt_merge_arrays-Use-sort-merge-join-algorithm.patch
Type: application/octet-stream
Part: 0
Patch
Same data as JSON:
GET /api/v1/attachments/:id/patch
the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes.
API reference →
Format: format-patch
Series: patch v14-0003
Subject: _bt_merge_arrays: Use sort-merge join algorithm
| File | + | − |
|---|---|---|
| src/backend/access/nbtree/nbtutils.c | 21 | 5 |
From 1d5b556c594f689186e506c8507cc70af6316fb3 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: Fri, 8 Mar 2024 14:51:29 +0100
Subject: [PATCH v14 3/3] _bt_merge_arrays: Use sort-merge join algorithm
This reduces the worst case performance from O(N log (M)) random operations
to O(N+M) mostly sequential accesses.
Future work may want to implement an exponential increment in the
inequality branches for best-case performance wins, but that's yet to
be implemented.
---
src/backend/access/nbtree/nbtutils.c | 26 +++++++++++++++++++++-----
1 file changed, 21 insertions(+), 5 deletions(-)
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 6e97455c87..d4e346de9d 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -684,25 +684,41 @@ _bt_merge_arrays(ScanKey skey, FmgrInfo *sortproc, bool reverse,
#endif
/*
- * Incrementally copy the original array into a temp buffer, skipping over
- * any items that are missing from the "next" array
+ * Sort-merge join the two arrays.
+ * The arrays are presorted using the same operators, so we can just use
+ * two cursors
*/
cxt.sortproc = sortproc;
cxt.collation = skey->sk_collation;
cxt.reverse = reverse;
- for (int i = 0; i < nelems_orig; i++)
+ for (int i = 0, j = 0; i < nelems_orig && j < nelems_next;)
{
Datum *elem = elems_orig + i;
+ Datum *next = elems_next + j;
+ int res;
- if (bsearch_arg(elem, elems_next, nelems_next, sizeof(Datum),
- _bt_compare_array_elements, &cxt))
+ res = _bt_compare_array_elements(elem, next, &cxt);
+
+ if (res == 0)
{
elems_orig[merged_nelems] = *elem;
#ifdef USE_ASSERT_CHECKING
merged[merged_nelems] = *elem;
#endif
merged_nelems++;
+ i++;
+ j++;
}
+ /*
+ * XXX: Future efforts may want to use exponential search to find the
+ * next candidate i or j value, rather than the linear scan used here,
+ * as it would allow best-case performance to improve from O(N) to
+ * O(log(N)).
+ */
+ else if (res < 0)
+ i++;
+ else /* res > 0 */
+ j++;
}
#ifdef USE_ASSERT_CHECKING
--
2.40.1