Multirange datatypes

Multiranges are basically sorted arrays of non-overlapping ranges with
set-theoretic operations defined over them.

Since v14, each range type automatically gets a corresponding multirange
datatype.  There are both manual and automatic mechanisms for naming multirange
types.  Once can specify multirange type name using multirange_type_name
attribute in CREATE TYPE.  Otherwise, a multirange type name is generated
automatically.  If the range type name contains "range" then we change that to
"multirange".  Otherwise, we add "_multirange" to the end.

Implementation of multiranges comes with a space-efficient internal
representation format, which evades extra paddings and duplicated storage of
oids.  Altogether this format allows fetching a particular range by its index
in O(n).

Statistic gathering and selectivity estimation are implemented for multiranges.
For this purpose, stored multirange is approximated as union range without gaps.
This field will likely need improvements in the future.

Catversion is bumped.

Discussion: https://postgr.es/m/CALNJ-vSUpQ_Y%3DjXvTxt1VYFztaBSsWVXeF1y6gTYQ4bOiWDLgQ%40mail.gmail.com
Discussion: https://postgr.es/m/a0b8026459d1e6167933be2104a6174e7d40d0ab.camel%40j-davis.com#fe7218c83b08068bfffb0c5293eceda0
Author: Paul Jungwirth, revised by me
Reviewed-by: David Fetter, Corey Huinker, Jeff Davis, Pavel Stehule
Reviewed-by: Alvaro Herrera, Tom Lane, Isaac Morland, David G. Johnston
Reviewed-by: Zhihong Yu, Alexander Korotkov

1 files changed, 177 insertions, 3 deletions

diff --git a/src/backend/utils/fmgr/funcapi.c b/src/backend/utils/fmgr/funcapi.c
index 9696c88f241..f6fa4ab2fb2 100644
--- a/src/backend/utils/fmgr/funcapi.c
+++ b/src/backend/utils/fmgr/funcapi.c
@@ -35,6 +35,7 @@ typedef struct polymorphic_actuals
 	Oid			anyelement_type;	/* anyelement mapping, if known */
 	Oid			anyarray_type;	/* anyarray mapping, if known */
 	Oid			anyrange_type;	/* anyrange mapping, if known */
+	Oid			anymultirange_type; /* anymultirange mapping, if known */
 } polymorphic_actuals;
 
 static void shutdown_MultiFuncCall(Datum arg);
@@ -46,6 +47,7 @@ static TypeFuncClass internal_get_result_type(Oid funcid,
 static void resolve_anyelement_from_others(polymorphic_actuals *actuals);
 static void resolve_anyarray_from_others(polymorphic_actuals *actuals);
 static void resolve_anyrange_from_others(polymorphic_actuals *actuals);
+static void resolve_anymultirange_from_others(polymorphic_actuals *actuals);
 static bool resolve_polymorphic_tupdesc(TupleDesc tupdesc,
 										oidvector *declared_args,
 										Node *call_expr);
@@ -503,6 +505,34 @@ resolve_anyelement_from_others(polymorphic_actuals *actuals)
 							format_type_be(range_base_type))));
 		actuals->anyelement_type = range_typelem;
 	}
+	else if (OidIsValid(actuals->anymultirange_type))
+	{
+		/* Use the element type based on the multirange type */
+		Oid			multirange_base_type;
+		Oid			multirange_typelem;
+		Oid			range_base_type;
+		Oid			range_typelem;
+
+		multirange_base_type = getBaseType(actuals->anymultirange_type);
+		multirange_typelem = get_multirange_range(multirange_base_type);
+		if (!OidIsValid(multirange_typelem))
+			ereport(ERROR,
+					(errcode(ERRCODE_DATATYPE_MISMATCH),
+					 errmsg("argument declared %s is not a multirange type but type %s",
+							"anymultirange",
+							format_type_be(multirange_base_type))));
+
+		range_base_type = getBaseType(multirange_typelem);
+		range_typelem = get_range_subtype(range_base_type);
+
+		if (!OidIsValid(range_typelem))
+			ereport(ERROR,
+					(errcode(ERRCODE_DATATYPE_MISMATCH),
+					 errmsg("argument declared %s does not contain a range type but type %s",
+							"anymultirange",
+							format_type_be(range_base_type))));
+		actuals->anyelement_type = range_typelem;
+	}
 	else
 		elog(ERROR, "could not determine polymorphic type");
 }
