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

16 files changed, 5404 insertions, 102 deletions

diff --git a/src/backend/catalog/pg_range.c b/src/backend/catalog/pg_range.c
index a606d8c3adb..91b0fb0611a 100644
--- a/src/backend/catalog/pg_range.c
+++ b/src/backend/catalog/pg_range.c
@@ -35,7 +35,7 @@
 void
 RangeCreate(Oid rangeTypeOid, Oid rangeSubType, Oid rangeCollation,
 			Oid rangeSubOpclass, RegProcedure rangeCanonical,
-			RegProcedure rangeSubDiff)
+			RegProcedure rangeSubDiff, Oid multirangeTypeOid)
 {
 	Relation	pg_range;
 	Datum		values[Natts_pg_range];
@@ -43,6 +43,7 @@ RangeCreate(Oid rangeTypeOid, Oid rangeSubType, Oid rangeCollation,
 	HeapTuple	tup;
 	ObjectAddress myself;
 	ObjectAddress referenced;
+	ObjectAddress referencing;
 	ObjectAddresses *addrs;
 
 	pg_range = table_open(RangeRelationId, RowExclusiveLock);
@@ -55,6 +56,7 @@ RangeCreate(Oid rangeTypeOid, Oid rangeSubType, Oid rangeCollation,
 	values[Anum_pg_range_rngsubopc - 1] = ObjectIdGetDatum(rangeSubOpclass);
 	values[Anum_pg_range_rngcanonical - 1] = ObjectIdGetDatum(rangeCanonical);
 	values[Anum_pg_range_rngsubdiff - 1] = ObjectIdGetDatum(rangeSubDiff);
+	values[Anum_pg_range_rngmultitypid - 1] = ObjectIdGetDatum(multirangeTypeOid);
 
 	tup = heap_form_tuple(RelationGetDescr(pg_range), values, nulls);
 
@@ -93,6 +95,12 @@ RangeCreate(Oid rangeTypeOid, Oid rangeSubType, Oid rangeCollation,
 	record_object_address_dependencies(&myself, addrs, DEPENDENCY_NORMAL);
 	free_object_addresses(addrs);
 
+	/* record multirange type's dependency on the range type */
+	referencing.classId = TypeRelationId;
+	referencing.objectId = multirangeTypeOid;
+	referencing.objectSubId = 0;
+	recordDependencyOn(&referencing, &myself, DEPENDENCY_INTERNAL);
+
 	table_close(pg_range, RowExclusiveLock);
 }
 
diff --git a/src/backend/catalog/pg_type.c b/src/backend/catalog/pg_type.c
index 4252875ef50..2aa686a640f 100644
--- a/src/backend/catalog/pg_type.c
+++ b/src/backend/catalog/pg_type.c
@@ -28,6 +28,7 @@
 #include "catalog/pg_proc.h"
 #include "catalog/pg_type.h"
 #include "commands/typecmds.h"
+#include "mb/pg_wchar.h"
 #include "miscadmin.h"
 #include "parser/scansup.h"
 #include "utils/acl.h"
@@ -37,6 +38,9 @@
 #include "utils/rel.h"
 #include "utils/syscache.h"
 
+static char *makeUniqueTypeName(const char *typeName, Oid typeNamespace,
+								bool tryOriginal);
+
 /* Potentially set by pg_upgrade_support functions */
 Oid			binary_upgrade_next_pg_type_oid = InvalidOid;
 
@@ -863,31 +867,10 @@ RenameTypeInternal(Oid typeOid, const char *newTypeName, Oid typeNamespace)
 char *
 makeArrayTypeName(const char *typeName, Oid typeNamespace)
 {
-	char	   *arr = (char *) palloc(NAMEDATALEN);
-	int			namelen = strlen(typeName);
-	int			i;
-
-	/*
-	 * The idea is to prepend underscores as needed until we make a name that
-	 * doesn't collide with anything...
-	 */
-	for (i = 1; i < NAMEDATALEN - 1; i++)
-	{
-		arr[i - 1] = '_';
-		if (i + namelen < NAMEDATALEN)
-			strcpy(arr + i, typeName);
-		else
-		{
-			memcpy(arr + i, typeName, NAMEDATALEN - i);
-			truncate_identifier(arr, NAMEDATALEN, false);
-		}
-		if (!SearchSysCacheExists2(TYPENAMENSP,
-								   CStringGetDatum(arr),
-								   ObjectIdGetDatum(typeNamespace)))
-			break;
-	}
+	char	   *arr;
 
-	if (i >= NAMEDATALEN - 1)
+	arr = makeUniqueTypeName(typeName, typeNamespace, false);
+	if (arr == NULL)
 		ereport(ERROR,
 				(errcode(ERRCODE_DUPLICATE_OBJECT),
 				 errmsg("could not form array type name for type \"%s\"",
@@ -958,3 +941,90 @@ moveArrayTypeName(Oid typeOid, const char *typeName, Oid typeNamespace)
 
 	return true;
 }
+
+
+/*
+ * makeMultirangeTypeName
+ *	  - given a range type name, make a multirange type name for it
+ *
+ * caller is responsible for pfreeing the result
+ */
+char *
+makeMultirangeTypeName(const char *rangeTypeName, Oid typeNamespace)
+{
+	char	   *buf;
+	char	   *rangestr;
+
+	/*
+	 * If the range type name contains "range" then change that to
+	 * "multirange". Otherwise add "_multirange" to the end.
+	 */
+	rangestr = strstr(rangeTypeName, "range");
+	if (rangestr)
+	{
+		char	   *prefix = pnstrdup(rangeTypeName, rangestr - rangeTypeName);
+
+		buf = psprintf("%s%s%s", prefix, "multi", rangestr);
+	}
+	else
+		buf = psprintf("%s_multirange", pnstrdup(rangeTypeName, NAMEDATALEN - 12));
+
+	/* clip it at NAMEDATALEN-1 bytes */
+	buf[pg_mbcliplen(buf, strlen(buf), NAMEDATALEN - 1)] = '\0';
+
+	if (SearchSysCacheExists2(TYPENAMENSP,
+							  CStringGetDatum(buf),
+							  ObjectIdGetDatum(typeNamespace)))
+		ereport(ERROR,
+				(errcode(ERRCODE_DUPLICATE_OBJECT),
+				 errmsg("type \"%s\" already exists", buf),
+				 errdetail("Failed while creating a multirange type for type \"%s\".", rangeTypeName),
+				 errhint("You can manually specify a multirange type name using the \"multirange_type_name\" attribute")));
+
+	return pstrdup(buf);
+}
+
+/*
+ * makeUniqueTypeName
+ *		Generate a unique name for a prospective new type
+ *
+ * Given a typeName, return a new palloc'ed name by preprending underscores
+ * until a non-conflicting name results.
+ *
+ * If tryOriginal, first try with zero underscores.
+ */
+static char *
+makeUniqueTypeName(const char *typeName, Oid typeNamespace, bool tryOriginal)
+{
+	int			i;
+	int			namelen;
+	char		dest[NAMEDATALEN];
+
+	Assert(strlen(typeName) <= NAMEDATALEN - 1);
+
+	if (tryOriginal &&
+		!SearchSysCacheExists2(TYPENAMENSP,
+							   CStringGetDatum(typeName),
+							   ObjectIdGetDatum(typeNamespace)))
+		return pstrdup(typeName);
+
+	/*
+	 * The idea is to prepend underscores as needed until we make a name that
+	 * doesn't collide with anything ...
+	 */
+	namelen = strlen(typeName);
+	for (i = 1; i < NAMEDATALEN - 1; i++)
+	{
+		dest[i - 1] = '_';
+		strlcpy(dest + i, typeName, NAMEDATALEN - i);
+		if (namelen + i >= NAMEDATALEN)
+			truncate_identifier(dest, NAMEDATALEN, false);
+
+		if (!SearchSysCacheExists2(TYPENAMENSP,
+								   CStringGetDatum(dest),
+								   ObjectIdGetDatum(typeNamespace)))
+			return pstrdup(dest);
+	}
+
+	return NULL;
+}
diff --git a/src/backend/commands/typecmds.c b/src/backend/commands/typecmds.c
index 7c0b2c3bf02..0fcd8c8f16e 100644
--- a/src/backend/commands/typecmds.c
+++ b/src/backend/commands/typecmds.c
@@ -107,9 +107,14 @@ typedef struct
 
 /* Potentially set by pg_upgrade_support functions */
 Oid			binary_upgrade_next_array_pg_type_oid = InvalidOid;
+Oid			binary_upgrade_next_mrng_pg_type_oid = InvalidOid;
+Oid			binary_upgrade_next_mrng_array_pg_type_oid = InvalidOid;
 
 static void makeRangeConstructors(const char *name, Oid namespace,
 								  Oid rangeOid, Oid subtype);
+static void makeMultirangeConstructors(const char *name, Oid namespace,
+									   Oid multirangeOid, Oid rangeOid,
+									   Oid rangeArrayOid, Oid *castFuncOid);
 static Oid	findTypeInputFunction(List *procname, Oid typeOid);
 static Oid	findTypeOutputFunction(List *procname, Oid typeOid);
 static Oid	findTypeReceiveFunction(List *procname, Oid typeOid);
@@ -772,7 +777,8 @@ DefineDomain(CreateDomainStmt *stmt)
 		typtype != TYPTYPE_COMPOSITE &&
 		typtype != TYPTYPE_DOMAIN &&
 		typtype != TYPTYPE_ENUM &&
-		typtype != TYPTYPE_RANGE)
+		typtype != TYPTYPE_RANGE &&
+		typtype != TYPTYPE_MULTIRANGE)
 		ereport(ERROR,
 				(errcode(ERRCODE_DATATYPE_MISMATCH),
 				 errmsg("\"%s\" is not a valid base type for a domain",
@@ -1323,6 +1329,11 @@ checkEnumOwner(HeapTuple tup)
 /*
  * DefineRange
  *		Registers a new range type.
+ *
+ * Perhaps it might be worthwhile to set pg_type.typelem to the base type,
+ * and likewise on multiranges to set it to the range type. But having a
+ * non-zero typelem is treated elsewhere as a synonym for being an array,
+ * and users might have queries with that same assumption.
  */
 ObjectAddress
 DefineRange(CreateRangeStmt *stmt)
@@ -1331,7 +1342,12 @@ DefineRange(CreateRangeStmt *stmt)
 	Oid			typeNamespace;
 	Oid			typoid;
 	char	   *rangeArrayName;
+	char	   *multirangeTypeName = NULL;
+	char	   *multirangeArrayName;
+	Oid			multirangeNamespace = InvalidOid;
 	Oid			rangeArrayOid;
+	Oid			multirangeOid;
+	Oid			multirangeArrayOid;
 	Oid			rangeSubtype = InvalidOid;
 	List	   *rangeSubOpclassName = NIL;
 	List	   *rangeCollationName = NIL;
@@ -1348,6 +1364,8 @@ DefineRange(CreateRangeStmt *stmt)
 	AclResult	aclresult;
 	ListCell   *lc;
 	ObjectAddress address;
+	ObjectAddress mltrngaddress;
+	Oid			castFuncOid;
 
 	/* Convert list of names to a name and namespace */
 	typeNamespace = QualifiedNameGetCreationNamespace(stmt->typeName,
@@ -1431,6 +1449,16 @@ DefineRange(CreateRangeStmt *stmt)
 						 errmsg("conflicting or redundant options")));
 			rangeSubtypeDiffName = defGetQualifiedName(defel);
 		}
+		else if (strcmp(defel->defname, "multirange_type_name") == 0)
+		{
+			if (multirangeTypeName != NULL)
+				ereport(ERROR,
+						(errcode(ERRCODE_SYNTAX_ERROR),
+						 errmsg("conflicting or redundant options")));
+			/* we can look up the subtype name immediately */
+			multirangeNamespace = QualifiedNameGetCreationNamespace(defGetQualifiedName(defel),
+																	&multirangeTypeName);
+		}
 		else
 			ereport(ERROR,
 					(errcode(ERRCODE_SYNTAX_ERROR),
@@ -1496,8 +1524,10 @@ DefineRange(CreateRangeStmt *stmt)
 	/* alignment must be TYPALIGN_INT or TYPALIGN_DOUBLE for ranges */
 	alignment = (subtypalign == TYPALIGN_DOUBLE) ? TYPALIGN_DOUBLE : TYPALIGN_INT;
 
-	/* Allocate OID for array type */
+	/* Allocate OID for array type, its multirange, and its multirange array */
 	rangeArrayOid = AssignTypeArrayOid();
+	multirangeOid = AssignTypeMultirangeOid();
+	multirangeArrayOid = AssignTypeMultirangeArrayOid();
 
 	/* Create the pg_type entry */
 	address =
@@ -1536,9 +1566,75 @@ DefineRange(CreateRangeStmt *stmt)
 	Assert(typoid == InvalidOid || typoid == address.objectId);
 	typoid = address.objectId;
 
+	/* Create the multirange that goes with it */
+	if (multirangeTypeName)
+	{
+		Oid		old_typoid;
+
+		/*
+		 * Look to see if multirange type already exists.
+		 */
+		old_typoid = GetSysCacheOid2(TYPENAMENSP, Anum_pg_type_oid,
+									 CStringGetDatum(multirangeTypeName),
+									 ObjectIdGetDatum(multirangeNamespace));
+
+		/*
+		 * If it's not a shell, see if it's an autogenerated array type, and if so
+		 * rename it out of the way.
+		 */
+		if (OidIsValid(old_typoid) && get_typisdefined(old_typoid))
+		{
+			if (!moveArrayTypeName(old_typoid, multirangeTypeName, multirangeNamespace))
+				ereport(ERROR,
+						(errcode(ERRCODE_DUPLICATE_OBJECT),
+						 errmsg("type \"%s\" already exists", multirangeTypeName)));
+		}
+	}
+	else
+	{
+		/* Generate multirange name automatically */
+		multirangeNamespace = typeNamespace;
+		multirangeTypeName = makeMultirangeTypeName(typeName, multirangeNamespace);
+	}
+
+	mltrngaddress =
+		TypeCreate(multirangeOid,	/* force assignment of this type OID */
+				   multirangeTypeName,	/* type name */
+				   multirangeNamespace,	/* namespace */
+				   InvalidOid,	/* relation oid (n/a here) */
+				   0,			/* relation kind (ditto) */
+				   GetUserId(), /* owner's ID */
+				   -1,			/* internal size (always varlena) */
+				   TYPTYPE_MULTIRANGE,	/* type-type (multirange type) */
+				   TYPCATEGORY_RANGE,	/* type-category (range type) */
+				   false,		/* multirange types are never preferred */
+				   DEFAULT_TYPDELIM,	/* array element delimiter */
+				   F_MULTIRANGE_IN, /* input procedure */
+				   F_MULTIRANGE_OUT,	/* output procedure */
+				   F_MULTIRANGE_RECV,	/* receive procedure */
+				   F_MULTIRANGE_SEND,	/* send procedure */
+				   InvalidOid,	/* typmodin procedure - none */
+				   InvalidOid,	/* typmodout procedure - none */
+				   F_MULTIRANGE_TYPANALYZE, /* analyze procedure */
+				   InvalidOid,	/* subscript procedure - none */
+				   InvalidOid,	/* element type ID - none */
+				   false,		/* this is not an array type */
+				   multirangeArrayOid,	/* array type we are about to create */
+				   InvalidOid,	/* base type ID (only for domains) */
+				   NULL,		/* never a default type value */
+				   NULL,		/* no binary form available either */
+				   false,		/* never passed by value */
+				   alignment,	/* alignment */
+				   'x',			/* TOAST strategy (always extended) */
+				   -1,			/* typMod (Domains only) */
+				   0,			/* Array dimensions of typbasetype */
+				   false,		/* Type NOT NULL */
+				   InvalidOid); /* type's collation (ranges never have one) */
+	Assert(multirangeOid == mltrngaddress.objectId);
+
 	/* Create the entry in pg_range */
 	RangeCreate(typoid, rangeSubtype, rangeCollation, rangeSubOpclass,
-				rangeCanonical, rangeSubtypeDiff);
+				rangeCanonical, rangeSubtypeDiff, multirangeOid);
 
 	/*
 	 * Create the array type that goes with it.
@@ -1580,8 +1676,54 @@ DefineRange(CreateRangeStmt *stmt)
 
 	pfree(rangeArrayName);
 
+	/* Create the multirange's array type */
+
+	multirangeArrayName = makeArrayTypeName(multirangeTypeName, typeNamespace);
+
+	TypeCreate(multirangeArrayOid,	/* force assignment of this type OID */
+			   multirangeArrayName, /* type name */
+			   multirangeNamespace,	/* namespace */
+			   InvalidOid,		/* relation oid (n/a here) */
+			   0,				/* relation kind (ditto) */
+			   GetUserId(),		/* owner's ID */
+			   -1,				/* internal size (always varlena) */
+			   TYPTYPE_BASE,	/* type-type (base type) */
+			   TYPCATEGORY_ARRAY,	/* type-category (array) */
+			   false,			/* array types are never preferred */
+			   DEFAULT_TYPDELIM,	/* array element delimiter */
+			   F_ARRAY_IN,		/* input procedure */
+			   F_ARRAY_OUT,		/* output procedure */
+			   F_ARRAY_RECV,	/* receive procedure */
+			   F_ARRAY_SEND,	/* send procedure */
+			   InvalidOid,		/* typmodin procedure - none */
+			   InvalidOid,		/* typmodout procedure - none */
+			   F_ARRAY_TYPANALYZE,	/* analyze procedure */
+			   F_ARRAY_SUBSCRIPT_HANDLER,	/* array subscript procedure */
+			   multirangeOid,	/* element type ID */
+			   true,			/* yes this is an array type */
+			   InvalidOid,		/* no further array type */
+			   InvalidOid,		/* base type ID */
+			   NULL,			/* never a default type value */
+			   NULL,			/* binary default isn't sent either */
+			   false,			/* never passed by value */
+			   alignment,		/* alignment - same as range's */
+			   'x',				/* ARRAY is always toastable */
+			   -1,				/* typMod (Domains only) */
+			   0,				/* Array dimensions of typbasetype */
+			   false,			/* Type NOT NULL */
+			   InvalidOid);		/* typcollation */
+
 	/* And create the constructor functions for this range type */
 	makeRangeConstructors(typeName, typeNamespace, typoid, rangeSubtype);
+	makeMultirangeConstructors(multirangeTypeName, typeNamespace,
+							   multirangeOid, typoid, rangeArrayOid,
+							   &castFuncOid);
+
+	/* Create cast from the range type to its multirange type */
+	CastCreate(typoid, multirangeOid, castFuncOid, 'e', 'f', DEPENDENCY_INTERNAL);
+
+	pfree(multirangeTypeName);
+	pfree(multirangeArrayName);
 
 	return address;
 }
@@ -1659,6 +1801,149 @@ makeRangeConstructors(const char *name, Oid namespace,
 	}
 }
 
+/*
+ * We make a separate multirange constructor for each range type
+ * so its name can include the base type, like range constructors do.
+ * If we had an anyrangearray polymorphic type we could use it here,
+ * but since each type has its own constructor name there's no need.
+ *
+ * Sets castFuncOid to the oid of the new constructor that can be used
+ * to cast from a range to a multirange.
+ */
+static void
+makeMultirangeConstructors(const char *name, Oid namespace,
+						   Oid multirangeOid, Oid rangeOid, Oid rangeArrayOid,
+						   Oid *castFuncOid)
+{
+	ObjectAddress myself,
+				referenced;
+	oidvector  *argtypes;
+	Datum		allParamTypes;
+	ArrayType  *allParameterTypes;
+	Datum		paramModes;
+	ArrayType  *parameterModes;
+
+	referenced.classId = TypeRelationId;
+	referenced.objectId = multirangeOid;
+	referenced.objectSubId = 0;
+
+	/* 0-arg constructor - for empty multiranges */
+	argtypes = buildoidvector(NULL, 0);
+	myself = ProcedureCreate(name,	/* name: same as multirange type */
+							 namespace,
+							 false, /* replace */
+							 false, /* returns set */
+							 multirangeOid, /* return type */
+							 BOOTSTRAP_SUPERUSERID, /* proowner */
+							 INTERNALlanguageId,	/* language */
+							 F_FMGR_INTERNAL_VALIDATOR,
+							 "multirange_constructor0", /* prosrc */
+							 NULL,	/* probin */
+							 PROKIND_FUNCTION,
+							 false, /* security_definer */
+							 false, /* leakproof */
+							 false, /* isStrict */
+							 PROVOLATILE_IMMUTABLE, /* volatility */
+							 PROPARALLEL_SAFE,	/* parallel safety */
+							 argtypes,	/* parameterTypes */
+							 PointerGetDatum(NULL), /* allParameterTypes */
+							 PointerGetDatum(NULL), /* parameterModes */
+							 PointerGetDatum(NULL), /* parameterNames */
+							 NIL,	/* parameterDefaults */
+							 PointerGetDatum(NULL), /* trftypes */
+							 PointerGetDatum(NULL), /* proconfig */
+							 InvalidOid,	/* prosupport */
+							 1.0,	/* procost */
+							 0.0);	/* prorows */
+
+	/*
+	 * Make the constructor internally-dependent on the multirange type so
+	 * that they go away silently when the type is dropped.  Note that pg_dump
+	 * depends on this choice to avoid dumping the constructors.
+	 */
+	recordDependencyOn(&myself, &referenced, DEPENDENCY_INTERNAL);
+	pfree(argtypes);
+
+	/*
+	 * 1-arg constructor - for casts
+	 *
+	 * In theory we shouldn't need both this and the vararg (n-arg)
+	 * constructor, but having a separate 1-arg function lets us define casts
+	 * against it.
+	 */
+	argtypes = buildoidvector(&rangeOid, 1);
+	myself = ProcedureCreate(name,	/* name: same as multirange type */
+							 namespace,
+							 false, /* replace */
+							 false, /* returns set */
+							 multirangeOid, /* return type */
+							 BOOTSTRAP_SUPERUSERID, /* proowner */
+							 INTERNALlanguageId,	/* language */
+							 F_FMGR_INTERNAL_VALIDATOR,
+							 "multirange_constructor1", /* prosrc */
+							 NULL,	/* probin */
+							 PROKIND_FUNCTION,
+							 false, /* security_definer */
+							 false, /* leakproof */
+							 true,	/* isStrict */
+							 PROVOLATILE_IMMUTABLE, /* volatility */
+							 PROPARALLEL_SAFE,	/* parallel safety */
+							 argtypes,	/* parameterTypes */
+							 PointerGetDatum(NULL), /* allParameterTypes */
+							 PointerGetDatum(NULL), /* parameterModes */
+							 PointerGetDatum(NULL), /* parameterNames */
+							 NIL,	/* parameterDefaults */
+							 PointerGetDatum(NULL), /* trftypes */
+							 PointerGetDatum(NULL), /* proconfig */
+							 InvalidOid,	/* prosupport */
+							 1.0,	/* procost */
+							 0.0);	/* prorows */
+	/* ditto */
+	recordDependencyOn(&myself, &referenced, DEPENDENCY_INTERNAL);
+	pfree(argtypes);
+	*castFuncOid = myself.objectId;
+
+	/* n-arg constructor - vararg */
+	argtypes = buildoidvector(&rangeArrayOid, 1);
+	allParamTypes = ObjectIdGetDatum(rangeArrayOid);
+	allParameterTypes = construct_array(&allParamTypes,
+										1, OIDOID,
+										sizeof(Oid), true, 'i');
+	paramModes = CharGetDatum(FUNC_PARAM_VARIADIC);
+	parameterModes = construct_array(&paramModes, 1, CHAROID,
+									 1, true, 'c');
+	myself = ProcedureCreate(name,	/* name: same as multirange type */
+							 namespace,
+							 false, /* replace */
+							 false, /* returns set */
+							 multirangeOid, /* return type */
+							 BOOTSTRAP_SUPERUSERID, /* proowner */
+							 INTERNALlanguageId,	/* language */
+							 F_FMGR_INTERNAL_VALIDATOR,
+							 "multirange_constructor2", /* prosrc */
+							 NULL,	/* probin */
+							 PROKIND_FUNCTION,
+							 false, /* security_definer */
+							 false, /* leakproof */
+							 false, /* isStrict */
+							 PROVOLATILE_IMMUTABLE, /* volatility */
+							 PROPARALLEL_SAFE,	/* parallel safety */
+							 argtypes,	/* parameterTypes */
+							 PointerGetDatum(allParameterTypes),	/* allParameterTypes */
+							 PointerGetDatum(parameterModes),	/* parameterModes */
+							 PointerGetDatum(NULL), /* parameterNames */
+							 NIL,	/* parameterDefaults */
+							 PointerGetDatum(NULL), /* trftypes */
+							 PointerGetDatum(NULL), /* proconfig */
+							 InvalidOid,	/* prosupport */
+							 1.0,	/* procost */
+							 0.0);	/* prorows */
+	/* ditto */
+	recordDependencyOn(&myself, &referenced, DEPENDENCY_INTERNAL);
+	pfree(argtypes);
+	pfree(allParameterTypes);
+	pfree(parameterModes);
+}
 
 /*
  * Find suitable I/O and other support functions for a type.
@@ -2152,6 +2437,72 @@ AssignTypeArrayOid(void)
 	return type_array_oid;
 }
 
+/*
+ *	AssignTypeMultirangeOid
+ *
+ *	Pre-assign the range type's multirange OID for use in pg_type.oid
+ */
+Oid
+AssignTypeMultirangeOid(void)
+{
+	Oid			type_multirange_oid;
+
+	/* Use binary-upgrade override for pg_type.oid? */
+	if (IsBinaryUpgrade)
+	{
+		if (!OidIsValid(binary_upgrade_next_mrng_pg_type_oid))
+			ereport(ERROR,
+					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+					 errmsg("pg_type multirange OID value not set when in binary upgrade mode")));
+
+		type_multirange_oid = binary_upgrade_next_mrng_pg_type_oid;
+		binary_upgrade_next_mrng_pg_type_oid = InvalidOid;
+	}
+	else
+	{
+		Relation	pg_type = table_open(TypeRelationId, AccessShareLock);
+
+		type_multirange_oid = GetNewOidWithIndex(pg_type, TypeOidIndexId,
+												 Anum_pg_type_oid);
+		table_close(pg_type, AccessShareLock);
+	}
+
+	return type_multirange_oid;
+}
+
+/*
+ *	AssignTypeMultirangeArrayOid
+ *
+ *	Pre-assign the range type's multirange array OID for use in pg_type.typarray
+ */
+Oid
+AssignTypeMultirangeArrayOid(void)
+{
+	Oid			type_multirange_array_oid;
+
+	/* Use binary-upgrade override for pg_type.oid? */
+	if (IsBinaryUpgrade)
+	{
+		if (!OidIsValid(binary_upgrade_next_mrng_array_pg_type_oid))
+			ereport(ERROR,
+					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+					 errmsg("pg_type multirange array OID value not set when in binary upgrade mode")));
+
+		type_multirange_array_oid = binary_upgrade_next_mrng_array_pg_type_oid;
+		binary_upgrade_next_mrng_array_pg_type_oid = InvalidOid;
+	}
+	else
+	{
+		Relation	pg_type = table_open(TypeRelationId, AccessShareLock);
+
+		type_multirange_array_oid = GetNewOidWithIndex(pg_type, TypeOidIndexId,
+													   Anum_pg_type_oid);
+		table_close(pg_type, AccessShareLock);
+	}
+
+	return type_multirange_array_oid;
+}
+
 
 /*-------------------------------------------------------------------
  * DefineCompositeType
diff --git a/src/backend/executor/functions.c b/src/backend/executor/functions.c
index 459a33375b1..ca8d637e73a 100644
--- a/src/backend/executor/functions.c
+++ b/src/backend/executor/functions.c
@@ -1711,7 +1711,8 @@ check_sql_fn_retval(List *queryTreeLists,
 	if (fn_typtype == TYPTYPE_BASE ||
 		fn_typtype == TYPTYPE_DOMAIN ||
 		fn_typtype == TYPTYPE_ENUM ||
-		fn_typtype == TYPTYPE_RANGE)
+		fn_typtype == TYPTYPE_RANGE ||
+		fn_typtype == TYPTYPE_MULTIRANGE)
 	{
 		/*
 		 * For scalar-type returns, the target list must have exactly one
diff --git a/src/backend/parser/parse_coerce.c b/src/backend/parser/parse_coerce.c
index da6c3ae4b5f..e33618f9744 100644
--- a/src/backend/parser/parse_coerce.c
+++ b/src/backend/parser/parse_coerce.c
@@ -190,19 +190,21 @@ coerce_type(ParseState *pstate, Node *node,
 	if (targetTypeId == ANYARRAYOID ||
 		targetTypeId == ANYENUMOID ||
 		targetTypeId == ANYRANGEOID ||
+		targetTypeId == ANYMULTIRANGEOID ||
 		targetTypeId == ANYCOMPATIBLEARRAYOID ||
-		targetTypeId == ANYCOMPATIBLERANGEOID)
+		targetTypeId == ANYCOMPATIBLERANGEOID ||
+		targetTypeId == ANYCOMPATIBLEMULTIRANGEOID)
 	{
 		/*
 		 * Assume can_coerce_type verified that implicit coercion is okay.
 		 *
 		 * These cases are unlike the ones above because the exposed type of
-		 * the argument must be an actual array, enum, or range type.  In
-		 * particular the argument must *not* be an UNKNOWN constant.  If it
-		 * is, we just fall through; below, we'll call the pseudotype's input
-		 * function, which will produce an error.  Also, if what we have is a
-		 * domain over array, enum, or range, we have to relabel it to its
-		 * base type.
+		 * the argument must be an actual array, enum, range, or multirange
+		 * type.  In particular the argument must *not* be an UNKNOWN
+		 * constant.  If it is, we just fall through; below, we'll call the
+		 * pseudotype's input function, which will produce an error.  Also, if
+		 * what we have is a domain over array, enum, range, or multirange, we
+		 * have to relabel it to its base type.
 		 *
 		 * Note: currently, we can't actually see a domain-over-enum here,
 		 * since the other functions in this file will not match such a
@@ -1570,8 +1572,8 @@ select_common_typmod(ParseState *pstate, List *exprs, Oid common_type)
  * 1) All arguments declared ANYELEMENT must have the same datatype.
  * 2) All arguments declared ANYARRAY must have the same datatype,
  *	  which must be a varlena array type.
- * 3) All arguments declared ANYRANGE must have the same datatype,
- *	  which must be a range type.
+ * 3) All arguments declared ANYRANGE or ANYMULTIRANGE must be a range or
+ *	  multirange type, all derived from the same base datatype.
  * 4) If there are arguments of more than one of these polymorphic types,
  *	  the array element type and/or range subtype must be the same as each
  *	  other and the same as the ANYELEMENT type.
@@ -1586,8 +1588,8 @@ select_common_typmod(ParseState *pstate, List *exprs, Oid common_type)
  *	  to a common supertype (chosen as per select_common_type's rules).
  *	  ANYCOMPATIBLENONARRAY works like ANYCOMPATIBLE but also requires the
  *	  common supertype to not be an array.  If there are ANYCOMPATIBLEARRAY
- *	  or ANYCOMPATIBLERANGE arguments, their element types or subtypes are
- *	  included while making the choice of common supertype.
+ *	  or ANYCOMPATIBLERANGE or ANYCOMPATIBLEMULTIRANGE arguments, their element
+ *	  types or subtypes are included while making the choice of common supertype.
  * 8) The resolved type of ANYCOMPATIBLEARRAY arguments will be the array
  *	  type over the common supertype (which might not be the same array type
  *	  as any of the original arrays).
@@ -1595,6 +1597,10 @@ select_common_typmod(ParseState *pstate, List *exprs, Oid common_type)
  *	  (after domain flattening), since we have no preference rule that would
  *	  let us choose one over another.  Furthermore, that range's subtype
  *	  must exactly match the common supertype chosen by rule 7.
+ * 10) All ANYCOMPATIBLEMULTIRANGE arguments must be the exact same multirange
+ *	  type (after domain flattening), since we have no preference rule that would
+ *	  let us choose one over another.  Furthermore, that multirange's range's
+ *	  subtype must exactly match the common supertype chosen by rule 7.
  *
  * Domains over arrays match ANYARRAY, and are immediately flattened to their
  * base type.  (Thus, for example, we will consider it a match if one ANYARRAY
@@ -1603,7 +1609,9 @@ select_common_typmod(ParseState *pstate, List *exprs, Oid common_type)
  * for ANYCOMPATIBLEARRAY and ANYCOMPATIBLENONARRAY.
  *
  * Similarly, domains over ranges match ANYRANGE or ANYCOMPATIBLERANGE,
- * and are immediately flattened to their base type.
+ * and are immediately flattened to their base type, and domains over
+ * multiranges match ANYMULTIRANGE or ANYCOMPATIBLEMULTIRANGE and are immediately
+ * flattened to their base type.
  *
  * Note that domains aren't currently considered to match ANYENUM,
  * even if their base type would match.
@@ -1621,8 +1629,12 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 	Oid			elem_typeid = InvalidOid;
 	Oid			array_typeid = InvalidOid;
 	Oid			range_typeid = InvalidOid;
+	Oid			multirange_typeid = InvalidOid;
 	Oid			anycompatible_range_typeid = InvalidOid;
 	Oid			anycompatible_range_typelem = InvalidOid;
+	Oid			anycompatible_multirange_typeid = InvalidOid;
+	Oid			anycompatible_multirange_typelem = InvalidOid;
+	Oid			range_typelem = InvalidOid;
 	bool		have_anynonarray = false;
 	bool		have_anyenum = false;
 	bool		have_anycompatible_nonarray = false;
@@ -1671,6 +1683,15 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 				return false;
 			range_typeid = actual_type;
 		}
+		else if (decl_type == ANYMULTIRANGEOID)
+		{
+			if (actual_type == UNKNOWNOID)
+				continue;
+			actual_type = getBaseType(actual_type); /* flatten domains */
+			if (OidIsValid(multirange_typeid) && actual_type != multirange_typeid)
+				return false;
+			multirange_typeid = actual_type;
+		}
 		else if (decl_type == ANYCOMPATIBLEOID ||
 				 decl_type == ANYCOMPATIBLENONARRAYOID)
 		{
@@ -1715,6 +1736,45 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 				anycompatible_actual_types[n_anycompatible_args++] = anycompatible_range_typelem;
 			}
 		}
