v1-0004-Add-multirange_me_ops-SP-GiST-opclass-using-multi.patch

From d6d2c121554a523b09e9f4698a200a71d934a9c1 Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <maxime.schoemans@enterprisedb.com>
Date: Fri, 3 Apr 2026 19:32:01 +0200
Subject: [PATCH v1 4/4] Add multirange_me_ops SP-GiST opclass using
 multi-entry

Add a built-in SP-GiST operator class for multirange types that uses
the multi-entry infrastructure to decompose each multirange into its
component ranges, storing each as a separate quad-tree entry.

The opclass is marked non-default, consistent with the GiST
multirange_me_ops.

The opclass reuses the existing range quad-tree structure (choose and
picksplit from range_ops) and the multirange_gist_extractvalue function
from the GiST multi-entry opclass. Three new SP-GiST-specific functions
are added:

  spg_multirange_me_config: Configures the quad tree with leafType set
  to the corresponding range type and canReturnData disabled.

  spg_multirange_me_inner_consistent: Handles range, multirange, and
  element query types. Multirange queries are converted to bounding
  range bounds for quadrant pruning. CONTAINS and EQ with multirange
  queries are relaxed to OVERLAPS since matching components may span
  multiple subtrees.

  spg_multirange_me_leaf_consistent: Per-component filtering with
  recheck for all strategies except OVERLAPS and CONTAINS_ELEM, which
  are exact per-component. Handles empty-range sentinels for empty
  multiranges.

Catalog entries register the opclass for all multirange types with 19
operators (range, multirange, and element variants) and 6 support
functions (config, choose, picksplit, inner consistent, leaf consistent,
and extractValue).

Regression tests verify correctness across sequential scan, index scan,
and bitmap scan for all operators with range, multirange, empty, and
element queries.
---
 src/backend/utils/adt/rangetypes_spgist.c     | 608 ++++++++++++++++
 src/include/catalog/pg_amop.dat               |  56 ++
 src/include/catalog/pg_amproc.dat             |  18 +
 src/include/catalog/pg_opclass.dat            |   3 +
 src/include/catalog/pg_opfamily.dat           |   2 +
 src/include/catalog/pg_proc.dat               |  11 +
 src/test/regress/expected/multirangetypes.out | 667 ++++++++++++++++++
 src/test/regress/expected/psql.out            |  23 +-
 src/test/regress/sql/multirangetypes.sql      | 149 ++++
 9 files changed, 1526 insertions(+), 11 deletions(-)

diff --git a/src/backend/utils/adt/rangetypes_spgist.c b/src/backend/utils/adt/rangetypes_spgist.c
index b198375e64d..17da99ff427 100644
--- a/src/backend/utils/adt/rangetypes_spgist.c
+++ b/src/backend/utils/adt/rangetypes_spgist.c
@@ -41,6 +41,8 @@
 #include "catalog/pg_type.h"
 #include "utils/datum.h"
 #include "utils/fmgrprotos.h"
+#include "utils/lsyscache.h"
+#include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
 
 static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid,
@@ -998,3 +1000,609 @@ spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
 
 	PG_RETURN_BOOL(res);
 }
