v1-0001-Document-nbtree-row-comparison-design.patch

From f9793fbb317382540f8291b6053ccd78411f85ab Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Thu, 30 Oct 2025 15:28:00 -0400
Subject: [PATCH v1] Document nbtree row comparison design.

Follow-up to commits 7d9cd2df, bd3f59fd, and ec986020.
---
 src/backend/access/nbtree/nbtsearch.c |  3 ++
 src/backend/access/nbtree/nbtutils.c  | 56 +++++++++++++++++++++++----
 2 files changed, 51 insertions(+), 8 deletions(-)

diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index d69798795..0d02b89ce 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1272,6 +1272,8 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 			bool		loosen_strat = false,
 						tighten_strat = false;
 
+			Assert(bkey->sk_strategy == strat_total);
+
 			/*
 			 * Cannot be a NULL in the first row member: _bt_preprocess_keys
 			 * would've marked the qual as unsatisfiable, preventing us from
@@ -1288,6 +1290,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 			 * our row compare header key must be the final startKeys[] entry.
 			 */
 			Assert(subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD));
+			Assert(subkey->sk_strategy == bkey->sk_strategy);
 			Assert(i == keysz - 1);
 
 			/*
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 288da8b68..768071b8a 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -63,7 +63,7 @@ static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 							  bool advancenonrequired, bool forcenonrequired,
 							  bool *continuescan, int *ikey);
 static bool _bt_rowcompare_cmpresult(ScanKey subkey, int cmpresult);
-static bool _bt_check_rowcompare(ScanKey skey,
+static bool _bt_check_rowcompare(ScanKey header,
 								 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
 								 ScanDirection dir, bool forcenonrequired, bool *continuescan);
 static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
@@ -3044,19 +3044,59 @@ _bt_rowcompare_cmpresult(ScanKey subkey, int cmpresult)
  * it's not possible for any future tuples in the current scan direction
  * to pass the qual.
  *
- * This is a subroutine for _bt_checkkeys/_bt_check_compare.
+ * This is a subroutine for _bt_checkkeys/_bt_check_compare.  Caller passes us
+ * a row compare header key taken from so->keyData[].
+ *
+ * The SQL standard describes row value comparisons in terms of logical
+ * expansions that only use scalar operators.  Consider the following example
+ * row comparison:
+ *
+ * "(a, b, c) > (7, 'bar', 77)"
+ *
+ * This is logically/semantically equivalent to:
+ *
+ * "(a = 7 AND b = 'bar' AND c > 77) OR (a = 7 AND b > 'bar') OR (a > 7)".
+ *
+ * Notice that this condition is satisfied by _all_ rows that satisfy "a > 7",
+ * and by a subset of all rows that satisfy "a >= 7" (possibly all such rows).
+ * It _can't_ be satisfied by other rows (where "a < 7" or where "a IS NULL").
+ * A row comparison header key can therefore often be treated as if it was a
+ * simple scalar inequality on the most significant row member's index column.
+ *
+ * Things get more complicated for our row compare with rows where "a = 7".
+ * Note that a row comparison isn't necessarily satisfied by _every_ row that
+ * appears after the first satisfied/matching row.  A forwards scan that uses
+ * our example qual might first return a row "(a, b, c) = (7, 'zebra', 54)".
+ * But it must not return a row "(a, b, c) = (7, NULL, 1)" that'll appear to
+ * the right of the first match (assumes that "b" was declared NULLS LAST).
+ * The scan only returns additional matches upon reaching rows where "a > 7".
+ * If you rereview our example row comparison's logical expansion, you'll
+ * understand why this is so.
+ *
+ * Note that a row comparison key behaves _exactly_ the same as an equivalent
+ * scalar inequality key on its most significant column once the scan reaches
+ * the point where it no longer needs to consider any of its lower-order keys.
+ * For example, once a forwards scan that uses our example qual reaches the
+ * first tuple "a > 7", we'll behave in precisely the same way as our caller
+ * would behave with a scalar inequality "a > 7" for the remainder of the scan
+ * (assuming that the scan never changes direction/never goes backwards).
+ * This includes setting continuescan=false based on a deduced NOT NULL
+ * constraint according to the same rules that our caller applies when a NULL
+ * tuple value fails to satisfy a scalar inequality that's marked required in
+ * the opposite scan direction.
  */
 static bool
-_bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
+_bt_check_rowcompare(ScanKey header, IndexTuple tuple, int tupnatts,
 					 TupleDesc tupdesc, ScanDirection dir,
 					 bool forcenonrequired, bool *continuescan)
 {
-	ScanKey		subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
+	ScanKey		subkey = (ScanKey) DatumGetPointer(header->sk_argument);
 	int32		cmpresult = 0;
 	bool		result;
 
 	/* First subkey should be same as the header says */
-	Assert(subkey->sk_attno == skey->sk_attno);
+	Assert(header->sk_flags & SK_ROW_HEADER);
+	Assert(subkey->sk_attno == header->sk_attno);
 
 	/* Loop over columns of the row condition */
 	for (;;)
@@ -3076,7 +3116,7 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
 			 * columns are required for the scan direction, we can stop the
 			 * scan, because there can't be another tuple that will succeed.
 			 */
-			Assert(subkey != (ScanKey) DatumGetPointer(skey->sk_argument));
+			Assert(subkey != (ScanKey) DatumGetPointer(header->sk_argument));
 			subkey--;
 			if (forcenonrequired)
 			{
@@ -3147,7 +3187,7 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
 				 * can only happen with an "a" NULL some time after the scan
 				 * completely stops needing to use its "b" and "c" members.)
 				 */
-				if (subkey == (ScanKey) DatumGetPointer(skey->sk_argument))
+				if (subkey == (ScanKey) DatumGetPointer(header->sk_argument))
 					reqflags |= SK_BT_REQFWD;	/* safe, first row member */
 
 				if ((subkey->sk_flags & reqflags) &&
@@ -3185,7 +3225,7 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
 				 * happen with an "a" NULL some time after the scan completely
 				 * stops needing to use its "b" and "c" members.)
 				 */
-				if (subkey == (ScanKey) DatumGetPointer(skey->sk_argument))
+				if (subkey == (ScanKey) DatumGetPointer(header->sk_argument))
 					reqflags |= SK_BT_REQBKWD;	/* safe, first row member */
 
 				if ((subkey->sk_flags & reqflags) &&
-- 
2.51.0