+		else if (decl_type == ANYCOMPATIBLEMULTIRANGEOID)
+		{
+			if (actual_type == UNKNOWNOID)
+				continue;
+			actual_type = getBaseType(actual_type); /* flatten domains */
+			if (OidIsValid(anycompatible_multirange_typeid))
+			{
+				/* All ANYCOMPATIBLEMULTIRANGE arguments must be the same type */
+				if (anycompatible_multirange_typeid != actual_type)
+					return false;
+			}
+			else
+			{
+				anycompatible_multirange_typeid = actual_type;
+				anycompatible_multirange_typelem = get_multirange_range(actual_type);
+				if (!OidIsValid(anycompatible_multirange_typelem))
+					return false;	/* not a multirange type */
+
+				if (OidIsValid(anycompatible_range_typeid))
+				{
+					/*
+					 * ANYCOMPATIBLEMULTIRANGE and ANYCOMPATIBLERANGE
+					 * arguments must match
+					 */
+					if (anycompatible_range_typeid != anycompatible_multirange_typelem)
+						return false;
+				}
+				else
+				{
+					anycompatible_range_typeid = anycompatible_multirange_typelem;
+					anycompatible_range_typelem = get_range_subtype(anycompatible_range_typeid);
+					if (!OidIsValid(anycompatible_range_typelem))
+						return false;	/* not a range type */
+				}
+				/* collect the subtype for common-supertype choice */
+				anycompatible_actual_types[n_anycompatible_args++] =
+					anycompatible_range_typelem;
+			}
+		}
 	}
 
 	/* Get the element type based on the array type, if we have one */
@@ -1761,8 +1821,6 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 	/* Get the element type based on the range type, if we have one */
 	if (OidIsValid(range_typeid))
 	{
-		Oid			range_typelem;
-
 		range_typelem = get_range_subtype(range_typeid);
 		if (!OidIsValid(range_typelem))
 			return false;		/* should be a range, but isn't */
@@ -1781,6 +1839,45 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 		}
 	}
 
+	/* Get the element type based on the multirange type, if we have one */
+	if (OidIsValid(multirange_typeid))
+	{
+		Oid			multirange_typelem;
+
+		multirange_typelem = get_multirange_range(multirange_typeid);
+		if (!OidIsValid(multirange_typelem))
+			return false;		/* should be a multirange, but isn't */
+
+		if (!OidIsValid(range_typeid))
+		{
+			/*
+			 * If we don't have a range type yet, use the one we just got
+			 */
+			range_typeid = multirange_typelem;
+			range_typelem = get_range_subtype(multirange_typelem);
+			if (!OidIsValid(range_typelem))
+				return false;	/* should be a range, but isn't */
+		}
+		else if (multirange_typelem != range_typeid)
+		{
+			/* otherwise, they better match */
+			return false;
+		}
+
+		if (!OidIsValid(elem_typeid))
+		{
+			/*
+			 * If we don't have an element type yet, use the one we just got
+			 */
+			elem_typeid = range_typelem;
+		}
+		else if (range_typelem != elem_typeid)
+		{
+			/* otherwise, they better match */
+			return false;
+		}
+	}
+
 	if (have_anynonarray)
 	{
 		/* require the element type to not be an array or domain over array */
@@ -1819,8 +1916,10 @@ check_generic_type_consistency(const Oid *actual_arg_types,
 		}
 
 		/*
-		 * the anycompatible type must exactly match the range element type,
-		 * if we were able to identify one
+		 * The anycompatible type must exactly match the range element type,
+		 * if we were able to identify one. This checks compatibility for
+		 * anycompatiblemultirange too since that also sets
+		 * anycompatible_range_typelem above.
 		 */
 		if (OidIsValid(anycompatible_range_typelem) &&
 			anycompatible_range_typelem != anycompatible_typeid)
@@ -1859,21 +1958,27 @@ check_generic_type_consistency(const Oid *actual_arg_types,
  *	  argument's actual type as the function's return type.
  * 2) If return type is ANYARRAY, and any argument is ANYARRAY, use the
  *	  argument's actual type as the function's return type.
- * 3) Similarly, if return type is ANYRANGE, and any argument is ANYRANGE,
- *	  use the argument's actual type as the function's return type.
- * 4) Otherwise, if return type is ANYELEMENT or ANYARRAY, and there is
+ * 3) Similarly, if return type is ANYRANGE or ANYMULTIRANGE, and any
+ *	  argument is ANYRANGE or ANYMULTIRANGE, use that argument's
+ *	  actual type, range type or multirange type as the function's return
+ *	  type.
+ * 4) Otherwise, if return type is ANYMULTIRANGE, and any argument is
+ *	  ANYMULTIRANGE, use the argument's actual type as the function's return
+ *	  type. Or if any argument is ANYRANGE, use its multirange type as the
+ *	  function's return type.
+ * 5) Otherwise, if return type is ANYELEMENT or ANYARRAY, and there is
  *	  at least one ANYELEMENT, ANYARRAY, or ANYRANGE input, deduce the
  *	  return type from those inputs, or throw error if we can't.
- * 5) Otherwise, if return type is ANYRANGE, throw error.  (We have no way to
- *	  select a specific range type if the arguments don't include ANYRANGE.)
- * 6) ANYENUM is treated the same as ANYELEMENT except that if it is used
+ * 6) Otherwise, if return type is ANYRANGE or ANYMULTIRANGE, throw error.
+ *	  (We have no way to select a specific range type if the arguments don't
+ *	  include ANYRANGE.)
  *	  (alone or in combination with plain ANYELEMENT), we add the extra
  *	  condition that the ANYELEMENT type must be an enum.
- * 7) ANYNONARRAY is treated the same as ANYELEMENT except that if it is used,
+ * 8) ANYNONARRAY is treated the same as ANYELEMENT except that if it is used,
  *	  we add the extra condition that the ANYELEMENT type must not be an array.
  *	  (This is a no-op if used in combination with ANYARRAY or ANYENUM, but
  *	  is an extra restriction if not.)
- * 8) ANYCOMPATIBLE, ANYCOMPATIBLEARRAY, ANYCOMPATIBLENONARRAY, and
+ * 9) ANYCOMPATIBLE, ANYCOMPATIBLEARRAY, ANYCOMPATIBLENONARRAY, and
  *	  ANYCOMPATIBLERANGE are handled by resolving the common supertype
  *	  of those arguments (or their element types/subtypes, for array and range
  *	  inputs), and then coercing all those arguments to the common supertype,
@@ -1927,10 +2032,15 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 	Oid			elem_typeid = InvalidOid;
 	Oid			array_typeid = InvalidOid;
 	Oid			range_typeid = InvalidOid;
+	Oid			multirange_typeid = InvalidOid;
 	Oid			anycompatible_typeid = InvalidOid;
 	Oid			anycompatible_array_typeid = InvalidOid;
 	Oid			anycompatible_range_typeid = InvalidOid;
 	Oid			anycompatible_range_typelem = InvalidOid;
+	Oid			anycompatible_multirange_typeid = InvalidOid;
+	Oid			anycompatible_multirange_typelem = InvalidOid;
+	Oid			range_typelem;
+	Oid			multirange_typelem;
 	bool		have_anynonarray = (rettype == ANYNONARRAYOID);
 	bool		have_anyenum = (rettype == ANYENUMOID);
 	bool		have_anycompatible_nonarray = (rettype == ANYCOMPATIBLENONARRAYOID);
@@ -2015,6 +2125,26 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 								   format_type_be(actual_type))));
 			range_typeid = actual_type;
 		}
+		else if (decl_type == ANYMULTIRANGEOID)
+		{
+			n_poly_args++;
+			if (actual_type == UNKNOWNOID)
+			{
+				have_poly_unknowns = true;
+				continue;
+			}
+			if (allow_poly && decl_type == actual_type)
+				continue;		/* no new information here */
+			actual_type = getBaseType(actual_type); /* flatten domains */
+			if (OidIsValid(multirange_typeid) && actual_type != multirange_typeid)
+				ereport(ERROR,
+						(errcode(ERRCODE_DATATYPE_MISMATCH),
+						 errmsg("arguments declared \"anymultirange\" are not all alike"),
+						 errdetail("%s versus %s",
+								   format_type_be(multirange_typeid),
+								   format_type_be(actual_type))));
+			multirange_typeid = actual_type;
+		}
 		else if (decl_type == ANYCOMPATIBLEOID ||
 				 decl_type == ANYCOMPATIBLENONARRAYOID)
 		{
@@ -2083,6 +2213,40 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 				anycompatible_actual_types[n_anycompatible_args++] = anycompatible_range_typelem;
 			}
 		}
+		else if (decl_type == ANYCOMPATIBLEMULTIRANGEOID)
+		{
+			have_poly_anycompatible = true;
+			if (actual_type == UNKNOWNOID)
+				continue;
+			if (allow_poly && decl_type == actual_type)
+				continue;		/* no new information here */
+			actual_type = getBaseType(actual_type); /* flatten domains */
+			if (OidIsValid(anycompatible_multirange_typeid))
+			{
+				/* All ANYCOMPATIBLEMULTIRANGE arguments must be the same type */
+				if (anycompatible_multirange_typeid != actual_type)
+					ereport(ERROR,
+							(errcode(ERRCODE_DATATYPE_MISMATCH),
+							 errmsg("arguments declared \"anycompatiblemultirange\" are not all alike"),
+							 errdetail("%s versus %s",
+									   format_type_be(anycompatible_multirange_typeid),
+									   format_type_be(actual_type))));
+			}
+			else
+			{
+				anycompatible_multirange_typeid = actual_type;
+				anycompatible_multirange_typelem = get_multirange_range(actual_type);
+				anycompatible_range_typelem = get_range_subtype(anycompatible_multirange_typelem);
+				if (!OidIsValid(anycompatible_multirange_typelem))
+					ereport(ERROR,
+							(errcode(ERRCODE_DATATYPE_MISMATCH),
+							 errmsg("argument declared %s is not a multirange type but type %s",
+									"anycompatiblemultirange",
+									format_type_be(actual_type))));
+				/* collect the subtype for common-supertype choice */
+				anycompatible_actual_types[n_anycompatible_args++] = anycompatible_range_typelem;
+			}
+		}
 	}
 
 	/*
@@ -2151,8 +2315,6 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 		/* Get the element type based on the range type, if we have one */
 		if (OidIsValid(range_typeid))
 		{
-			Oid			range_typelem;
-
 			range_typelem = get_range_subtype(range_typeid);
 			if (!OidIsValid(range_typelem))
 				ereport(ERROR,
@@ -2181,6 +2343,61 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 								   format_type_be(elem_typeid))));
 			}
 		}
+		else
+			range_typelem = InvalidOid;
+
+		/* Get the element type based on the multirange type, if we have one */
+		if (OidIsValid(multirange_typeid))
+		{
+			multirange_typelem = get_multirange_range(multirange_typeid);
+			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_typeid))));
+
+			if (!OidIsValid(range_typeid))
+			{
+				/*
+				 * If we don't have a range type yet, use the one we just got
+				 */
+				range_typeid = multirange_typelem;
+				range_typelem = get_range_subtype(range_typeid);
+			}
+			else if (multirange_typelem != range_typeid)
+			{
+				/* otherwise, they better match */
+				ereport(ERROR,
+						(errcode(ERRCODE_DATATYPE_MISMATCH),
+						 errmsg("argument declared %s is not consistent with argument declared %s",
+								"anymultirange", "anyrange"),
+						 errdetail("%s versus %s",
+								   format_type_be(multirange_typeid),
+								   format_type_be(range_typeid))));
+			}
+
+			if (!OidIsValid(elem_typeid))
+			{
+				/*
+				 * if we don't have an element type yet, use the one we just got
+				 */
+				elem_typeid = range_typelem;
+			}
+			else if (range_typelem != elem_typeid)
+			{
+				/* otherwise, they better match */
+				ereport(ERROR,
+						(errcode(ERRCODE_DATATYPE_MISMATCH),
+						 errmsg("argument declared %s is not consistent with argument declared %s",
+								"anymultirange", "anyelement"),
+						 errdetail("%s versus %s",
+								   format_type_be(multirange_typeid),
+								   format_type_be(elem_typeid))));
+			}
+		}
+		else
+			multirange_typelem = InvalidOid;
 
 		if (!OidIsValid(elem_typeid))
 		{
@@ -2189,6 +2406,7 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 				elem_typeid = ANYELEMENTOID;
 				array_typeid = ANYARRAYOID;
 				range_typeid = ANYRANGEOID;
+				multirange_typeid = ANYMULTIRANGEOID;
 			}
 			else
 			{
@@ -2288,6 +2506,7 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 				anycompatible_typeid = ANYCOMPATIBLEOID;
 				anycompatible_array_typeid = ANYCOMPATIBLEARRAYOID;
 				anycompatible_range_typeid = ANYCOMPATIBLERANGEOID;
+				anycompatible_multirange_typeid = ANYCOMPATIBLEMULTIRANGEOID;
 			}
 			else
 			{
@@ -2319,6 +2538,8 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 				declared_arg_types[j] = anycompatible_array_typeid;
 			else if (decl_type == ANYCOMPATIBLERANGEOID)
 				declared_arg_types[j] = anycompatible_range_typeid;
+			else if (decl_type == ANYCOMPATIBLEMULTIRANGEOID)
+				declared_arg_types[j] = anycompatible_multirange_typeid;
 		}
 	}
 
@@ -2369,6 +2590,17 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 				}
 				declared_arg_types[j] = range_typeid;
 			}
+			else if (decl_type == ANYMULTIRANGEOID)
+			{
+				if (!OidIsValid(multirange_typeid))
+				{
+					ereport(ERROR,
+							(errcode(ERRCODE_UNDEFINED_OBJECT),
+							 errmsg("could not find multirange type for data type %s",
+									format_type_be(elem_typeid))));
+				}
+				declared_arg_types[j] = multirange_typeid;
+			}
 		}
 	}
 
@@ -2405,6 +2637,22 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 		return range_typeid;
 	}
 
+	/* if we return ANYMULTIRANGE use the appropriate argument type */
+	if (rettype == ANYMULTIRANGEOID)
+	{
+		if (!OidIsValid(multirange_typeid))
+		{
+			if (OidIsValid(range_typeid))
+				multirange_typeid = get_range_multirange(range_typeid);
+			else
+				ereport(ERROR,
+						(errcode(ERRCODE_UNDEFINED_OBJECT),
+						 errmsg("could not find multirange type for data type %s",
+								format_type_be(elem_typeid))));
+		}
+		return multirange_typeid;
+	}
+
 	/* if we return ANYCOMPATIBLE use the appropriate type */
 	if (rettype == ANYCOMPATIBLEOID ||
 		rettype == ANYCOMPATIBLENONARRAYOID)
@@ -2439,6 +2687,17 @@ enforce_generic_type_consistency(const Oid *actual_arg_types,
 		return anycompatible_range_typeid;
 	}
 