+
+
+/*----------------------------------------------------------
+ * Multi-entry SP-GiST support for multirange types.
+ *
+ * When an extractValue support function is registered, SP-GiST decomposes
+ * each multirange into its component ranges and stores each as a separate
+ * index entry.  The quad tree structure is the same as the standard range
+ * opclass, but the consistent functions must handle multirange, range, and
+ * element query types.
+ *----------------------------------------------------------
+ */
+
+/*
+ * SP-GiST config function for multirange_me_ops.
+ *
+ * Same quad tree structure as range_ops, but leafType is the corresponding
+ * range type (not the multirange input type), and canReturnData is false
+ * because multi-entry decomposition prevents reconstructing the original.
+ */
+Datum
+spg_multirange_me_config(PG_FUNCTION_ARGS)
+{
+	spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
+	spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
+
+	cfg->prefixType = ANYRANGEOID;
+	cfg->labelType = VOIDOID;	/* we don't need node labels */
+	cfg->leafType = get_multirange_range(cfgin->attType);
+	cfg->canReturnData = false;
+	cfg->longValuesOK = false;
+	PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST inner consistent function for multirange_me_ops.
+ *
+ * Handles range, multirange, and element query types.  The tree structure
+ * is the standard range quad tree, so the quadrant pruning logic is the
+ * same as spg_range_quad_inner_consistent.  For multirange queries, the
+ * query is converted to its bounding range for pruning purposes.  For
+ * CONTAINS and EQ with non-empty multirange queries, the pruning is
+ * relaxed to OVERLAPS because a matching multirange's components may be
+ * spread across multiple subtrees.
+ */
+Datum
+spg_multirange_me_inner_consistent(PG_FUNCTION_ARGS)
+{
+	spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
+	spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
+	int			which;
+	int			i;
+	MemoryContext oldCtx;
+
+	/*
+	 * For adjacent search we need also previous centroid (if any) to improve
+	 * the precision of the consistent check.
+	 */
+	bool		needPrevious = false;
+
+	if (in->allTheSame)
+	{
+		/* Report that all nodes should be visited */
+		out->nNodes = in->nNodes;
+		out->nodeNumbers = palloc_array(int, in->nNodes);
+		for (i = 0; i < in->nNodes; i++)
+			out->nodeNumbers[i] = i;
+		PG_RETURN_VOID();
+	}
+
+	if (!in->hasPrefix)
+	{
+		/*
+		 * No centroid on this inner node.  Node 0 = empty ranges, node 1 =
+		 * non-empty ranges.
+		 */
+		Assert(in->nNodes == 2);
+
+		which = (1 << 1) | (1 << 2);
+		for (i = 0; i < in->nkeys; i++)
+		{
+			StrategyNumber strategy = in->scankeys[i].sk_strategy;
+			Oid			subtype = in->scankeys[i].sk_subtype;
+			bool		empty;
+
+			/* Determine if the query is empty based on its type */
+			if (strategy == RANGESTRAT_CONTAINS_ELEM)
+				empty = false;
+			else if (subtype == ANYMULTIRANGEOID)
+				empty = MultirangeIsEmpty(
+					DatumGetMultirangeTypeP(in->scankeys[i].sk_argument));
+			else
+				empty = RangeIsEmpty(
+					DatumGetRangeTypeP(in->scankeys[i].sk_argument));
+
+			switch (strategy)
+			{
+				case RANGESTRAT_BEFORE:
+				case RANGESTRAT_OVERLEFT:
+				case RANGESTRAT_OVERLAPS:
+				case RANGESTRAT_OVERRIGHT:
+				case RANGESTRAT_AFTER:
+				case RANGESTRAT_ADJACENT:
+					if (empty)
+						which = 0;
+					else
+						which &= (1 << 2);
+					break;
+
+				case RANGESTRAT_CONTAINS:
+					if (!empty)
+						which &= (1 << 2);
+					break;
+
+				case RANGESTRAT_CONTAINED_BY:
+					if (empty)
+						which &= (1 << 1);
+					break;
+
+				case RANGESTRAT_CONTAINS_ELEM:
+					which &= (1 << 2);
+					break;
+
+				case RANGESTRAT_EQ:
+					if (empty)
+						which &= (1 << 1);
+					else
+						which &= (1 << 2);
+					break;
+
+				default:
+					elog(ERROR, "unrecognized range strategy: %d", strategy);
+					break;
+			}
+			if (which == 0)
+				break;
+		}
+	}
+	else
+	{
+		RangeBound	centroidLower,
+					centroidUpper;
+		bool		centroidEmpty;
+		TypeCacheEntry *typcache;
+		RangeType  *centroid;
+
+		centroid = DatumGetRangeTypeP(in->prefixDatum);
+		typcache = range_get_typcache(fcinfo, RangeTypeGetOid(centroid));
+		range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
+						  &centroidEmpty);
+
+		Assert(in->nNodes == 4 || in->nNodes == 5);
+
+		which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
+
+		for (i = 0; i < in->nkeys; i++)
+		{
+			StrategyNumber strategy;
+			RangeBound	lower,
+						upper;
+			bool		empty;
+			RangeType  *range = NULL;
+			Oid			subtype;
+			bool		is_multirange;
+
+			RangeType  *prevCentroid = NULL;
+			RangeBound	prevLower,
+						prevUpper;
+			bool		prevEmpty;
+
+			RangeBound *minLower = NULL,
+					   *maxLower = NULL,
+					   *minUpper = NULL,
+					   *maxUpper = NULL;
+
+			bool		inclusive = true;
+			bool		strictEmpty = true;
+			int			cmp,
+						which1,
+						which2;
+
+			strategy = in->scankeys[i].sk_strategy;
+			subtype = in->scankeys[i].sk_subtype;
+			is_multirange = subtype == ANYMULTIRANGEOID;
+
+			/*
+			 * Extract query bounds depending on the query type.
+			 */
+			if (strategy == RANGESTRAT_CONTAINS_ELEM)
+			{
+				/* Element query: expand to point range bounds */
+				lower.inclusive = true;
+				lower.infinite = false;
+				lower.lower = true;
+				lower.val = in->scankeys[i].sk_argument;
+
+				upper.inclusive = true;
+				upper.infinite = false;
+				upper.lower = false;
+				upper.val = in->scankeys[i].sk_argument;
+
+				empty = false;
+
+				strategy = RANGESTRAT_CONTAINS;
+			}
+			else if (is_multirange)
+			{
+				/* Multirange query: extract bounding range bounds */
+				MultirangeType *mr =
+					DatumGetMultirangeTypeP(in->scankeys[i].sk_argument);
+
+				if (MultirangeIsEmpty(mr))
+				{
+					empty = true;
+				}
+				else
+				{
+					int32		range_count = mr->rangeCount;
+					RangeBound	tmp;
+
+					/*
+					 * Use the range typcache (from the centroid) to
+					 * extract multirange bounds.  We can't use
+					 * multirange_get_typcache here because it caches in
+					 * fn_extra, conflicting with range_get_typcache.
+					 */
+					multirange_get_bounds(typcache, mr,
+										  0, &lower, &upper);
+					if (range_count > 1)
+						multirange_get_bounds(typcache, mr,
+											  range_count - 1,
+											  &tmp, &upper);
+					empty = false;
+				}
+
+				/*
+				 * For CONTAINS/EQ with non-empty multirange, relax to
+				 * OVERLAPS: components of a matching multirange may be
+				 * spread across multiple subtrees.
+				 */
+				if (!empty &&
+					(strategy == RANGESTRAT_CONTAINS ||
+					 strategy == RANGESTRAT_EQ))
+					strategy = RANGESTRAT_OVERLAPS;
+			}
+			else
+			{
+				/* Range query */
+				range = DatumGetRangeTypeP(in->scankeys[i].sk_argument);
+				range_deserialize(typcache, range, &lower, &upper, &empty);
+			}
+
+			/*
+			 * Apply the same quadrant pruning logic as the standard range
+			 * opclass.  See spg_range_quad_inner_consistent for details.
+			 */
+			switch (strategy)
+			{
+				case RANGESTRAT_BEFORE:
+					maxUpper = &lower;
+					inclusive = false;
+					break;
+
+				case RANGESTRAT_OVERLEFT:
+					maxUpper = &upper;
+					break;
+
+				case RANGESTRAT_OVERLAPS:
+					maxLower = &upper;
+					minUpper = &lower;
+					break;
+
+				case RANGESTRAT_OVERRIGHT:
+					minLower = &lower;
+					break;
+
+				case RANGESTRAT_AFTER:
+					minLower = &upper;
+					inclusive = false;
+					break;
+
+				case RANGESTRAT_ADJACENT:
+					if (empty)
+						break;	/* Skip to strictEmpty check. */
+
+					if (in->traversalValue)
+					{
+						prevCentroid = in->traversalValue;
+						range_deserialize(typcache, prevCentroid,
+										  &prevLower, &prevUpper, &prevEmpty);
+					}
+
+					cmp = adjacent_inner_consistent(typcache, &lower,
+													&centroidUpper,
+													prevCentroid ? &prevUpper : NULL);
+					if (cmp > 0)
+						which1 = (1 << 1) | (1 << 4);
+					else if (cmp < 0)
+						which1 = (1 << 2) | (1 << 3);
+					else
+						which1 = 0;
+
+					cmp = adjacent_inner_consistent(typcache, &upper,
+													&centroidLower,
+													prevCentroid ? &prevLower : NULL);
+					if (cmp > 0)
+						which2 = (1 << 1) | (1 << 2);
+					else if (cmp < 0)
+						which2 = (1 << 3) | (1 << 4);
+					else
+						which2 = 0;
+
+					which &= which1 | which2;
+					needPrevious = true;
+					break;
+
+				case RANGESTRAT_CONTAINS:
+					strictEmpty = false;
+					if (!empty)
+					{
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+						maxLower = &lower;
+						minUpper = &upper;
+					}
+					break;
+
+				case RANGESTRAT_CONTAINED_BY:
+					strictEmpty = false;
+					if (empty)
+					{
+						which &= (1 << 5);
+					}
+					else
+					{
+						minLower = &lower;
+						maxUpper = &upper;
+					}
+					break;
+
+				case RANGESTRAT_EQ:
+					strictEmpty = false;
+					if (empty)
+					{
+						which &= (1 << 5);
+					}
+					else
+					{
+						/*
+						 * For range queries, restrict to the exact quadrant.
+						 * For multirange queries (already converted to
+						 * OVERLAPS above), we won't reach here.
+						 */
+						which &= (1 << getQuadrant(typcache, centroid, range));
+					}
+					break;
+
+				default:
+					elog(ERROR, "unrecognized range strategy: %d", strategy);
+					break;
+			}
+
+			if (strictEmpty)
+			{
+				if (empty)
+				{
+					which = 0;
+					break;
+				}
+				else
+				{
+					which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+				}
+			}
+
+			if (minLower)
+			{
+				if (range_cmp_bounds(typcache, &centroidLower, minLower) <= 0)
+					which &= (1 << 1) | (1 << 2) | (1 << 5);
+			}
+			if (maxLower)
+			{
+				cmp = range_cmp_bounds(typcache, &centroidLower, maxLower);
+				if (cmp > 0 || (!inclusive && cmp == 0))
+					which &= (1 << 3) | (1 << 4) | (1 << 5);
+			}
+			if (minUpper)
+			{
+				if (range_cmp_bounds(typcache, &centroidUpper, minUpper) <= 0)
+					which &= (1 << 1) | (1 << 4) | (1 << 5);
+			}
+			if (maxUpper)
+			{
+				cmp = range_cmp_bounds(typcache, &centroidUpper, maxUpper);
+				if (cmp > 0 || (!inclusive && cmp == 0))
+					which &= (1 << 2) | (1 << 3) | (1 << 5);
+			}
+
+			if (which == 0)
+				break;
+		}
+	}
+
+	/* Build the output node list */
+	out->nodeNumbers = palloc_array(int, in->nNodes);
+	if (needPrevious)
+		out->traversalValues = palloc_array(void *, in->nNodes);
+	out->nNodes = 0;
+
+	oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
+
+	for (i = 1; i <= in->nNodes; i++)
+	{
+		if (which & (1 << i))
+		{
+			if (needPrevious)
+			{
+				Datum		previousCentroid;
+
+				previousCentroid = datumCopy(in->prefixDatum, false, -1);
+				out->traversalValues[out->nNodes] = DatumGetPointer(previousCentroid);
+			}
+			out->nodeNumbers[out->nNodes] = i - 1;
+			out->nNodes++;
+		}
+	}
+
+	MemoryContextSwitchTo(oldCtx);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST leaf consistent function for multirange_me_ops.
+ *
+ * The leaf datum is a single component range from the indexed multirange.
+ * Most strategies need recheck because a single component cannot fully
+ * determine the multirange's relationship with the query.  OVERLAPS and
+ * CONTAINS_ELEM are exact per-component and skip recheck.
+ */
+Datum
+spg_multirange_me_leaf_consistent(PG_FUNCTION_ARGS)
+{
+	spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
+	spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
+	RangeType  *leafRange = DatumGetRangeTypeP(in->leafDatum);
+	TypeCacheEntry *typcache;
+	bool		res;
+	int			i;
+
+	out->recheck = false;
+	out->leafValue = in->leafDatum;
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
+	res = true;
+	for (i = 0; i < in->nkeys; i++)
+	{
+		StrategyNumber strategy = in->scankeys[i].sk_strategy;
+		Datum		keyDatum = in->scankeys[i].sk_argument;
+		Oid			subtype = in->scankeys[i].sk_subtype;
+
+		/*
+		 * Set recheck for all strategies except OVERLAPS and CONTAINS_ELEM,
+		 * which are exact per-component.
+		 */
+		if (strategy != RANGESTRAT_OVERLAPS &&
+			strategy != RANGESTRAT_CONTAINS_ELEM)
+			out->recheck = true;
+
+		if (strategy == RANGESTRAT_CONTAINS_ELEM)
+		{
+			/* Element query */
+			res = range_contains_elem_internal(typcache, leafRange, keyDatum);
+		}
+		else if (subtype == ANYMULTIRANGEOID)
+		{
+			/* Multirange query */
+			MultirangeType *query = DatumGetMultirangeTypeP(keyDatum);
+
+			/* Empty key is sentinel for empty multirange */
+			if (RangeIsEmpty(leafRange))
+			{
+				if (strategy == RANGESTRAT_CONTAINED_BY)
+					res = true;
+				else if (strategy == RANGESTRAT_CONTAINS ||
+						 strategy == RANGESTRAT_EQ)
+					res = MultirangeIsEmpty(query);
+				else
+					res = false;
+			}
+			else if (MultirangeIsEmpty(query))
+			{
+				if (strategy == RANGESTRAT_CONTAINS)
+					res = true;
+				else
+					res = false;
+			}
+			else
+			{
+				switch (strategy)
+				{
+					case RANGESTRAT_BEFORE:
+						res = range_before_multirange_internal(typcache,
+															  leafRange, query);
+						break;
+					case RANGESTRAT_OVERLEFT:
+						res = range_overleft_multirange_internal(typcache,
+																leafRange, query);
+						break;
+					case RANGESTRAT_OVERRIGHT:
+						res = range_overright_multirange_internal(typcache,
+																 leafRange, query);
+						break;
+					case RANGESTRAT_AFTER:
+						res = range_after_multirange_internal(typcache,
+															 leafRange, query);
+						break;
+					case RANGESTRAT_ADJACENT:
+						res = range_adjacent_multirange_internal(typcache,
+																leafRange, query);
+						break;
+					case RANGESTRAT_OVERLAPS:
+					case RANGESTRAT_CONTAINS:
+					case RANGESTRAT_CONTAINED_BY:
+					case RANGESTRAT_EQ:
+						/* Use overlaps as necessary condition */
+						res = range_overlaps_multirange_internal(typcache,
+																leafRange, query);
+						break;
+					default:
+						elog(ERROR, "unrecognized range strategy: %d",
+							 strategy);
+						res = false;
+						break;
+				}
+			}
+		}
+		else
+		{
+			/* Range query */
+			RangeType  *query = DatumGetRangeTypeP(keyDatum);
+
+			/* Empty key is sentinel for empty multirange */
+			if (RangeIsEmpty(leafRange))
+			{
+				if (strategy == RANGESTRAT_CONTAINED_BY)
+					res = true;
+				else if (strategy == RANGESTRAT_CONTAINS)
+					res = RangeIsEmpty(query);
+				else
+					res = false;
+			}
+			else if (RangeIsEmpty(query))
+			{
+				if (strategy == RANGESTRAT_CONTAINS)
+					res = true;
+				else
+					res = false;
+			}
+			else
+			{
+				switch (strategy)
+				{
+					case RANGESTRAT_BEFORE:
+						res = range_before_internal(typcache, leafRange, query);
+						break;
+					case RANGESTRAT_OVERLEFT:
+						res = range_overleft_internal(typcache, leafRange,
+													  query);
+						break;
+					case RANGESTRAT_OVERRIGHT:
+						res = range_overright_internal(typcache, leafRange,
+													   query);
+						break;
+					case RANGESTRAT_AFTER:
+						res = range_after_internal(typcache, leafRange, query);
+						break;
+					case RANGESTRAT_ADJACENT:
+						res = range_adjacent_internal(typcache, leafRange,
+													  query);
+						break;
+					case RANGESTRAT_OVERLAPS:
+						res = range_overlaps_internal(typcache, leafRange,
+													  query);
+						break;
+					case RANGESTRAT_CONTAINS:
+					case RANGESTRAT_CONTAINED_BY:
+					case RANGESTRAT_EQ:
+						/* Use overlaps as necessary condition */
+						res = range_overlaps_internal(typcache, leafRange,
+													  query);
+						break;
+					default:
+						elog(ERROR, "unrecognized range strategy: %d",
+							 strategy);
+						res = false;
+						break;
+				}
+			}
+		}
+
+		if (!res)
+			break;
+	}
+
+	PG_RETURN_BOOL(res);
+}
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 3cc3ba61eeb..fb427a940fb 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1732,6 +1732,62 @@
   amoprighttype => 'anyrange', amopstrategy => '18',
   amopopr => '=(anyrange,anyrange)', amopmethod => 'spgist' },
 
