v1-0001-nbtree-Optimize-preprocessing-for-single-ScanKey-.patch.txt
text/plain
Filename: v1-0001-nbtree-Optimize-preprocessing-for-single-ScanKey-.patch.txt
Type: text/plain
Part: 0
From 16808e85f5fae7b16fd52d8a2be8437e4cff8640 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
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