+	/* if we return ANYCOMPATIBLEMULTIRANGE use the appropriate argument type */
+	if (rettype == ANYCOMPATIBLEMULTIRANGEOID)
+	{
+		/* this error is unreachable if the function signature is valid: */
+		if (!OidIsValid(anycompatible_multirange_typeid))
+			ereport(ERROR,
+					(errcode(ERRCODE_DATATYPE_MISMATCH),
+					 errmsg_internal("could not identify anycompatiblemultirange type")));
+		return anycompatible_multirange_typeid;
+	}
+
 	/* we don't return a generic type; send back the original return type */
 	return rettype;
 }
@@ -2456,20 +2715,38 @@ check_valid_polymorphic_signature(Oid ret_type,
 								  const Oid *declared_arg_types,
 								  int nargs)
 {
-	if (ret_type == ANYRANGEOID || ret_type == ANYCOMPATIBLERANGEOID)
+	if (ret_type == ANYRANGEOID || ret_type == ANYMULTIRANGEOID)
 	{
 		/*
-		 * ANYRANGE requires an ANYRANGE input, else we can't tell which of
-		 * several range types with the same element type to use.  Likewise
-		 * for ANYCOMPATIBLERANGE.
+		 * ANYRANGE and ANYMULTIRANGE require an ANYRANGE or ANYMULTIRANGE
+		 * input, else we can't tell which of several range types with the
+		 * same element type to use.
 		 */
 		for (int i = 0; i < nargs; i++)
 		{
-			if (declared_arg_types[i] == ret_type)
+			if (declared_arg_types[i] == ANYRANGEOID ||
+				declared_arg_types[i] == ANYMULTIRANGEOID)
 				return NULL;	/* OK */
 		}
-		return psprintf(_("A result of type %s requires at least one input of type %s."),
-						format_type_be(ret_type), format_type_be(ret_type));
+		return psprintf(_("A result of type %s requires at least one input of type anyrange or anymultirange."),
+						format_type_be(ret_type));
+	}
+	else if (ret_type == ANYCOMPATIBLERANGEOID || ret_type == ANYCOMPATIBLEMULTIRANGEOID)
+	{
+		/*
+		 * ANYCOMPATIBLERANGE and ANYCOMPATIBLEMULTIRANGE require an
+		 * ANYCOMPATIBLERANGE or ANYCOMPATIBLEMULTIRANGE input, else we can't
+		 * tell which of several range types with the same element type to
+		 * use.
+		 */
+		for (int i = 0; i < nargs; i++)
+		{
+			if (declared_arg_types[i] == ANYCOMPATIBLERANGEOID ||
+				declared_arg_types[i] == ANYCOMPATIBLEMULTIRANGEOID)
+				return NULL;	/* OK */
+		}
+		return psprintf(_("A result of type %s requires at least one input of type anycompatiblerange or anycompatiblemultirange."),
+						format_type_be(ret_type));
 	}
 	else if (IsPolymorphicTypeFamily1(ret_type))
 	{
@@ -2480,7 +2757,7 @@ check_valid_polymorphic_signature(Oid ret_type,
 				return NULL;	/* OK */
 		}
 		/* Keep this list in sync with IsPolymorphicTypeFamily1! */
-		return psprintf(_("A result of type %s requires at least one input of type anyelement, anyarray, anynonarray, anyenum, or anyrange."),
+		return psprintf(_("A result of type %s requires at least one input of type anyelement, anyarray, anynonarray, anyenum, anyrange, or anymultirange."),
 						format_type_be(ret_type));
 	}
 	else if (IsPolymorphicTypeFamily2(ret_type))
@@ -2632,6 +2909,11 @@ IsBinaryCoercible(Oid srctype, Oid targettype)
 		if (type_is_range(srctype))
 			return true;
 
+	/* Also accept any multirange type as coercible to ANMULTIYRANGE */
+	if (targettype == ANYMULTIRANGEOID || targettype == ANYCOMPATIBLEMULTIRANGEOID)
+		if (type_is_multirange(srctype))
+			return true;
+
 	/* Also accept any composite type as coercible to RECORD */
 	if (targettype == RECORDOID)
 		if (ISCOMPLEX(srctype))
diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile
index ce09ad73754..82732146d3d 100644
--- a/src/backend/utils/adt/Makefile
+++ b/src/backend/utils/adt/Makefile
@@ -60,6 +60,8 @@ OBJS = \
 	mac8.o \
 	mcxtfuncs.o \
 	misc.o \
+	multirangetypes.o \
+	multirangetypes_selfuncs.o \
 	name.o \
 	network.o \
 	network_gist.o \
diff --git a/src/backend/utils/adt/multirangetypes.c b/src/backend/utils/adt/multirangetypes.c
new file mode 100644
index 00000000000..a4dc439a218
--- /dev/null
+++ b/src/backend/utils/adt/multirangetypes.c
@@ -0,0 +1,2679 @@
+/*-------------------------------------------------------------------------
+ *
+ * multirangetypes.c
+ *	  I/O functions, operators, and support functions for multirange types.
+ *
+ * The stored (serialized) format of a multirange value is:
+ *
+ *	12 bytes: MultirangeType struct including varlena header, multirange
+ *			  type's OID and the number of ranges in the multirange.
+ *	4 * (rangesCount - 1) bytes: 32-bit items pointing to the each range
+ *								 in the multirange starting from
+ *								 the second one.
+ *	1 * rangesCount bytes : 8-bit flags for each range in the multirange
+ *	The rest of the multirange are range bound values pointed by multirange
+ *	items.
+ *
+ *	Majority of items contain lengths of corresponding range bound values.
+ *	Thanks to that items are typically low numbers.  This makes multiranges
+ *	compression-friendly.  Every MULTIRANGE_ITEM_OFFSET_STRIDE item contains
+ *	an offset of the corresponding range bound values.  That allows fast lookups
+ *	for a particular range index.  Offsets are counted starting from the end of
+ *	flags aligned to the bound type.
+ *
+ * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/adt/multirangetypes.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/tupmacs.h"
+#include "common/hashfn.h"
+#include "lib/stringinfo.h"
+#include "libpq/pqformat.h"
+#include "miscadmin.h"
+#include "utils/builtins.h"
+#include "utils/lsyscache.h"
+#include "utils/rangetypes.h"
+#include "utils/multirangetypes.h"
+#include "utils/array.h"
+#include "utils/memutils.h"
+
+/* fn_extra cache entry for one of the range I/O functions */
+typedef struct MultirangeIOData
+{
+	TypeCacheEntry *typcache;	/* multirange type's typcache entry */
+	FmgrInfo	typioproc;		/* range type's I/O proc */
+	Oid			typioparam;		/* range type's I/O parameter */
+} MultirangeIOData;
+
+typedef enum
+{
+	MULTIRANGE_BEFORE_RANGE,
+	MULTIRANGE_IN_RANGE,
+	MULTIRANGE_IN_RANGE_ESCAPED,
+	MULTIRANGE_IN_RANGE_QUOTED,
+	MULTIRANGE_IN_RANGE_QUOTED_ESCAPED,
+	MULTIRANGE_AFTER_RANGE,
+	MULTIRANGE_FINISHED,
+} MultirangeParseState;
+
+/*
+ * Macros for accessing past MultirangeType parts of multirange: items, flags
+ * and boundaries.
+ */
+#define MultirangeGetItemsPtr(mr) ((uint32 *) ((Pointer) (mr) + \
+	sizeof(MultirangeType)))
+#define MultirangeGetFlagsPtr(mr) ((uint8 *) ((Pointer) (mr) + \
+	sizeof(MultirangeType) + ((mr)->rangeCount - 1) * sizeof(uint32)))
+#define MultirangeGetBoundariesPtr(mr, align) ((Pointer) (mr) + \
+	att_align_nominal(sizeof(MultirangeType) + \
+		((mr)->rangeCount - 1) * sizeof(uint32) + \
+		(mr)->rangeCount * sizeof(uint8), (align)))
+
+#define MULTIRANGE_ITEM_OFF_BIT 0x80000000
+#define MULTIRANGE_ITEM_GET_OFFLEN(item) ((item) & 0x7FFFFFFF)
+#define MULTIRANGE_ITEM_HAS_OFF(item) ((item) & MULTIRANGE_ITEM_OFF_BIT)
+#define MULTIRANGE_ITEM_OFFSET_STRIDE 4
+
+typedef int (*multirange_bsearch_comparison) (TypeCacheEntry *typcache,
+											  RangeBound *lower,
+											  RangeBound *upper,
+											  void *key,
+											  bool *match);
+
+static MultirangeIOData *get_multirange_io_data(FunctionCallInfo fcinfo,
+												Oid mltrngtypid,
+												IOFuncSelector func);
+static int32 multirange_canonicalize(TypeCacheEntry *rangetyp,
+									 int32 input_range_count,
+									 RangeType **ranges);
+
+/*
+ *----------------------------------------------------------
+ * I/O FUNCTIONS
+ *----------------------------------------------------------
+ */
+
+/*
+ * Converts string to multirange.
+ *
+ * We expect curly brackets to bound the list, with zero or more ranges
+ * separated by commas.  We accept whitespace anywhere: before/after our
+ * brackets and around the commas.  Ranges can be the empty literal or some
+ * stuff inside parens/brackets.  Mostly we delegate parsing the individual
+ * range contents to range_in, but we have to detect quoting and
+ * backslash-escaping which can happen for range bounds.  Backslashes can
+ * escape something inside or outside a quoted string, and a quoted string
+ * can escape quote marks with either backslashes or double double-quotes.
+ */
+Datum
+multirange_in(PG_FUNCTION_ARGS)
+{
+	char	   *input_str = PG_GETARG_CSTRING(0);
+	Oid			mltrngtypoid = PG_GETARG_OID(1);
+	Oid			typmod = PG_GETARG_INT32(2);
+	TypeCacheEntry *rangetyp;
+	int32		ranges_seen = 0;
+	int32		range_count = 0;
+	int32		range_capacity = 8;
+	RangeType  *range;
+	RangeType **ranges = palloc(range_capacity * sizeof(RangeType *));
+	MultirangeIOData *cache;
+	MultirangeType *ret;
+	MultirangeParseState parse_state;
+	const char *ptr = input_str;
+	const char *range_str = NULL;
+	int32		range_str_len;
+	char	   *range_str_copy;
+
+	cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_input);
+	rangetyp = cache->typcache->rngtype;
+
+	/* consume whitespace */
+	while (*ptr != '\0' && isspace((unsigned char) *ptr))
+		ptr++;
+
+	if (*ptr == '{')
+		ptr++;
+	else
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+				 errmsg("malformed multirange literal: \"%s\"",
+						input_str),
+				 errdetail("Missing left bracket.")));
+
+	/* consume ranges */
+	parse_state = MULTIRANGE_BEFORE_RANGE;
+	for (; parse_state != MULTIRANGE_FINISHED; ptr++)
+	{
+		char		ch = *ptr;
+
+		if (ch == '\0')
+			ereport(ERROR,
+					(errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+					 errmsg("malformed multirange literal: \"%s\"",
+							input_str),
+					 errdetail("Unexpected end of input.")));
+
+		/* skip whitespace */
+		if (isspace((unsigned char) ch))
+			continue;
+
+		switch (parse_state)
+		{
+			case MULTIRANGE_BEFORE_RANGE:
+				if (ch == '[' || ch == '(')
+				{
+					range_str = ptr;
+					parse_state = MULTIRANGE_IN_RANGE;
+				}
+				else if (ch == '}' && ranges_seen == 0)
+					parse_state = MULTIRANGE_FINISHED;
+				else if (pg_strncasecmp(ptr, RANGE_EMPTY_LITERAL,
+										strlen(RANGE_EMPTY_LITERAL)) == 0)
+				{
+					ranges_seen++;
+					/* nothing to do with an empty range */
+					ptr += strlen(RANGE_EMPTY_LITERAL) - 1;
+					parse_state = MULTIRANGE_AFTER_RANGE;
+				}
+				else
+					ereport(ERROR,
+							(errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+							 errmsg("malformed multirange literal: \"%s\"",
+									input_str),
+							 errdetail("Expected range start.")));
+				break;
+			case MULTIRANGE_IN_RANGE:
+				if (ch == '"')
+					parse_state = MULTIRANGE_IN_RANGE_QUOTED;
+				else if (ch == '\\')
+					parse_state = MULTIRANGE_IN_RANGE_ESCAPED;
+				else if (ch == ']' || ch == ')')
+				{
+					range_str_len = ptr - range_str + 1;
+					range_str_copy = pnstrdup(range_str, range_str_len);
+					if (range_capacity == range_count)
+					{
+						range_capacity *= 2;
+						ranges = (RangeType **)
+							repalloc(ranges, range_capacity * sizeof(RangeType *));
+					}
+					ranges_seen++;
+					range = DatumGetRangeTypeP(InputFunctionCall(&cache->typioproc,
+																 range_str_copy,
+																 cache->typioparam,
+																 typmod));
+					if (!RangeIsEmpty(range))
+						ranges[range_count++] = range;
+					parse_state = MULTIRANGE_AFTER_RANGE;
+				}
+				else
+					 /* include it in range_str */ ;
+				break;
+			case MULTIRANGE_IN_RANGE_ESCAPED:
+				/* include it in range_str */
+				parse_state = MULTIRANGE_IN_RANGE;
+				break;
+			case MULTIRANGE_IN_RANGE_QUOTED:
+				if (ch == '"')
+					if (*(ptr + 1) == '"')
+					{
+						/* two quote marks means an escaped quote mark */
+						ptr++;
+					}
+					else
+						parse_state = MULTIRANGE_IN_RANGE;
+				else if (ch == '\\')
+					parse_state = MULTIRANGE_IN_RANGE_QUOTED_ESCAPED;
+				else
+					 /* include it in range_str */ ;
+				break;
+			case MULTIRANGE_AFTER_RANGE:
+				if (ch == ',')
+					parse_state = MULTIRANGE_BEFORE_RANGE;
+				else if (ch == '}')
+					parse_state = MULTIRANGE_FINISHED;
+				else
+					ereport(ERROR,
+							(errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+							 errmsg("malformed multirange literal: \"%s\"",
+									input_str),
+							 errdetail("Expected comma or end of multirange.")));
+				break;
+			case MULTIRANGE_IN_RANGE_QUOTED_ESCAPED:
+				/* include it in range_str */
+				parse_state = MULTIRANGE_IN_RANGE_QUOTED;
+				break;
+			default:
+				elog(ERROR, "unknown parse state: %d", parse_state);
+		}
+	}
+
+	/* consume whitespace */
+	while (*ptr != '\0' && isspace((unsigned char) *ptr))
+		ptr++;
+
+	if (*ptr != '\0')
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+				 errmsg("malformed multirange literal: \"%s\"",
+						input_str),
+				 errdetail("Junk after right bracket.")));
+
+	ret = make_multirange(mltrngtypoid, rangetyp, range_count, ranges);
+	PG_RETURN_MULTIRANGE_P(ret);
+}
+
+Datum
+multirange_out(PG_FUNCTION_ARGS)
+{
+	MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0);
+	Oid			mltrngtypoid = MultirangeTypeGetOid(multirange);
+	MultirangeIOData *cache;
+	StringInfoData buf;
+	RangeType  *range;
+	char	   *rangeStr;
+	int32		range_count;
+	int32		i;
+	RangeType **ranges;
+
+	cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_output);
+
+	initStringInfo(&buf);
+
+	appendStringInfoChar(&buf, '{');
+
+	multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges);
+	for (i = 0; i < range_count; i++)
+	{
+		if (i > 0)
+			appendStringInfoChar(&buf, ',');
+		range = ranges[i];
+		rangeStr = OutputFunctionCall(&cache->typioproc, RangeTypePGetDatum(range));
+		appendStringInfoString(&buf, rangeStr);
+	}
+
+	appendStringInfoChar(&buf, '}');
+
+	PG_RETURN_CSTRING(buf.data);
+}
+
+/*
+ * Binary representation: First a int32-sized count of ranges, followed by
+ * ranges in their native binary representation.
+ */
+Datum
+multirange_recv(PG_FUNCTION_ARGS)
+{
+	StringInfo	buf = (StringInfo) PG_GETARG_POINTER(0);
+	Oid			mltrngtypoid = PG_GETARG_OID(1);
+	int32		typmod = PG_GETARG_INT32(2);
+	MultirangeIOData *cache;
+	uint32		range_count;
+	RangeType **ranges;
+	MultirangeType *ret;
+	StringInfoData tmpbuf;
+
+	cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_receive);
+
+	range_count = pq_getmsgint(buf, 4);
+	ranges = palloc(range_count * sizeof(RangeType *));
+
+	initStringInfo(&tmpbuf);
+	for (int i = 0; i < range_count; i++)
+	{
+		uint32		range_len = pq_getmsgint(buf, 4);
+		const char *range_data = pq_getmsgbytes(buf, range_len);
+
+		resetStringInfo(&tmpbuf);
+		appendBinaryStringInfo(&tmpbuf, range_data, range_len);
+
+		ranges[i] = DatumGetRangeTypeP(ReceiveFunctionCall(&cache->typioproc,
+														   &tmpbuf,
+														   cache->typioparam,
+														   typmod));
+	}
+	pfree(tmpbuf.data);
+
+	pq_getmsgend(buf);
+
+	ret = make_multirange(mltrngtypoid, cache->typcache->rngtype,
+						  range_count, ranges);
+	PG_RETURN_MULTIRANGE_P(ret);
+}
+
+Datum
+multirange_send(PG_FUNCTION_ARGS)
+{
+	MultirangeType *multirange = PG_GETARG_MULTIRANGE_P(0);
+	Oid			mltrngtypoid = MultirangeTypeGetOid(multirange);
+	StringInfo	buf = makeStringInfo();
+	RangeType **ranges;
+	int32		range_count;
+	MultirangeIOData *cache;
+
+	cache = get_multirange_io_data(fcinfo, mltrngtypoid, IOFunc_send);
+
+	/* construct output */
+	pq_begintypsend(buf);
+
+	pq_sendint32(buf, multirange->rangeCount);
+
+	multirange_deserialize(cache->typcache->rngtype, multirange, &range_count, &ranges);
+	for (int i = 0; i < range_count; i++)
+	{
+		Datum		range;
+
+		range = RangeTypePGetDatum(ranges[i]);
+		range = PointerGetDatum(SendFunctionCall(&cache->typioproc, range));
+
+		pq_sendint32(buf, VARSIZE(range) - VARHDRSZ);
+		pq_sendbytes(buf, VARDATA(range), VARSIZE(range) - VARHDRSZ);
+	}
+
+	PG_RETURN_BYTEA_P(pq_endtypsend(buf));
+}
+
+/*
+ * get_multirange_io_data: get cached information needed for multirange type I/O
+ *
+ * The multirange I/O functions need a bit more cached info than other multirange
+ * functions, so they store a MultirangeIOData struct in fn_extra, not just a
+ * pointer to a type cache entry.
+ */
+static MultirangeIOData *
+get_multirange_io_data(FunctionCallInfo fcinfo, Oid mltrngtypid, IOFuncSelector func)
+{
+	MultirangeIOData *cache = (MultirangeIOData *) fcinfo->flinfo->fn_extra;
+
+	if (cache == NULL || cache->typcache->type_id != mltrngtypid)
+	{
+		Oid			typiofunc;
+		int16		typlen;
+		bool		typbyval;
+		char		typalign;
+		char		typdelim;
+
+		cache = (MultirangeIOData *) MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
+														sizeof(MultirangeIOData));
+		cache->typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO);
+		if (cache->typcache->rngtype == NULL)
+			elog(ERROR, "type %u is not a multirange type", mltrngtypid);
+
+		/* get_type_io_data does more than we need, but is convenient */
+		get_type_io_data(cache->typcache->rngtype->type_id,
+						 func,
+						 &typlen,
+						 &typbyval,
+						 &typalign,
+						 &typdelim,
+						 &cache->typioparam,
+						 &typiofunc);
+
+		if (!OidIsValid(typiofunc))
+		{
+			/* this could only happen for receive or send */
+			if (func == IOFunc_receive)
+				ereport(ERROR,
+						(errcode(ERRCODE_UNDEFINED_FUNCTION),
+						 errmsg("no binary input function available for type %s",
+								format_type_be(cache->typcache->rngtype->type_id))));
+			else
+				ereport(ERROR,
+						(errcode(ERRCODE_UNDEFINED_FUNCTION),
+						 errmsg("no binary output function available for type %s",
+								format_type_be(cache->typcache->rngtype->type_id))));
+		}
+		fmgr_info_cxt(typiofunc, &cache->typioproc,
+					  fcinfo->flinfo->fn_mcxt);
+
+		fcinfo->flinfo->fn_extra = (void *) cache;
+	}
+
+	return cache;
+}
+
+/*
+ * Converts a list of arbitrary ranges into a list that is sorted and merged.
+ * Changes the contents of `ranges`.
+ *
+ * Returns the number of slots actually used, which may be less than
+ * input_range_count but never more.
+ *
+ * We assume that no input ranges are null, but empties are okay.
+ */
+static int32
+multirange_canonicalize(TypeCacheEntry *rangetyp, int32 input_range_count,
+						RangeType **ranges)
+{
+	RangeType  *lastRange = NULL;
+	RangeType  *currentRange;
+	int32		i;
+	int32		output_range_count = 0;
+
+	/* Sort the ranges so we can find the ones that overlap/meet. */
+	qsort_arg(ranges, input_range_count, sizeof(RangeType *), range_compare,
+			  rangetyp);
+
+	/* Now merge where possible: */
+	for (i = 0; i < input_range_count; i++)
+	{
+		currentRange = ranges[i];
+		if (RangeIsEmpty(currentRange))
+			continue;
+
+		if (lastRange == NULL)
+		{
+			ranges[output_range_count++] = lastRange = currentRange;
+			continue;
+		}
+
+		/*
+		 * range_adjacent_internal gives true if *either* A meets B or B meets
+		 * A, which is not quite want we want, but we rely on the sorting
+		 * above to rule out B meets A ever happening.
+		 */
+		if (range_adjacent_internal(rangetyp, lastRange, currentRange))
+		{
+			/* The two ranges touch (without overlap), so merge them: */
+			ranges[output_range_count - 1] = lastRange =
+				range_union_internal(rangetyp, lastRange, currentRange, false);
+		}
+		else if (range_before_internal(rangetyp, lastRange, currentRange))
+		{
+			/* There's a gap, so make a new entry: */
+			lastRange = ranges[output_range_count] = currentRange;
+			output_range_count++;
+		}
+		else
+		{
+			/* They must overlap, so merge them: */
+			ranges[output_range_count - 1] = lastRange =
+				range_union_internal(rangetyp, lastRange, currentRange, true);
+		}
+	}
+
+	return output_range_count;
+}
+
+/*
+ *----------------------------------------------------------
+ * SUPPORT FUNCTIONS
+ *
+ *	 These functions aren't in pg_proc, but are useful for
+ *	 defining new generic multirange functions in C.
+ *----------------------------------------------------------
+ */
+
+/*
+ * multirange_get_typcache: get cached information about a multirange type
+ *
+ * This is for use by multirange-related functions that follow the convention
+ * of using the fn_extra field as a pointer to the type cache entry for
+ * the multirange type.  Functions that need to cache more information than
+ * that must fend for themselves.
+ */
+TypeCacheEntry *
+multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid)
+{
+	TypeCacheEntry *typcache = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+
+	if (typcache == NULL ||
+		typcache->type_id != mltrngtypid)
+	{
+		typcache = lookup_type_cache(mltrngtypid, TYPECACHE_MULTIRANGE_INFO);
+		if (typcache->rngtype == NULL)
+			elog(ERROR, "type %u is not a multirange type", mltrngtypid);
+		fcinfo->flinfo->fn_extra = (void *) typcache;
+	}
+
+	return typcache;
+}
+
+
+/*
+ * Estimate size occupied by serialized multirage.
+ */
+static Size
+multirange_size_estimate(TypeCacheEntry *rangetyp, int32 range_count,
+						 RangeType **ranges)
+{
+	char		elemalign = rangetyp->rngelemtype->typalign;
+	Size		size;
+	int32		i;
+
+	/*
+	 * Count space for MultirangeType struct, items and flags.
+	 */
+	size = att_align_nominal(sizeof(MultirangeType) +
+							 Max(range_count - 1, 0) * sizeof(uint32) +
+							 range_count * sizeof(uint8), elemalign);
+
+	/* Count space for range bounds */
+	for (i = 0; i < range_count; i++)
+		size += att_align_nominal(VARSIZE(ranges[i]) -
+								  sizeof(RangeType) -
+								  sizeof(char), elemalign);
+
+	return size;
+}
+
+/*
+ * Write multirange data into pre-allocated space.
+ */
+static void
+write_multirange_data(MultirangeType *multirange, TypeCacheEntry *rangetyp,
+					  int32 range_count, RangeType **ranges)
+{
+	uint32	   *items;
+	uint32		prev_offset = 0;
+	uint8	   *flags;
+	int32		i;
+	Pointer		begin,
+				ptr;
+	char		elemalign = rangetyp->rngelemtype->typalign;
+
+	items = MultirangeGetItemsPtr(multirange);
+	flags = MultirangeGetFlagsPtr(multirange);
+	ptr = begin = MultirangeGetBoundariesPtr(multirange, elemalign);
+	for (i = 0; i < range_count; i++)
+	{
+		uint32		len;
+
+		if (i > 0)
+		{
+			/*
+			 * Every range, except the first one, has an item.  Every
+			 * MULTIRANGE_ITEM_OFFSET_STRIDE item contains an offset, others
+			 * contain lengths.
+			 */
+			items[i - 1] = ptr - begin;
+			if ((i % MULTIRANGE_ITEM_OFFSET_STRIDE) != 0)
+				items[i - 1] -= prev_offset;
+			else
+				items[i - 1] |= MULTIRANGE_ITEM_OFF_BIT;
+			prev_offset = ptr - begin;
+		}
+		flags[i] = *((Pointer) ranges[i] + VARSIZE(ranges[i]) - sizeof(char));
+		len = VARSIZE(ranges[i]) - sizeof(RangeType) - sizeof(char);
+		memcpy(ptr, (Pointer) (ranges[i] + 1), len);
+		ptr += att_align_nominal(len, elemalign);
+	}
+}
+
+
+/*
+ * This serializes the multirange from a list of non-null ranges.  It also
+ * sorts the ranges and merges any that touch.  The ranges should already be
+ * detoasted, and there should be no NULLs.  This should be used by most
+ * callers.
+ *
+ * Note that we may change the `ranges` parameter (the pointers, but not
+ * any already-existing RangeType contents).
+ */
+MultirangeType *
+make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count,
+				RangeType **ranges)
+{
+	MultirangeType *multirange;
+	Size		size;
+
+	/* Sort and merge input ranges. */
+	range_count = multirange_canonicalize(rangetyp, range_count, ranges);
+
+	/* Note: zero-fill is required here, just as in heap tuples */
+	size = multirange_size_estimate(rangetyp, range_count, ranges);
+	multirange = palloc0(size);
+	SET_VARSIZE(multirange, size);
+
+	/* Now fill in the datum */
+	multirange->multirangetypid = mltrngtypoid;
+	multirange->rangeCount = range_count;
+
+	write_multirange_data(multirange, rangetyp, range_count, ranges);
+
+	return multirange;
+}
+
+/*
+ * Get offset of bounds values of the i'th range in the multirange.
+ */
+static uint32
+multirange_get_bounds_offset(const MultirangeType *multirange, int32 i)
+{
+	uint32	   *items = MultirangeGetItemsPtr(multirange);
+	uint32		offset = 0;
+
+	/*
+	 * Summarize lengths till we meet an offset.
+	 */
+	while (i > 0)
+	{
+		offset += MULTIRANGE_ITEM_GET_OFFLEN(items[i - 1]);
+		if (MULTIRANGE_ITEM_HAS_OFF(items[i - 1]))
+			break;
+		i--;
+	}
+	return offset;
+}
+
+/*
+ * Fetch the i'th range from the multirange.
+ */
+RangeType *
+multirange_get_range(TypeCacheEntry *rangetyp,
+					 const MultirangeType *multirange, int i)
+{
+	uint32		offset;
+	uint8		flags;
+	Pointer		begin,
+				ptr;
+	int16		typlen = rangetyp->rngelemtype->typlen;
+	char		typalign = rangetyp->rngelemtype->typalign;
+	uint32		len;
+	RangeType  *range;
+
+	Assert(i < multirange->rangeCount);
+
+	offset = multirange_get_bounds_offset(multirange, i);
+	flags = MultirangeGetFlagsPtr(multirange)[i];
+	ptr = begin = MultirangeGetBoundariesPtr(multirange, typalign) + offset;
+
+	/*
+	 * Calculate the size of bound values.  In principle, we could get offset
+	 * of the next range bound values and calculate accordingly.  But range
+	 * bound values are aligned, so we have to walk the values to get the
+	 * exact size.
+	 */
+	if (RANGE_HAS_LBOUND(flags))
+		ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+	if (RANGE_HAS_UBOUND(flags))
+		ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+	len = (ptr - begin) + sizeof(RangeType) + sizeof(uint8);
+
+	range = palloc0(len);
+	SET_VARSIZE(range, len);
+	range->rangetypid = rangetyp->type_id;
+
+	memcpy(range + 1, begin, ptr - begin);
+	*((uint8 *) (range + 1) + (ptr - begin)) = flags;
+
+	return range;
+}
+
+/*
+ * Fetch bounds from the i'th range of the multirange.  This is the shortcut for
+ * doing the same thing as multirange_get_range() + range_deserialize(), but
+ * performing fewer operations.
+ */
+void
+multirange_get_bounds(TypeCacheEntry *rangetyp,
+					  const MultirangeType *multirange,
+					  uint32 i, RangeBound *lower, RangeBound *upper)
+{
+	uint32		offset;
+	uint8		flags;
+	Pointer		ptr;
+	int16		typlen = rangetyp->rngelemtype->typlen;
+	char		typalign = rangetyp->rngelemtype->typalign;
+	bool		typbyval = rangetyp->rngelemtype->typbyval;
+	Datum		lbound;
+	Datum		ubound;
+
+	Assert(i < multirange->rangeCount);
+
+	offset = multirange_get_bounds_offset(multirange, i);
+	flags = MultirangeGetFlagsPtr(multirange)[i];
+	ptr = MultirangeGetBoundariesPtr(multirange, typalign) + offset;
+
+	/* multirange can't contain empty ranges */
+	Assert((flags & RANGE_EMPTY) == 0);
+
+	/* fetch lower bound, if any */
+	if (RANGE_HAS_LBOUND(flags))
+	{
+		/* att_align_pointer cannot be necessary here */
+		lbound = fetch_att(ptr, typbyval, typlen);
+		ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+	}
+	else
+		lbound = (Datum) 0;
+
+	/* fetch upper bound, if any */
+	if (RANGE_HAS_UBOUND(flags))
+	{
+		ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
+		ubound = fetch_att(ptr, typbyval, typlen);
+		/* no need for att_addlength_pointer */
+	}
+	else
+		ubound = (Datum) 0;
+
+	/* emit results */
+	lower->val = lbound;
+	lower->infinite = (flags & RANGE_LB_INF) != 0;
+	lower->inclusive = (flags & RANGE_LB_INC) != 0;
+	lower->lower = true;
+
+	upper->val = ubound;
+	upper->infinite = (flags & RANGE_UB_INF) != 0;
+	upper->inclusive = (flags & RANGE_UB_INC) != 0;
+	upper->lower = false;
+}
+
+/*
+ * multirange_deserialize: deconstruct a multirange value
+ *
+ * NB: the given multirange object must be fully detoasted; it cannot have a
+ * short varlena header.
+ */
+void
+multirange_deserialize(TypeCacheEntry *rangetyp,
+					   const MultirangeType *multirange, int32 *range_count,
+					   RangeType ***ranges)
+{
+	*range_count = multirange->rangeCount;
+
+	/* Convert each ShortRangeType into a RangeType */
+	if (*range_count > 0)
+	{
+		int			i;
+
+		*ranges = palloc(*range_count * sizeof(RangeType *));
+		for (i = 0; i < *range_count; i++)
+			(*ranges)[i] = multirange_get_range(rangetyp, multirange, i);
+	}
+	else
+	{
+		*ranges = NULL;
+	}
+}
+
+MultirangeType *
+make_empty_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp)
+{
+	return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
+}
+
+/*
+ * Similar to range_overlaps_internal(), but takes range bounds instead of
+ * ranges as arguments.
+ */
+static bool
+range_bounds_overlaps(TypeCacheEntry *typcache,
+					  RangeBound *lower1, RangeBound *upper1,
+					  RangeBound *lower2, RangeBound *upper2)
+{
+	if (range_cmp_bounds(typcache, lower1, lower2) >= 0 &&
+		range_cmp_bounds(typcache, lower1, upper2) <= 0)
+		return true;
+
+	if (range_cmp_bounds(typcache, lower2, lower1) >= 0 &&
+		range_cmp_bounds(typcache, lower2, upper1) <= 0)
+		return true;
+
+	return false;
+}
+
+/*
+ * Similar to range_contains_internal(), but takes range bounds instead of
+ * ranges as arguments.
+ */
+static bool
+range_bounds_contains(TypeCacheEntry *typcache,
+					  RangeBound *lower1, RangeBound *upper1,
+					  RangeBound *lower2, RangeBound *upper2)
+{
+	if (range_cmp_bounds(typcache, lower1, lower2) <= 0 &&
+		range_cmp_bounds(typcache, upper1, upper2) >= 0)
+		return true;
+
+	return false;
+}
+
+/*
+ * Check if the given key matches any range in multirange using binary search.
+ * If the required range isn't found, that counts as a mismatch.  When the
+ * required range is found, the comparison function can still report this as
+ * either match or mismatch.  For instance, if we search for containment, we can
+ * found a range, which is overlapping but not containing the key range, and
+ * that would count as a mismatch.
+ */
+static bool
+multirange_bsearch_match(TypeCacheEntry *typcache, MultirangeType *mr,
+						 void *key, multirange_bsearch_comparison cmp_func)
+{
+	uint32		l,
+				u,
+				idx;
+	int			comparison;
+	bool		match = false;
+
+	l = 0;
+	u = mr->rangeCount;
+	while (l < u)
+	{
+		RangeBound	lower,
+					upper;
+
+		idx = (l + u) / 2;
+		multirange_get_bounds(typcache, mr, idx, &lower, &upper);
+		comparison = (*cmp_func) (typcache, &lower, &upper, key, &match);
+
+		if (comparison < 0)
+			u = idx;
+		else if (comparison > 0)
+			l = idx + 1;
+		else
+			return match;
+	}
+
+	return false;
+}
+
+/*
+ *----------------------------------------------------------
+ * GENERIC FUNCTIONS
+ *----------------------------------------------------------
+ */
+
+/*
+ * Construct multirange value from zero or more ranges.  Since this is a
+ * variadic function we get passed an array.  The array must contain ranges
+ * that match our return value, and there must be no NULLs.
+ */
+Datum
+multirange_constructor2(PG_FUNCTION_ARGS)
+{
+	Oid			mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
+	Oid			rngtypid;
+	TypeCacheEntry *typcache;
+	TypeCacheEntry *rangetyp;
+	ArrayType  *rangeArray;
+	int			range_count;
+	Datum	   *elements;
+	bool	   *nulls;
+	RangeType **ranges;
+	int			dims;
+	int			i;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypid);
+	rangetyp = typcache->rngtype;
+
+	/*
+	 * A no-arg invocation should call multirange_constructor0 instead, but
+	 * returning an empty range is what that does.
+	 */
+
+	if (PG_NARGS() == 0)
+		PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL));
+
+	/*
+	 * These checks should be guaranteed by our signature, but let's do them
+	 * just in case.
+	 */
+
+	if (PG_ARGISNULL(0))
+		ereport(ERROR,
+				(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
+				 errmsg("multirange values cannot contain NULL members")));
+
+	rangeArray = PG_GETARG_ARRAYTYPE_P(0);
+
+	dims = ARR_NDIM(rangeArray);
+	if (dims > 1)
+		ereport(ERROR,
+				(errcode(ERRCODE_CARDINALITY_VIOLATION),
+				 errmsg("multiranges cannot be constructed from multi-dimensional arrays")));
+
+	rngtypid = ARR_ELEMTYPE(rangeArray);
+	if (rngtypid != rangetyp->type_id)
+		ereport(ERROR,
+				(errcode(ERRCODE_DATATYPE_MISMATCH),
+				 errmsg("type %u does not match constructor type", rngtypid)));
+
+	/*
+	 * Be careful: we can still be called with zero ranges, like this:
+	 * `int4multirange(variadic '{}'::int4range[])
+	 */
+	if (dims == 0)
+	{
+		range_count = 0;
+		ranges = NULL;
+	}
+	else
+	{
+		deconstruct_array(rangeArray, rngtypid, rangetyp->typlen, rangetyp->typbyval,
+						  rangetyp->typalign, &elements, &nulls, &range_count);
+
+		ranges = palloc0(range_count * sizeof(RangeType *));
+		for (i = 0; i < range_count; i++)
+		{
+			if (nulls[i])
+				ereport(ERROR,
+						(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
+						 errmsg("multirange values cannot contain NULL members")));
+
+			/* make_multirange will do its own copy */
+			ranges[i] = DatumGetRangeTypeP(elements[i]);
+		}
+	}
+
+	PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, range_count, ranges));
+}
+
+/*
+ * Construct multirange value from a single range.  It'd be nice if we could
+ * just use multirange_constructor2 for this case, but we need a non-variadic
+ * single-arg function to let us define a CAST from a range to its multirange.
+ */
+Datum
+multirange_constructor1(PG_FUNCTION_ARGS)
+{
+	Oid			mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
+	Oid			rngtypid;
+	TypeCacheEntry *typcache;
+	TypeCacheEntry *rangetyp;
+	RangeType  *range;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypid);
+	rangetyp = typcache->rngtype;
+
+	/*
+	 * These checks should be guaranteed by our signature, but let's do them
+	 * just in case.
+	 */
+
+	if (PG_ARGISNULL(0))
+		ereport(ERROR,
+				(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
+				 errmsg("multirange values cannot contain NULL members")));
+
+	range = PG_GETARG_RANGE_P(0);
+
+	/* Make sure the range type matches. */
+	rngtypid = RangeTypeGetOid(range);
+	if (rngtypid != rangetyp->type_id)
+		ereport(ERROR,
+				(errcode(ERRCODE_DATATYPE_MISMATCH),
+				 errmsg("type %u does not match constructor type", rngtypid)));
+
+	PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 1, &range));
+}
+
+/*
+ * Constructor just like multirange_constructor1, but opr_sanity gets angry
+ * if the same internal function handles multiple functions with different arg
+ * counts.
+ */
+Datum
+multirange_constructor0(PG_FUNCTION_ARGS)
+{
+	Oid			mltrngtypid = get_fn_expr_rettype(fcinfo->flinfo);
+	TypeCacheEntry *typcache;
+	TypeCacheEntry *rangetyp;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypid);
+	rangetyp = typcache->rngtype;
+
+	/* We should always be called with no arguments */
+
+	if (PG_NARGS() == 0)
+		PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypid, rangetyp, 0, NULL));
+	else
+		elog(ERROR,				/* can't happen */
+			 "niladic multirange constructor must not receive arguments");
+}
+
+
+/* multirange, multirange -> multirange type functions */
+
+/* multirange union */
+Datum
+multirange_union(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	int32		range_count1;
+	int32		range_count2;
+	int32		range_count3;
+	RangeType **ranges1;
+	RangeType **ranges2;
+	RangeType **ranges3;
+
+	if (MultirangeIsEmpty(mr1))
+		PG_RETURN_MULTIRANGE_P(mr2);
+	if (MultirangeIsEmpty(mr2))
+		PG_RETURN_MULTIRANGE_P(mr1);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
+	multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
+
+	range_count3 = range_count1 + range_count2;
+	ranges3 = palloc0(range_count3 * sizeof(RangeType *));
+	memcpy(ranges3, ranges1, range_count1 * sizeof(RangeType *));
+	memcpy(ranges3 + range_count1, ranges2, range_count2 * sizeof(RangeType *));
+	PG_RETURN_MULTIRANGE_P(make_multirange(typcache->type_id, typcache->rngtype,
+										   range_count3, ranges3));
+}
+
+/* multirange minus */
+Datum
+multirange_minus(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	Oid			mltrngtypoid = MultirangeTypeGetOid(mr1);
+	TypeCacheEntry *typcache;
+	TypeCacheEntry *rangetyp;
+	int32		range_count1;
+	int32		range_count2;
+	RangeType **ranges1;
+	RangeType **ranges2;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
+	rangetyp = typcache->rngtype;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		PG_RETURN_MULTIRANGE_P(mr1);
+
+	multirange_deserialize(typcache->rngtype, mr1, &range_count1, &ranges1);
+	multirange_deserialize(typcache->rngtype, mr2, &range_count2, &ranges2);
+
+	PG_RETURN_MULTIRANGE_P(multirange_minus_internal(mltrngtypoid,
+													 rangetyp,
+													 range_count1,
+													 ranges1,
+													 range_count2,
+													 ranges2));
+}
+
+MultirangeType *
+multirange_minus_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
+						  int32 range_count1, RangeType **ranges1,
+						  int32 range_count2, RangeType **ranges2)
+{
+	RangeType  *r1;
+	RangeType  *r2;
+	RangeType **ranges3;
+	int32		range_count3;
+	int32		i1;
+	int32		i2;
+
+	/*
+	 * Worst case: every range in ranges1 makes a different cut to some range
+	 * in ranges2.
+	 */
+	ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
+	range_count3 = 0;
+
+	/*
+	 * For each range in mr1, keep subtracting until it's gone or the ranges
+	 * in mr2 have passed it. After a subtraction we assign what's left back
+	 * to r1. The parallel progress through mr1 and mr2 is similar to
+	 * multirange_overlaps_multirange_internal.
+	 */
+	r2 = ranges2[0];
+	for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
+	{
+		r1 = ranges1[i1];
+
+		/* Discard r2s while r2 << r1 */
+		while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
+		{
+			r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
+		}
+
+		while (r2 != NULL)
+		{
+			if (range_split_internal(rangetyp, r1, r2, &ranges3[range_count3], &r1))
+			{
+				/*
+				 * If r2 takes a bite out of the middle of r1, we need two
+				 * outputs
+				 */
+				range_count3++;
+				r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
+
+			}
+			else if (range_overlaps_internal(rangetyp, r1, r2))
+			{
+				/*
+				 * If r2 overlaps r1, replace r1 with r1 - r2.
+				 */
+				r1 = range_minus_internal(rangetyp, r1, r2);
+
+				/*
+				 * If r2 goes past r1, then we need to stay with it, in case
+				 * it hits future r1s. Otherwise we need to keep r1, in case
+				 * future r2s hit it. Since we already subtracted, there's no
+				 * point in using the overright/overleft calls.
+				 */
+				if (RangeIsEmpty(r1) || range_before_internal(rangetyp, r1, r2))
+					break;
+				else
+					r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
+
+			}
+			else
+			{
+				/*
+				 * This and all future r2s are past r1, so keep them. Also
+				 * assign whatever is left of r1 to the result.
+				 */
+				break;
+			}
+		}
+
+		/*
+		 * Nothing else can remove anything from r1, so keep it. Even if r1 is
+		 * empty here, make_multirange will remove it.
+		 */
+		ranges3[range_count3++] = r1;
+	}
+
+	return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
+}
+
+/* multirange intersection */
+Datum
+multirange_intersect(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	Oid			mltrngtypoid = MultirangeTypeGetOid(mr1);
+	TypeCacheEntry *typcache;
+	TypeCacheEntry *rangetyp;
+	int32		range_count1;
+	int32		range_count2;
+	RangeType **ranges1;
+	RangeType **ranges2;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
+	rangetyp = typcache->rngtype;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		PG_RETURN_MULTIRANGE_P(make_empty_multirange(mltrngtypoid, rangetyp));
+
+	multirange_deserialize(rangetyp, mr1, &range_count1, &ranges1);
+	multirange_deserialize(rangetyp, mr2, &range_count2, &ranges2);
+
+	PG_RETURN_MULTIRANGE_P(multirange_intersect_internal(mltrngtypoid,
+														 rangetyp,
+														 range_count1,
+														 ranges1,
+														 range_count2,
+														 ranges2));
+}
+
+MultirangeType *
+multirange_intersect_internal(Oid mltrngtypoid, TypeCacheEntry *rangetyp,
+							  int32 range_count1, RangeType **ranges1,
+							  int32 range_count2, RangeType **ranges2)
+{
+	RangeType  *r1;
+	RangeType  *r2;
+	RangeType **ranges3;
+	int32		range_count3;
+	int32		i1;
+	int32		i2;
+
+	if (range_count1 == 0 || range_count2 == 0)
+		return make_multirange(mltrngtypoid, rangetyp, 0, NULL);
+
+	/*-----------------------------------------------
+	 * Worst case is a stitching pattern like this:
+	 *
+	 * mr1: --- --- --- ---
+	 * mr2:   --- --- ---
+	 * mr3:   - - - - - -
+	 *
+	 * That seems to be range_count1 + range_count2 - 1,
+	 * but one extra won't hurt.
+	 *-----------------------------------------------
+	 */
+	ranges3 = palloc0((range_count1 + range_count2) * sizeof(RangeType *));
+	range_count3 = 0;
+
+	/*
+	 * For each range in mr1, keep intersecting until the ranges in mr2 have
+	 * passed it. The parallel progress through mr1 and mr2 is similar to
+	 * multirange_minus_multirange_internal, but we don't have to assign back
+	 * to r1.
+	 */
+	r2 = ranges2[0];
+	for (i1 = 0, i2 = 0; i1 < range_count1; i1++)
+	{
+		r1 = ranges1[i1];
+
+		/* Discard r2s while r2 << r1 */
+		while (r2 != NULL && range_before_internal(rangetyp, r2, r1))
+		{
+			r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
+		}
+
+		while (r2 != NULL)
+		{
+			if (range_overlaps_internal(rangetyp, r1, r2))
+			{
+				/* Keep the overlapping part */
+				ranges3[range_count3++] = range_intersect_internal(rangetyp, r1, r2);
+
+				/* If we "used up" all of r2, go to the next one... */
+				if (range_overleft_internal(rangetyp, r2, r1))
+					r2 = ++i2 >= range_count2 ? NULL : ranges2[i2];
+
+				/* ...otherwise go to the next r1 */
+				else
+					break;
+			}
+			else
+				/* We're past r1, so move to the next one */
+				break;
+		}
+
+		/* If we're out of r2s, there can be no more intersections */
+		if (r2 == NULL)
+			break;
+	}
+
+	return make_multirange(mltrngtypoid, rangetyp, range_count3, ranges3);
+}
+
+/*
+ * range_agg_transfn: combine adjacent/overlapping ranges.
+ *
+ * All we do here is gather the input ranges into an array
+ * so that the finalfn can sort and combine them.
+ */
+Datum
+range_agg_transfn(PG_FUNCTION_ARGS)
+{
+	MemoryContext aggContext;
+	Oid			rngtypoid;
+	ArrayBuildState *state;
+
+	if (!AggCheckCallContext(fcinfo, &aggContext))
+		elog(ERROR, "range_agg_transfn called in non-aggregate context");
+
+	rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
+	if (!type_is_range(rngtypoid))
+		ereport(ERROR,
+				(errcode(ERRCODE_DATATYPE_MISMATCH),
+				 errmsg("range_agg must be called with a range")));
+
+	if (PG_ARGISNULL(0))
+		state = initArrayResult(rngtypoid, aggContext, false);
+	else
+		state = (ArrayBuildState *) PG_GETARG_POINTER(0);
+
+	/* skip NULLs */
+	if (!PG_ARGISNULL(1))
+		accumArrayResult(state, PG_GETARG_DATUM(1), false, rngtypoid, aggContext);
+
+	PG_RETURN_POINTER(state);
+}
+
+/*
+ * range_agg_finalfn: use our internal array to merge touching ranges.
+ */
+Datum
+range_agg_finalfn(PG_FUNCTION_ARGS)
+{
+	MemoryContext aggContext;
+	Oid			mltrngtypoid;
+	TypeCacheEntry *typcache;
+	ArrayBuildState *state;
+	int32		range_count;
+	RangeType **ranges;
+	int			i;
+
+	if (!AggCheckCallContext(fcinfo, &aggContext))
+		elog(ERROR, "range_agg_finalfn called in non-aggregate context");
+
+	state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
+	if (state == NULL)
+		/* This shouldn't be possible, but just in case.... */
+		PG_RETURN_NULL();
+
+	/* Also return NULL if we had zero inputs, like other aggregates */
+	range_count = state->nelems;
+	if (range_count == 0)
+		PG_RETURN_NULL();
+
+	mltrngtypoid = get_fn_expr_rettype(fcinfo->flinfo);
+	typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
+
+	ranges = palloc0(range_count * sizeof(RangeType *));
+	for (i = 0; i < range_count; i++)
+		ranges[i] = DatumGetRangeTypeP(state->dvalues[i]);
+
+	PG_RETURN_MULTIRANGE_P(make_multirange(mltrngtypoid, typcache->rngtype, range_count, ranges));
+}
+
+Datum
+multirange_intersect_agg_transfn(PG_FUNCTION_ARGS)
+{
+	MemoryContext aggContext;
+	Oid			mltrngtypoid;
+	TypeCacheEntry *typcache;
+	MultirangeType *result;
+	MultirangeType *current;
+	int32		range_count1;
+	int32		range_count2;
+	RangeType **ranges1;
+	RangeType **ranges2;
+
+	if (!AggCheckCallContext(fcinfo, &aggContext))
+		elog(ERROR, "multirange_intersect_agg_transfn called in non-aggregate context");
+
+	mltrngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
+	if (!type_is_multirange(mltrngtypoid))
+		ereport(ERROR,
+				(errcode(ERRCODE_DATATYPE_MISMATCH),
+				 errmsg("range_intersect_agg must be called with a multirange")));
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
+
+	/* strictness ensures these are non-null */
+	result = PG_GETARG_MULTIRANGE_P(0);
+	current = PG_GETARG_MULTIRANGE_P(1);
+
+	multirange_deserialize(typcache->rngtype, result, &range_count1, &ranges1);
+	multirange_deserialize(typcache->rngtype, current, &range_count2, &ranges2);
+
+	result = multirange_intersect_internal(mltrngtypoid,
+										   typcache->rngtype,
+										   range_count1,
+										   ranges1,
+										   range_count2,
+										   ranges2);
+	PG_RETURN_RANGE_P(result);
+}
+
+
+/* multirange -> element type functions */
+
+/* extract lower bound value */
+Datum
+multirange_lower(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_NULL();
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	multirange_get_bounds(typcache->rngtype, mr, 0,
+						  &lower, &upper);
+
+	if (!lower.infinite)
+		PG_RETURN_DATUM(lower.val);
+	else
+		PG_RETURN_NULL();
+}
+
+/* extract upper bound value */
+Datum
+multirange_upper(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_NULL();
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+						  &lower, &upper);
+
+	if (!upper.infinite)
+		PG_RETURN_DATUM(upper.val);
+	else
+		PG_RETURN_NULL();
+}
+
+
+/* multirange -> bool functions */
+
+/* is multirange empty? */
+Datum
+multirange_empty(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+
+	PG_RETURN_BOOL(MultirangeIsEmpty(mr));
+}
+
+/* is lower bound inclusive? */
+Datum
+multirange_lower_inc(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	multirange_get_bounds(typcache->rngtype, mr, 0,
+						  &lower, &upper);
+
+	PG_RETURN_BOOL(lower.inclusive);
+}
+
+/* is upper bound inclusive? */
+Datum
+multirange_upper_inc(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+						  &lower, &upper);
+
+	PG_RETURN_BOOL(upper.inclusive);
+}
+
+/* is lower bound infinite? */
+Datum
+multirange_lower_inf(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	multirange_get_bounds(typcache->rngtype, mr, 0,
+						  &lower, &upper);
+
+	PG_RETURN_BOOL(lower.infinite);
+}
+
+/* is upper bound infinite? */
+Datum
+multirange_upper_inf(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	TypeCacheEntry *typcache;
+	RangeBound	lower;
+	RangeBound	upper;
+
+	if (MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+						  &lower, &upper);
+
+	PG_RETURN_BOOL(upper.infinite);
+}
+
+
+
+/* multirange, element -> bool functions */
+
+/* contains? */
+Datum
+multirange_contains_elem(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	Datum		val = PG_GETARG_DATUM(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(multirange_contains_elem_internal(typcache, mr, val));
+}
+
+/* contained by? */
+Datum
+elem_contained_by_multirange(PG_FUNCTION_ARGS)
+{
+	Datum		val = PG_GETARG_DATUM(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(multirange_contains_elem_internal(typcache, mr, val));
+}
+
+/*
+ * Comparison function for checking if any range of multirange contains given
+ * key element using binary search.
+ */
+static int
+multirange_elem_bsearch_comparison(TypeCacheEntry *typcache,
+								   RangeBound *lower, RangeBound *upper,
+								   void *key, bool *match)
+{
+	Datum		val = *((Datum *) key);
+	int			cmp;
+
+	if (!lower->infinite)
+	{
+		cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
+											  typcache->rng_collation,
+											  lower->val, val));
+		if (cmp > 0 || (cmp == 0 && !lower->inclusive))
+			return -1;
+	}
+
+	if (!upper->infinite)
+	{
+		cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
+											  typcache->rng_collation,
+											  upper->val, val));
+		if (cmp < 0 || (cmp == 0 && !upper->inclusive))
+			return 1;
+	}
+
+	*match = true;
+	return 0;
+}
+
+/*
+ * Test whether multirange mr contains a specific element value.
+ */
+bool
+multirange_contains_elem_internal(TypeCacheEntry *typcache,
+								  MultirangeType *mr, Datum val)
+{
+	if (MultirangeIsEmpty(mr))
+		return false;
+
+	return multirange_bsearch_match(typcache->rngtype, mr, &val,
+									multirange_elem_bsearch_comparison);
+}
+
+/* multirange, range -> bool functions */
+
+/* contains? */
+Datum
+multirange_contains_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(multirange_contains_range_internal(typcache, mr, r));
+}
+
+/* contained by? */
+Datum
+range_contained_by_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(multirange_contains_range_internal(typcache, mr, r));
+}
+
+/*
+ * Comparison function for checking if any range of multirange contains given
+ * key range using binary search.
+ */
+static int
+multirange_range_contains_bsearch_comparison(TypeCacheEntry *typcache,
+											 RangeBound *lower, RangeBound *upper,
+											 void *key, bool *match)
+{
+	RangeBound *keyLower = (RangeBound *) key;
+	RangeBound *keyUpper = (RangeBound *) key + 1;
+
+	/* Check if key range is strictly in the left or in the right */
+	if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
+		return -1;
+	if (range_cmp_bounds(typcache, keyLower, upper) > 0)
+		return -1;
+
+	/*
+	 * At this point we found overlapping range.  But we have to check if it
+	 * really contains the key range.  Anyway, we have to stop our search
+	 * here, because multirange contains only non-overlapping ranges.
+	 */
+	*match = range_bounds_contains(typcache, lower, upper, keyLower, keyUpper);
+
+	return 0;
+}
+
+/*
+ * Test whether multirange mr contains a specific range r.
+ */
+bool
+multirange_contains_range_internal(TypeCacheEntry *typcache, MultirangeType *mr, RangeType *r)
+{
+	TypeCacheEntry *rangetyp;
+	RangeBound	bounds[2];
+	bool		empty;
+
+	rangetyp = typcache->rngtype;
+
+	/*
+	 * Every multirange contains an infinite number of empty ranges, even an
+	 * empty one.
+	 */
+	if (RangeIsEmpty(r))
+		return true;
+
+	if (MultirangeIsEmpty(mr))
+		return false;
+
+	range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
+	Assert(!empty);
+
+	return multirange_bsearch_match(rangetyp, mr, bounds,
+									multirange_range_contains_bsearch_comparison);
+}
+
+
+/* multirange, multirange -> bool functions */
+
+/* equality (internal version) */
+bool
+multirange_eq_internal(TypeCacheEntry *typcache, MultirangeType *mr1, MultirangeType *mr2)
+{
+	TypeCacheEntry *rangetyp = typcache->rngtype;
+	int32		range_count_1;
+	int32		range_count_2;
+	int32		i;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	/* Different types should be prevented by ANYMULTIRANGE matching rules */
+	if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
+		elog(ERROR, "multirange types do not match");
+
+	range_count_1 = mr1->rangeCount;
+	range_count_2 = mr2->rangeCount;
+
+	if (range_count_1 != range_count_2)
+		return false;
+
+	for (i = 0; i < range_count_1; i++)
+	{
+		multirange_get_bounds(rangetyp, mr1, i, &lower1, &upper1);
+		multirange_get_bounds(rangetyp, mr2, i, &lower2, &upper2);
+
+		if (range_cmp_bounds(rangetyp, &lower1, &lower2) != 0 ||
+			range_cmp_bounds(rangetyp, &upper1, &upper2) != 0)
+			return false;
+	}
+
+	return true;
+}
+
+/* equality */
+Datum
+multirange_eq(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_eq_internal(typcache, mr1, mr2));
+}
+
+/* inequality (internal version) */
+bool
+multirange_ne_internal(TypeCacheEntry *typcache, MultirangeType *mr1, MultirangeType *mr2)
+{
+	return (!multirange_eq_internal(typcache, mr1, mr2));
+}
+
+/* inequality */
+Datum
+multirange_ne(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_ne_internal(typcache, mr1, mr2));
+}
+
+/* overlaps? */
+Datum
+range_overlaps_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_overlaps_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_overlaps_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_overlaps_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_overlaps_multirange_internal(typcache, mr1, mr2));
+}
+
+/*
+ * Comparison function for checking if any range of multirange overlaps given
+ * key range using binary search.
+ */
+static int
+multirange_range_overlaps_bsearch_comparison(TypeCacheEntry *typcache,
+											 RangeBound *lower, RangeBound *upper,
+											 void *key, bool *match)
+{
+	RangeBound *keyLower = (RangeBound *) key;
+	RangeBound *keyUpper = (RangeBound *) key + 1;
+
+	if (range_cmp_bounds(typcache, keyUpper, lower) < 0)
+		return -1;
+	if (range_cmp_bounds(typcache, keyLower, upper) > 0)
+		return -1;
+
+	*match = true;
+	return 0;
+}
+
+bool
+range_overlaps_multirange_internal(TypeCacheEntry *typcache, RangeType *r, MultirangeType *mr)
+{
+	TypeCacheEntry *rangetyp;
+	RangeBound	bounds[2];
+	bool		empty;
+
+	rangetyp = typcache->rngtype;
+
+	/*
+	 * Empties never overlap, even with empties. (This seems strange since
+	 * they *do* contain each other, but we want to follow how ranges work.)
+	 */
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		return false;
+
+	range_deserialize(rangetyp, r, &bounds[0], &bounds[1], &empty);
+	Assert(!empty);
+
+	return multirange_bsearch_match(rangetyp, mr, bounds,
+									multirange_range_overlaps_bsearch_comparison);
+}
+
+bool
+multirange_overlaps_multirange_internal(TypeCacheEntry *typcache, MultirangeType *mr1,
+										MultirangeType *mr2)
+{
+	TypeCacheEntry *rangetyp;
+	int32		range_count1;
+	int32		range_count2;
+	int32		i1;
+	int32		i2;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	/*
+	 * Empties never overlap, even with empties. (This seems strange since
+	 * they *do* contain each other, but we want to follow how ranges work.)
+	 */
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		return false;
+
+	rangetyp = typcache->rngtype;
+
+	range_count1 = mr1->rangeCount;
+	range_count2 = mr2->rangeCount;
+
+	/*
+	 * Every range in mr1 gets a chance to overlap with the ranges in mr2, but
+	 * we can use their ordering to avoid O(n^2). This is similar to
+	 * range_overlaps_multirange where r1 : r2 :: mrr : r, but there if we
+	 * don't find an overlap with r we're done, and here if we don't find an
+	 * overlap with r2 we try the next r2.
+	 */
+	i1 = 0;
+	multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
+	for (i1 = 0, i2 = 0; i2 < range_count2; i2++)
+	{
+		multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
+
+		/* Discard r1s while r1 << r2 */
+		while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
+		{
+			if (++i1 >= range_count1)
+				return false;
+			multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
+		}
+
+		/*
+		 * If r1 && r2, we're done, otherwise we failed to find an overlap for
+		 * r2, so go to the next one.
+		 */
+		if (range_bounds_overlaps(rangetyp, &lower1, &upper1, &lower2, &upper2))
+			return true;
+	}
+
+	/* We looked through all of mr2 without finding an overlap */
+	return false;
+}
+
+/* does not extend to right of? */
+Datum
+range_overleft_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	range_deserialize(typcache->rngtype, r, &lower1, &upper1, &empty);
+	Assert(!empty);
+	multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+						  &lower2, &upper2);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
+}
+
+Datum
+multirange_overleft_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+
+	if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+						  &lower1, &upper1);
+	range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
+	Assert(!empty);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
+}
+
+Datum
+multirange_overleft_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1,
+						  &lower1, &upper1);
+	multirange_get_bounds(typcache->rngtype, mr2, mr2->rangeCount - 1,
+						  &lower2, &upper2);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &upper1, &upper2) <= 0);
+}
+
+/* does not extend to left of? */
+Datum
+range_overright_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	range_deserialize(typcache->rngtype, r, &lower1, &upper1, &empty);
+	Assert(!empty);
+	multirange_get_bounds(typcache->rngtype, mr, 0, &lower2, &upper2);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
+}
+
+Datum
+multirange_overright_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+
+	if (MultirangeIsEmpty(mr) || RangeIsEmpty(r))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	multirange_get_bounds(typcache->rngtype, mr, 0, &lower1, &upper1);
+	range_deserialize(typcache->rngtype, r, &lower2, &upper2, &empty);
+	Assert(!empty);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
+}
+
+Datum
+multirange_overright_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		PG_RETURN_BOOL(false);
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	multirange_get_bounds(typcache->rngtype, mr1, 0, &lower1, &upper1);
+	multirange_get_bounds(typcache->rngtype, mr2, 0, &lower2, &upper2);
+
+	PG_RETURN_BOOL(range_cmp_bounds(typcache->rngtype, &lower1, &lower2) >= 0);
+}
+
+/* contains? */
+Datum
+multirange_contains_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache, mr1, mr2));
+}
+
+/* contained by? */
+Datum
+multirange_contained_by_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_contains_multirange_internal(typcache, mr2, mr1));
+}
+
+/*
+ * Test whether multirange mr1 contains every range from another multirange mr2.
+ */
+bool
+multirange_contains_multirange_internal(TypeCacheEntry *typcache,
+										MultirangeType *mr1, MultirangeType *mr2)
+{
+	TypeCacheEntry *rangetyp;
+	int32		range_count1 = mr1->rangeCount;
+	int32		range_count2 = mr2->rangeCount;
+	int			i1,
+				i2;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	rangetyp = typcache->rngtype;
+
+	/*
+	 * We follow the same logic for empties as ranges: - an empty multirange
+	 * contains an empty range/multirange. - an empty multirange can't contain
+	 * any other range/multirange. - an empty multirange is contained by any
+	 * other range/multirange.
+	 */
+
+	if (range_count2 == 0)
+		return true;
+	if (range_count1 == 0)
+		return false;
+
+	/*
+	 * Every range in mr2 must be contained by some range in mr1. To avoid
+	 * O(n^2) we walk through both ranges in tandem.
+	 */
+	i1 = 0;
+	multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
+	for (i2 = 0; i2 < range_count2; i2++)
+	{
+		multirange_get_bounds(rangetyp, mr2, i2, &lower2, &upper2);
+
+		/* Discard r1s while r1 << r2 */
+		while (range_cmp_bounds(rangetyp, &upper1, &lower2) < 0)
+		{
+			if (++i1 >= range_count1)
+				return false;
+			multirange_get_bounds(rangetyp, mr1, i1, &lower1, &upper1);
+		}
+
+		/*
+		 * If r1 @> r2, go to the next r2, otherwise return false (since every
+		 * r1[n] and r1[n+1] must have a gap). Note this will give weird
+		 * answers if you don't canonicalize, e.g. with a custom
+		 * int2multirange {[1,1], [2,2]} there is a "gap". But that is
+		 * consistent with other range operators, e.g. '[1,1]'::int2range -|-
+		 * '[2,2]'::int2range is false.
+		 */
+		if (!range_bounds_contains(rangetyp, &lower1, &upper1,
+								   &lower2, &upper2))
+			return false;
+	}
+
+	/* All ranges in mr2 are satisfied */
+	return true;
+}
+
+/* strictly left of? */
+Datum
+range_before_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_before_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_before_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_after_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_before_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_before_multirange_internal(typcache, mr1, mr2));
+}
+
+/* strictly right of? */
+Datum
+range_after_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_after_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_after_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_before_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_after_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	PG_RETURN_BOOL(multirange_before_multirange_internal(typcache, mr2, mr1));
+}
+
+/* strictly left of? (internal version) */
+bool
+range_before_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+								 MultirangeType *mr)
+{
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		return false;
+
+	range_deserialize(typcache->rngtype, r, &lower1, &upper1, &empty);
+	Assert(!empty);
+
+	multirange_get_bounds(typcache->rngtype, mr, 0,
+						  &lower2, &upper2);
+
+	return (range_cmp_bounds(typcache->rngtype, &upper1, &lower2) < 0);
+}
+
+bool
+multirange_before_multirange_internal(TypeCacheEntry *typcache,
+									  MultirangeType *mr1,
+									  MultirangeType *mr2)
+{
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		return false;
+
+	multirange_get_bounds(typcache->rngtype, mr1, mr1->rangeCount - 1,
+						  &lower1, &upper1);
+	multirange_get_bounds(typcache->rngtype, mr2, 0,
+						  &lower2, &upper2);
+
+	return (range_cmp_bounds(typcache->rngtype, &upper1, &lower2) < 0);
+}
+
+/* strictly right of? (internal version) */
+bool
+range_after_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+								MultirangeType *mr)
+{
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+	int32		range_count;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		return false;
+
+	range_deserialize(typcache->rngtype, r, &lower1, &upper1, &empty);
+	Assert(!empty);
+
+	range_count = mr->rangeCount;
+	multirange_get_bounds(typcache->rngtype, mr, range_count - 1,
+						  &lower2, &upper2);
+
+	return (range_cmp_bounds(typcache->rngtype, &lower1, &upper2) > 0);
+}
+
+bool
+range_adjacent_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+								   MultirangeType *mr)
+{
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+	bool		empty;
+	int32		range_count;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		return false;
+
+	range_deserialize(typcache->rngtype, r, &lower1, &upper1, &empty);
+	Assert(!empty);
+
+	range_count = mr->rangeCount;
+	multirange_get_bounds(typcache->rngtype, mr, 0,
+						  &lower2, &upper2);
+
+	if (bounds_adjacent(typcache->rngtype, upper1, lower2))
+		return true;
+
+	if (range_count > 1)
+		multirange_get_bounds(typcache->rngtype, mr, range_count - 1,
+							  &lower2, &upper2);
+
+	if (bounds_adjacent(typcache->rngtype, upper2, lower1))
+		return true;
+
+	return false;
+}
+
+/* adjacent to? */
+Datum
+range_adjacent_multirange(PG_FUNCTION_ARGS)
+{
+	RangeType  *r = PG_GETARG_RANGE_P(0);
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_adjacent_range(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	RangeType  *r = PG_GETARG_RANGE_P(1);
+	TypeCacheEntry *typcache;
+
+	if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
+		return false;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	PG_RETURN_BOOL(range_adjacent_multirange_internal(typcache, r, mr));
+}
+
+Datum
+multirange_adjacent_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	TypeCacheEntry *typcache;
+	int32		range_count1;
+	int32		range_count2;
+	RangeBound	lower1,
+				upper1,
+				lower2,
+				upper2;
+
+	if (MultirangeIsEmpty(mr1) || MultirangeIsEmpty(mr2))
+		return false;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	range_count1 = mr1->rangeCount;
+	range_count2 = mr2->rangeCount;
+	multirange_get_bounds(typcache->rngtype, mr1, range_count1 - 1,
+						  &lower1, &upper1);
+	multirange_get_bounds(typcache->rngtype, mr2, 0,
+						  &lower2, &upper2);
+	if (bounds_adjacent(typcache->rngtype, upper1, lower2))
+		PG_RETURN_BOOL(true);
+
+	if (range_count1 > 1)
+		multirange_get_bounds(typcache->rngtype, mr1, 0,
+							  &lower1, &upper1);
+	if (range_count2 > 1)
+		multirange_get_bounds(typcache->rngtype, mr2, range_count2 - 1,
+							  &lower2, &upper2);
+	if (bounds_adjacent(typcache->rngtype, upper2, lower1))
+		PG_RETURN_BOOL(true);
+	PG_RETURN_BOOL(false);
+}
+
+/* Btree support */
+
+/* btree comparator */
+Datum
+multirange_cmp(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr1 = PG_GETARG_MULTIRANGE_P(0);
+	MultirangeType *mr2 = PG_GETARG_MULTIRANGE_P(1);
+	int32		range_count_1;
+	int32		range_count_2;
+	int32		range_count_max;
+	int32		i;
+	TypeCacheEntry *typcache;
+	int			cmp = 0;		/* If both are empty we'll use this. */
+
+	/* Different types should be prevented by ANYMULTIRANGE matching rules */
+	if (MultirangeTypeGetOid(mr1) != MultirangeTypeGetOid(mr2))
+		elog(ERROR, "multirange types do not match");
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr1));
+
+	range_count_1 = mr1->rangeCount;
+	range_count_2 = mr2->rangeCount;
+
+	/* Loop over source data */
+	range_count_max = Max(range_count_1, range_count_2);
+	for (i = 0; i < range_count_max; i++)
+	{
+		RangeBound	lower1,
+					upper1,
+					lower2,
+					upper2;
+
+		/*
+		 * If one multirange is shorter, it's as if it had empty ranges at the
+		 * end to extend its length. An empty range compares earlier than any
+		 * other range, so the shorter multirange comes before the longer.
+		 * This is the same behavior as in other types, e.g. in strings 'aaa'
+		 * < 'aaaaaa'.
+		 */
+		if (i >= range_count_1)
+		{
+			cmp = -1;
+			break;
+		}
+		if (i >= range_count_2)
+		{
+			cmp = 1;
+			break;
+		}
+
+		multirange_get_bounds(typcache->rngtype, mr1, i, &lower1, &upper1);
+		multirange_get_bounds(typcache->rngtype, mr2, i, &lower2, &upper2);
+
+		cmp = range_cmp_bounds(typcache->rngtype, &lower1, &lower2);
+		if (cmp == 0)
+			cmp = range_cmp_bounds(typcache->rngtype, &upper1, &upper2);
+		if (cmp != 0)
+			break;
+	}
+
+	PG_FREE_IF_COPY(mr1, 0);
+	PG_FREE_IF_COPY(mr2, 1);
+
+	PG_RETURN_INT32(cmp);
+}
+
+/* inequality operators using the multirange_cmp function */
+Datum
+multirange_lt(PG_FUNCTION_ARGS)
+{
+	int			cmp = multirange_cmp(fcinfo);
+
+	PG_RETURN_BOOL(cmp < 0);
+}
+
+Datum
+multirange_le(PG_FUNCTION_ARGS)
+{
+	int			cmp = multirange_cmp(fcinfo);
+
+	PG_RETURN_BOOL(cmp <= 0);
+}
+
+Datum
+multirange_ge(PG_FUNCTION_ARGS)
+{
+	int			cmp = multirange_cmp(fcinfo);
+
+	PG_RETURN_BOOL(cmp >= 0);
+}
+
+Datum
+multirange_gt(PG_FUNCTION_ARGS)
+{
+	int			cmp = multirange_cmp(fcinfo);
+
+	PG_RETURN_BOOL(cmp > 0);
+}
+
+/* multirange -> range functions */
+
+/* Find the smallest range that includes everything in the multirange */
+Datum
+range_merge_from_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	Oid			mltrngtypoid = MultirangeTypeGetOid(mr);
+	TypeCacheEntry *typcache;
+	RangeType  *result;
+
+	typcache = multirange_get_typcache(fcinfo, mltrngtypoid);
+
+	if (MultirangeIsEmpty(mr))
+	{
+		result = make_empty_range(typcache->rngtype);
+	}
+	else if (mr->rangeCount == 1)
+	{
+		result = multirange_get_range(typcache->rngtype, mr, 0);
+	}
+	else
+	{
+		RangeBound	firstLower,
+					firstUpper,
+					lastLower,
+					lastUpper;
+
+		multirange_get_bounds(typcache->rngtype, mr, 0,
+							  &firstLower, &firstUpper);
+		multirange_get_bounds(typcache->rngtype, mr, mr->rangeCount - 1,
+							  &lastLower, &lastUpper);
+
+		result = make_range(typcache->rngtype, &firstLower, &lastUpper, false);
+	}
+
+	PG_RETURN_RANGE_P(result);
+}
+
+/* Hash support */
+
+/* hash a multirange value */
+Datum
+hash_multirange(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	uint32		result = 1;
+	TypeCacheEntry *typcache,
+			   *scache;
+	int32		range_count,
+				i;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	scache = typcache->rngtype->rngelemtype;
+	if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
+	{
+		scache = lookup_type_cache(scache->type_id,
+								   TYPECACHE_HASH_PROC_FINFO);
+		if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
+			ereport(ERROR,
+					(errcode(ERRCODE_UNDEFINED_FUNCTION),
+					 errmsg("could not identify a hash function for type %s",
+							format_type_be(scache->type_id))));
+	}
+
+	range_count = mr->rangeCount;
+	for (i = 0; i < range_count; i++)
+	{
+		RangeBound	lower,
+					upper;
+		uint8		flags = MultirangeGetFlagsPtr(mr)[i];
+		uint32		lower_hash;
+		uint32		upper_hash;
+		uint32		range_hash;
+
+		multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
+
+		if (RANGE_HAS_LBOUND(flags))
+			lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
+														  typcache->rngtype->rng_collation,
+														  lower.val));
+		else
+			lower_hash = 0;
+
+		if (RANGE_HAS_UBOUND(flags))
+			upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
+														  typcache->rngtype->rng_collation,
+														  upper.val));
+		else
+			upper_hash = 0;
+
+		/* Merge hashes of flags and bounds */
+		range_hash = hash_uint32((uint32) flags);
+		range_hash ^= lower_hash;
+		range_hash = (range_hash << 1) | (range_hash >> 31);
+		range_hash ^= upper_hash;
+
+		/*
+		 * Use the same approach as hash_array to combine the individual
+		 * elements' hash values:
+		 */
+		result = (result << 5) - result + range_hash;
+	}
+
+	PG_FREE_IF_COPY(mr, 0);
+
+	PG_RETURN_UINT32(result);
+}
+
+/*
+ * Returns 64-bit value by hashing a value to a 64-bit value, with a seed.
+ * Otherwise, similar to hash_multirange.
+ */
+Datum
+hash_multirange_extended(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	Datum		seed = PG_GETARG_DATUM(1);
+	uint64		result = 1;
+	TypeCacheEntry *typcache,
+			   *scache;
+	int32		range_count,
+				i;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+	scache = typcache->rngtype->rngelemtype;
+	if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
+	{
+		scache = lookup_type_cache(scache->type_id,
+								   TYPECACHE_HASH_EXTENDED_PROC_FINFO);
+		if (!OidIsValid(scache->hash_extended_proc_finfo.fn_oid))
+			ereport(ERROR,
+					(errcode(ERRCODE_UNDEFINED_FUNCTION),
+					 errmsg("could not identify a hash function for type %s",
+							format_type_be(scache->type_id))));
+	}
+
+	range_count = mr->rangeCount;
+	for (i = 0; i < range_count; i++)
+	{
+		RangeBound	lower,
+					upper;
+		uint8		flags = MultirangeGetFlagsPtr(mr)[i];
+		uint64		lower_hash;
+		uint64		upper_hash;
+		uint64		range_hash;
+
+		multirange_get_bounds(typcache->rngtype, mr, i, &lower, &upper);
+
+		if (RANGE_HAS_LBOUND(flags))
+			lower_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
+														  typcache->rngtype->rng_collation,
+														  lower.val,
+														  seed));
+		else
+			lower_hash = 0;
+
+		if (RANGE_HAS_UBOUND(flags))
+			upper_hash = DatumGetUInt64(FunctionCall2Coll(&scache->hash_extended_proc_finfo,
+														  typcache->rngtype->rng_collation,
+														  upper.val,
+														  seed));
+		else
+			upper_hash = 0;
+
+		/* Merge hashes of flags and bounds */
+		range_hash = DatumGetUInt64(hash_uint32_extended((uint32) flags,
+														 DatumGetInt64(seed)));
+		range_hash ^= lower_hash;
+		range_hash = ROTATE_HIGH_AND_LOW_32BITS(range_hash);
+		range_hash ^= upper_hash;
+
+		/*
+		 * Use the same approach as hash_array to combine the individual
+		 * elements' hash values:
+		 */
+		result = (result << 5) - result + range_hash;
+	}
+
+	PG_FREE_IF_COPY(mr, 0);
+
+	PG_RETURN_UINT64(result);
+}
diff --git a/src/backend/utils/adt/multirangetypes_selfuncs.c b/src/backend/utils/adt/multirangetypes_selfuncs.c
new file mode 100644
index 00000000000..7259af0b853
--- /dev/null
+++ b/src/backend/utils/adt/multirangetypes_selfuncs.c
@@ -0,0 +1,1320 @@
+/*-------------------------------------------------------------------------
+ *
+ * multirangetypes_selfuncs.c
+ *	  Functions for selectivity estimation of multirange operators
+ *
+ * Estimates are based on histograms of lower and upper bounds, and the
+ * fraction of empty multiranges.
+ *
+ * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/adt/multirangetypes_selfuncs.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include <math.h>
+
+#include "access/htup_details.h"
+#include "catalog/pg_operator.h"
+#include "catalog/pg_statistic.h"
+#include "catalog/pg_type.h"
+#include "utils/float.h"
+#include "utils/fmgrprotos.h"
+#include "utils/lsyscache.h"
+#include "utils/rangetypes.h"
+#include "utils/multirangetypes.h"
+#include "utils/selfuncs.h"
+#include "utils/typcache.h"
+
+static double calc_multirangesel(TypeCacheEntry *typcache,
+								 VariableStatData *vardata,
+								 const MultirangeType *constval, Oid operator);
+static double default_multirange_selectivity(Oid operator);
+static double default_multirange_selectivity(Oid operator);
+static double calc_hist_selectivity(TypeCacheEntry *typcache,
+									VariableStatData *vardata,
+									const MultirangeType *constval,
+									Oid operator);
+static double calc_hist_selectivity_scalar(TypeCacheEntry *typcache,
+										   const RangeBound *constbound,
+										   const RangeBound *hist,
+										   int hist_nvalues, bool equal);
+static int	rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value,
+						   const RangeBound *hist, int hist_length, bool equal);
+static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value,
+						   const RangeBound *hist1, const RangeBound *hist2);
+static float8 get_len_position(double value, double hist1, double hist2);
+static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1,
+						   const RangeBound *bound2);
+static int	length_hist_bsearch(Datum *length_hist_values,
+								int length_hist_nvalues, double value,
+								bool equal);
+static double calc_length_hist_frac(Datum *length_hist_values,
+									int length_hist_nvalues, double length1,
+									double length2, bool equal);
+static double calc_hist_selectivity_contained(TypeCacheEntry *typcache,
+											  const RangeBound *lower,
+											  RangeBound *upper,
+											  const RangeBound *hist_lower,
+											  int hist_nvalues,
+											  Datum *length_hist_values,
+											  int length_hist_nvalues);
+static double calc_hist_selectivity_contains(TypeCacheEntry *typcache,
+											 const RangeBound *lower,
+											 const RangeBound *upper,
+											 const RangeBound *hist_lower,
+											 int hist_nvalues,
+											 Datum *length_hist_values,
+											 int length_hist_nvalues);
+
+/*
+ * Returns a default selectivity estimate for given operator, when we don't
+ * have statistics or cannot use them for some reason.
+ */
+static double
+default_multirange_selectivity(Oid operator)
+{
+	switch (operator)
+	{
+		case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
+		case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
+			return 0.01;
+
+		case OID_MULTIRANGE_CONTAINS_RANGE_OP:
+		case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
+		case OID_MULTIRANGE_RANGE_CONTAINED_OP:
+		case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
+			return 0.005;
+
+		case OID_MULTIRANGE_CONTAINS_ELEM_OP:
+		case OID_MULTIRANGE_ELEM_CONTAINED_OP:
+
+			/*
+			 * "multirange @> elem" is more or less identical to a scalar
+			 * inequality "A >= b AND A <= c".
+			 */
+			return DEFAULT_MULTIRANGE_INEQ_SEL;
+
+		case OID_MULTIRANGE_LESS_OP:
+		case OID_MULTIRANGE_LESS_EQUAL_OP:
+		case OID_MULTIRANGE_GREATER_OP:
+		case OID_MULTIRANGE_GREATER_EQUAL_OP:
+		case OID_MULTIRANGE_LEFT_RANGE_OP:
+		case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
+		case OID_RANGE_LEFT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_RIGHT_RANGE_OP:
+		case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
+		case OID_RANGE_RIGHT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
+		case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
+		case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+			/* these are similar to regular scalar inequalities */
+			return DEFAULT_INEQ_SEL;
+
+		default:
+
+			/*
+			 * all multirange operators should be handled above, but just in
+			 * case
+			 */
+			return 0.01;
+	}
+}
+
+/*
+ * multirangesel -- restriction selectivity for multirange operators
+ */
+Datum
+multirangesel(PG_FUNCTION_ARGS)
+{
+	PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
+	Oid			operator = PG_GETARG_OID(1);
+	List	   *args = (List *) PG_GETARG_POINTER(2);
+	int			varRelid = PG_GETARG_INT32(3);
+	VariableStatData vardata;
+	Node	   *other;
+	bool		varonleft;
+	Selectivity selec;
+	TypeCacheEntry *typcache = NULL;
+	MultirangeType *constmultirange = NULL;
+	RangeType  *constrange = NULL;
+
+	/*
+	 * If expression is not (variable op something) or (something op
+	 * variable), then punt and return a default estimate.
+	 */
+	if (!get_restriction_variable(root, args, varRelid,
+								  &vardata, &other, &varonleft))
+		PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
+
+	/*
+	 * Can't do anything useful if the something is not a constant, either.
+	 */
+	if (!IsA(other, Const))
+	{
+		ReleaseVariableStats(vardata);
+		PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
+	}
+
+	/*
+	 * All the multirange operators are strict, so we can cope with a NULL
+	 * constant right away.
+	 */
+	if (((Const *) other)->constisnull)
+	{
+		ReleaseVariableStats(vardata);
+		PG_RETURN_FLOAT8(0.0);
+	}
+
+	/*
+	 * If var is on the right, commute the operator, so that we can assume the
+	 * var is on the left in what follows.
+	 */
+	if (!varonleft)
+	{
+		/* we have other Op var, commute to make var Op other */
+		operator = get_commutator(operator);
+		if (!operator)
+		{
+			/* Use default selectivity (should we raise an error instead?) */
+			ReleaseVariableStats(vardata);
+			PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
+		}
+	}
+
+	/*
+	 * OK, there's a Var and a Const we're dealing with here.  We need the
+	 * Const to be of same multirange type as the column, else we can't do
+	 * anything useful. (Such cases will likely fail at runtime, but here we'd
+	 * rather just return a default estimate.)
+	 *
+	 * If the operator is "multirange @> element", the constant should be of
+	 * the element type of the multirange column. Convert it to a multirange
+	 * that includes only that single point, so that we don't need special
+	 * handling for that in what follows.
+	 */
+	if (operator == OID_MULTIRANGE_CONTAINS_ELEM_OP)
+	{
+		typcache = multirange_get_typcache(fcinfo, vardata.vartype);
+
+		if (((Const *) other)->consttype == typcache->rngtype->rngelemtype->type_id)
+		{
+			RangeBound	lower,
+						upper;
+
+			lower.inclusive = true;
+			lower.val = ((Const *) other)->constvalue;
+			lower.infinite = false;
+			lower.lower = true;
+			upper.inclusive = true;
+			upper.val = ((Const *) other)->constvalue;
+			upper.infinite = false;
+			upper.lower = false;
+			constrange = range_serialize(typcache->rngtype, &lower, &upper, false);
+			constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
+											  1, &constrange);
+		}
+	}
+	else if (operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
+			 operator == OID_MULTIRANGE_OVERLAPS_RANGE_OP ||
+			 operator == OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP ||
+			 operator == OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP ||
+			 operator == OID_MULTIRANGE_LEFT_RANGE_OP ||
+			 operator == OID_MULTIRANGE_RIGHT_RANGE_OP)
+	{
+		/*
+		 * Promote a range in "multirange OP range" just like we do an element
+		 * in "multirange OP element".
+		 */
+		typcache = multirange_get_typcache(fcinfo, vardata.vartype);
+		if (((Const *) other)->consttype == typcache->rngtype->type_id)
+		{
+			constrange = DatumGetRangeTypeP(((Const *) other)->constvalue);
+			constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
+											  1, &constrange);
+		}
+	}
+	else if (operator == OID_RANGE_OVERLAPS_MULTIRANGE_OP ||
+			 operator == OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP ||
+			 operator == OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP ||
+			 operator == OID_RANGE_LEFT_MULTIRANGE_OP ||
+			 operator == OID_RANGE_RIGHT_MULTIRANGE_OP ||
+			 operator == OID_MULTIRANGE_ELEM_CONTAINED_OP ||
+			 operator == OID_MULTIRANGE_RANGE_CONTAINED_OP)
+	{
+		/*
+		 * Here, the Var is the elem/range, not the multirange.  For now we
+		 * just punt and return the default estimate.  In future we could
+		 * disassemble the multirange constant to do something more
+		 * intelligent.
+		 */
+	}
+	else if (((Const *) other)->consttype == vardata.vartype)
+	{
+		/* Both sides are the same multirange type */
+		typcache = multirange_get_typcache(fcinfo, vardata.vartype);
+
+		constmultirange = DatumGetMultirangeTypeP(((Const *) other)->constvalue);
+	}
+
+	/*
+	 * If we got a valid constant on one side of the operator, proceed to
+	 * estimate using statistics. Otherwise punt and return a default constant
+	 * estimate.  Note that calc_multirangesel need not handle
+	 * OID_MULTIRANGE_*_CONTAINED_OP.
+	 */
+	if (constmultirange)
+		selec = calc_multirangesel(typcache, &vardata, constmultirange, operator);
+	else
+		selec = default_multirange_selectivity(operator);
+
+	ReleaseVariableStats(vardata);
+
+	CLAMP_PROBABILITY(selec);
+
+	PG_RETURN_FLOAT8((float8) selec);
+}
+
+static double
+calc_multirangesel(TypeCacheEntry *typcache, VariableStatData *vardata,
+				   const MultirangeType *constval, Oid operator)
+{
+	double		hist_selec;
+	double		selec;
+	float4		empty_frac,
+				null_frac;
+
+	/*
+	 * First look up the fraction of NULLs and empty multiranges from
+	 * pg_statistic.
+	 */
+	if (HeapTupleIsValid(vardata->statsTuple))
+	{
+		Form_pg_statistic stats;
+		AttStatsSlot sslot;
+
+		stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
+		null_frac = stats->stanullfrac;
+
+		/* Try to get fraction of empty multiranges */
+		if (get_attstatsslot(&sslot, vardata->statsTuple,
+							 STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
+							 InvalidOid,
+							 ATTSTATSSLOT_NUMBERS))
+		{
+			if (sslot.nnumbers != 1)
+				elog(ERROR, "invalid empty fraction statistic");	/* shouldn't happen */
+			empty_frac = sslot.numbers[0];
+			free_attstatsslot(&sslot);
+		}
+		else
+		{
+			/* No empty fraction statistic. Assume no empty ranges. */
+			empty_frac = 0.0;
+		}
+	}
+	else
+	{
+		/*
+		 * No stats are available. Follow through the calculations below
+		 * anyway, assuming no NULLs and no empty multiranges. This still
+		 * allows us to give a better-than-nothing estimate based on whether
+		 * the constant is an empty multirange or not.
+		 */
+		null_frac = 0.0;
+		empty_frac = 0.0;
+	}
+
+	if (MultirangeIsEmpty(constval))
+	{
+		/*
+		 * An empty multirange matches all multiranges, all empty multiranges,
+		 * or nothing, depending on the operator
+		 */
+		switch (operator)
+		{
+				/* these return false if either argument is empty */
+			case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
+			case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+			case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
+			case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+			case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
+			case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
+				/* nothing is less than an empty multirange */
+			case OID_MULTIRANGE_LESS_OP:
+				selec = 0.0;
+				break;
+
+				/*
+				 * only empty multiranges can be contained by an empty
+				 * multirange
+				 */
+			case OID_MULTIRANGE_RANGE_CONTAINED_OP:
+			case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
+				/* only empty ranges are <= an empty multirange */
+			case OID_MULTIRANGE_LESS_EQUAL_OP:
+				selec = empty_frac;
+				break;
+
+				/* everything contains an empty multirange */
+			case OID_MULTIRANGE_CONTAINS_RANGE_OP:
+			case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
+				/* everything is >= an empty multirange */
+			case OID_MULTIRANGE_GREATER_EQUAL_OP:
+				selec = 1.0;
+				break;
+
+				/* all non-empty multiranges are > an empty multirange */
+			case OID_MULTIRANGE_GREATER_OP:
+				selec = 1.0 - empty_frac;
+				break;
+
+				/* an element cannot be empty */
+			case OID_MULTIRANGE_ELEM_CONTAINED_OP:
+			case OID_MULTIRANGE_CONTAINS_ELEM_OP:
+			default:
+				elog(ERROR, "unexpected operator %u", operator);
+				selec = 0.0;	/* keep compiler quiet */
+				break;
+		}
+	}
+	else
+	{
+		/*
+		 * Calculate selectivity using bound histograms. If that fails for
+		 * some reason, e.g no histogram in pg_statistic, use the default
+		 * constant estimate for the fraction of non-empty values. This is
+		 * still somewhat better than just returning the default estimate,
+		 * because this still takes into account the fraction of empty and
+		 * NULL tuples, if we had statistics for them.
+		 */
+		hist_selec = calc_hist_selectivity(typcache, vardata, constval,
+										   operator);
+		if (hist_selec < 0.0)
+			hist_selec = default_multirange_selectivity(operator);
+
+		/*
+		 * Now merge the results for the empty multiranges and histogram
+		 * calculations, realizing that the histogram covers only the
+		 * non-null, non-empty values.
+		 */
+		if (operator == OID_MULTIRANGE_ELEM_CONTAINED_OP ||
+			operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
+			operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
+		{
+			/* empty is contained by anything non-empty */
+			selec = (1.0 - empty_frac) * hist_selec + empty_frac;
+		}
+		else
+		{
+			/* with any other operator, empty Op non-empty matches nothing */
+			selec = (1.0 - empty_frac) * hist_selec;
+		}
+	}
+
+	/* all multirange operators are strict */
+	selec *= (1.0 - null_frac);
+
+	/* result should be in range, but make sure... */
+	CLAMP_PROBABILITY(selec);
+
+	return selec;
+}
+
+/*
+ * Calculate multirange operator selectivity using histograms of multirange bounds.
+ *
+ * This estimate is for the portion of values that are not empty and not
+ * NULL.
+ */
+static double
+calc_hist_selectivity(TypeCacheEntry *typcache, VariableStatData *vardata,
+					  const MultirangeType *constval, Oid operator)
+{
+	TypeCacheEntry *rng_typcache = typcache->rngtype;
+	AttStatsSlot hslot;
+	AttStatsSlot lslot;
+	int			nhist;
+	RangeBound *hist_lower;
+	RangeBound *hist_upper;
+	int			i;
+	RangeBound	const_lower;
+	RangeBound	const_upper;
+	RangeBound	tmp;
+	double		hist_selec;
+
+	/* Can't use the histogram with insecure multirange support functions */
+	if (!statistic_proc_security_check(vardata,
+									   rng_typcache->rng_cmp_proc_finfo.fn_oid))
+		return -1;
+	if (OidIsValid(rng_typcache->rng_subdiff_finfo.fn_oid) &&
+		!statistic_proc_security_check(vardata,
+									   rng_typcache->rng_subdiff_finfo.fn_oid))
+		return -1;
+
+	/* Try to get histogram of ranges */
+	if (!(HeapTupleIsValid(vardata->statsTuple) &&
+		  get_attstatsslot(&hslot, vardata->statsTuple,
+						   STATISTIC_KIND_BOUNDS_HISTOGRAM, InvalidOid,
+						   ATTSTATSSLOT_VALUES)))
+		return -1.0;
+
+	/* check that it's a histogram, not just a dummy entry */
+	if (hslot.nvalues < 2)
+	{
+		free_attstatsslot(&hslot);
+		return -1.0;
+	}
+
+	/*
+	 * Convert histogram of ranges into histograms of its lower and upper
+	 * bounds.
+	 */
+	nhist = hslot.nvalues;
+	hist_lower = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
+	hist_upper = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
+	for (i = 0; i < nhist; i++)
+	{
+		bool		empty;
+
+		range_deserialize(rng_typcache, DatumGetRangeTypeP(hslot.values[i]),
+						  &hist_lower[i], &hist_upper[i], &empty);
+		/* The histogram should not contain any empty ranges */
+		if (empty)
+			elog(ERROR, "bounds histogram contains an empty range");
+	}
+
+	/* @> and @< also need a histogram of range lengths */
+	if (operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
+		operator == OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP ||
+		operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
+		operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
+	{
+		if (!(HeapTupleIsValid(vardata->statsTuple) &&
+			  get_attstatsslot(&lslot, vardata->statsTuple,
+							   STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
+							   InvalidOid,
+							   ATTSTATSSLOT_VALUES)))
+		{
+			free_attstatsslot(&hslot);
+			return -1.0;
+		}
+
+		/* check that it's a histogram, not just a dummy entry */
+		if (lslot.nvalues < 2)
+		{
+			free_attstatsslot(&lslot);
+			free_attstatsslot(&hslot);
+			return -1.0;
+		}
+	}
+	else
+		memset(&lslot, 0, sizeof(lslot));
+
+	/* Extract the bounds of the constant value. */
+	Assert(constval->rangeCount > 0);
+	multirange_get_bounds(rng_typcache, constval, 0,
+						  &const_lower, &tmp);
+	multirange_get_bounds(rng_typcache, constval, constval->rangeCount - 1,
+						  &tmp, &const_upper);
+
+	/*
+	 * Calculate selectivity comparing the lower or upper bound of the
+	 * constant with the histogram of lower or upper bounds.
+	 */
+	switch (operator)
+	{
+		case OID_MULTIRANGE_LESS_OP:
+
+			/*
+			 * The regular b-tree comparison operators (<, <=, >, >=) compare
+			 * the lower bounds first, and the upper bounds for values with
+			 * equal lower bounds. Estimate that by comparing the lower bounds
+			 * only. This gives a fairly accurate estimate assuming there
+			 * aren't many rows with a lower bound equal to the constant's
+			 * lower bound.
+			 */
+			hist_selec =
+				calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+											 hist_lower, nhist, false);
+			break;
+
+		case OID_MULTIRANGE_LESS_EQUAL_OP:
+			hist_selec =
+				calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+											 hist_lower, nhist, true);
+			break;
+
+		case OID_MULTIRANGE_GREATER_OP:
+			hist_selec =
+				1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+												 hist_lower, nhist, false);
+			break;
+
+		case OID_MULTIRANGE_GREATER_EQUAL_OP:
+			hist_selec =
+				1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+												 hist_lower, nhist, true);
+			break;
+
+		case OID_RANGE_LEFT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_LEFT_RANGE_OP:
+		case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
+			/* var << const when upper(var) < lower(const) */
+			hist_selec =
+				calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+											 hist_upper, nhist, false);
+			break;
+
+		case OID_RANGE_RIGHT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_RIGHT_RANGE_OP:
+		case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
+			/* var >> const when lower(var) > upper(const) */
+			hist_selec =
+				1 - calc_hist_selectivity_scalar(rng_typcache, &const_upper,
+												 hist_lower, nhist, true);
+			break;
+
+		case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
+			/* compare lower bounds */
+			hist_selec =
+				1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+												 hist_lower, nhist, false);
+			break;
+
+		case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
+			/* compare upper bounds */
+			hist_selec =
+				calc_hist_selectivity_scalar(rng_typcache, &const_upper,
+											 hist_upper, nhist, true);
+			break;
+
+		case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
+		case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
+		case OID_MULTIRANGE_CONTAINS_ELEM_OP:
+
+			/*
+			 * A && B <=> NOT (A << B OR A >> B).
+			 *
+			 * Since A << B and A >> B are mutually exclusive events we can
+			 * sum their probabilities to find probability of (A << B OR A >>
+			 * B).
+			 *
+			 * "multirange @> elem" is equivalent to "multirange &&
+			 * {[elem,elem]}". The caller already constructed the singular
+			 * range from the element constant, so just treat it the same as
+			 * &&.
+			 */
+			hist_selec =
+				calc_hist_selectivity_scalar(rng_typcache,
+											 &const_lower, hist_upper,
+											 nhist, false);
+			hist_selec +=
+				(1.0 - calc_hist_selectivity_scalar(rng_typcache,
+													&const_upper, hist_lower,
+													nhist, true));
+			hist_selec = 1.0 - hist_selec;
+			break;
+
+		case OID_MULTIRANGE_CONTAINS_RANGE_OP:
+		case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
+			hist_selec =
+				calc_hist_selectivity_contains(rng_typcache, &const_lower,
+											   &const_upper, hist_lower, nhist,
+											   lslot.values, lslot.nvalues);
+			break;
+
+		case OID_MULTIRANGE_RANGE_CONTAINED_OP:
+		case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
+			if (const_lower.infinite)
+			{
+				/*
+				 * Lower bound no longer matters. Just estimate the fraction
+				 * with an upper bound <= const upper bound
+				 */
+				hist_selec =
+					calc_hist_selectivity_scalar(rng_typcache, &const_upper,
+												 hist_upper, nhist, true);
+			}
+			else if (const_upper.infinite)
+			{
+				hist_selec =
+					1.0 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
+													   hist_lower, nhist, false);
+			}
+			else
+			{
+				hist_selec =
+					calc_hist_selectivity_contained(rng_typcache, &const_lower,
+													&const_upper, hist_lower, nhist,
+													lslot.values, lslot.nvalues);
+			}
+			break;
+
+		default:
+			elog(ERROR, "unknown multirange operator %u", operator);
+			hist_selec = -1.0;	/* keep compiler quiet */
+			break;
+	}
+
+	free_attstatsslot(&lslot);
+	free_attstatsslot(&hslot);
+
+	return hist_selec;
+}
+
+
+/*
+ * Look up the fraction of values less than (or equal, if 'equal' argument
+ * is true) a given const in a histogram of range bounds.
+ */
+static double
+calc_hist_selectivity_scalar(TypeCacheEntry *typcache, const RangeBound *constbound,
+							 const RangeBound *hist, int hist_nvalues, bool equal)
+{
+	Selectivity selec;
+	int			index;
+
+	/*
+	 * Find the histogram bin the given constant falls into. Estimate
+	 * selectivity as the number of preceding whole bins.
+	 */
+	index = rbound_bsearch(typcache, constbound, hist, hist_nvalues, equal);
+	selec = (Selectivity) (Max(index, 0)) / (Selectivity) (hist_nvalues - 1);
+
+	/* Adjust using linear interpolation within the bin */
+	if (index >= 0 && index < hist_nvalues - 1)
+		selec += get_position(typcache, constbound, &hist[index],
+							  &hist[index + 1]) / (Selectivity) (hist_nvalues - 1);
+
+	return selec;
+}
+
+/*
+ * Binary search on an array of range bounds. Returns greatest index of range
+ * bound in array which is less(less or equal) than given range bound. If all
+ * range bounds in array are greater or equal(greater) than given range bound,
+ * return -1. When "equal" flag is set conditions in brackets are used.
+ *
+ * This function is used in scalar operator selectivity estimation. Another
+ * goal of this function is to find a histogram bin where to stop
+ * interpolation of portion of bounds which are less or equal to given bound.
+ */
+static int
+rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist,
+			   int hist_length, bool equal)
+{
+	int			lower = -1,
+				upper = hist_length - 1,
+				cmp,
+				middle;
+
+	while (lower < upper)
+	{
+		middle = (lower + upper + 1) / 2;
+		cmp = range_cmp_bounds(typcache, &hist[middle], value);
+
+		if (cmp < 0 || (equal && cmp == 0))
+			lower = middle;
+		else
+			upper = middle - 1;
+	}
+	return lower;
+}
+
+
+/*
+ * Binary search on length histogram. Returns greatest index of range length in
+ * histogram which is less than (less than or equal) the given length value. If
+ * all lengths in the histogram are greater than (greater than or equal) the
+ * given length, returns -1.
+ */
+static int
+length_hist_bsearch(Datum *length_hist_values, int length_hist_nvalues,
+					double value, bool equal)
+{
+	int			lower = -1,
+				upper = length_hist_nvalues - 1,
+				middle;
+
+	while (lower < upper)
+	{
+		double		middleval;
+
+		middle = (lower + upper + 1) / 2;
+
+		middleval = DatumGetFloat8(length_hist_values[middle]);
+		if (middleval < value || (equal && middleval <= value))
+			lower = middle;
+		else
+			upper = middle - 1;
+	}
+	return lower;
+}
+
+/*
+ * Get relative position of value in histogram bin in [0,1] range.
+ */
+static float8
+get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1,
+			 const RangeBound *hist2)
+{
+	bool		has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
+	float8		position;
+
+	if (!hist1->infinite && !hist2->infinite)
+	{
+		float8		bin_width;
+
+		/*
+		 * Both bounds are finite. Assuming the subtype's comparison function
+		 * works sanely, the value must be finite, too, because it lies
+		 * somewhere between the bounds.  If it doesn't, arbitrarily return
+		 * 0.5.
+		 */
+		if (value->infinite)
+			return 0.5;
+
+		/* Can't interpolate without subdiff function */
+		if (!has_subdiff)
+			return 0.5;
+
+		/* Calculate relative position using subdiff function. */
+		bin_width = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
+													 typcache->rng_collation,
+													 hist2->val,
+													 hist1->val));
+		if (isnan(bin_width) || bin_width <= 0.0)
+			return 0.5;			/* punt for NaN or zero-width bin */
+
+		position = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
+													typcache->rng_collation,
+													value->val,
+													hist1->val))
+			/ bin_width;
+
+		if (isnan(position))
+			return 0.5;			/* punt for NaN from subdiff, Inf/Inf, etc */
+
+		/* Relative position must be in [0,1] range */
+		position = Max(position, 0.0);
+		position = Min(position, 1.0);
+		return position;
+	}
+	else if (hist1->infinite && !hist2->infinite)
+	{
+		/*
+		 * Lower bin boundary is -infinite, upper is finite. If the value is
+		 * -infinite, return 0.0 to indicate it's equal to the lower bound.
+		 * Otherwise return 1.0 to indicate it's infinitely far from the lower
+		 * bound.
+		 */
+		return ((value->infinite && value->lower) ? 0.0 : 1.0);
+	}
+	else if (!hist1->infinite && hist2->infinite)
+	{
+		/* same as above, but in reverse */
+		return ((value->infinite && !value->lower) ? 1.0 : 0.0);
+	}
+	else
+	{
+		/*
+		 * If both bin boundaries are infinite, they should be equal to each
+		 * other, and the value should also be infinite and equal to both
+		 * bounds. (But don't Assert that, to avoid crashing if a user creates
+		 * a datatype with a broken comparison function).
+		 *
+		 * Assume the value to lie in the middle of the infinite bounds.
+		 */
+		return 0.5;
+	}
+}
+
+
+/*
+ * Get relative position of value in a length histogram bin in [0,1] range.
+ */
+static double
+get_len_position(double value, double hist1, double hist2)
+{
+	if (!isinf(hist1) && !isinf(hist2))
+	{
+		/*
+		 * Both bounds are finite. The value should be finite too, because it
+		 * lies somewhere between the bounds. If it doesn't, just return
+		 * something.
+		 */
+		if (isinf(value))
+			return 0.5;
+
+		return 1.0 - (hist2 - value) / (hist2 - hist1);
+	}
+	else if (isinf(hist1) && !isinf(hist2))
+	{
+		/*
+		 * Lower bin boundary is -infinite, upper is finite. Return 1.0 to
+		 * indicate the value is infinitely far from the lower bound.
+		 */
+		return 1.0;
+	}
+	else if (isinf(hist1) && isinf(hist2))
+	{
+		/* same as above, but in reverse */
+		return 0.0;
+	}
+	else
+	{
+		/*
+		 * If both bin boundaries are infinite, they should be equal to each
+		 * other, and the value should also be infinite and equal to both
+		 * bounds. (But don't Assert that, to avoid crashing unnecessarily if
+		 * the caller messes up)
+		 *
+		 * Assume the value to lie in the middle of the infinite bounds.
+		 */
+		return 0.5;
+	}
+}
+
+/*
+ * Measure distance between two range bounds.
+ */
+static float8
+get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
+{
+	bool		has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
+
+	if (!bound1->infinite && !bound2->infinite)
+	{
+		/*
+		 * Neither bound is infinite, use subdiff function or return default
+		 * value of 1.0 if no subdiff is available.
+		 */
+		if (has_subdiff)
+		{
+			float8		res;
+
+			res = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
+												   typcache->rng_collation,
+												   bound2->val,
+												   bound1->val));
+			/* Reject possible NaN result, also negative result */
+			if (isnan(res) || res < 0.0)
+				return 1.0;
+			else
+				return res;
+		}
+		else
+			return 1.0;
+	}
+	else if (bound1->infinite && bound2->infinite)
+	{
+		/* Both bounds are infinite */
+		if (bound1->lower == bound2->lower)
+			return 0.0;
+		else
+			return get_float8_infinity();
+	}
+	else
+	{
+		/* One bound is infinite, the other is not */
+		return get_float8_infinity();
+	}
+}
+
+/*
+ * Calculate the average of function P(x), in the interval [length1, length2],
+ * where P(x) is the fraction of tuples with length < x (or length <= x if
+ * 'equal' is true).
+ */
+static double
+calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues,
+					  double length1, double length2, bool equal)
+{
+	double		frac;
+	double		A,
+				B,
+				PA,
+				PB;
+	double		pos;
+	int			i;
+	double		area;
+
+	Assert(length2 >= length1);
+
+	if (length2 < 0.0)
+		return 0.0;				/* shouldn't happen, but doesn't hurt to check */
+
+	/* All lengths in the table are <= infinite. */
+	if (isinf(length2) && equal)
+		return 1.0;
+
+	/*----------
+	 * The average of a function between A and B can be calculated by the
+	 * formula:
+	 *
+	 *			B
+	 *	  1		/
+	 * -------	| P(x)dx
+	 *	B - A	/
+	 *			A
+	 *
+	 * The geometrical interpretation of the integral is the area under the
+	 * graph of P(x). P(x) is defined by the length histogram. We calculate
+	 * the area in a piecewise fashion, iterating through the length histogram
+	 * bins. Each bin is a trapezoid:
+	 *
+	 *		 P(x2)
+	 *		  /|
+	 *		 / |
+	 * P(x1)/  |
+	 *	   |   |
+	 *	   |   |
+	 *	---+---+--
+	 *	   x1  x2
+	 *
+	 * where x1 and x2 are the boundaries of the current histogram, and P(x1)
+	 * and P(x1) are the cumulative fraction of tuples at the boundaries.
+	 *
+	 * The area of each trapezoid is 1/2 * (P(x2) + P(x1)) * (x2 - x1)
+	 *
+	 * The first bin contains the lower bound passed by the caller, so we
+	 * use linear interpolation between the previous and next histogram bin
+	 * boundary to calculate P(x1). Likewise for the last bin: we use linear
+	 * interpolation to calculate P(x2). For the bins in between, x1 and x2
+	 * lie on histogram bin boundaries, so P(x1) and P(x2) are simply:
+	 * P(x1) =	  (bin index) / (number of bins)
+	 * P(x2) = (bin index + 1 / (number of bins)
+	 */
+
+	/* First bin, the one that contains lower bound */
+	i = length_hist_bsearch(length_hist_values, length_hist_nvalues, length1, equal);
+	if (i >= length_hist_nvalues - 1)
+		return 1.0;
+
+	if (i < 0)
+	{
+		i = 0;
+		pos = 0.0;
+	}
+	else
+	{
+		/* interpolate length1's position in the bin */
+		pos = get_len_position(length1,
+							   DatumGetFloat8(length_hist_values[i]),
+							   DatumGetFloat8(length_hist_values[i + 1]));
+	}
+	PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
+	B = length1;
+
+	/*
+	 * In the degenerate case that length1 == length2, simply return
+	 * P(length1). This is not merely an optimization: if length1 == length2,
+	 * we'd divide by zero later on.
+	 */
+	if (length2 == length1)
+		return PB;
+
+	/*
+	 * Loop through all the bins, until we hit the last bin, the one that
+	 * contains the upper bound. (if lower and upper bounds are in the same
+	 * bin, this falls out immediately)
+	 */
+	area = 0.0;
+	for (; i < length_hist_nvalues - 1; i++)
+	{
+		double		bin_upper = DatumGetFloat8(length_hist_values[i + 1]);
+
+		/* check if we've reached the last bin */
+		if (!(bin_upper < length2 || (equal && bin_upper <= length2)))
+			break;
+
+		/* the upper bound of previous bin is the lower bound of this bin */
+		A = B;
+		PA = PB;
+
+		B = bin_upper;
+		PB = (double) i / (double) (length_hist_nvalues - 1);
+
+		/*
+		 * Add the area of this trapezoid to the total. The point of the
+		 * if-check is to avoid NaN, in the corner case that PA == PB == 0,
+		 * and B - A == Inf. The area of a zero-height trapezoid (PA == PB ==
+		 * 0) is zero, regardless of the width (B - A).
+		 */
+		if (PA > 0 || PB > 0)
+			area += 0.5 * (PB + PA) * (B - A);
+	}
+
+	/* Last bin */
+	A = B;
+	PA = PB;
+
+	B = length2;				/* last bin ends at the query upper bound */
+	if (i >= length_hist_nvalues - 1)
+		pos = 0.0;
+	else
+	{
+		if (DatumGetFloat8(length_hist_values[i]) == DatumGetFloat8(length_hist_values[i + 1]))
+			pos = 0.0;
+		else
+			pos = get_len_position(length2,
+								   DatumGetFloat8(length_hist_values[i]),
+								   DatumGetFloat8(length_hist_values[i + 1]));
+	}
+	PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
+
+	if (PA > 0 || PB > 0)
+		area += 0.5 * (PB + PA) * (B - A);
+
+	/*
+	 * Ok, we have calculated the area, ie. the integral. Divide by width to
+	 * get the requested average.
+	 *
+	 * Avoid NaN arising from infinite / infinite. This happens at least if
+	 * length2 is infinite. It's not clear what the correct value would be in
+	 * that case, so 0.5 seems as good as any value.
+	 */
+	if (isinf(area) && isinf(length2))
+		frac = 0.5;
+	else
+		frac = area / (length2 - length1);
+
+	return frac;
+}
+
+/*
+ * Calculate selectivity of "var <@ const" operator, ie. estimate the fraction
+ * of multiranges that fall within the constant lower and upper bounds. This uses
+ * the histograms of range lower bounds and range lengths, on the assumption
+ * that the range lengths are independent of the lower bounds.
+ *
+ * The caller has already checked that constant lower and upper bounds are
+ * finite.
+ */
+static double
+calc_hist_selectivity_contained(TypeCacheEntry *typcache,
+								const RangeBound *lower, RangeBound *upper,
+								const RangeBound *hist_lower, int hist_nvalues,
+								Datum *length_hist_values, int length_hist_nvalues)
+{
+	int			i,
+				upper_index;
+	float8		prev_dist;
+	double		bin_width;
+	double		upper_bin_width;
+	double		sum_frac;
+
+	/*
+	 * Begin by finding the bin containing the upper bound, in the lower bound
+	 * histogram. Any range with a lower bound > constant upper bound can't
+	 * match, ie. there are no matches in bins greater than upper_index.
+	 */
+	upper->inclusive = !upper->inclusive;
+	upper->lower = true;
+	upper_index = rbound_bsearch(typcache, upper, hist_lower, hist_nvalues,
+								 false);
+
+	/*
+	 * If the upper bound value is below the histogram's lower limit, there
+	 * are no matches.
+	 */
+	if (upper_index < 0)
+		return 0.0;
+
+	/*
+	 * If the upper bound value is at or beyond the histogram's upper limit,
+	 * start our loop at the last actual bin, as though the upper bound were
+	 * within that bin; get_position will clamp its result to 1.0 anyway.
+	 * (This corresponds to assuming that the data population above the
+	 * histogram's upper limit is empty, exactly like what we just assumed for
+	 * the lower limit.)
+	 */
+	upper_index = Min(upper_index, hist_nvalues - 2);
+
+	/*
+	 * Calculate upper_bin_width, ie. the fraction of the (upper_index,
+	 * upper_index + 1) bin which is greater than upper bound of query range
+	 * using linear interpolation of subdiff function.
+	 */
+	upper_bin_width = get_position(typcache, upper,
+								   &hist_lower[upper_index],
+								   &hist_lower[upper_index + 1]);
+
+	/*
+	 * In the loop, dist and prev_dist are the distance of the "current" bin's
+	 * lower and upper bounds from the constant upper bound.
+	 *
+	 * bin_width represents the width of the current bin. Normally it is 1.0,
+	 * meaning a full width bin, but can be less in the corner cases: start
+	 * and end of the loop. We start with bin_width = upper_bin_width, because
+	 * we begin at the bin containing the upper bound.
+	 */
+	prev_dist = 0.0;
+	bin_width = upper_bin_width;
+
+	sum_frac = 0.0;
+	for (i = upper_index; i >= 0; i--)
+	{
+		double		dist;
+		double		length_hist_frac;
+		bool		final_bin = false;
+
+		/*
+		 * dist -- distance from upper bound of query range to lower bound of
+		 * the current bin in the lower bound histogram. Or to the lower bound
+		 * of the constant range, if this is the final bin, containing the
+		 * constant lower bound.
+		 */
+		if (range_cmp_bounds(typcache, &hist_lower[i], lower) < 0)
+		{
+			dist = get_distance(typcache, lower, upper);
+
+			/*
+			 * Subtract from bin_width the portion of this bin that we want to
+			 * ignore.
+			 */
+			bin_width -= get_position(typcache, lower, &hist_lower[i],
+									  &hist_lower[i + 1]);
+			if (bin_width < 0.0)
+				bin_width = 0.0;
+			final_bin = true;
+		}
+		else
+			dist = get_distance(typcache, &hist_lower[i], upper);
+
+		/*
+		 * Estimate the fraction of tuples in this bin that are narrow enough
+		 * to not exceed the distance to the upper bound of the query range.
+		 */
+		length_hist_frac = calc_length_hist_frac(length_hist_values,
+												 length_hist_nvalues,
+												 prev_dist, dist, true);
+
+		/*
+		 * Add the fraction of tuples in this bin, with a suitable length, to
+		 * the total.
+		 */
+		sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
+
+		if (final_bin)
+			break;
+
+		bin_width = 1.0;
+		prev_dist = dist;
+	}
+
+	return sum_frac;
+}
+
+/*
+ * Calculate selectivity of "var @> const" operator, ie. estimate the fraction
+ * of multiranges that contain the constant lower and upper bounds. This uses
+ * the histograms of range lower bounds and range lengths, on the assumption
+ * that the range lengths are independent of the lower bounds.
+ */
+static double
+calc_hist_selectivity_contains(TypeCacheEntry *typcache,
+							   const RangeBound *lower, const RangeBound *upper,
+							   const RangeBound *hist_lower, int hist_nvalues,
+							   Datum *length_hist_values, int length_hist_nvalues)
+{
+	int			i,
+				lower_index;
+	double		bin_width,
+				lower_bin_width;
+	double		sum_frac;
+	float8		prev_dist;
+
+	/* Find the bin containing the lower bound of query range. */
+	lower_index = rbound_bsearch(typcache, lower, hist_lower, hist_nvalues,
+								 true);
+
+	/*
+	 * If the lower bound value is below the histogram's lower limit, there
+	 * are no matches.
+	 */
+	if (lower_index < 0)
+		return 0.0;
+
+	/*
+	 * If the lower bound value is at or beyond the histogram's upper limit,
+	 * start our loop at the last actual bin, as though the upper bound were
+	 * within that bin; get_position will clamp its result to 1.0 anyway.
+	 * (This corresponds to assuming that the data population above the
+	 * histogram's upper limit is empty, exactly like what we just assumed for
+	 * the lower limit.)
+	 */
+	lower_index = Min(lower_index, hist_nvalues - 2);
+
+	/*
+	 * Calculate lower_bin_width, ie. the fraction of the of (lower_index,
+	 * lower_index + 1) bin which is greater than lower bound of query range
+	 * using linear interpolation of subdiff function.
+	 */
+	lower_bin_width = get_position(typcache, lower, &hist_lower[lower_index],
+								   &hist_lower[lower_index + 1]);
+
+	/*
+	 * Loop through all the lower bound bins, smaller than the query lower
+	 * bound. In the loop, dist and prev_dist are the distance of the
+	 * "current" bin's lower and upper bounds from the constant upper bound.
+	 * We begin from query lower bound, and walk backwards, so the first bin's
+	 * upper bound is the query lower bound, and its distance to the query
+	 * upper bound is the length of the query range.
+	 *
+	 * bin_width represents the width of the current bin. Normally it is 1.0,
+	 * meaning a full width bin, except for the first bin, which is only
+	 * counted up to the constant lower bound.
+	 */
+	prev_dist = get_distance(typcache, lower, upper);
+	sum_frac = 0.0;
+	bin_width = lower_bin_width;
+	for (i = lower_index; i >= 0; i--)
+	{
+		float8		dist;
+		double		length_hist_frac;
+
+		/*
+		 * dist -- distance from upper bound of query range to current value
+		 * of lower bound histogram or lower bound of query range (if we've
+		 * reach it).
+		 */
+		dist = get_distance(typcache, &hist_lower[i], upper);
+
+		/*
+		 * Get average fraction of length histogram which covers intervals
+		 * longer than (or equal to) distance to upper bound of query range.
+		 */
+		length_hist_frac =
+			1.0 - calc_length_hist_frac(length_hist_values,
+										length_hist_nvalues,
+										prev_dist, dist, false);
+
+		sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
+
+		bin_width = 1.0;
+		prev_dist = dist;
+	}
+
+	return sum_frac;
+}
diff --git a/src/backend/utils/adt/pg_upgrade_support.c b/src/backend/utils/adt/pg_upgrade_support.c
index 8a5953881ee..521ebaaab6d 100644
--- a/src/backend/utils/adt/pg_upgrade_support.c
+++ b/src/backend/utils/adt/pg_upgrade_support.c
@@ -53,6 +53,28 @@ binary_upgrade_set_next_array_pg_type_oid(PG_FUNCTION_ARGS)
 }
 
 Datum