+# SP-GiST multirange_me_ops
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '1',
+  amopopr => '<<(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '1',
+  amopopr => '<<(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '2',
+  amopopr => '&<(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '2',
+  amopopr => '&<(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '3',
+  amopopr => '&&(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '3',
+  amopopr => '&&(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '4',
+  amopopr => '&>(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '4',
+  amopopr => '&>(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '5',
+  amopopr => '>>(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '5',
+  amopopr => '>>(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '6',
+  amopopr => '-|-(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '6',
+  amopopr => '-|-(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '7',
+  amopopr => '@>(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '7',
+  amopopr => '@>(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '8',
+  amopopr => '<@(anymultirange,anymultirange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '8',
+  amopopr => '<@(anymultirange,anyrange)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyelement', amopstrategy => '16',
+  amopopr => '@>(anymultirange,anyelement)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '18',
+  amopopr => '=(anymultirange,anymultirange)', amopmethod => 'spgist' },
+
 # SP-GiST box_ops
 { amopfamily => 'spgist/box_ops', amoplefttype => 'box', amoprighttype => 'box',
   amopstrategy => '1', amopopr => '<<(box,box)', amopmethod => 'spgist' },
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 0bf9ea1145e..50013f293f1 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -785,6 +785,24 @@
 { amprocfamily => 'spgist/range_ops', amproclefttype => 'anyrange',
   amprocrighttype => 'anyrange', amprocnum => '5',
   amproc => 'spg_range_quad_leaf_consistent' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '1',
+  amproc => 'spg_multirange_me_config' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '2',
+  amproc => 'spg_range_quad_choose' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '3',
+  amproc => 'spg_range_quad_picksplit' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '4',
+  amproc => 'spg_multirange_me_inner_consistent' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '5',
+  amproc => 'spg_multirange_me_leaf_consistent' },
+{ amprocfamily => 'spgist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '8',
+  amproc => 'multirange_gist_extractvalue' },
 { amprocfamily => 'spgist/network_ops', amproclefttype => 'inet',
   amprocrighttype => 'inet', amprocnum => '1', amproc => 'inet_spg_config' },
 { amprocfamily => 'spgist/network_ops', amproclefttype => 'inet',
diff --git a/src/include/catalog/pg_opclass.dat b/src/include/catalog/pg_opclass.dat
index 07920290013..1925150374f 100644
--- a/src/include/catalog/pg_opclass.dat
+++ b/src/include/catalog/pg_opclass.dat
@@ -249,6 +249,9 @@
 { opcmethod => 'gist', opcname => 'multirange_me_ops',
   opcfamily => 'gist/multirange_me_ops', opcintype => 'anymultirange',
   opckeytype => 'anyrange', opcdefault => 'f' },
+{ opcmethod => 'spgist', opcname => 'multirange_me_ops',
+  opcfamily => 'spgist/multirange_me_ops', opcintype => 'anymultirange',
+  opckeytype => 'anyrange', opcdefault => 'f' },
 { opcmethod => 'spgist', opcname => 'box_ops', opcfamily => 'spgist/box_ops',
   opcintype => 'box' },
 { opcmethod => 'spgist', opcname => 'quad_point_ops',
diff --git a/src/include/catalog/pg_opfamily.dat b/src/include/catalog/pg_opfamily.dat
index 93a80175352..cc06084004c 100644
--- a/src/include/catalog/pg_opfamily.dat
+++ b/src/include/catalog/pg_opfamily.dat
@@ -310,5 +310,7 @@
   opfmethod => 'gist', opfname => 'multirange_ops' },
 { oid => '9319',
   opfmethod => 'gist', opfname => 'multirange_me_ops' },
+{ oid => '9323',
+  opfmethod => 'spgist', opfname => 'multirange_me_ops' },
 
 ]
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 699d8416d47..a9b7f02f5e0 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -11172,6 +11172,17 @@
   proname => 'multirange_gist_extractvalue', prorettype => 'internal',
   proargtypes => 'internal internal internal',
   prosrc => 'multirange_gist_extractvalue' },
