v1-0002-Add-multirange_me_ops-GiST-opclass-using-multi-en.patch

From 18f4cb4bd7af1c7d7763262a7465431cbde46379 Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <maxime.schoemans@enterprisedb.com>
Date: Thu, 2 Apr 2026 18:15:00 +0200
Subject: [PATCH v1 2/4] Add multirange_me_ops GiST opclass using multi-entry

Add a new GiST opclass, multirange_me_ops, that uses the multi-entry
infrastructure from the previous commit to decompose multiranges into
their component ranges for indexing.  Unlike the existing multirange_ops
which compresses a multirange into its bounding union range (losing gap
information), this opclass stores each component range as a separate
index entry, giving the R-tree much tighter bounds and significantly
reducing false-positive rechecks.

The opclass provides:

  - extractValue: decomposes a multirange into component ranges.  Empty
    multiranges are stored as empty range sentinels (not NULLs) so they
    remain visible to operator queries.

  - Leaf consistent functions: account for the fact that each leaf entry
    is a single component, not the full multirange.  OVERLAPS and
    CONTAINS_ELEM are recheck-free (a component match implies a
    multirange match); all other strategies set recheck.

  - Internal consistent functions: like the standard range GiST internal
    checks, but CONTAINS and EQ are relaxed to use overlap instead of
    containment, since a matching multirange's components may be spread
    across multiple subtrees.

The opclass is non-default (multirange_ops remains the default) and
supports the same operator set: <<, &<, &&, &>, >>, -|-, @>, <@, @>elem,
and =.

Regression tests verify index correctness against sequential scan results
for all operators, including empty range/multirange edge cases, bitmap
scans, multi-column restriction enforcement, and NULL handling.
---
 src/backend/utils/adt/rangetypes_gist.c       | 466 ++++++++++++
 src/include/catalog/pg_amop.dat               |  56 ++
 src/include/catalog/pg_amproc.dat             |  21 +
 src/include/catalog/pg_opclass.dat            |   3 +
 src/include/catalog/pg_opfamily.dat           |   2 +
 src/include/catalog/pg_proc.dat               |   8 +
 src/test/regress/expected/multirangetypes.out | 672 ++++++++++++++++++
 src/test/regress/sql/multirangetypes.sql      | 154 ++++
 8 files changed, 1382 insertions(+)

diff --git a/src/backend/utils/adt/rangetypes_gist.c b/src/backend/utils/adt/rangetypes_gist.c
index 1a01a8f4c3c..222103cbb57 100644
--- a/src/backend/utils/adt/rangetypes_gist.c
+++ b/src/backend/utils/adt/rangetypes_gist.c
@@ -160,6 +160,30 @@ static bool range_gist_consistent_leaf_element(TypeCacheEntry *typcache,
 											   StrategyNumber strategy,
 											   const RangeType *key,
 											   Datum query);
+static bool range_me_consistent_int_range(TypeCacheEntry *typcache,
+										  StrategyNumber strategy,
+										  const RangeType *key,
+										  const RangeType *query);
+static bool range_me_consistent_int_multirange(TypeCacheEntry *typcache,
+											   StrategyNumber strategy,
+											   const RangeType *key,
+											   const MultirangeType *query);
+static bool range_me_consistent_int_element(TypeCacheEntry *typcache,
+											StrategyNumber strategy,
+											const RangeType *key,
+											Datum query);
+static bool range_me_consistent_leaf_range(TypeCacheEntry *typcache,
+										   StrategyNumber strategy,
+										   const RangeType *key,
+										   const RangeType *query);
+static bool range_me_consistent_leaf_multirange(TypeCacheEntry *typcache,
+												StrategyNumber strategy,
+												const RangeType *key,
+												const MultirangeType *query);
+static bool range_me_consistent_leaf_element(TypeCacheEntry *typcache,
+											 StrategyNumber strategy,
+											 const RangeType *key,
+											 Datum query);
 static void range_gist_fallback_split(TypeCacheEntry *typcache,
 									  GistEntryVector *entryvec,
 									  GIST_SPLITVEC *v);
@@ -1796,3 +1820,445 @@ call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
 		return value;
 	return 0.0;
 }