+binary_upgrade_set_next_multirange_pg_type_oid(PG_FUNCTION_ARGS)
+{
+	Oid			typoid = PG_GETARG_OID(0);
+
+	CHECK_IS_BINARY_UPGRADE;
+	binary_upgrade_next_mrng_pg_type_oid = typoid;
+
+	PG_RETURN_VOID();
+}
+
+Datum
+binary_upgrade_set_next_multirange_array_pg_type_oid(PG_FUNCTION_ARGS)
+{
+	Oid			typoid = PG_GETARG_OID(0);
+
+	CHECK_IS_BINARY_UPGRADE;
+	binary_upgrade_next_mrng_array_pg_type_oid = typoid;
+
+	PG_RETURN_VOID();
+}
+
+Datum
 binary_upgrade_set_next_heap_pg_class_oid(PG_FUNCTION_ARGS)
 {
 	Oid			reloid = PG_GETARG_OID(0);
diff --git a/src/backend/utils/adt/pseudotypes.c b/src/backend/utils/adt/pseudotypes.c
index 3d6b2f90935..99a93271fe1 100644
--- a/src/backend/utils/adt/pseudotypes.c
+++ b/src/backend/utils/adt/pseudotypes.c
@@ -26,6 +26,7 @@
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/rangetypes.h"
+#include "utils/multirangetypes.h"
 
 
 /*
@@ -228,6 +229,43 @@ anycompatiblerange_out(PG_FUNCTION_ARGS)
 }
 
 /*
+ * anycompatiblemultirange
+ *
+ * We may as well allow output, since multirange_out will in fact work.
+ */
+PSEUDOTYPE_DUMMY_INPUT_FUNC(anycompatiblemultirange);
+
+Datum
+anycompatiblemultirange_out(PG_FUNCTION_ARGS)
+{
+	return multirange_out(fcinfo);
+}
+
+/*
+ * anymultirange_in		- input routine for pseudo-type ANYMULTIRANGE.
+ */
+Datum
+anymultirange_in(PG_FUNCTION_ARGS)
+{
+	ereport(ERROR,
+			(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+			 errmsg("cannot accept a value of type %s", "anymultirange")));
+
+	PG_RETURN_VOID();			/* keep compiler quiet */
+}
+
+/*
+ * anymultirange_out		- output routine for pseudo-type ANYMULTIRANGE.
+ *
+ * We may as well allow this, since multirange_out will in fact work.
+ */
+Datum
+anymultirange_out(PG_FUNCTION_ARGS)
+{
+	return multirange_out(fcinfo);
+}
+
+/*
  * void
  *
  * We support void_in so that PL functions can return VOID without any
diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index 01ad8bc240b..8957cc19842 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -43,8 +43,6 @@
 #include "utils/timestamp.h"
 
 
-#define RANGE_EMPTY_LITERAL "empty"
-
 /* fn_extra cache entry for one of the range I/O functions */
 typedef struct RangeIOData
 {
@@ -957,7 +955,25 @@ range_minus(PG_FUNCTION_ARGS)
 {
 	RangeType  *r1 = PG_GETARG_RANGE_P(0);
 	RangeType  *r2 = PG_GETARG_RANGE_P(1);
+	RangeType  *ret;
 	TypeCacheEntry *typcache;
+
+	/* Different types should be prevented by ANYRANGE matching rules */
+	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
+		elog(ERROR, "range types do not match");
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
+
+	ret = range_minus_internal(typcache, r1, r2);
+	if (ret)
+		PG_RETURN_RANGE_P(ret);
+	else
+		PG_RETURN_NULL();
+}
+
+RangeType *
+range_minus_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
+{
 	RangeBound	lower1,
 				lower2;
 	RangeBound	upper1,
@@ -969,18 +985,12 @@ range_minus(PG_FUNCTION_ARGS)
 				cmp_u1l2,
 				cmp_u1u2;
 
-	/* Different types should be prevented by ANYRANGE matching rules */
-	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
-		elog(ERROR, "range types do not match");
-
-	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
-
 	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 
 	/* if either is empty, r1 is the correct answer */
 	if (empty1 || empty2)
-		PG_RETURN_RANGE_P(r1);
+		return r1;
 
 	cmp_l1l2 = range_cmp_bounds(typcache, &lower1, &lower2);
 	cmp_l1u2 = range_cmp_bounds(typcache, &lower1, &upper2);
@@ -993,34 +1003,34 @@ range_minus(PG_FUNCTION_ARGS)
 				 errmsg("result of range difference would not be contiguous")));
 
 	if (cmp_l1u2 > 0 || cmp_u1l2 < 0)
-		PG_RETURN_RANGE_P(r1);
+		return r1;
 
 	if (cmp_l1l2 >= 0 && cmp_u1u2 <= 0)
-		PG_RETURN_RANGE_P(make_empty_range(typcache));
+		return make_empty_range(typcache);
 
 	if (cmp_l1l2 <= 0 && cmp_u1l2 >= 0 && cmp_u1u2 <= 0)
 	{
 		lower2.inclusive = !lower2.inclusive;
 		lower2.lower = false;	/* it will become the upper bound */
-		PG_RETURN_RANGE_P(make_range(typcache, &lower1, &lower2, false));
+		return make_range(typcache, &lower1, &lower2, false);
 	}
 
 	if (cmp_l1l2 >= 0 && cmp_u1u2 >= 0 && cmp_l1u2 <= 0)
 	{
 		upper2.inclusive = !upper2.inclusive;
 		upper2.lower = true;	/* it will become the lower bound */
-		PG_RETURN_RANGE_P(make_range(typcache, &upper2, &upper1, false));
+		return make_range(typcache, &upper2, &upper1, false);
 	}
 
 	elog(ERROR, "unexpected case in range_minus");
-	PG_RETURN_NULL();
+	return NULL;
 }
 
 /*
  * Set union.  If strict is true, it is an error that the two input ranges
  * are not adjacent or overlapping.
  */