@@ -540,10 +570,53 @@ static void
 resolve_anyrange_from_others(polymorphic_actuals *actuals)
 {
 	/*
-	 * We can't deduce a range type from other polymorphic inputs, because
-	 * there may be multiple range types with the same subtype.
+	 * We can't deduce a range type from other polymorphic array or base
+	 * types, because there may be multiple range types with the same subtype,
+	 * but we can deduce it from a polymorphic multirange type.
+	 */
+	if (OidIsValid(actuals->anymultirange_type))
+	{
+		/* Use the element type based on the multirange type */
+		Oid			multirange_base_type = getBaseType(actuals->anymultirange_type);
+		Oid			multirange_typelem = get_multirange_range(multirange_base_type);
+
+		if (!OidIsValid(multirange_typelem))
+			ereport(ERROR,
+					(errcode(ERRCODE_DATATYPE_MISMATCH),
+					 errmsg("argument declared %s is not a multirange type but type %s",
+							"anymultirange",
+							format_type_be(multirange_base_type))));
+		actuals->anyrange_type = multirange_typelem;
+	}
+	else
+		elog(ERROR, "could not determine polymorphic type");
+}
+
+/*
+ * Resolve actual type of ANYMULTIRANGE from other polymorphic inputs
+ */
+static void
+resolve_anymultirange_from_others(polymorphic_actuals *actuals)
+{
+	/*
+	 * We can't deduce a multirange type from polymorphic array or base types,
+	 * because there may be multiple range types with the same subtype, but we
+	 * can deduce it from a polymorphic range type.
 	 */
-	elog(ERROR, "could not determine polymorphic type");
+	if (OidIsValid(actuals->anyrange_type))
+	{
+		Oid			range_base_type = getBaseType(actuals->anyrange_type);
+		Oid			multirange_typeid = get_range_multirange(range_base_type);
+
+		if (!OidIsValid(multirange_typeid))
+			ereport(ERROR,
+					(errcode(ERRCODE_UNDEFINED_OBJECT),
+					 errmsg("could not find multirange type for data type %s",
+							format_type_be(actuals->anyrange_type))));
+		actuals->anymultirange_type = multirange_typeid;
+	}
+	else
+		elog(ERROR, "could not determine polymorphic type");
 }
 
 /*
@@ -566,9 +639,11 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 	bool		have_anyelement_result = false;
 	bool		have_anyarray_result = false;
 	bool		have_anyrange_result = false;
+	bool		have_anymultirange_result = false;
 	bool		have_anycompatible_result = false;
 	bool		have_anycompatible_array_result = false;
 	bool		have_anycompatible_range_result = false;
+	bool		have_anycompatible_multirange_result = false;
 	polymorphic_actuals poly_actuals;
 	polymorphic_actuals anyc_actuals;
 	Oid			anycollation = InvalidOid;
@@ -594,6 +669,10 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 				have_polymorphic_result = true;
 				have_anyrange_result = true;
 				break;
+			case ANYMULTIRANGEOID:
+				have_polymorphic_result = true;
+				have_anymultirange_result = true;
+				break;
 			case ANYCOMPATIBLEOID:
 			case ANYCOMPATIBLENONARRAYOID:
 				have_polymorphic_result = true;
@@ -607,6 +686,10 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 				have_polymorphic_result = true;
 				have_anycompatible_range_result = true;
 				break;
+			case ANYCOMPATIBLEMULTIRANGEOID:
+				have_polymorphic_result = true;
+				have_anycompatible_multirange_result = true;
+				break;
 			default:
 				break;
 		}
@@ -660,6 +743,15 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 						return false;
 				}
 				break;
+			case ANYMULTIRANGEOID:
+				if (!OidIsValid(poly_actuals.anymultirange_type))
+				{
+					poly_actuals.anymultirange_type =
+						get_call_expr_argtype(call_expr, i);
+					if (!OidIsValid(poly_actuals.anymultirange_type))
+						return false;
+				}
+				break;
 			case ANYCOMPATIBLEOID:
 			case ANYCOMPATIBLENONARRAYOID:
 				if (!OidIsValid(anyc_actuals.anyelement_type))
@@ -688,6 +780,15 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 						return false;
 				}
 				break;
+			case ANYCOMPATIBLEMULTIRANGEOID:
+				if (!OidIsValid(anyc_actuals.anymultirange_type))
+				{
+					anyc_actuals.anymultirange_type =
+						get_call_expr_argtype(call_expr, i);
+					if (!OidIsValid(anyc_actuals.anymultirange_type))
+						return false;
+				}
+				break;
 			default:
 				break;
 		}
@@ -703,6 +804,9 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 	if (have_anyrange_result && !OidIsValid(poly_actuals.anyrange_type))
 		resolve_anyrange_from_others(&poly_actuals);
 
+	if (have_anymultirange_result && !OidIsValid(poly_actuals.anymultirange_type))
+		resolve_anymultirange_from_others(&poly_actuals);
+
 	if (have_anycompatible_result && !OidIsValid(anyc_actuals.anyelement_type))
 		resolve_anyelement_from_others(&anyc_actuals);
 
@@ -712,6 +816,9 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 	if (have_anycompatible_range_result && !OidIsValid(anyc_actuals.anyrange_type))
 		resolve_anyrange_from_others(&anyc_actuals);
 
+	if (have_anycompatible_multirange_result && !OidIsValid(anyc_actuals.anymultirange_type))
+		resolve_anymultirange_from_others(&anyc_actuals);
+
 	/*
 	 * Identify the collation to use for polymorphic OUT parameters. (It'll
 	 * necessarily be the same for both anyelement and anyarray, likewise for
@@ -780,6 +887,14 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 								   0);
 				/* no collation should be attached to a range type */
 				break;