+{ oid => '9320', descr => 'SP-GiST support for multi-entry multirange',
+  proname => 'spg_multirange_me_config', prorettype => 'void',
+  proargtypes => 'internal internal', prosrc => 'spg_multirange_me_config' },
+{ oid => '9321', descr => 'SP-GiST support for multi-entry multirange',
+  proname => 'spg_multirange_me_inner_consistent', prorettype => 'void',
+  proargtypes => 'internal internal',
+  prosrc => 'spg_multirange_me_inner_consistent' },
+{ oid => '9322', descr => 'SP-GiST support for multi-entry multirange',
+  proname => 'spg_multirange_me_leaf_consistent', prorettype => 'bool',
+  proargtypes => 'internal internal',
+  prosrc => 'spg_multirange_me_leaf_consistent' },
 { oid => '3902', descr => 'hash a range',
   proname => 'hash_range', prorettype => 'int4', proargtypes => 'anyrange',
   prosrc => 'hash_range' },
diff --git a/src/test/regress/expected/multirangetypes.out b/src/test/regress/expected/multirangetypes.out
index 4134f1358ed..59c843c1a7c 100644
--- a/src/test/regress/expected/multirangetypes.out
+++ b/src/test/regress/expected/multirangetypes.out
@@ -3546,6 +3546,673 @@ drop table test_me_nulls;
 drop table test_me_multicol;
 drop table test_multirange_me_gist;
 --