-static RangeType *
+RangeType *
 range_union_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2,
 					 bool strict)
 {
@@ -1101,6 +1111,19 @@ range_intersect(PG_FUNCTION_ARGS)
 	RangeType  *r1 = PG_GETARG_RANGE_P(0);
 	RangeType  *r2 = PG_GETARG_RANGE_P(1);
 	TypeCacheEntry *typcache;
+
+	/* Different types should be prevented by ANYRANGE matching rules */
+	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
+		elog(ERROR, "range types do not match");
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
+
+	PG_RETURN_RANGE_P(range_intersect_internal(typcache, r1, r2));
+}
+
+RangeType *
+range_intersect_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
+{
 	RangeBound	lower1,
 				lower2;
 	RangeBound	upper1,
@@ -1110,17 +1133,11 @@ range_intersect(PG_FUNCTION_ARGS)
 	RangeBound *result_lower;
 	RangeBound *result_upper;
 
-	/* Different types should be prevented by ANYRANGE matching rules */
-	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
-		elog(ERROR, "range types do not match");
-
-	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
-
 	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 
-	if (empty1 || empty2 || !DatumGetBool(range_overlaps(fcinfo)))
-		PG_RETURN_RANGE_P(make_empty_range(typcache));
+	if (empty1 || empty2 || !range_overlaps_internal(typcache, r1, r2))
+		return make_empty_range(typcache);
 
 	if (range_cmp_bounds(typcache, &lower1, &lower2) >= 0)
 		result_lower = &lower1;
@@ -1132,9 +1149,81 @@ range_intersect(PG_FUNCTION_ARGS)
 	else
 		result_upper = &upper2;
 
-	PG_RETURN_RANGE_P(make_range(typcache, result_lower, result_upper, false));
+	return make_range(typcache, result_lower, result_upper, false);
 }
 
