From 9f9ce415a5f66d54fce627103c4fc73289d430cf Mon Sep 17 00:00:00 2001 From: Matthias van de Meent Date: Fri, 8 Mar 2024 14:02:19 +0100 Subject: [PATCH v14 2/3] Notes & small fixes for nbtree SAOP patch - Comments fixed - Assertions updated - improve _bt_merge_arrays to only alloc when assertions are enabled. --- src/backend/access/nbtree/nbtsearch.c | 2 +- src/backend/access/nbtree/nbtutils.c | 96 +++++++++++++++++++++++++-- 2 files changed, 93 insertions(+), 5 deletions(-) diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 68bc32c6e1..2b61bda523 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -1763,7 +1763,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum, int truncatt; truncatt = BTreeTupleGetNAtts(itup, scan->indexRelation); - pstate.prechecked = false; /* prechecked earlier tuple */ + pstate.prechecked = false; /* prechecked didn't cover HIKEY */ _bt_checkkeys(scan, &pstate, arrayKeys, itup, truncatt); } diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 08219001a6..6e97455c87 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -678,8 +678,10 @@ _bt_merge_arrays(ScanKey skey, FmgrInfo *sortproc, bool reverse, Datum *elems_next, int nelems_next) { BTSortArrayContext cxt; - Datum *merged = palloc(sizeof(Datum) * Min(nelems_orig, nelems_next)); int merged_nelems = 0; +#ifdef USE_ASSERT_CHECKING + Datum *merged = palloc(sizeof(Datum) * Min(nelems_orig, nelems_next)); +#endif /* * Incrementally copy the original array into a temp buffer, skipping over @@ -694,15 +696,23 @@ _bt_merge_arrays(ScanKey skey, FmgrInfo *sortproc, bool reverse, if (bsearch_arg(elem, elems_next, nelems_next, sizeof(Datum), _bt_compare_array_elements, &cxt)) - merged[merged_nelems++] = *elem; + { + elems_orig[merged_nelems] = *elem; +#ifdef USE_ASSERT_CHECKING + merged[merged_nelems] = *elem; +#endif + merged_nelems++; + } } +#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)); + Assert(memcmp(elems_orig, merged, merged_nelems * sizeof(Datum)) == 0); pfree(merged); +#endif return merged_nelems; } @@ -1396,6 +1406,48 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, so->scanBehind = false; /* reset */ + /* + * Phase 1: Move array keys to more-appropriate positions + * + * We move the trigger scankey (i.e. the first non-matching scankey that + * the caller found) to the first appropriate array key value. This + * has 6 possible options: + * + * The scankey is a required equality array key, and + * 1. The tuple's attribute value is present in the array key + * 2. The tuple's attribute value is not present in the array key, but + * the array has a larger value. + * 3. The tuple's attribute value is not present in the array key, and + * no larger value exists in the array + * The scankey is not a required equality array key (so: non-required, or + * inequality key, or non-array) + * 4. The scankey is required and does match the tuple. + * 5. The scankey is required and does not match the tuple. + * 6. The scankey is not required. + * + * In case 1, we just update that key, and continue with the next key as + * if that were the next trigger scankey. + * + * In case 2, we update this array key to the larger value, and set all + * subsequent array keys to their first value. + * + * In case 3 and 5, we set beyond_end_advance to true, and we set all + * array scankeys starting from this one to their last value. Phase 2 + * will handle the array wraparounds triggered by beyond_end_advance. + * + * In case 4, we just continue on to the next key. + * + * In case 6, we ignore the key for the purposes of this system. + * + * We also gather several flags used later: + * - arrays_advanced: Did we update any array keys yet? + * This is used mostly to detect whether we've found the end of the + * index scan. + * - sktrig_required: Was the trigger scankey a required scankey? + * - all_required_satisfied: Could we apply case 1 for all keys? + * - so->scanBehind: XXX + * - XXX: Document more flags? + */ for (int ikey = 0; ikey < so->numberOfKeys; ikey++) { ScanKey cur = so->keyData + ikey; @@ -1419,6 +1471,12 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, } else { + /* + * This is an inequality key, so this should never be required in + * both directions. However, let's try to be very sure about that. + */ + Assert((cur->sk_flags & (SK_BT_REQBKWD|SK_BT_REQFWD)) != + (SK_BT_REQBKWD|SK_BT_REQFWD)); /* * Are any inequalities required in the opposite direction only * present here? @@ -1687,11 +1745,20 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, } } + /* + * Phase 2: post-processing + */ + /* * Consider if we need to advance the array keys incrementally to finish * off "beyond end of array element" array advancement. This is the only * way that the array keys can be exhausted, which is how top-level index * scans usually determine that they've run out of tuples to return. + * + * This is similar to adding 1 to 999 and carrying the digits up to 1000: + * If we try to advance an array key that's at it's last element, we wrap + * it around and increment the preceding array key by one. If that too is + * at its last element, wrap that, and increment the one before, etc. */ arrays_exhausted = false; if (beyond_end_advance) @@ -1765,6 +1832,27 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, * here will advance the array keys to the maximum possible extent * that we can know to be safe based on caller's tuple alone. If we * didn't perform this step, then that guarantee wouldn't quite hold. + * + * Example: + * + * If we were called with the following arguments: + * ScanKey (a=1 [1,2,3], b < 3) + * Tuple a=2, b=4 + * Then by now, the ScanKey would look like this: + * ScanKey (a=2 [1,2,3], b<3) + * This doesn't match the tuple (4 is not less than 3), and also won't + * match more tuples in the scan direction. The required unsatisfied + * inequality condition "b<3" was previously hidden by the unsatisfied + * array key, but now indicates we should update the array keys again. + * After another round of _bt_advance_array_keys, the key will look + * like this, and thus will be ready for further use: + * ScanKey (a=3 [1,2,3], b<3) + * + * Note that we will only ever need one additional advancement: The + * key is already advanced and at least as large as the current tuple + * (after accounting for the scan direction). Advancement will further + * increase this; this is only preparation so that the next scan may + * hit matching tuples (rather than being guaranteed to not match). */ if (unlikely(!pstate->continuescan)) { @@ -1821,7 +1909,7 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, * By here we have established that the scan's required arrays were * advanced, and that they haven't become exhausted. */ - Assert(arrays_advanced || !arrays_exhausted); + Assert(arrays_advanced && !arrays_exhausted); /* * We generally permit primitive index scans to continue onto the next -- 2.40.1