v1-0001-Presort-ScalarArrayOp-arrays-during-planning.patch

From ca69e66e705f92439349d8fed5a2ea93cbcbd470 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Thu, 31 Jul 2025 19:31:15 -0400
Subject: [PATCH v1] Presort ScalarArrayOp arrays during planning.

---
 src/include/access/nbtree.h                   |   2 +
 src/include/access/skey.h                     |   5 +-
 src/backend/access/nbtree/nbtpreprocesskeys.c | 107 +++++++++++++++++-
 src/backend/executor/nodeIndexscan.c          |   6 +
 src/backend/optimizer/plan/createplan.c       |  19 ++++
 src/test/regress/expected/btree_index.out     |   2 +-
 src/test/regress/expected/create_index.out    |  20 ++--
 7 files changed, 144 insertions(+), 17 deletions(-)

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index e709d2e0a..7f9b0373e 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1297,6 +1297,8 @@ extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate);
  * prototypes for functions in nbtpreprocesskeys.c
  */
 extern void _bt_preprocess_keys(IndexScanDesc scan);
+extern Datum _bt_presort_const_array(Datum scanvalue, Oid opno, Oid opfamily,
+									 Oid collation, bool reverse);
 
 /*
  * prototypes for functions in nbtsearch.c
diff --git a/src/include/access/skey.h b/src/include/access/skey.h
index e650c2e7b..21fc13a1d 100644
--- a/src/include/access/skey.h
+++ b/src/include/access/skey.h
@@ -38,7 +38,9 @@
  * "column op ANY(ARRAY[...])".  This is signaled by the SK_SEARCHARRAY
  * flag bit.  The sk_argument is not a value of the operator's right-hand
  * argument type, but rather an array of such values, and the per-element
- * comparisons are to be ORed together.
+ * comparisons are to be ORed together.  Index AMs with native support for
+ * SAOP scans have their scan key marked SK_PRESORTED, indicating that the
+ * array has been sorted and deduplicated (and has had all NULLs removed).
  *
  * A ScanKey can also represent a condition "column IS NULL" or "column
  * IS NOT NULL"; these cases are signaled by the SK_SEARCHNULL and
@@ -121,6 +123,7 @@ typedef ScanKeyData *ScanKey;
 #define SK_SEARCHNULL		0x0040	/* scankey represents "col IS NULL" */
 #define SK_SEARCHNOTNULL	0x0080	/* scankey represents "col IS NOT NULL" */
 #define SK_ORDER_BY			0x0100	/* scankey is for ORDER BY op */
+#define SK_PRESORTED		0x0200	/* constant/presorted SAOP array */
 
 
 /*
diff --git a/src/backend/access/nbtree/nbtpreprocesskeys.c b/src/backend/access/nbtree/nbtpreprocesskeys.c
index 21c519cd1..4904f2aad 100644
--- a/src/backend/access/nbtree/nbtpreprocesskeys.c
+++ b/src/backend/access/nbtree/nbtpreprocesskeys.c
@@ -2017,10 +2017,18 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		 * all btree operators are strict.
 		 */
 		num_nonnulls = 0;
-		for (int j = 0; j < num_elems; j++)
+		if (!(cur->sk_flags & SK_PRESORTED))
 		{
-			if (!elem_nulls[j])
-				elem_values[num_nonnulls++] = elem_values[j];
+			for (int j = 0; j < num_elems; j++)
+			{
+				if (!elem_nulls[j])
+					elem_values[num_nonnulls++] = elem_values[j];
+			}
+		}
+		else
+		{
+			/* Planner removed NULLs for us using _bt_presort_const_array */
+			num_nonnulls = num_elems;
 		}
 
 		/* We could pfree(elem_nulls) now, but not worth the cycles */
@@ -2090,10 +2098,14 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		 * sort in the same ordering used by the index column, so that the
 		 * arrays can be advanced in lockstep with the scan's progress through
 		 * the index's key space.
+		 *
+		 * When SK_PRESORTED is set, _bt_presort_const_array will have been
+		 * called during planning to avoid repeated sorting across rescans.
 		 */
 		reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
-		num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
-											elem_values, num_nonnulls);
+		if (!(cur->sk_flags & SK_PRESORTED))
+			num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
+												elem_values, num_nonnulls);
 
 		if (origarrayatt == cur->sk_attno)
 		{
@@ -2832,3 +2844,88 @@ _bt_compare_array_elements(const void *a, const void *b, void *arg)
 		INVERT_COMPARE_RESULT(compare);
 	return compare;
 }