+/* range, range -> range, range functions */
+
+/*
+ * range_split_internal - if r2 intersects the middle of r1, leaving non-empty
+ * ranges on both sides, then return true and set output1 and output2 to the
+ * results of r1 - r2 (in order). Otherwise return false and don't set output1
+ * or output2. Neither input range should be empty.
+ */
+bool
+range_split_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2,
+					 RangeType **output1, RangeType **output2)
+{
+	RangeBound	lower1,
+				lower2;
+	RangeBound	upper1,
+				upper2;
+	bool		empty1,
+				empty2;
+
+	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
+	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
+
+	if (range_cmp_bounds(typcache, &lower1, &lower2) < 0 &&
+		range_cmp_bounds(typcache, &upper1, &upper2) > 0)
+	{
+		/*
+		 * Need to invert inclusive/exclusive for the lower2 and upper2
+		 * points. They can't be infinite though. We're allowed to overwrite
+		 * these RangeBounds since they only exist locally.
+		 */
+		lower2.inclusive = !lower2.inclusive;
+		lower2.lower = false;
+		upper2.inclusive = !upper2.inclusive;
+		upper2.lower = true;
+
+		*output1 = make_range(typcache, &lower1, &lower2, false);
+		*output2 = make_range(typcache, &upper2, &upper1, false);
+		return true;
+	}
+
+	return false;
+}
+
+/* range -> range aggregate functions */
+
+Datum
+range_intersect_agg_transfn(PG_FUNCTION_ARGS)
+{
+	MemoryContext aggContext;
+	Oid			rngtypoid;
+	TypeCacheEntry *typcache;
+	RangeType  *result;
+	RangeType  *current;
+
+	if (!AggCheckCallContext(fcinfo, &aggContext))
+		elog(ERROR, "range_intersect_agg_transfn called in non-aggregate context");
+
+	rngtypoid = get_fn_expr_argtype(fcinfo->flinfo, 1);
+	if (!type_is_range(rngtypoid))
+		ereport(ERROR, (errmsg("range_intersect_agg must be called with a range")));
+
+	typcache = range_get_typcache(fcinfo, rngtypoid);
+
+	/* strictness ensures these are non-null */
+	result = PG_GETARG_RANGE_P(0);
+	current = PG_GETARG_RANGE_P(1);
+
+	result = range_intersect_internal(typcache, result, current);
+	PG_RETURN_RANGE_P(result);
+}
+
+
 /* Btree support */
 
 /* btree comparator */
