From e268e5965207ab9b9f377c1fb01aefb058588191 Mon Sep 17 00:00:00 2001 From: Peter Geoghegan Date: Fri, 27 Jun 2025 18:47:28 -0400 Subject: [PATCH v1] Teach nbtree to set pstate.ikey beyond a row compare. Follow up to commit 8a510275, which optimized nbtree search scan key comparisons, but didn't offer support for row compare keys. Author: Peter Geoghegan --- src/backend/access/nbtree/nbtutils.c | 166 +++++++++++++++++++++------ 1 file changed, 134 insertions(+), 32 deletions(-) diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 9aed20799..921a709af 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -59,6 +59,7 @@ static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, bool advancenonrequired, bool forcenonrequired, bool *continuescan, int *ikey); +static bool _bt_rowcompare_result(ScanKey subkey, int cmpresult); static bool _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, ScanDirection dir, bool forcenonrequired, bool *continuescan); @@ -2435,15 +2436,103 @@ _bt_set_startikey(IndexScanDesc scan, BTReadPageState *pstate) * Determine if it's safe to set pstate.startikey to an offset to a * key that comes after this key, by examining this key */ - if (!(key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) - { - /* Scan key isn't marked required (corner case) */ - break; /* unsafe */ - } if (key->sk_flags & SK_ROW_HEADER) { - /* RowCompare inequalities currently aren't supported */ - break; /* "unsafe" */ + /* + * RowCompare inequality header key. + * + * We can prove that the row compare must satisfy every tuple on + * the page when both firsttup and lasttup are satisfied by the + * row compare _before_ we need to read a value from an attribute + * that's > firstchangingattnum. + * + * We need to be careful of NULLs here. If any tuple on the page + * has NULLs in a possibly-deciding attribute, we cannot safely + * set pstate.ikey beyond the row compare header key. Similarly, + * reaching an ISNULL row compare member makes it unsafe. + */ + ScanKey subkey = (ScanKey) DatumGetPointer(key->sk_argument); + bool firstsatisfied = false, + lastsatisfied = false; + + for (;;) + { + int cmpresult; + + if (subkey->sk_attno > firstchangingattnum) /* >, not >= */ + break; + + if (subkey->sk_flags & SK_ISNULL) + break; + + /* + * Compare the first tuple's datum for this row compare member + * (unless we already know that firsttup must satisfy qual) + */ + if (!firstsatisfied) + { + firstdatum = index_getattr(firsttup, subkey->sk_attno, + tupdesc, &firstnull); + + if (firstnull) + break; /* unsafe, deciding attribute has some NULLs */ + + cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func, + subkey->sk_collation, + firstdatum, + subkey->sk_argument)); + if (subkey->sk_flags & SK_BT_DESC) + INVERT_COMPARE_RESULT(cmpresult); + + if (cmpresult != 0 || (subkey->sk_flags & SK_ROW_END)) + { + if (!_bt_rowcompare_result(subkey, cmpresult)) + break; + firstsatisfied = true; + } + } + + /* + * Compare the last tuple's datum for this row compare member + * (unless we already know that lasttup must satisfy qual) + */ + if (!lastsatisfied) + { + lastdatum = index_getattr(lasttup, subkey->sk_attno, + tupdesc, &lastnull); + + if (lastnull) + break; /* unsafe, deciding attribute has some NULLs */ + + cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func, + subkey->sk_collation, + lastdatum, + subkey->sk_argument)); + if (subkey->sk_flags & SK_BT_DESC) + INVERT_COMPARE_RESULT(cmpresult); + + if (cmpresult != 0 || (subkey->sk_flags & SK_ROW_END)) + { + if (!_bt_rowcompare_result(subkey, cmpresult)) + break; + lastsatisfied = true; + } + } + + if (firstsatisfied && lastsatisfied) + break; + + /* Move on to next row member, if any */ + if (subkey->sk_flags & SK_ROW_END) + break; + subkey++; + } + + if (!firstsatisfied || !lastsatisfied) + break; /* unsafe */ + + /* Safe, row compare satisfied by every tuple */ + continue; } if (key->sk_strategy != BTEqualStrategyNumber) { @@ -2911,6 +3000,42 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir, return true; } +/* + * Call here when a row compare member returns a non-zero result, or with the + * result for the final ROW_END row compare member (even when it's 0). + * + * cmpresult indicates the overall result of the row comparison, and subkey + * points to the deciding column (or the last column if the result is "="). + */ +static bool +_bt_rowcompare_result(ScanKey subkey, int cmpresult) +{ + bool satisfied; + + switch (subkey->sk_strategy) + { + /* EQ and NE cases aren't allowed here */ + case BTLessStrategyNumber: + satisfied = (cmpresult < 0); + break; + case BTLessEqualStrategyNumber: + satisfied = (cmpresult <= 0); + break; + case BTGreaterEqualStrategyNumber: + satisfied = (cmpresult >= 0); + break; + case BTGreaterStrategyNumber: + satisfied = (cmpresult > 0); + break; + default: + elog(ERROR, "unexpected strategy number %d", subkey->sk_strategy); + satisfied = false; /* keep compiler quiet */ + break; + } + + return satisfied; +} + /* * Test whether an indextuple satisfies a row-comparison scan condition. * @@ -3091,31 +3216,8 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts, subkey++; } - /* - * At this point cmpresult indicates the overall result of the row - * comparison, and subkey points to the deciding column (or the last - * column if the result is "="). - */ - switch (subkey->sk_strategy) - { - /* EQ and NE cases aren't allowed here */ - case BTLessStrategyNumber: - result = (cmpresult < 0); - break; - case BTLessEqualStrategyNumber: - result = (cmpresult <= 0); - break; - case BTGreaterEqualStrategyNumber: - result = (cmpresult >= 0); - break; - case BTGreaterStrategyNumber: - result = (cmpresult > 0); - break; - default: - elog(ERROR, "unexpected strategy number %d", subkey->sk_strategy); - result = 0; /* keep compiler quiet */ - break; - } + /* Determine if cmpresult satisfies final subkey's strategy */ + result = _bt_rowcompare_result(subkey, cmpresult); if (!result && !forcenonrequired) { -- 2.50.0