+
+/*
+ *	_bt_presort_const_array() -- presort ScalarArrarOp array.
+ *
+ * Returns a sorted and deduplicated copy of caller's scanvalue array,
+ * enabling the array's input scan key to be marked SK_PRESORTED later on.
+ *
+ * Called by the planner whenever it encounters a ScalarArrayOp whose array
+ * arg is a constant.  The array won't need to be sorted during preprocessing.
+ * This optimization saves many cycles with larger SAOP arrays that are reused
+ * across rescans.
+ */
+extern Datum
+_bt_presort_const_array(Datum scanvalue, Oid opno, Oid opfamily,
+						Oid collation, bool reverse)
+{
+	ArrayType  *arrayval;
+	int16		elmlen;
+	bool		elmbyval;
+	char		elmalign;
+	int			op_strategy;
+	Oid			op_lefttype,
+				op_righttype;
+	Datum	   *elem_values;
+	bool	   *elem_nulls;
+	int			num_elems,
+				num_nonnulls;
+	RegProcedure cmp_proc;
+	FmgrInfo	sortproc;
+
+	/*
+	 * Deconstruct the array into elements
+	 */
+	arrayval = DatumGetArrayTypeP(scanvalue);
+	/* We could cache this data, but not clear it's worth it */
+	get_typlenbyvalalign(ARR_ELEMTYPE(arrayval), &elmlen, &elmbyval, &elmalign);
+	deconstruct_array(arrayval, ARR_ELEMTYPE(arrayval),
+					  elmlen, elmbyval, elmalign,
+					  &elem_values, &elem_nulls, &num_elems);
+
+	/*
+	 * Compress out any null elements.  We can ignore them since we assume all
+	 * btree operators are strict.
+	 */
+	num_nonnulls = 0;
+	for (int j = 0; j < num_elems; j++)
+	{
+		if (!elem_nulls[j])
+			elem_values[num_nonnulls++] = elem_values[j];
+	}
+
+	/* Look up the appropriate same-type comparison function in the opfamily */
+	get_op_opfamily_properties(opno, opfamily, false, &op_strategy,
+							   &op_lefttype, &op_righttype);
+	cmp_proc = get_opfamily_proc(opfamily, op_righttype, op_righttype,
+								 BTORDER_PROC);
+	if (!RegProcedureIsValid(cmp_proc))
+		elog(ERROR, "missing support function %d(%u,%u)",
+			 BTORDER_PROC, op_righttype, op_righttype);
+
+	/* Set same-type ORDER proc for caller */
+	fmgr_info(cmp_proc, &sortproc);
+
+	/* Sort the non-null elements and eliminate any duplicates */
+	if (num_nonnulls > 1)
+	{
+		BTSortArrayContext cxt;
+
+		/* Sort the array elements */
+		cxt.sortproc = &sortproc;
+		cxt.collation = collation;
+		cxt.reverse = reverse;
+		qsort_arg(elem_values, num_nonnulls, sizeof(Datum),
+				  _bt_compare_array_elements, &cxt);
+
+		/* Now scan the sorted elements and remove duplicates */
+		num_nonnulls = qunique_arg(elem_values, num_nonnulls, sizeof(Datum),
+								   _bt_compare_array_elements, &cxt);
+	}
+
+	return PointerGetDatum(construct_array(elem_values, num_nonnulls,
+										   ARR_ELEMTYPE(arrayval),
+										   elmlen, elmbyval, elmalign));
+
+}
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c
index 7fcaa37fe..04ae671d7 100644
--- a/src/backend/executor/nodeIndexscan.c
+++ b/src/backend/executor/nodeIndexscan.c
@@ -1510,6 +1510,12 @@ ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
 					scanvalue = ((Const *) rightop)->constvalue;
 					if (((Const *) rightop)->constisnull)
 						flags |= SK_ISNULL;
