From 1d5b556c594f689186e506c8507cc70af6316fb3 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent 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