+			case ANYMULTIRANGEOID:
+				TupleDescInitEntry(tupdesc, i + 1,
+								   NameStr(att->attname),
+								   poly_actuals.anymultirange_type,
+								   -1,
+								   0);
+				/* no collation should be attached to a multirange type */
+				break;
 			case ANYCOMPATIBLEOID:
 			case ANYCOMPATIBLENONARRAYOID:
 				TupleDescInitEntry(tupdesc, i + 1,
@@ -805,6 +920,14 @@ resolve_polymorphic_tupdesc(TupleDesc tupdesc, oidvector *declared_args,
 								   0);
 				/* no collation should be attached to a range type */
 				break;
+			case ANYCOMPATIBLEMULTIRANGEOID:
+				TupleDescInitEntry(tupdesc, i + 1,
+								   NameStr(att->attname),
+								   anyc_actuals.anymultirange_type,
+								   -1,
+								   0);
+				/* no collation should be attached to a multirange type */
+				break;
 			default:
 				break;
 		}
@@ -834,9 +957,11 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 	bool		have_anyelement_result = false;
 	bool		have_anyarray_result = false;
 	bool		have_anyrange_result = false;
+	bool		have_anymultirange_result = false;
 	bool		have_anycompatible_result = false;
 	bool		have_anycompatible_array_result = false;
 	bool		have_anycompatible_range_result = false;
+	bool		have_anycompatible_multirange_result = false;
 	polymorphic_actuals poly_actuals;
 	polymorphic_actuals anyc_actuals;
 	int			inargno;
@@ -912,6 +1037,24 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 					argtypes[i] = poly_actuals.anyrange_type;
 				}
 				break;