+-- Multi-entry SP-GiST index (multirange_me_ops)
+-- Decomposes multiranges into component ranges for quad-tree indexing.
+--
+create table test_multirange_me_spgist(mr int4multirange);
+insert into test_multirange_me_spgist select int4multirange(int4range(g, g+10),int4range(g+20, g+30),int4range(g+40, g+50)) from generate_series(1,2000) g;
+insert into test_multirange_me_spgist select '{}'::int4multirange from generate_series(1,500) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(g, g+10000)) from generate_series(1,1000) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(NULL, g*10, '(]'), int4range(g*10, g*20, '(]')) from generate_series(1,100) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(g*10, g*20, '(]'), int4range(g*20, NULL, '(]')) from generate_series(1,100) g;
+create index test_multirange_me_spgist_idx on test_multirange_me_spgist using spgist (mr multirange_me_ops);
+-- first, verify non-indexed results
+SET enable_seqscan    = t;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = f;
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+     3
+(1 row)
+
+-- now check same queries using index
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+SET enable_bitmapscan = f;
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+     3
+(1 row)
+
+-- also check bitmap scan
+SET enable_seqscan    = f;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = t;
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+     3
+(1 row)
+
+-- test NULL handling
+create table test_me_spgist_nulls(mr int4multirange);
+insert into test_me_spgist_nulls values (NULL), ('{}'::int4multirange), ('{[1,3]}');
+create index on test_me_spgist_nulls using spgist (mr multirange_me_ops);
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+select * from test_me_spgist_nulls where mr @> 1;
+   mr    
+---------
+ {[1,4)}
+(1 row)
+
+drop table test_me_spgist_nulls;
+drop table test_multirange_me_spgist;
+--
 -- range_agg function
 --
 create table reservations ( room_id integer not null, booked_during daterange );
