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