@@ -1938,6 +2027,46 @@ range_cmp_bound_values(TypeCacheEntry *typcache, const RangeBound *b1,
 }
 
 /*
+ * qsort callback for sorting ranges.
+ *
+ * Two empty ranges compare equal; an empty range sorts to the left of any
+ * non-empty range.  Two non-empty ranges are sorted by lower bound first
+ * and by upper bound next.
+ */
+int
+range_compare(const void *key1, const void *key2, void *arg)
+{
+	RangeType  *r1 = *(RangeType **) key1;
+	RangeType  *r2 = *(RangeType **) key2;
+	TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
+	RangeBound	lower1;
+	RangeBound	upper1;
+	RangeBound	lower2;
+	RangeBound	upper2;
+	bool		empty1;
+	bool		empty2;
+	int			cmp;
+
+	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
+	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
+
+	if (empty1 && empty2)
+		cmp = 0;
+	else if (empty1)
+		cmp = -1;
+	else if (empty2)
+		cmp = 1;
+	else
+	{
+		cmp = range_cmp_bounds(typcache, &lower1, &lower2);
+		if (cmp == 0)
+			cmp = range_cmp_bounds(typcache, &upper1, &upper2);
+	}
+
+	return cmp;
+}
+
+/*
  * Build an empty range value of the type indicated by the typcache entry.
  */
 RangeType *