diff --git a/src/test/regress/expected/psql.out b/src/test/regress/expected/psql.out
index c8f3932edf0..3262d7f3b63 100644
--- a/src/test/regress/expected/psql.out
+++ b/src/test/regress/expected/psql.out
@@ -5262,17 +5262,18 @@ List of access methods
 (3 rows)
 
 \dAf spgist
-          List of operator families
-   AM   | Operator family | Applicable types 
---------+-----------------+------------------
- spgist | box_ops         | box
- spgist | kd_point_ops    | point
- spgist | network_ops     | inet
- spgist | poly_ops        | polygon
- spgist | quad_point_ops  | point
- spgist | range_ops       | anyrange
- spgist | text_ops        | text
-(7 rows)
+           List of operator families
+   AM   |  Operator family  | Applicable types 
+--------+-------------------+------------------
+ spgist | box_ops           | box
+ spgist | kd_point_ops      | point
+ spgist | multirange_me_ops | anymultirange
+ spgist | network_ops       | inet
+ spgist | poly_ops          | polygon
+ spgist | quad_point_ops    | point
+ spgist | range_ops         | anyrange
+ spgist | text_ops          | text
+(8 rows)
 
 \dAf btree int4
               List of operator families
diff --git a/src/test/regress/sql/multirangetypes.sql b/src/test/regress/sql/multirangetypes.sql
index 902d719d75c..10839646983 100644
--- a/src/test/regress/sql/multirangetypes.sql
+++ b/src/test/regress/sql/multirangetypes.sql
@@ -712,6 +712,155 @@ drop table test_me_nulls;
 drop table test_me_multicol;
 drop table test_multirange_me_gist;
 