+			case ANYMULTIRANGEOID:
+				if (argmode == PROARGMODE_OUT || argmode == PROARGMODE_TABLE)
+				{
+					have_polymorphic_result = true;
+					have_anymultirange_result = true;
+				}
+				else
+				{
+					if (!OidIsValid(poly_actuals.anymultirange_type))
+					{
+						poly_actuals.anymultirange_type =
+							get_call_expr_argtype(call_expr, inargno);
+						if (!OidIsValid(poly_actuals.anymultirange_type))
+							return false;
+					}
+					argtypes[i] = poly_actuals.anymultirange_type;
+				}
+				break;
 			case ANYCOMPATIBLEOID:
 			case ANYCOMPATIBLENONARRAYOID:
 				if (argmode == PROARGMODE_OUT || argmode == PROARGMODE_TABLE)
@@ -967,6 +1110,24 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 					argtypes[i] = anyc_actuals.anyrange_type;
 				}
 				break;
+			case ANYCOMPATIBLEMULTIRANGEOID:
+				if (argmode == PROARGMODE_OUT || argmode == PROARGMODE_TABLE)
+				{
+					have_polymorphic_result = true;
+					have_anycompatible_multirange_result = true;
+				}
+				else
+				{
+					if (!OidIsValid(anyc_actuals.anymultirange_type))
+					{
+						anyc_actuals.anymultirange_type =
+							get_call_expr_argtype(call_expr, inargno);
+						if (!OidIsValid(anyc_actuals.anymultirange_type))
+							return false;
+					}
+					argtypes[i] = anyc_actuals.anymultirange_type;
+				}
+				break;
 			default:
 				break;
 		}
@@ -988,6 +1149,9 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 	if (have_anyrange_result && !OidIsValid(poly_actuals.anyrange_type))
 		resolve_anyrange_from_others(&poly_actuals);
 
+	if (have_anymultirange_result && !OidIsValid(poly_actuals.anymultirange_type))
+		resolve_anymultirange_from_others(&poly_actuals);
+
 	if (have_anycompatible_result && !OidIsValid(anyc_actuals.anyelement_type))
 		resolve_anyelement_from_others(&anyc_actuals);
 
@@ -997,6 +1161,9 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 	if (have_anycompatible_range_result && !OidIsValid(anyc_actuals.anyrange_type))
 		resolve_anyrange_from_others(&anyc_actuals);
 
+	if (have_anycompatible_multirange_result && !OidIsValid(anyc_actuals.anymultirange_type))
+		resolve_anymultirange_from_others(&anyc_actuals);
+
 	/* And finally replace the output column types as needed */
 	for (i = 0; i < numargs; i++)
 	{
@@ -1013,6 +1180,9 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 			case ANYRANGEOID:
 				argtypes[i] = poly_actuals.anyrange_type;
 				break;
+			case ANYMULTIRANGEOID:
+				argtypes[i] = poly_actuals.anymultirange_type;
+				break;
 			case ANYCOMPATIBLEOID:
 			case ANYCOMPATIBLENONARRAYOID:
 				argtypes[i] = anyc_actuals.anyelement_type;
@@ -1023,6 +1193,9 @@ resolve_polymorphic_argtypes(int numargs, Oid *argtypes, char *argmodes,
 			case ANYCOMPATIBLERANGEOID:
 				argtypes[i] = anyc_actuals.anyrange_type;
 				break;
+			case ANYCOMPATIBLEMULTIRANGEOID:
+				argtypes[i] = anyc_actuals.anymultirange_type;
+				break;
 			default:
 				break;
 		}
@@ -1052,6 +1225,7 @@ get_type_func_class(Oid typid, Oid *base_typeid)
 		case TYPTYPE_BASE:
 		case TYPTYPE_ENUM:
 		case TYPTYPE_RANGE:
+		case TYPTYPE_MULTIRANGE:
 			return TYPEFUNC_SCALAR;
 		case TYPTYPE_DOMAIN:
 			*base_typeid = typid = getBaseType(typid);