diff --git a/src/backend/utils/adt/rangetypes_typanalyze.c b/src/backend/utils/adt/rangetypes_typanalyze.c
index 57413b07201..1376cf06940 100644
--- a/src/backend/utils/adt/rangetypes_typanalyze.c
+++ b/src/backend/utils/adt/rangetypes_typanalyze.c
@@ -30,11 +30,13 @@
 #include "utils/fmgrprotos.h"
 #include "utils/lsyscache.h"
 #include "utils/rangetypes.h"
+#include "utils/multirangetypes.h"
 
 static int	float8_qsort_cmp(const void *a1, const void *a2);
 static int	range_bound_qsort_cmp(const void *a1, const void *a2, void *arg);
 static void compute_range_stats(VacAttrStats *stats,
-								AnalyzeAttrFetchFunc fetchfunc, int samplerows, double totalrows);
+								AnalyzeAttrFetchFunc fetchfunc, int samplerows,
+								double totalrows);
 
 /*
  * range_typanalyze -- typanalyze function for range columns
@@ -61,6 +63,33 @@ range_typanalyze(PG_FUNCTION_ARGS)
 }
 
 /*
+ * multirange_typanalyze -- typanalyze function for multirange columns
+ *
+ * We do the same analysis as for ranges, but on the smallest range that
+ * completely includes the multirange.
+ */
+Datum
+multirange_typanalyze(PG_FUNCTION_ARGS)
+{
+	VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
+	TypeCacheEntry *typcache;
+	Form_pg_attribute attr = stats->attr;
+
+	/* Get information about multirange type; note column might be a domain */
+	typcache = multirange_get_typcache(fcinfo, getBaseType(stats->attrtypid));
+
+	if (attr->attstattarget < 0)
+		attr->attstattarget = default_statistics_target;
+
+	stats->compute_stats = compute_range_stats;
+	stats->extra_data = typcache;
+	/* same as in std_typanalyze */
+	stats->minrows = 300 * attr->attstattarget;
+
+	PG_RETURN_BOOL(true);
+}
+
+/*
  * Comparison function for sorting float8s, used for range lengths.
  */
 static int
@@ -98,7 +127,8 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 					int samplerows, double totalrows)
 {
 	TypeCacheEntry *typcache = (TypeCacheEntry *) stats->extra_data;
-	bool		has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
+	TypeCacheEntry *mltrng_typcache = NULL;
+	bool		has_subdiff;
 	int			null_cnt = 0;
 	int			non_null_cnt = 0;
 	int			non_empty_cnt = 0;
@@ -112,6 +142,15 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 			   *uppers;
 	double		total_width = 0;
 
+	if (typcache->typtype == TYPTYPE_MULTIRANGE)
+	{
+		mltrng_typcache = typcache;
+		typcache = typcache->rngtype;
+	}
+	else
+		Assert(typcache->typtype == TYPTYPE_RANGE);
+	has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
+
 	/* Allocate memory to hold range bounds and lengths of the sample ranges. */
 	lowers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
 	uppers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
@@ -123,6 +162,7 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 		Datum		value;
 		bool		isnull,
 					empty;
+		MultirangeType *multirange;
 		RangeType  *range;
 		RangeBound	lower,
 					upper;
@@ -145,8 +185,31 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 		total_width += VARSIZE_ANY(DatumGetPointer(value));
 
 		/* Get range and deserialize it for further analysis. */
-		range = DatumGetRangeTypeP(value);
-		range_deserialize(typcache, range, &lower, &upper, &empty);
+		if (mltrng_typcache != NULL)
+		{
+			/* Treat multiranges like a big range without gaps. */
+			multirange = DatumGetMultirangeTypeP(value);
+			if (!MultirangeIsEmpty(multirange))
+			{
+				RangeBound	tmp;
+
+				multirange_get_bounds(typcache, multirange, 0,
+									  &lower, &tmp);
+				multirange_get_bounds(typcache, multirange,
+									  multirange->rangeCount - 1,
+									  &tmp, &upper);
+				empty = false;
+			}
+			else
+			{
+				empty = true;
+			}
+		}
+		else
+		{
+			range = DatumGetRangeTypeP(value);
+			range_deserialize(typcache, range, &lower, &upper, &empty);
+		}
 
 		if (!empty)
 		{
@@ -262,6 +325,13 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 			stats->stakind[slot_idx] = STATISTIC_KIND_BOUNDS_HISTOGRAM;
 			stats->stavalues[slot_idx] = bound_hist_values;
 			stats->numvalues[slot_idx] = num_hist;
+
+			/* Store ranges even if we're analyzing a multirange column */
+			stats->statypid[slot_idx] = typcache->type_id;
+			stats->statyplen[slot_idx] = typcache->typlen;
+			stats->statypbyval[slot_idx] = typcache->typbyval;
+			stats->statypalign[slot_idx] = 'd';
+
 			slot_idx++;
 		}
 
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 204bcd03c0b..ad92636f7f1 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -2611,6 +2611,16 @@ type_is_range(Oid typid)
 }
 
 /*
+ * type_is_multirange
+ *	  Returns true if the given type is a multirange type.
+ */
+bool
+type_is_multirange(Oid typid)
+{
+	return (get_typtype(typid) == TYPTYPE_MULTIRANGE);
+}
+
+/*
  * get_type_category_preferred
  *
  *		Given the type OID, fetch its category and preferred-type status.
@@ -3308,7 +3318,7 @@ get_namespace_name_or_temp(Oid nspid)
 		return get_namespace_name(nspid);
 }
 
-/*				---------- PG_RANGE CACHE ----------				 */
+/*				---------- PG_RANGE CACHES ----------				 */
 
 /*
  * get_range_subtype
@@ -3361,6 +3371,56 @@ get_range_collation(Oid rangeOid)
 		return InvalidOid;
 }
 
+/*
+ * get_range_multirange
+ *		Returns the multirange type of a given range type
+ *
+ * Returns InvalidOid if the type is not a range type.
+ */
+Oid
+get_range_multirange(Oid rangeOid)
+{
+	HeapTuple	tp;
+
+	tp = SearchSysCache1(RANGETYPE, ObjectIdGetDatum(rangeOid));
+	if (HeapTupleIsValid(tp))
+	{
+		Form_pg_range rngtup = (Form_pg_range) GETSTRUCT(tp);
+		Oid			result;
+
+		result = rngtup->rngmultitypid;
+		ReleaseSysCache(tp);
+		return result;
+	}
+	else
+		return InvalidOid;
+}
+
+/*
+ * get_multirange_range
+ *		Returns the range type of a given multirange
+ *
+ * Returns InvalidOid if the type is not a multirange.
+ */
+Oid
+get_multirange_range(Oid multirangeOid)
+{
+	HeapTuple	tp;
+
+	tp = SearchSysCache1(RANGEMULTIRANGE, ObjectIdGetDatum(multirangeOid));
+	if (HeapTupleIsValid(tp))
+	{
+		Form_pg_range rngtup = (Form_pg_range) GETSTRUCT(tp);
+		Oid			result;
+
+		result = rngtup->rngtypid;
+		ReleaseSysCache(tp);
+		return result;
+	}
+	else
+		return InvalidOid;
+}
+
 /*				---------- PG_INDEX CACHE ----------				 */
 
 /*
diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.c
index 809b27a038f..89f08a4f43c 100644
--- a/src/backend/utils/cache/syscache.c
+++ b/src/backend/utils/cache/syscache.c
@@ -650,6 +650,18 @@ static const struct cachedesc cacheinfo[] = {
 		},
 		64
 	},
+	{RangeRelationId,			/* RANGEMULTIRANGE */
+		RangeMultirangeTypidIndexId,
+		1,
+		{
+			Anum_pg_range_rngmultitypid,
+			0,
+			0,
+			0
+		},
+		4
+	},
+
 	{RangeRelationId,			/* RANGETYPE */
 		RangeTypidIndexId,
 		1,
diff --git a/src/backend/utils/cache/typcache.c b/src/backend/utils/cache/typcache.c
index 1e331098c0d..8c97ef39557 100644
--- a/src/backend/utils/cache/typcache.c
+++ b/src/backend/utils/cache/typcache.c
@@ -287,6 +287,7 @@ static uint64 tupledesc_id_counter = INVALID_TUPLEDESC_IDENTIFIER;
 
 static void load_typcache_tupdesc(TypeCacheEntry *typentry);
 static void load_rangetype_info(TypeCacheEntry *typentry);
+static void load_multirangetype_info(TypeCacheEntry *typentry);
 static void load_domaintype_info(TypeCacheEntry *typentry);
 static int	dcs_cmp(const void *a, const void *b);
 static void decr_dcc_refcount(DomainConstraintCache *dcc);
@@ -305,6 +306,9 @@ static void cache_record_field_properties(TypeCacheEntry *typentry);
 static bool range_element_has_hashing(TypeCacheEntry *typentry);
 static bool range_element_has_extended_hashing(TypeCacheEntry *typentry);
 static void cache_range_element_properties(TypeCacheEntry *typentry);
+static bool multirange_element_has_hashing(TypeCacheEntry *typentry);
+static bool multirange_element_has_extended_hashing(TypeCacheEntry *typentry);
+static void cache_multirange_element_properties(TypeCacheEntry *typentry);
 static void TypeCacheRelCallback(Datum arg, Oid relid);
 static void TypeCacheTypCallback(Datum arg, int cacheid, uint32 hashvalue);
 static void TypeCacheOpcCallback(Datum arg, int cacheid, uint32 hashvalue);
@@ -557,8 +561,8 @@ lookup_type_cache(Oid type_id, int flags)
 		 * to see if the element type or column types support equality.  If
 		 * not, array_eq or record_eq would fail at runtime, so we don't want
 		 * to report that the type has equality.  (We can omit similar
-		 * checking for ranges because ranges can't be created in the first
-		 * place unless their subtypes support equality.)
+		 * checking for ranges and multiranges because ranges can't be created
+		 * in the first place unless their subtypes support equality.)
 		 */
 		if (eq_opr == ARRAY_EQ_OP &&
 			!array_element_has_equality(typentry))
@@ -595,7 +599,7 @@ lookup_type_cache(Oid type_id, int flags)
 
 		/*
 		 * As above, make sure array_cmp or record_cmp will succeed; but again
-		 * we need no special check for ranges.
+		 * we need no special check for ranges or multiranges.
 		 */
 		if (lt_opr == ARRAY_LT_OP &&
 			!array_element_has_compare(typentry))
@@ -620,7 +624,7 @@ lookup_type_cache(Oid type_id, int flags)
 
 		/*
 		 * As above, make sure array_cmp or record_cmp will succeed; but again
-		 * we need no special check for ranges.
+		 * we need no special check for ranges or multiranges.
 		 */
 		if (gt_opr == ARRAY_GT_OP &&
 			!array_element_has_compare(typentry))
@@ -645,7 +649,7 @@ lookup_type_cache(Oid type_id, int flags)
 
 		/*
 		 * As above, make sure array_cmp or record_cmp will succeed; but again
-		 * we need no special check for ranges.
+		 * we need no special check for ranges or multiranges.
 		 */
 		if (cmp_proc == F_BTARRAYCMP &&
 			!array_element_has_compare(typentry))
@@ -695,6 +699,13 @@ lookup_type_cache(Oid type_id, int flags)
 			!range_element_has_hashing(typentry))
 			hash_proc = InvalidOid;
 
+		/*
+		 * Likewise for hash_multirange.
+		 */
+		if (hash_proc == F_HASH_MULTIRANGE &&
+			!multirange_element_has_hashing(typentry))
+			hash_proc = InvalidOid;
+
 		/* Force update of hash_proc_finfo only if we're changing state */
 		if (typentry->hash_proc != hash_proc)
 			typentry->hash_proc_finfo.fn_oid = InvalidOid;
@@ -737,6 +748,13 @@ lookup_type_cache(Oid type_id, int flags)
 			!range_element_has_extended_hashing(typentry))
 			hash_extended_proc = InvalidOid;
 
+		/*
+		 * Likewise for hash_multirange_extended.
+		 */
+		if (hash_extended_proc == F_HASH_MULTIRANGE_EXTENDED &&
+			!multirange_element_has_extended_hashing(typentry))
+			hash_extended_proc = InvalidOid;
+
 		/* Force update of proc finfo only if we're changing state */
 		if (typentry->hash_extended_proc != hash_extended_proc)
 			typentry->hash_extended_proc_finfo.fn_oid = InvalidOid;
@@ -817,6 +835,16 @@ lookup_type_cache(Oid type_id, int flags)
 	}
 
 	/*
+	 * If requested, get information about a multirange type
+	 */
+	if ((flags & TYPECACHE_MULTIRANGE_INFO) &&
+		typentry->rngtype == NULL &&
+		typentry->typtype == TYPTYPE_MULTIRANGE)
+	{
+		load_multirangetype_info(typentry);
+	}
+
+	/*
 	 * If requested, get information about a domain type
 	 */
 	if ((flags & TYPECACHE_DOMAIN_BASE_INFO) &&
@@ -927,6 +955,22 @@ load_rangetype_info(TypeCacheEntry *typentry)
 	typentry->rngelemtype = lookup_type_cache(subtypeOid, 0);
 }
 
+/*
+ * load_multirangetype_info --- helper routine to set up multirange type
+ * information
+ */
+static void
+load_multirangetype_info(TypeCacheEntry *typentry)
+{
+	Oid			rangetypeOid;
+
+	rangetypeOid = get_multirange_range(typentry->type_id);
+	if (!OidIsValid(rangetypeOid))
+		elog(ERROR, "cache lookup failed for multirange type %u",
+			 typentry->type_id);
+
+	typentry->rngtype = lookup_type_cache(rangetypeOid, TYPECACHE_RANGE_INFO);
+}
 
 /*
  * load_domaintype_info --- helper routine to set up domain constraint info
@@ -1559,11 +1603,11 @@ cache_record_field_properties(TypeCacheEntry *typentry)
 }
 
 /*
- * Likewise, some helper functions for range types.
+ * Likewise, some helper functions for range and multirange types.
  *
  * We can borrow the flag bits for array element properties to use for range
  * element properties, since those flag bits otherwise have no use in a
- * range type's typcache entry.
+ * range or multirange type's typcache entry.
  */
 
 static bool
@@ -1606,6 +1650,46 @@ cache_range_element_properties(TypeCacheEntry *typentry)
 	typentry->flags |= TCFLAGS_CHECKED_ELEM_PROPERTIES;
 }
 
+static bool
+multirange_element_has_hashing(TypeCacheEntry *typentry)
+{
+	if (!(typentry->flags & TCFLAGS_CHECKED_ELEM_PROPERTIES))
+		cache_multirange_element_properties(typentry);
+	return (typentry->flags & TCFLAGS_HAVE_ELEM_HASHING) != 0;
+}
+
+static bool
+multirange_element_has_extended_hashing(TypeCacheEntry *typentry)
+{
+	if (!(typentry->flags & TCFLAGS_CHECKED_ELEM_PROPERTIES))
+		cache_multirange_element_properties(typentry);
+	return (typentry->flags & TCFLAGS_HAVE_ELEM_EXTENDED_HASHING) != 0;
+}
+
+static void
+cache_multirange_element_properties(TypeCacheEntry *typentry)
+{
+	/* load up range link if we didn't already */
+	if (typentry->rngtype == NULL &&
+		typentry->typtype == TYPTYPE_MULTIRANGE)
+		load_multirangetype_info(typentry);
+
+	if (typentry->rngtype != NULL && typentry->rngtype->rngelemtype != NULL)
+	{
+		TypeCacheEntry *elementry;
+
+		/* might need to calculate subtype's hash function properties */
+		elementry = lookup_type_cache(typentry->rngtype->rngelemtype->type_id,
+									  TYPECACHE_HASH_PROC |
+									  TYPECACHE_HASH_EXTENDED_PROC);
+		if (OidIsValid(elementry->hash_proc))
+			typentry->flags |= TCFLAGS_HAVE_ELEM_HASHING;
+		if (OidIsValid(elementry->hash_extended_proc))
+			typentry->flags |= TCFLAGS_HAVE_ELEM_EXTENDED_HASHING;
+	}
+	typentry->flags |= TCFLAGS_CHECKED_ELEM_PROPERTIES;
+}
+
 /*
  * Make sure that RecordCacheArray and RecordIdentifierArray are large enough
  * to store 'typmod'.
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);