Relax ordering-related hardcoded btree requirements in planning

There were several places in ordering-related planning where a
requirement for btree was hardcoded but an amcanorder index could
suffice.  This fixes that.  We just need to do the necessary mapping
between strategy numbers and compare types and adjust some related
APIs so that this works independent of btree strategy numbers.  For
instance, non-btree amcanorder indexes can now be used to support
sorting and merge joins.  Also, predtest.c works independent of btree
strategy numbers now.

To avoid performance regressions, some details on btree and other
built-in index types are still hardcoded as shortcuts, but other index
types now have access to the same features by providing the required
flags and callbacks.

Author: Mark Dilger <mark.dilger@enterprisedb.com>
Co-authored-by: Peter Eisentraut <peter@eisentraut.org>
Discussion: https://www.postgresql.org/message-id/flat/E72EAA49-354D-4C2E-8EB9-255197F55330@enterprisedb.com

1 files changed, 111 insertions, 54 deletions

diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 82031c1e8e5..c460a72b75d 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -207,10 +207,45 @@ get_opfamily_member_for_cmptype(Oid opfamily, Oid lefttype, Oid righttype,
 }
 
 /*
+ * get_opmethod_canorder
+ *		Return amcanorder field for given index AM.
+ *
+ * To speed things up in the common cases, we're hardcoding the results from
+ * the built-in index types.  Note that we also need to hardcode the negative
+ * results from the built-in non-btree index types, since you'll usually get a
+ * few hits for those as well.  It would be nice to organize and cache this a
+ * bit differently to avoid the hardcoding.
+ */
+static bool
+get_opmethod_canorder(Oid amoid)
+{
+	switch (amoid)
+	{
+		case BTREE_AM_OID:
+			return true;
+		case HASH_AM_OID:
+		case GIST_AM_OID:
+		case GIN_AM_OID:
+		case SPGIST_AM_OID:
+		case BRIN_AM_OID:
+			return false;
+		default:
+			{
+				bool		result;
+				IndexAmRoutine *amroutine = GetIndexAmRoutineByAmId(amoid, false);
+
+				result = amroutine->amcanorder;
+				pfree(amroutine);
+				return result;
+			}
+	}
+}
+
+/*
  * get_ordering_op_properties
- *		Given the OID of an ordering operator (a btree "<" or ">" operator),
+ *		Given the OID of an ordering operator (a "<" or ">" operator),
  *		determine its opfamily, its declared input datatype, and its
- *		strategy number (BTLessStrategyNumber or BTGreaterStrategyNumber).
+ *		comparison type.
  *
  * Returns true if successful, false if no matching pg_amop entry exists.
  * (This indicates that the operator is not a valid ordering operator.)
@@ -228,7 +263,7 @@ get_opfamily_member_for_cmptype(Oid opfamily, Oid lefttype, Oid righttype,
  */
 bool
 get_ordering_op_properties(Oid opno,
-						   Oid *opfamily, Oid *opcintype, int16 *strategy)
+						   Oid *opfamily, Oid *opcintype, CompareType *cmptype)
 {
 	bool		result = false;
 	CatCList   *catlist;
@@ -237,7 +272,7 @@ get_ordering_op_properties(Oid opno,
 	/* ensure outputs are initialized on failure */
 	*opfamily = InvalidOid;
 	*opcintype = InvalidOid;
-	*strategy = 0;
+	*cmptype = COMPARE_INVALID;
 
 	/*
 	 * Search pg_amop to see if the target operator is registered as the "<"
@@ -249,13 +284,18 @@ get_ordering_op_properties(Oid opno,
 	{
 		HeapTuple	tuple = &catlist->members[i]->tuple;
 		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+		CompareType am_cmptype;
 
-		/* must be btree */
-		if (aform->amopmethod != BTREE_AM_OID)
+		/* must be ordering index */
+		if (!get_opmethod_canorder(aform->amopmethod))
 			continue;
 
-		if (aform->amopstrategy == BTLessStrategyNumber ||
-			aform->amopstrategy == BTGreaterStrategyNumber)
+		am_cmptype = IndexAmTranslateStrategy(aform->amopstrategy,
+											  aform->amopmethod,
+											  aform->amopfamily,
+											  true);
+
+		if (am_cmptype == COMPARE_LT || am_cmptype == COMPARE_GT)
 		{
 			/* Found it ... should have consistent input types */
 			if (aform->amoplefttype == aform->amoprighttype)
@@ -263,7 +303,7 @@ get_ordering_op_properties(Oid opno,
 				/* Found a suitable opfamily, return info */
 				*opfamily = aform->amopfamily;
 				*opcintype = aform->amoplefttype;
-				*strategy = aform->amopstrategy;
+				*cmptype = am_cmptype;
 				result = true;
 				break;
 			}
@@ -277,7 +317,7 @@ get_ordering_op_properties(Oid opno,
 
 /*
  * get_equality_op_for_ordering_op
- *		Get the OID of the datatype-specific btree equality operator
+ *		Get the OID of the datatype-specific equality operator
  *		associated with an ordering operator (a "<" or ">" operator).
  *
  * If "reverse" isn't NULL, also set *reverse to false if the operator is "<",
@@ -292,19 +332,19 @@ get_equality_op_for_ordering_op(Oid opno, bool *reverse)
 	Oid			result = InvalidOid;
 	Oid			opfamily;
 	Oid			opcintype;
-	int16		strategy;
+	CompareType cmptype;
 
 	/* Find the operator in pg_amop */
 	if (get_ordering_op_properties(opno,
-								   &opfamily, &opcintype, &strategy))
+								   &opfamily, &opcintype, &cmptype))
 	{
 		/* Found a suitable opfamily, get matching equality operator */
-		result = get_opfamily_member(opfamily,
-									 opcintype,
-									 opcintype,
-									 BTEqualStrategyNumber);
+		result = get_opfamily_member_for_cmptype(opfamily,
+												 opcintype,
+												 opcintype,
+												 COMPARE_EQ);
 		if (reverse)
-			*reverse = (strategy == BTGreaterStrategyNumber);
+			*reverse = (cmptype == COMPARE_GT);
 	}
 
 	return result;
@@ -312,7 +352,7 @@ get_equality_op_for_ordering_op(Oid opno, bool *reverse)
 
 /*
  * get_ordering_op_for_equality_op
- *		Get the OID of a datatype-specific btree "less than" ordering operator
+ *		Get the OID of a datatype-specific "less than" ordering operator
  *		associated with an equality operator.  (If there are multiple
  *		possibilities, assume any one will do.)
  *
@@ -341,20 +381,25 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
 	{
 		HeapTuple	tuple = &catlist->members[i]->tuple;
 		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+		CompareType cmptype;
 
-		/* must be btree */
-		if (aform->amopmethod != BTREE_AM_OID)
+		/* must be ordering index */
+		if (!get_opmethod_canorder(aform->amopmethod))
 			continue;
 
-		if (aform->amopstrategy == BTEqualStrategyNumber)
+		cmptype = IndexAmTranslateStrategy(aform->amopstrategy,
+										   aform->amopmethod,
+										   aform->amopfamily,
+										   true);
+		if (cmptype == COMPARE_EQ)
 		{
 			/* Found a suitable opfamily, get matching ordering operator */
 			Oid			typid;
 
 			typid = use_lhs_type ? aform->amoplefttype : aform->amoprighttype;
-			result = get_opfamily_member(aform->amopfamily,
-										 typid, typid,
-										 BTLessStrategyNumber);
+			result = get_opfamily_member_for_cmptype(aform->amopfamily,
+													 typid, typid,
+													 COMPARE_LT);
 			if (OidIsValid(result))
 				break;
 			/* failure probably shouldn't happen, but keep looking if so */
@@ -369,7 +414,7 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
 /*
  * get_mergejoin_opfamilies
  *		Given a putatively mergejoinable operator, return a list of the OIDs
- *		of the btree opfamilies in which it represents equality.
+ *		of the amcanorder opfamilies in which it represents equality.
  *
  * It is possible (though at present unusual) for an operator to be equality
  * in more than one opfamily, hence the result is a list.  This also lets us
@@ -394,7 +439,7 @@ get_mergejoin_opfamilies(Oid opno)
 
 	/*
 	 * Search pg_amop to see if the target operator is registered as the "="
-	 * operator of any btree opfamily.
+	 * operator of any opfamily of an ordering index type.
 	 */
 	catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno));
 
@@ -403,9 +448,12 @@ get_mergejoin_opfamilies(Oid opno)
 		HeapTuple	tuple = &catlist->members[i]->tuple;
 		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
 
-		/* must be btree equality */
-		if (aform->amopmethod == BTREE_AM_OID &&
-			aform->amopstrategy == BTEqualStrategyNumber)
+		/* must be ordering index equality */
+		if (get_opmethod_canorder(aform->amopmethod) &&
+			IndexAmTranslateStrategy(aform->amopstrategy,
+									 aform->amopmethod,
+									 aform->amopfamily,
+									 true) == COMPARE_EQ)
 			result = lappend_oid(result, aform->amopfamily);
 	}
 