+
+
+/*
+ *----------------------------------------------------------
+ * MULTI-ENTRY GiST SUPPORT FOR MULTIRANGES
+ *
+ * When an extractValue support function is registered, GiST decomposes
+ * each multirange into its component ranges and stores each as a separate
+ * index entry.  This requires a different consistent function because
+ * leaf entries are individual component ranges, not the union range.
+ *----------------------------------------------------------
+ */
+
+/*
+ * Multi-entry GiST extractValue function for multirange types.
+ *
+ * Decomposes a multirange into its component ranges.  Returns an array
+ * of Datum values (one per range) via the return value, and sets *nkeys
+ * to the number of entries.
+ */
+Datum
+multirange_gist_extractvalue(PG_FUNCTION_ARGS)
+{
+	MultirangeType *mr = PG_GETARG_MULTIRANGE_P(0);
+	int32	   *nkeys = (int32 *) PG_GETARG_POINTER(1);
+	TypeCacheEntry *typcache;
+	int32		range_count;
+	RangeType **ranges;
+	Datum	   *entries;
+	int			i;
+
+	typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
+
+	if (MultirangeIsEmpty(mr))
+	{
+		/*
+		 * Store an empty range as a sentinel for empty multiranges so they
+		 * remain visible to operator queries (NULL entries only match IS NULL).
+		 */
+		RangeBound	lower = {0};
+		RangeBound	upper = {0};
+
+		lower.lower = true;
+		entries = palloc(sizeof(Datum));
+		entries[0] = RangeTypePGetDatum(
+			make_range(typcache->rngtype, &lower, &upper, true, NULL));
+		*nkeys = 1;
+		PG_RETURN_POINTER(entries);
+	}
+
+	multirange_deserialize(typcache->rngtype, mr, &range_count, &ranges);
+
+	entries = palloc(sizeof(Datum) * range_count);
+	for (i = 0; i < range_count; i++)
+		entries[i] = RangeTypePGetDatum(ranges[i]);
+
+	*nkeys = range_count;
+	PG_RETURN_POINTER(entries);
+}
+
+/*
+ * Multi-entry GiST consistent function for multirange types.
+ *
+ * This is used when the multirange opclass has an extractValue function.
+ * Leaf entries are individual component ranges (not the union range), so
+ * most leaf checks set recheck=true since a single component cannot fully
+ * determine the relationship with the query.  OVERLAPS and CONTAINS_ELEM
+ * are exact per-component and skip recheck (see comments in the leaf
+ * consistent functions below).  Internal nodes still store union ranges,
+ * so the internal consistent checks are unchanged.
+ */
+Datum
+multirange_gist_me_consistent(PG_FUNCTION_ARGS)
+{
+	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+	Datum		query = PG_GETARG_DATUM(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+	bool		result;
+	Oid			subtype = PG_GETARG_OID(3);
+	bool	   *recheck = (bool *) PG_GETARG_POINTER(4);
+	RangeType  *key = DatumGetRangeTypeP(entry->key);
+	TypeCacheEntry *typcache;
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
+
+	if (GIST_LEAF(entry))
+	{
+		/*
+		 * Leaf entries are individual component ranges from the multirange.
+		 * Use multi-entry leaf consistent functions which account for the
+		 * fact that we're seeing only one component, not the full value.
+		 *
+		 * Most strategies need recheck because a single component cannot
+		 * determine the full multirange's relationship with the query.
+		 * However, some strategies are exact per-component:
+		 *
+		 * - OVERLAPS: if component Ri overlaps Q, then M overlaps Q, because
+		 *   the shared points between Ri and Q are also in M.
+		 * - CONTAINS_ELEM: if Ri contains elem, M contains elem, because
+		 *   Ri is a subset of M.
+		 */
+		if (strategy == RANGESTRAT_OVERLAPS ||
+			strategy == RANGESTRAT_CONTAINS_ELEM)
+			*recheck = false;
+		else
+			*recheck = true;
+
+		if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
+			result = range_me_consistent_leaf_multirange(typcache, strategy,
+														 key,
+														 DatumGetMultirangeTypeP(query));
+		else if (subtype == ANYRANGEOID)
+			result = range_me_consistent_leaf_range(typcache, strategy, key,
+													DatumGetRangeTypeP(query));
+		else
+			result = range_me_consistent_leaf_element(typcache, strategy,
+													  key, query);
+	}
+	else
+	{
+		/*
+		 * Internal nodes store union ranges of components from potentially
+		 * many different multiranges.  We use multi-entry-aware internal
+		 * consistent functions that relax CONTAINS and EQ checks: the
+		 * standard functions require the union key to fully contain the
+		 * query, but in multi-entry a matching multirange's components may
+		 * be spread across multiple subtrees.
+		 */
+		if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
+			result = range_me_consistent_int_multirange(typcache, strategy,
+														key,
+														DatumGetMultirangeTypeP(query));
+		else if (subtype == ANYRANGEOID)
+			result = range_me_consistent_int_range(typcache, strategy, key,
+												   DatumGetRangeTypeP(query));
+		else
+			result = range_me_consistent_int_element(typcache, strategy,
+													 key, query);
+	}
+	PG_RETURN_BOOL(result);
+}
+
+/*
+ * Multi-entry leaf consistent test with a range query.
+ *
+ * The key is one component range from the indexed multirange M.  We must
+ * avoid false negatives: if the operator holds for M and query Q, at least
+ * one component must return true here.  False positives are filtered by
+ * recheck.  See multirange_gist_me_consistent for which strategies are
+ * recheck-free.
+ */
+static bool
+range_me_consistent_leaf_range(TypeCacheEntry *typcache,
+							   StrategyNumber strategy,
+							   const RangeType *key,
+							   const RangeType *query)
+{
+	/* Empty key is the sentinel for an empty multirange */
+	if (RangeIsEmpty(key))
+	{
+		if (strategy == RANGESTRAT_CONTAINED_BY)
+			return true;
+		if (strategy == RANGESTRAT_CONTAINS)
+			return RangeIsEmpty(query);
+		return false;
+	}
+
+	/* Empty range is contained by everything, has no other relationships */
+	if (RangeIsEmpty(query))
+	{
+		if (strategy == RANGESTRAT_CONTAINS)
+			return true;
+		return false;
+	}
+
+	switch (strategy)
+	{
+			/*
+			 * Bound operators: if M satisfies the bound, every component
+			 * does too, so the exact per-component check has no false
+			 * negatives.  Still needs recheck since other components may
+			 * violate the bound.
+			 */
+		case RANGESTRAT_BEFORE:
+			return range_before_internal(typcache, key, query);
+		case RANGESTRAT_OVERLEFT:
+			return range_overleft_internal(typcache, key, query);
+		case RANGESTRAT_OVERRIGHT:
+			return range_overright_internal(typcache, key, query);
+		case RANGESTRAT_AFTER:
+			return range_after_internal(typcache, key, query);
+
+			/* Exact and recheck-free: if component overlaps Q, so does M */
+		case RANGESTRAT_OVERLAPS:
+			return range_overlaps_internal(typcache, key, query);
+
+			/* Exact check, but another component might overlap Q */
+		case RANGESTRAT_ADJACENT:
+			return range_adjacent_internal(typcache, key, query);
+
+			/*
+			 * Use overlaps as a necessary condition.  For @>: Q is
+			 * contiguous and must lie within some component, so that
+			 * component overlaps Q.  For <@: every component is a subset
+			 * of Q, so every component overlaps Q.
+			 */
+		case RANGESTRAT_CONTAINS:
+		case RANGESTRAT_CONTAINED_BY:
+		case RANGESTRAT_EQ:
+			return range_overlaps_internal(typcache, key, query);
+
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
+
+/*
+ * Multi-entry leaf consistent test with a multirange query.
+ *
+ * Same framework as range_me_consistent_leaf_range: no false negatives
+ * allowed, false positives filtered by recheck.
+ */
+static bool
+range_me_consistent_leaf_multirange(TypeCacheEntry *typcache,
+									StrategyNumber strategy,
+									const RangeType *key,
+									const MultirangeType *query)
+{
+	/* Empty key is the sentinel for an empty multirange */
+	if (RangeIsEmpty(key))
+	{
+		if (strategy == RANGESTRAT_CONTAINED_BY)
+			return true;
+		if (strategy == RANGESTRAT_CONTAINS || strategy == RANGESTRAT_EQ)
+			return MultirangeIsEmpty(query);
+		return false;
+	}
+
+	/* Empty multirange is contained by everything, has no other relationships */
+	if (MultirangeIsEmpty(query))
+	{
+		if (strategy == RANGESTRAT_CONTAINS)
+			return true;
+		return false;
+	}
+
+	switch (strategy)
+	{
+			/* Bound operators: same reasoning as the range query case */
+		case RANGESTRAT_BEFORE:
+			return range_before_multirange_internal(typcache, key, query);
+		case RANGESTRAT_OVERLEFT:
+			return range_overleft_multirange_internal(typcache, key, query);
+		case RANGESTRAT_OVERRIGHT:
+			return range_overright_multirange_internal(typcache, key, query);
+		case RANGESTRAT_AFTER:
+			return range_after_multirange_internal(typcache, key, query);
+
+			/* Exact check, but another component might overlap Q */
+		case RANGESTRAT_ADJACENT:
+			return range_adjacent_multirange_internal(typcache, key, query);
+
+			/* Overlaps is recheck-free; the rest use it as necessary condition */
+		case RANGESTRAT_OVERLAPS:
+		case RANGESTRAT_CONTAINS:
+		case RANGESTRAT_CONTAINED_BY:
+		case RANGESTRAT_EQ:
+			return range_overlaps_multirange_internal(typcache, key, query);
+
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
+
+/*
+ * Multi-entry leaf consistent test with an element query.
+ *
+ * Recheck-free: if component Ri contains elem, so does M.
+ */
+static bool
+range_me_consistent_leaf_element(TypeCacheEntry *typcache,
+								 StrategyNumber strategy,
+								 const RangeType *key,
+								 Datum query)
+{
+	switch (strategy)
+	{
+		case RANGESTRAT_CONTAINS_ELEM:
+			return range_contains_elem_internal(typcache, key, query);
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
+
+/*
+ * Multi-entry internal consistent test with a range query.
+ *
+ * Like range_gist_consistent_int_range but relaxes CONTAINS and EQ to use
+ * overlaps: a matching multirange's components may be spread across multiple
+ * subtrees, so the union key need not fully contain the query.
+ */
+static bool
+range_me_consistent_int_range(TypeCacheEntry *typcache,
+							  StrategyNumber strategy,
+							  const RangeType *key,
+							  const RangeType *query)
+{
+	switch (strategy)
+	{
+		case RANGESTRAT_BEFORE:
+			if (RangeIsEmpty(key) || RangeIsEmpty(query))
+				return false;
+			return (!range_overright_internal(typcache, key, query));
+		case RANGESTRAT_OVERLEFT:
+			if (RangeIsEmpty(key) || RangeIsEmpty(query))
+				return false;
+			return (!range_after_internal(typcache, key, query));
+		case RANGESTRAT_OVERLAPS:
+			return range_overlaps_internal(typcache, key, query);
+		case RANGESTRAT_OVERRIGHT:
+			if (RangeIsEmpty(key) || RangeIsEmpty(query))
+				return false;
+			return (!range_before_internal(typcache, key, query));
+		case RANGESTRAT_AFTER:
+			if (RangeIsEmpty(key) || RangeIsEmpty(query))
+				return false;
+			return (!range_overleft_internal(typcache, key, query));
+		case RANGESTRAT_ADJACENT:
+			if (RangeIsEmpty(key) || RangeIsEmpty(query))
+				return false;
+			if (range_adjacent_internal(typcache, key, query))
+				return true;
+			return range_overlaps_internal(typcache, key, query);
+
+			/*
+			 * Relaxed: overlaps instead of contains, because a matching
+			 * multirange's components may be spread across subtrees.
+			 * Empty query is contained by everything, so always descend.
+			 */
+		case RANGESTRAT_CONTAINS:
+			if (RangeIsEmpty(query))
+				return true;
+			return range_overlaps_internal(typcache, key, query);
+		case RANGESTRAT_CONTAINED_BY:
+			if (RangeIsOrContainsEmpty(key))
+				return true;
+			return range_overlaps_internal(typcache, key, query);
+		case RANGESTRAT_EQ:
+			if (RangeIsEmpty(query))
+				return RangeIsOrContainsEmpty(key);
+			return range_overlaps_internal(typcache, key, query);
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
+
+/*
+ * Multi-entry internal consistent test with a multirange query.
+ *
+ * Like range_gist_consistent_int_multirange but relaxes CONTAINS and EQ.
+ */
+static bool
+range_me_consistent_int_multirange(TypeCacheEntry *typcache,
+								   StrategyNumber strategy,
+								   const RangeType *key,
+								   const MultirangeType *query)
+{
+	switch (strategy)
+	{
+		case RANGESTRAT_BEFORE:
+			if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
+				return false;
+			return (!range_overright_multirange_internal(typcache, key, query));
+		case RANGESTRAT_OVERLEFT:
+			if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
+				return false;
+			return (!range_after_multirange_internal(typcache, key, query));
+		case RANGESTRAT_OVERLAPS:
+			return range_overlaps_multirange_internal(typcache, key, query);
+		case RANGESTRAT_OVERRIGHT:
+			if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
+				return false;
+			return (!range_before_multirange_internal(typcache, key, query));
+		case RANGESTRAT_AFTER:
+			if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
+				return false;
+			return (!range_overleft_multirange_internal(typcache, key, query));
+		case RANGESTRAT_ADJACENT:
+			if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
+				return false;
+			if (range_adjacent_multirange_internal(typcache, key, query))
+				return true;
+			return range_overlaps_multirange_internal(typcache, key, query);
+
+			/*
+			 * Relaxed: overlaps instead of contains, because a matching
+			 * multirange's components may be spread across subtrees.
+			 * Empty query is contained by everything, so always descend.
+			 */
+		case RANGESTRAT_CONTAINS:
+			if (MultirangeIsEmpty(query))
+				return true;
+			return range_overlaps_multirange_internal(typcache, key, query);
+		case RANGESTRAT_CONTAINED_BY:
+			if (RangeIsOrContainsEmpty(key))
+				return true;
+			return range_overlaps_multirange_internal(typcache, key, query);
+		case RANGESTRAT_EQ:
+			if (MultirangeIsEmpty(query))
+				return RangeIsOrContainsEmpty(key);
+			return range_overlaps_multirange_internal(typcache, key, query);
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
+
+/*
+ * Multi-entry internal consistent test with an element query.
+ *
+ * Same as range_gist_consistent_int_element -- only CONTAINS_ELEM is used
+ * and doesn't need relaxation.
+ */
+static bool
+range_me_consistent_int_element(TypeCacheEntry *typcache,
+								StrategyNumber strategy,
+								const RangeType *key,
+								Datum query)
+{
+	switch (strategy)
+	{
+		case RANGESTRAT_CONTAINS_ELEM:
+			return range_contains_elem_internal(typcache, key, query);
+		default:
+			elog(ERROR, "unrecognized range strategy: %d", strategy);
+			return false;		/* keep compiler quiet */
+	}
+}
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 8d5a0004a47..3cc3ba61eeb 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1477,6 +1477,62 @@
   amoprighttype => 'anymultirange', amopstrategy => '18',
   amopopr => '=(anymultirange,anymultirange)', amopmethod => 'gist' },
 
+# GiST multirange_me_ops
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '1',
+  amopopr => '<<(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '1',
+  amopopr => '<<(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '2',
+  amopopr => '&<(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '2',
+  amopopr => '&<(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '3',
+  amopopr => '&&(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '3',
+  amopopr => '&&(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '4',
+  amopopr => '&>(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '4',
+  amopopr => '&>(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '5',
+  amopopr => '>>(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '5',
+  amopopr => '>>(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '6',
+  amopopr => '-|-(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '6',
+  amopopr => '-|-(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '7',
+  amopopr => '@>(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '7',
+  amopopr => '@>(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '8',
+  amopopr => '<@(anymultirange,anymultirange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyrange', amopstrategy => '8',
+  amopopr => '<@(anymultirange,anyrange)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anyelement', amopstrategy => '16',
+  amopopr => '@>(anymultirange,anyelement)', amopmethod => 'gist' },
+{ amopfamily => 'gist/multirange_me_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '18',
+  amopopr => '=(anymultirange,anymultirange)', amopmethod => 'gist' },
+
 # btree multirange_ops
 { amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
   amoprighttype => 'anymultirange', amopstrategy => '1',
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 4a1efdbc899..0bf9ea1145e 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -689,6 +689,27 @@
 { amprocfamily => 'gist/multirange_ops', amproclefttype => 'any',
   amprocrighttype => 'any', amprocnum => '12',
   amproc => 'gist_translate_cmptype_common' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '1',
+  amproc => 'multirange_gist_me_consistent' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '2',
+  amproc => 'range_gist_union' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '5',
+  amproc => 'range_gist_penalty' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '6',
+  amproc => 'range_gist_picksplit' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '7',
+  amproc => 'range_gist_same' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'any',
+  amprocrighttype => 'any', amprocnum => '12',
+  amproc => 'gist_translate_cmptype_common' },
+{ amprocfamily => 'gist/multirange_me_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '13',
+  amproc => 'multirange_gist_extractvalue' },
 
 # gin
 { amprocfamily => 'gin/array_ops', amproclefttype => 'anyarray',
diff --git a/src/include/catalog/pg_opclass.dat b/src/include/catalog/pg_opclass.dat
index df170b80840..07920290013 100644
--- a/src/include/catalog/pg_opclass.dat
+++ b/src/include/catalog/pg_opclass.dat
@@ -246,6 +246,9 @@
 { opcmethod => 'gist', opcname => 'multirange_ops',
   opcfamily => 'gist/multirange_ops', opcintype => 'anymultirange',
   opckeytype => 'anyrange' },
+{ opcmethod => 'gist', opcname => 'multirange_me_ops',
+  opcfamily => 'gist/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 7a027c4810e..93a80175352 100644
--- a/src/include/catalog/pg_opfamily.dat
+++ b/src/include/catalog/pg_opfamily.dat
@@ -308,5 +308,7 @@
   opfmethod => 'hash', opfname => 'multirange_ops' },
 { oid => '6158',
   opfmethod => 'gist', opfname => 'multirange_ops' },
+{ oid => '9319',
+  opfmethod => 'gist', opfname => 'multirange_me_ops' },
 
 ]
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 99fa9a6ede2..699d8416d47 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -11164,6 +11164,14 @@
 { oid => '6156', descr => 'GiST support',
   proname => 'multirange_gist_compress', prorettype => 'internal',
   proargtypes => 'internal', prosrc => 'multirange_gist_compress' },
+{ oid => '9317', descr => 'GiST support',
+  proname => 'multirange_gist_me_consistent', prorettype => 'bool',
+  proargtypes => 'internal anymultirange int2 oid internal',
+  prosrc => 'multirange_gist_me_consistent' },
+{ oid => '9318', descr => 'GiST support',
+  proname => 'multirange_gist_extractvalue', prorettype => 'internal',
+  proargtypes => 'internal internal internal',
+  prosrc => 'multirange_gist_extractvalue' },
 { 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 f5e7df8df43..4134f1358ed 100644
--- a/src/test/regress/expected/multirangetypes.out
+++ b/src/test/regress/expected/multirangetypes.out
@@ -2874,6 +2874,678 @@ select count(*) from test_multirange_gist where mr -|- int4multirange(int4range(
 
 drop table test_multirange_gist;
 --
+-- Multi-entry GiST index (multirange_me_ops)
+-- Decomposes multiranges into component ranges for indexing.
+--
+create table test_multirange_me_gist(mr int4multirange);
+insert into test_multirange_me_gist 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_gist select '{}'::int4multirange from generate_series(1,500) g;
+insert into test_multirange_me_gist select int4multirange(int4range(g, g+10000)) from generate_series(1,1000) g;
+insert into test_multirange_me_gist select int4multirange(int4range(NULL, g*10, '(]'), int4range(g*10, g*20, '(]')) from generate_series(1,100) g;
+insert into test_multirange_me_gist select int4multirange(int4range(g*10, g*20, '(]'), int4range(g*20, NULL, '(]')) from generate_series(1,100) g;
+create index test_multirange_me_gist_idx on test_multirange_me_gist using gist (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_gist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist 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_gist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist 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_gist where mr = '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+ count 
+-------
+  3700
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+ count 
+-------
+     0
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+ count 
+-------
+     1
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> 10;
+ count 
+-------
+   120
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+ count 
+-------
+   139
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+ count 
+-------
+     3
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+ count 
+-------
+   110
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+ count 
+-------
+   218
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+ count 
+-------
+   500
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+    54
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2053
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+   474
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+  2893
+(1 row)
+
+select count(*) from test_multirange_me_gist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+ count 
+-------
+     3
+(1 row)
+
+-- test that multi-column indexes with extractValue are disallowed
+create table test_me_multicol(mr int4multirange, r int4range);
+create index on test_me_multicol using gist (mr multirange_me_ops, r);
+ERROR:  multi-entry GiST indexes do not support multiple key columns
+-- test NULL handling
+create table test_me_nulls(mr int4multirange);
+insert into test_me_nulls values (NULL), ('{}'::int4multirange), ('{[1,3]}');
+create index on test_me_nulls using gist (mr multirange_me_ops);
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+select * from test_me_nulls where mr @> 1;
+   mr    
+---------
+ {[1,4)}
+(1 row)
+
+drop table test_me_nulls;
+drop table test_me_multicol;
+drop table test_multirange_me_gist;
+--
 -- range_agg function
 --
 create table reservations ( room_id integer not null, booked_during daterange );
diff --git a/src/test/regress/sql/multirangetypes.sql b/src/test/regress/sql/multirangetypes.sql
index 112334b03eb..902d719d75c 100644
--- a/src/test/regress/sql/multirangetypes.sql
+++ b/src/test/regress/sql/multirangetypes.sql
@@ -558,6 +558,160 @@ select count(*) from test_multirange_gist where mr -|- int4multirange(int4range(
 
 drop table test_multirange_gist;
 
+--
+-- Multi-entry GiST index (multirange_me_ops)
+-- Decomposes multiranges into component ranges for indexing.
+--
+create table test_multirange_me_gist(mr int4multirange);
+insert into test_multirange_me_gist 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_gist select '{}'::int4multirange from generate_series(1,500) g;
+insert into test_multirange_me_gist select int4multirange(int4range(g, g+10000)) from generate_series(1,1000) g;
+insert into test_multirange_me_gist select int4multirange(int4range(NULL, g*10, '(]'), int4range(g*10, g*20, '(]')) from generate_series(1,100) g;
+insert into test_multirange_me_gist select int4multirange(int4range(g*10, g*20, '(]'), int4range(g*20, NULL, '(]')) from generate_series(1,100) g;
+create index test_multirange_me_gist_idx on test_multirange_me_gist using gist (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_gist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_gist where mr @> 10;
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist 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_gist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_gist where mr @> 10;
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist 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_gist where mr = '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr @> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr && 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr <@ 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr << 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr >> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &< 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr &> 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr -|- 'empty'::int4range;
+select count(*) from test_multirange_me_gist where mr @> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr && '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr >> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &< '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr &> '{}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr -|- '{}'::int4multirange;
+
+select count(*) from test_multirange_me_gist where mr = int4multirange(int4range(10,20), int4range(30,40), int4range(50,60));
+select count(*) from test_multirange_me_gist where mr @> 10;
+select count(*) from test_multirange_me_gist where mr @> int4range(10,20);
+select count(*) from test_multirange_me_gist where mr && int4range(10,20);
+select count(*) from test_multirange_me_gist where mr <@ int4range(10,50);
+select count(*) from test_multirange_me_gist where mr << int4range(100,500);
+select count(*) from test_multirange_me_gist where mr >> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &< int4range(100,500);
+select count(*) from test_multirange_me_gist where mr &> int4range(100,500);
+select count(*) from test_multirange_me_gist where mr -|- int4range(100,500);
+select count(*) from test_multirange_me_gist where mr @> int4multirange(int4range(10,20), int4range(30,40));
+select count(*) from test_multirange_me_gist where mr && '{(10,20),(30,40),(50,60)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr <@ '{(10,30),(40,60),(70,90)}'::int4multirange;
+select count(*) from test_multirange_me_gist where mr << int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr >> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &< int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr &> int4multirange(int4range(100,200), int4range(400,500));
+select count(*) from test_multirange_me_gist where mr -|- int4multirange(int4range(100,200), int4range(400,500));
+
+-- test that multi-column indexes with extractValue are disallowed
+create table test_me_multicol(mr int4multirange, r int4range);
+create index on test_me_multicol using gist (mr multirange_me_ops, r);
+
+-- test NULL handling
+create table test_me_nulls(mr int4multirange);
+insert into test_me_nulls values (NULL), ('{}'::int4multirange), ('{[1,3]}');
+create index on test_me_nulls using gist (mr multirange_me_ops);
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+select * from test_me_nulls where mr @> 1;
+
+drop table test_me_nulls;
+drop table test_me_multicol;
+drop table test_multirange_me_gist;
+
 --
 -- range_agg function
 --
-- 
2.50.1 (Apple Git-155)