From 16808e85f5fae7b16fd52d8a2be8437e4cff8640 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent Date: Tue, 19 Mar 2024 16:39:29 +0100 Subject: [PATCH v1 1/2] nbtree: Optimize preprocessing for single ScanKey per column Before, there was only a single fast path: single-ScanKey index scans. With this optimization, we can fast-track processing of attributes with only a single scankey, significantly reducing overhead for common scans like "a = 10 and b < 8". --- src/backend/access/nbtree/nbtutils.c | 529 ++++++++++++++------------- 1 file changed, 278 insertions(+), 251 deletions(-) diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index b401b31191..8cd6270408 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -2511,7 +2511,6 @@ _bt_preprocess_keys(IndexScanDesc scan) ScanKey inkeys; ScanKey outkeys; ScanKey cur; - BTScanKeyPreproc xform[BTMaxStrategyNumber]; bool test_result; int i, j; @@ -2619,327 +2618,355 @@ _bt_preprocess_keys(IndexScanDesc scan) * xform[i] points to the currently best scan key of strategy type i+1; it * is NULL if we haven't yet found such a key for this attr. */ - attno = 1; - memset(xform, 0, sizeof(xform)); - /* - * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to - * handle after-last-key processing. Actual exit from the loop is at the - * "break" statement below. - */ - for (i = 0;; cur++, i++) + for (i = 0; i < numberOfKeys;) { - if (i < numberOfKeys) + BTScanKeyPreproc xform[BTMaxStrategyNumber]; + int priorNumberOfEqualCols = numberOfEqualCols; + bool fast = true; + + /* initialize for this attno */ + attno = cur->sk_attno; + + /* We'll try to merge keys if there are multiple for this attribute */ + if (i + 1 < numberOfKeys && (cur + 1)->sk_attno == attno) + fast = false; + + /* ... and have special care-taking for arrays and rows */ + if (cur->sk_flags & (SK_SEARCHARRAY | SK_ROW_HEADER)) + fast = false; + + /* no special array/row/multi-key processing */ + if (fast) { - /* Apply indoption to scankey (might change sk_strategy!) */ + ScanKey outkey; if (!_bt_fix_scankey_strategy(cur, indoption)) { - /* NULL can't be matched, so give up */ so->qual_ok = false; return; } + + /* mark key required if needed */ + if (numberOfEqualCols == attno - 1) + _bt_mark_scankey_required(cur); + /* ... and update the number of equal keys if needed */ + if (cur->sk_strategy == BTEqualStrategyNumber) + numberOfEqualCols++; + if (arrayKeyData) + keyDataMap[new_numberOfKeys] = i; + + /* Copy the key into the output key data */ + outkey = &outkeys[new_numberOfKeys++]; + memcpy(outkey, cur, sizeof(ScanKeyData)); + + cur++; + i++; + continue; } + memset(xform, 0, sizeof(xform)); + /* - * If we are at the end of the keys for a particular attr, finish up - * processing and emit the cleaned-up keys. + * Iterate over all ScanKeys for the current attno, collecting the + * most restrictive keys into xform. */ - if (i == numberOfKeys || cur->sk_attno != attno) + for (;i < numberOfKeys && cur->sk_attno == attno; cur++, i++) { - int priorNumberOfEqualCols = numberOfEqualCols; + /* Apply indoption to scankey (might change sk_strategy!) */ + if (!_bt_fix_scankey_strategy(cur, indoption)) + { + /* NULL can't be matched, so give up */ + so->qual_ok = false; + return; + } - /* check input keys are correctly ordered */ - if (i < numberOfKeys && cur->sk_attno < attno) - elog(ERROR, "btree index keys must be ordered by attribute"); + /* check strategy this key's operator corresponds to */ + j = cur->sk_strategy - 1; - /* - * If = has been specified, all other keys can be eliminated as - * redundant. If we have a case like key = 1 AND key > 2, we can - * set qual_ok to false and abandon further processing. - * - * We also have to deal with the case of "key IS NULL", which is - * unsatisfiable in combination with any other index condition. By - * the time we get here, that's been classified as an equality - * check, and we've rejected any combination of it with a regular - * equality condition; but not with other types of conditions. - */ - if (xform[BTEqualStrategyNumber - 1].skey) + /* if row comparison, push it directly to the output array */ + if (cur->sk_flags & SK_ROW_HEADER) { - ScanKey eq = xform[BTEqualStrategyNumber - 1].skey; - BTArrayKeyInfo *array = NULL; - FmgrInfo *orderproc = NULL; + ScanKey outkey = &outkeys[new_numberOfKeys++]; - if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY)) - { - int eq_in_ikey, - eq_arrayidx; + memcpy(outkey, cur, sizeof(ScanKeyData)); + if (arrayKeyData) + keyDataMap[new_numberOfKeys - 1] = i; + if (numberOfEqualCols == attno - 1) + _bt_mark_scankey_required(outkey); - eq_in_ikey = xform[BTEqualStrategyNumber - 1].ikey; - eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx; - array = &so->arrayKeys[eq_arrayidx - 1]; - orderproc = so->orderProcs + eq_in_ikey; + /* + * We don't support RowCompare using equality; such a qual would + * mess up the numberOfEqualCols tracking. + */ + Assert(j != (BTEqualStrategyNumber - 1)); + continue; + } - Assert(array->scan_key == eq_in_ikey); - Assert(OidIsValid(orderproc->fn_oid)); - } + /* + * Does this input scan key require further processing as an array? + */ + if (cur->sk_strategy == InvalidStrategy) + { + /* _bt_preprocess_array_keys marked this array key redundant */ + Assert(arrayKeyData); + Assert(cur->sk_flags & SK_SEARCHARRAY); + continue; + } - for (j = BTMaxStrategyNumber; --j >= 0;) - { - ScanKey chk = xform[j].skey; + if (cur->sk_strategy == BTEqualStrategyNumber && + (cur->sk_flags & SK_SEARCHARRAY)) + { + /* _bt_preprocess_array_keys kept this array key */ + Assert(arrayKeyData); + arrayidx++; + } - if (!chk || j == (BTEqualStrategyNumber - 1)) - continue; + /* + * have we seen a scan key for this same attribute and using this same + * operator strategy before now? + */ + if (xform[j].skey == NULL) + { + /* nope, so this scan key wins by default (at least for now) */ + xform[j].skey = cur; + xform[j].ikey = i; + xform[j].arrayidx = arrayidx; + } + else + { + FmgrInfo *orderproc = NULL; + BTArrayKeyInfo *array = NULL; - if (eq->sk_flags & SK_SEARCHNULL) + /* + * Seen one of these before, so keep only the more restrictive key + * if possible + */ + if (j == (BTEqualStrategyNumber - 1) && arrayKeyData) + { + /* + * Have to set up array keys + */ + if ((cur->sk_flags & SK_SEARCHARRAY)) { - /* IS NULL is contradictory to anything else */ - so->qual_ok = false; - return; - } + array = &so->arrayKeys[arrayidx - 1]; + orderproc = so->orderProcs + i; - if (_bt_compare_scankey_args(scan, chk, eq, chk, - array, orderproc, - &test_result)) - { - if (!test_result) - { - /* keys proven mutually contradictory */ - so->qual_ok = false; - return; - } - /* else discard the redundant non-equality key */ - Assert(!array || array->num_elems > 0); - xform[j].skey = NULL; - xform[j].ikey = -1; + Assert(array->scan_key == i); + Assert(OidIsValid(orderproc->fn_oid)); } - /* else, cannot determine redundancy, keep both keys */ - } - /* track number of attrs for which we have "=" keys */ - numberOfEqualCols++; - } + else if ((xform[j].skey->sk_flags & SK_SEARCHARRAY)) + { + array = &so->arrayKeys[xform[j].arrayidx - 1]; + orderproc = so->orderProcs + xform[j].ikey; - /* try to keep only one of <, <= */ - if (xform[BTLessStrategyNumber - 1].skey - && xform[BTLessEqualStrategyNumber - 1].skey) - { - ScanKey lt = xform[BTLessStrategyNumber - 1].skey; - ScanKey le = xform[BTLessEqualStrategyNumber - 1].skey; + Assert(array->scan_key == xform[j].ikey); + Assert(OidIsValid(orderproc->fn_oid)); + } - if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL, - &test_result)) - { - if (test_result) - xform[BTLessEqualStrategyNumber - 1].skey = NULL; - else - xform[BTLessStrategyNumber - 1].skey = NULL; + /* + * Both scan keys might have arrays, in which case we'll + * arbitrarily pass only one of the arrays. That won't + * matter, since _bt_compare_scankey_args is aware that two + * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys + * failed to eliminate redundant arrays through array merging. + * _bt_compare_scankey_args just returns false when it sees + * this; it won't even try to examine either array. + */ } - } - /* try to keep only one of >, >= */ - if (xform[BTGreaterStrategyNumber - 1].skey - && xform[BTGreaterEqualStrategyNumber - 1].skey) - { - ScanKey gt = xform[BTGreaterStrategyNumber - 1].skey; - ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].skey; - - if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL, - &test_result)) + if (_bt_compare_scankey_args(scan, cur, cur, xform[j].skey, + array, orderproc, &test_result)) { + /* Have all we need to determine redundancy */ if (test_result) - xform[BTGreaterEqualStrategyNumber - 1].skey = NULL; - else - xform[BTGreaterStrategyNumber - 1].skey = NULL; - } - } + { + Assert(!array || array->num_elems > 0); - /* - * Emit the cleaned-up keys into the outkeys[] array, and then - * mark them if they are required. They are required (possibly - * only in one direction) if all attrs before this one had "=". - */ - for (j = BTMaxStrategyNumber; --j >= 0;) - { - if (xform[j].skey) + /* + * New key is more restrictive, and so replaces old key... + */ + if (j != (BTEqualStrategyNumber - 1) || + !(xform[j].skey->sk_flags & SK_SEARCHARRAY)) + { + Assert(!array || array->scan_key == i); + xform[j].skey = cur; + xform[j].ikey = i; + xform[j].arrayidx = arrayidx; + } + else + { + /* + * ...unless we have to keep the old key because it's + * an array that rendered the new key redundant. We + * need to make sure that we don't throw away an array + * scan key. _bt_compare_scankey_args expects us to + * always keep arrays (and discard non-arrays). + */ + Assert(j == (BTEqualStrategyNumber - 1)); + Assert(xform[j].skey->sk_flags & SK_SEARCHARRAY); + Assert(xform[j].ikey == array->scan_key); + Assert(!(cur->sk_flags & SK_SEARCHARRAY)); + } + } + else if (j == (BTEqualStrategyNumber - 1)) + { + /* key == a && key == b, but a != b */ + so->qual_ok = false; + return; + } + /* else old key is more restrictive, keep it */ + } + else { + /* + * We can't determine which key is more restrictive. Push + * xform[j] directly to the output array, then set xform[j] to + * the new scan key. + * + * Note: We do things this way around so that our arrays are + * always in the same order as their corresponding scan keys, + * even with incomplete opfamilies. _bt_advance_array_keys + * depends on this. + */ ScanKey outkey = &outkeys[new_numberOfKeys++]; memcpy(outkey, xform[j].skey, sizeof(ScanKeyData)); if (arrayKeyData) keyDataMap[new_numberOfKeys - 1] = xform[j].ikey; - if (priorNumberOfEqualCols == attno - 1) + if (numberOfEqualCols == attno - 1) _bt_mark_scankey_required(outkey); + xform[j].skey = cur; + xform[j].ikey = i; + xform[j].arrayidx = arrayidx; } } - - /* - * Exit loop here if done. - */ - if (i == numberOfKeys) - break; - - /* Re-initialize for new attno */ - attno = cur->sk_attno; - memset(xform, 0, sizeof(xform)); - } - - /* check strategy this key's operator corresponds to */ - j = cur->sk_strategy - 1; - - /* if row comparison, push it directly to the output array */ - if (cur->sk_flags & SK_ROW_HEADER) - { - ScanKey outkey = &outkeys[new_numberOfKeys++]; - - memcpy(outkey, cur, sizeof(ScanKeyData)); - if (arrayKeyData) - keyDataMap[new_numberOfKeys - 1] = i; - if (numberOfEqualCols == attno - 1) - _bt_mark_scankey_required(outkey); - - /* - * We don't support RowCompare using equality; such a qual would - * mess up the numberOfEqualCols tracking. - */ - Assert(j != (BTEqualStrategyNumber - 1)); - continue; } /* - * Does this input scan key require further processing as an array? + * Now that we are at the end of the keys for a particular attr, + * finish up processing and emit the cleaned-up keys. */ - if (cur->sk_strategy == InvalidStrategy) - { - /* _bt_preprocess_array_keys marked this array key redundant */ - Assert(arrayKeyData); - Assert(cur->sk_flags & SK_SEARCHARRAY); - continue; - } - if (cur->sk_strategy == BTEqualStrategyNumber && - (cur->sk_flags & SK_SEARCHARRAY)) - { - /* _bt_preprocess_array_keys kept this array key */ - Assert(arrayKeyData); - arrayidx++; - } + /* check input keys are correctly ordered */ + if (i < numberOfKeys && cur->sk_attno < attno) + elog(ERROR, "btree index keys must be ordered by attribute"); /* - * have we seen a scan key for this same attribute and using this same - * operator strategy before now? + * If = has been specified, all other keys can be eliminated as + * redundant. If we have a case like key = 1 AND key > 2, we can + * set qual_ok to false and abandon further processing. + * + * We also have to deal with the case of "key IS NULL", which is + * unsatisfiable in combination with any other index condition. By + * the time we get here, that's been classified as an equality + * check, and we've rejected any combination of it with a regular + * equality condition; but not with other types of conditions. */ - if (xform[j].skey == NULL) + if (xform[BTEqualStrategyNumber - 1].skey) { - /* nope, so this scan key wins by default (at least for now) */ - xform[j].skey = cur; - xform[j].ikey = i; - xform[j].arrayidx = arrayidx; - } - else - { - FmgrInfo *orderproc = NULL; + ScanKey eq = xform[BTEqualStrategyNumber - 1].skey; BTArrayKeyInfo *array = NULL; + FmgrInfo *orderproc = NULL; - /* - * Seen one of these before, so keep only the more restrictive key - * if possible - */ - if (j == (BTEqualStrategyNumber - 1) && arrayKeyData) + if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY)) { - /* - * Have to set up array keys - */ - if ((cur->sk_flags & SK_SEARCHARRAY)) - { - array = &so->arrayKeys[arrayidx - 1]; - orderproc = so->orderProcs + i; - - Assert(array->scan_key == i); - Assert(OidIsValid(orderproc->fn_oid)); - } - else if ((xform[j].skey->sk_flags & SK_SEARCHARRAY)) - { - array = &so->arrayKeys[xform[j].arrayidx - 1]; - orderproc = so->orderProcs + xform[j].ikey; + int eq_in_ikey, + eq_arrayidx; - Assert(array->scan_key == xform[j].ikey); - Assert(OidIsValid(orderproc->fn_oid)); - } + eq_in_ikey = xform[BTEqualStrategyNumber - 1].ikey; + eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx; + array = &so->arrayKeys[eq_arrayidx - 1]; + orderproc = so->orderProcs + eq_in_ikey; - /* - * Both scan keys might have arrays, in which case we'll - * arbitrarily pass only one of the arrays. That won't - * matter, since _bt_compare_scankey_args is aware that two - * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys - * failed to eliminate redundant arrays through array merging. - * _bt_compare_scankey_args just returns false when it sees - * this; it won't even try to examine either array. - */ + Assert(array->scan_key == eq_in_ikey); + Assert(OidIsValid(orderproc->fn_oid)); } - if (_bt_compare_scankey_args(scan, cur, cur, xform[j].skey, - array, orderproc, &test_result)) + for (j = BTMaxStrategyNumber; --j >= 0;) { - /* Have all we need to determine redundancy */ - if (test_result) - { - Assert(!array || array->num_elems > 0); + ScanKey chk = xform[j].skey; - /* - * New key is more restrictive, and so replaces old key... - */ - if (j != (BTEqualStrategyNumber - 1) || - !(xform[j].skey->sk_flags & SK_SEARCHARRAY)) - { - Assert(!array || array->scan_key == i); - xform[j].skey = cur; - xform[j].ikey = i; - xform[j].arrayidx = arrayidx; - } - else - { - /* - * ...unless we have to keep the old key because it's - * an array that rendered the new key redundant. We - * need to make sure that we don't throw away an array - * scan key. _bt_compare_scankey_args expects us to - * always keep arrays (and discard non-arrays). - */ - Assert(j == (BTEqualStrategyNumber - 1)); - Assert(xform[j].skey->sk_flags & SK_SEARCHARRAY); - Assert(xform[j].ikey == array->scan_key); - Assert(!(cur->sk_flags & SK_SEARCHARRAY)); - } - } - else if (j == (BTEqualStrategyNumber - 1)) + if (!chk || j == (BTEqualStrategyNumber - 1)) + continue; + + if (eq->sk_flags & SK_SEARCHNULL) { - /* key == a && key == b, but a != b */ + /* IS NULL is contradictory to anything else */ so->qual_ok = false; return; } - /* else old key is more restrictive, keep it */ + + if (_bt_compare_scankey_args(scan, chk, eq, chk, + array, orderproc, + &test_result)) + { + if (!test_result) + { + /* keys proven mutually contradictory */ + so->qual_ok = false; + return; + } + /* else discard the redundant non-equality key */ + Assert(!array || array->num_elems > 0); + xform[j].skey = NULL; + xform[j].ikey = -1; + } + /* else, cannot determine redundancy, keep both keys */ } - else + /* track number of attrs for which we have "=" keys */ + numberOfEqualCols++; + } + + /* try to keep only one of <, <= */ + if (xform[BTLessStrategyNumber - 1].skey + && xform[BTLessEqualStrategyNumber - 1].skey) + { + ScanKey lt = xform[BTLessStrategyNumber - 1].skey; + ScanKey le = xform[BTLessEqualStrategyNumber - 1].skey; + + if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL, + &test_result)) + { + if (test_result) + xform[BTLessEqualStrategyNumber - 1].skey = NULL; + else + xform[BTLessStrategyNumber - 1].skey = NULL; + } + } + + /* try to keep only one of >, >= */ + if (xform[BTGreaterStrategyNumber - 1].skey + && xform[BTGreaterEqualStrategyNumber - 1].skey) + { + ScanKey gt = xform[BTGreaterStrategyNumber - 1].skey; + ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].skey; + + if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL, + &test_result)) + { + if (test_result) + xform[BTGreaterEqualStrategyNumber - 1].skey = NULL; + else + xform[BTGreaterStrategyNumber - 1].skey = NULL; + } + } + + /* + * Emit the cleaned-up keys into the outkeys[] array, and then + * mark them if they are required. They are required (possibly + * only in one direction) if all attrs before this one had "=". + */ + for (j = BTMaxStrategyNumber; --j >= 0;) + { + if (xform[j].skey) { - /* - * We can't determine which key is more restrictive. Push - * xform[j] directly to the output array, then set xform[j] to - * the new scan key. - * - * Note: We do things this way around so that our arrays are - * always in the same order as their corresponding scan keys, - * even with incomplete opfamilies. _bt_advance_array_keys - * depends on this. - */ ScanKey outkey = &outkeys[new_numberOfKeys++]; memcpy(outkey, xform[j].skey, sizeof(ScanKeyData)); if (arrayKeyData) keyDataMap[new_numberOfKeys - 1] = xform[j].ikey; - if (numberOfEqualCols == attno - 1) + if (priorNumberOfEqualCols == attno - 1) _bt_mark_scankey_required(outkey); - xform[j].skey = cur; - xform[j].ikey = i; - xform[j].arrayidx = arrayidx; } } } -- 2.40.1