@@ -611,20 +659,20 @@ get_op_hash_functions(Oid opno,
 }
 
 /*
- * get_op_btree_interpretation
- *		Given an operator's OID, find out which btree opfamilies it belongs to,
+ * get_op_index_interpretation
+ *		Given an operator's OID, find out which amcanorder opfamilies it belongs to,
  *		and what properties it has within each one.  The results are returned
- *		as a palloc'd list of OpBtreeInterpretation structs.
+ *		as a palloc'd list of OpIndexInterpretation structs.
  *
  * In addition to the normal btree operators, we consider a <> operator to be
  * a "member" of an opfamily if its negator is an equality operator of the
  * opfamily.  COMPARE_NE is returned as the strategy number for this case.
  */
 List *
-get_op_btree_interpretation(Oid opno)
+get_op_index_interpretation(Oid opno)
 {
 	List	   *result = NIL;
-	OpBtreeInterpretation *thisresult;
+	OpIndexInterpretation *thisresult;
 	CatCList   *catlist;
 	int			i;
 
@@ -637,20 +685,26 @@ get_op_btree_interpretation(Oid opno)
 	{
 		HeapTuple	op_tuple = &catlist->members[i]->tuple;
 		Form_pg_amop op_form = (Form_pg_amop) GETSTRUCT(op_tuple);
-		StrategyNumber op_strategy;
+		CompareType cmptype;
 
-		/* must be btree */
-		if (op_form->amopmethod != BTREE_AM_OID)
+		/* must be ordering index */
+		if (!get_opmethod_canorder(op_form->amopmethod))
 			continue;
 
-		/* Get the operator's btree strategy number */
-		op_strategy = (StrategyNumber) op_form->amopstrategy;
-		Assert(op_strategy >= 1 && op_strategy <= 5);
+		/* Get the operator's comparision type */
+		cmptype = IndexAmTranslateStrategy(op_form->amopstrategy,
+										   op_form->amopmethod,
+										   op_form->amopfamily,
+										   true);
+
+		/* should not happen */
+		if (cmptype == COMPARE_INVALID)
+			continue;
 
-		thisresult = (OpBtreeInterpretation *)
-			palloc(sizeof(OpBtreeInterpretation));
+		thisresult = (OpIndexInterpretation *)
+			palloc(sizeof(OpIndexInterpretation));
 		thisresult->opfamily_id = op_form->amopfamily;
-		thisresult->strategy = op_strategy;
+		thisresult->cmptype = cmptype;
 		thisresult->oplefttype = op_form->amoplefttype;
 		thisresult->oprighttype = op_form->amoprighttype;
 		result = lappend(result, thisresult);
@@ -675,25 +729,28 @@ get_op_btree_interpretation(Oid opno)
 			{
 				HeapTuple	op_tuple = &catlist->members[i]->tuple;
 				Form_pg_amop op_form = (Form_pg_amop) GETSTRUCT(op_tuple);
-				StrategyNumber op_strategy;
+				IndexAmRoutine *amroutine = GetIndexAmRoutineByAmId(op_form->amopmethod, false);
+				CompareType cmptype;
 
-				/* must be btree */
-				if (op_form->amopmethod != BTREE_AM_OID)
+				/* must be ordering index */
+				if (!amroutine->amcanorder)
 					continue;
 
-				/* Get the operator's btree strategy number */
-				op_strategy = (StrategyNumber) op_form->amopstrategy;
-				Assert(op_strategy >= 1 && op_strategy <= 5);
+				/* Get the operator's comparision type */
+				cmptype = IndexAmTranslateStrategy(op_form->amopstrategy,
+												   op_form->amopmethod,
+												   op_form->amopfamily,
+												   true);
 
 				/* Only consider negators that are = */
-				if (op_strategy != BTEqualStrategyNumber)
+				if (cmptype != COMPARE_EQ)
 					continue;
 
-				/* OK, report it with "strategy" COMPARE_NE */
-				thisresult = (OpBtreeInterpretation *)
-					palloc(sizeof(OpBtreeInterpretation));
+				/* OK, report it as COMPARE_NE */
+				thisresult = (OpIndexInterpretation *)
+					palloc(sizeof(OpIndexInterpretation));
 				thisresult->opfamily_id = op_form->amopfamily;
-				thisresult->strategy = COMPARE_NE;
+				thisresult->cmptype = COMPARE_NE;
 				thisresult->oplefttype = op_form->amoplefttype;
 				thisresult->oprighttype = op_form->amoprighttype;
 				result = lappend(result, thisresult);