+
+					/*
+					 * Const SAOP arrays are presorted during planning (with
+					 * indexes whose index AM is amsearcharray)
+					 */
+					flags |= SK_PRESORTED;
 				}
 				else
 				{
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index bfefc7dbe..4757cd6f2 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -18,6 +18,7 @@
 
 #include <math.h>
 
+#include "access/nbtree.h"
 #include "access/sysattr.h"
 #include "catalog/pg_class.h"
 #include "foreign/fdwapi.h"
@@ -5280,11 +5281,29 @@ fix_indexqual_clause(PlannerInfo *root, IndexOptInfo *index, int indexcol,
 	else if (IsA(clause, ScalarArrayOpExpr))
 	{
 		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+		Expr	   *arrayarg;
+		Const	   *arrayargconst = NULL;
 
 		/* Replace the indexkey expression with an index Var. */
 		linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
 													 index,
 													 indexcol);
+
+		/*
+		 * amsearcharray index AMs generally work with a sorted array at
+		 * runtime.  If a SAOP array argument is a Const, we presort here.
+		 * This avoids repeating sorting/deduplicating work across rescans.
+		 */
+		Assert(list_length(saop->args) == 2);
+		arrayarg = (Expr *) lsecond(saop->args);
+		if (index->amsearcharray && IsA(arrayarg, Const))
+			arrayargconst = (Const *) arrayarg;
+		if (arrayargconst && !arrayargconst->constisnull)
+			arrayargconst->constvalue =
+				_bt_presort_const_array(arrayargconst->constvalue,
+										saop->opno, index->opfamily[indexcol],
+										index->indexcollations[indexcol],
+										index->reverse_sort[indexcol]);
 	}
 	else if (IsA(clause, NullTest))
 	{
diff --git a/src/test/regress/expected/btree_index.out b/src/test/regress/expected/btree_index.out
index 21dc9b578..d78adcdcf 100644
--- a/src/test/regress/expected/btree_index.out
+++ b/src/test/regress/expected/btree_index.out
@@ -296,7 +296,7 @@ ORDER BY proname, proargtypes, pronamespace;
                                                                                                      QUERY PLAN                                                                                                     
 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Index Only Scan using pg_proc_proname_args_nsp_index on pg_proc
-   Index Cond: ((ROW(proname, proargtypes) > ROW('abs'::name, NULL::oidvector)) AND (proname = 'zzzzzz'::name) AND (proargtypes = ANY ('{"26 23",5077}'::oidvector[])) AND (pronamespace = ANY ('{1,2,3}'::oid[])))
+   Index Cond: ((ROW(proname, proargtypes) > ROW('abs'::name, NULL::oidvector)) AND (proname = 'zzzzzz'::name) AND (proargtypes = ANY ('{5077,"26 23"}'::oidvector[])) AND (pronamespace = ANY ('{1,2,3}'::oid[])))
 (2 rows)
 
 SELECT proname, proargtypes, pronamespace
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 98e68e972..055b8a064 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -2287,7 +2287,7 @@ ORDER BY unique1;
                       QUERY PLAN                       
 -------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: (unique1 = ANY ('{1,42,7}'::integer[]))
+   Index Cond: (unique1 = ANY ('{1,7,42}'::integer[]))
 (2 rows)
 
 SELECT unique1 FROM tenk1
@@ -2367,7 +2367,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = ANY('{7, 8,
                                              QUERY PLAN                                             
 ----------------------------------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 = ANY ('{7,8,9}'::integer[])))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 = ANY ('{7,8,9}'::integer[])))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = ANY('{7, 8, 9}');
@@ -2404,10 +2404,10 @@ SELECT unique1 FROM tenk1 WHERE unique1 = ANY(NULL);
 
 explain (costs off)
 SELECT unique1 FROM tenk1 WHERE unique1 = ANY('{NULL,NULL,NULL}');
-                          QUERY PLAN                           
----------------------------------------------------------------
+                   QUERY PLAN                    
+-------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: (unique1 = ANY ('{NULL,NULL,NULL}'::integer[]))
+   Index Cond: (unique1 = ANY ('{}'::integer[]))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 = ANY('{NULL,NULL,NULL}');
@@ -2433,7 +2433,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = 1;
                                 QUERY PLAN                                 
 ---------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 = 1))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 = 1))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = 1;
@@ -2447,7 +2447,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = 12345;
                                   QUERY PLAN                                   
 -------------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 = 12345))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 = 12345))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 = 12345;
@@ -2460,7 +2460,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 >= 42;
                                  QUERY PLAN                                  
 -----------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 >= 42))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 >= 42))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 >= 42;
@@ -2474,7 +2474,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 > 42;
                                  QUERY PLAN                                 
 ----------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 > 42))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 > 42))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 > 42;
@@ -2530,7 +2530,7 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 < (-1)::bigint
                                       QUERY PLAN                                      
 --------------------------------------------------------------------------------------
  Index Only Scan using tenk1_unique1 on tenk1
-   Index Cond: ((unique1 = ANY ('{1,42,7}'::integer[])) AND (unique1 < '-1'::bigint))
+   Index Cond: ((unique1 = ANY ('{1,7,42}'::integer[])) AND (unique1 < '-1'::bigint))
 (2 rows)
 
 SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 < (-1)::bigint;
-- 
2.50.0