+--
+-- Multi-entry SP-GiST index (multirange_me_ops)
+-- Decomposes multiranges into component ranges for quad-tree indexing.
+--
+create table test_multirange_me_spgist(mr int4multirange);
+insert into test_multirange_me_spgist select int4multirange(int4range(g, g+10),int4range(g+20, g+30),int4range(g+40, g+50)) from generate_series(1,2000) g;
+insert into test_multirange_me_spgist select '{}'::int4multirange from generate_series(1,500) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(g, g+10000)) from generate_series(1,1000) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(NULL, g*10, '(]'), int4range(g*10, g*20, '(]')) from generate_series(1,100) g;
+insert into test_multirange_me_spgist select int4multirange(int4range(g*10, g*20, '(]'), int4range(g*20, NULL, '(]')) from generate_series(1,100) g;
+create index test_multirange_me_spgist_idx on test_multirange_me_spgist using spgist (mr multirange_me_ops);
+
+-- first, verify non-indexed results
+SET enable_seqscan    = t;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = f;
+
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_spgist where mr @> 10;
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+
+-- now check same queries using index
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+SET enable_bitmapscan = f;
+
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_spgist where mr @> 10;
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+
+-- also check bitmap scan
+SET enable_seqscan    = f;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = t;
+
+select count(*) from test_multirange_me_spgist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_spgist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_spgist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_spgist where mr @> 10;
+select count(*) from test_multirange_me_spgist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr && int4range(10,20);
+select count(*) from test_multirange_me_spgist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_spgist where mr << int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_spgist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_spgist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_spgist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_spgist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+
+-- test NULL handling
+create table test_me_spgist_nulls(mr int4multirange);
+insert into test_me_spgist_nulls values (NULL), ('{}'::int4multirange), ('{[1,3]}');
+create index on test_me_spgist_nulls using spgist (mr multirange_me_ops);
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+select * from test_me_spgist_nulls where mr @> 1;
+
+drop table test_me_spgist_nulls;
+drop table test_multirange_me_spgist;
+
 --
 -- range_agg function
 --
-- 
2.50.1 (Apple Git-155)