public inbox for [email protected]
help / color / mirror / Atom feedFrom: Maxime Schoemans <[email protected]>
To: [email protected]
Subject: Re: Multi-Entry Indexing for GiST & SP-GiST
Date: Thu, 21 May 2026 10:34:14 -0700
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
This time with the patches attached.
Best,
Maxime
Attachments:
[application/octet-stream] v1-0001-Add-multi-entry-support-to-GiST.patch (21.5K, 2-v1-0001-Add-multi-entry-support-to-GiST.patch)
download | inline diff:
From 7388571d02681075ed7e9b00507fd02b3103e44c Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <[email protected]>
Date: Thu, 2 Apr 2026 18:11:44 +0200
Subject: [PATCH v1 1/4] Add multi-entry support to GiST
Add infrastructure for GiST indexes to store multiple index entries per
heap tuple, similar to how GIN decomposes values via extractValue but
within GiST's R-tree framework.
A new optional support function, extractValue (support procedure 13), is
added. When an opclass provides it, the function is called during insert
and index build to decompose each datum into multiple sub-entries, each
stored as a separate index tuple pointing to the same heap TID.
On the scan side, a simplehash-based TID deduplication hash table ensures
each heap tuple is returned only once despite having multiple index
entries. Three scan modes are handled:
- Bitmap scans: the TIDBitmap handles deduplication inherently.
- Non-ordered scans: the hash table filters duplicates in pageData.
- Ordered (KNN) scans: the hash table filters duplicates both when
enqueuing leaf items and when dequeuing from the pairing heap,
ensuring the first (nearest) distance wins.
Other changes:
- gistcanreturn() disables index-only scans on key columns that use
extractValue, since the original datum cannot be reconstructed from
a single component.
- Multi-entry is restricted to single-key-column indexes (INCLUDE
columns are allowed). Multi-column support is left for future work.
- gistvalidate.c marks extractValue as optional and validates its
signature (internal, internal, internal) -> internal.
---
src/backend/access/gist/gist.c | 58 ++++++++++-
src/backend/access/gist/gistbuild.c | 72 +++++++++-----
src/backend/access/gist/gistget.c | 130 ++++++++++++++++++++++++-
src/backend/access/gist/gistscan.c | 4 +
src/backend/access/gist/gistutil.c | 68 +++++++++++++
src/backend/access/gist/gistvalidate.c | 9 +-
src/include/access/gist.h | 3 +-
src/include/access/gist_private.h | 14 +++
8 files changed, 327 insertions(+), 31 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 8565e225be7..bb280e6ea5a 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -161,6 +161,10 @@ gistbuildempty(Relation index)
*
* This is the public interface routine for tuple insertion in GiSTs.
* It doesn't do any work; just locks the relation and passes the buck.
+ *
+ * If the opclass provides an extractValue function (multi-entry mode),
+ * a single heap tuple may produce multiple index entries. Each entry
+ * is inserted separately, all pointing to the same heap TID.
*/
bool
gistinsert(Relation r, Datum *values, bool *isnull,
@@ -170,7 +174,6 @@ gistinsert(Relation r, Datum *values, bool *isnull,
IndexInfo *indexInfo)
{
GISTSTATE *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
- IndexTuple itup;
MemoryContext oldCxt;
/* Initialize GISTSTATE cache if first call in this statement */
@@ -185,10 +188,31 @@ gistinsert(Relation r, Datum *values, bool *isnull,
oldCxt = MemoryContextSwitchTo(giststate->tempCxt);
- itup = gistFormTuple(giststate, r, values, isnull, true);
- itup->t_tid = *ht_ctid;
+ /*
+ * If the opclass provides an extractValue function, extract multiple
+ * entries and insert each one separately.
+ */
+ if (OidIsValid(giststate->extractValueFn[0].fn_oid))
+ {
+ IndexTuple *itups;
+ int32 nitups;
+ int i;
- gistdoinsert(r, itup, 0, giststate, heapRel, false);
+ itups = gistExtractEntries(giststate, r, values, isnull, &nitups);
+ for (i = 0; i < nitups; i++)
+ {
+ itups[i]->t_tid = *ht_ctid;
+ gistdoinsert(r, itups[i], 0, giststate, heapRel, false);
+ }
+ }
+ else
+ {
+ IndexTuple itup;
+
+ itup = gistFormTuple(giststate, r, values, isnull, true);
+ itup->t_tid = *ht_ctid;
+ gistdoinsert(r, itup, 0, giststate, heapRel, false);
+ }
/* cleanup */
MemoryContextSwitchTo(oldCxt);
@@ -1623,6 +1647,14 @@ initGISTstate(Relation index)
else
giststate->fetchFn[i].fn_oid = InvalidOid;
+ /* opclasses are not required to provide an ExtractValue method */
+ if (OidIsValid(index_getprocid(index, i + 1, GIST_EXTRACTVALUE_PROC)))
+ fmgr_info_copy(&(giststate->extractValueFn[i]),
+ index_getprocinfo(index, i + 1, GIST_EXTRACTVALUE_PROC),
+ scanCxt);
+ else
+ giststate->extractValueFn[i].fn_oid = InvalidOid;
+
/*
* If the index column has a specified collation, we should honor that
* while doing comparisons. However, we may have a collatable storage
@@ -1640,6 +1672,23 @@ initGISTstate(Relation index)
giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
}
+ /*
+ * Multi-entry indexes (those with extractValue) are currently only
+ * supported for single-column indexes. The semantics of decomposing
+ * multiple columns simultaneously are unclear (cross product? parallel
+ * arrays?), so we disallow it for now.
+ */
+ if (IndexRelationGetNumberOfKeyAttributes(index) > 1)
+ {
+ for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(index); i++)
+ {
+ if (OidIsValid(giststate->extractValueFn[i].fn_oid))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("multi-entry GiST indexes do not support multiple key columns")));
+ }
+ }
+
/* No opclass information for INCLUDE attributes */
for (; i < index->rd_att->natts; i++)
{
@@ -1652,6 +1701,7 @@ initGISTstate(Relation index)
giststate->equalFn[i].fn_oid = InvalidOid;
giststate->distanceFn[i].fn_oid = InvalidOid;
giststate->fetchFn[i].fn_oid = InvalidOid;
+ giststate->extractValueFn[i].fn_oid = InvalidOid;
giststate->supportCollation[i] = InvalidOid;
}
diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c
index 7f57c787f4c..ef786682b84 100644
--- a/src/backend/access/gist/gistbuild.c
+++ b/src/backend/access/gist/gistbuild.c
@@ -827,21 +827,8 @@ gistBuildCallback(Relation index,
void *state)
{
GISTBuildState *buildstate = (GISTBuildState *) state;
- IndexTuple itup;
MemoryContext oldCtx;
- oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
-
- /* form an index tuple and point it at the heap tuple */
- itup = gistFormTuple(buildstate->giststate, index,
- values, isnull,
- true);
- itup->t_tid = *tid;
-
- /* Update tuple count and total size. */
- buildstate->indtuples += 1;
- buildstate->indtuplesSize += IndexTupleSize(itup);
-
/*
* XXX In buffering builds, the tempCxt is also reset down inside
* gistProcessEmptyingQueue(). This is not great because it risks
@@ -850,20 +837,61 @@ gistBuildCallback(Relation index,
* better that a memory context be "owned" by only one function. However,
* currently this isn't causing issues so it doesn't seem worth the amount
* of refactoring that would be needed to avoid it.
+ *
+ * If the opclass provides an extractValue function, extract multiple
+ * entries and insert each one. Otherwise, form a single index tuple.
+ *
+ * We extract entries in the caller's memory context so that the itups
+ * array survives MemoryContextReset(tempCxt) inside
+ * gistProcessEmptyingQueue during buffering builds.
*/
- if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
+ if (OidIsValid(buildstate->giststate->extractValueFn[0].fn_oid))
{
- /* We have buffers, so use them. */
- gistBufferingBuildInsert(buildstate, itup);
+ IndexTuple *itups;
+ int32 nitups;
+ int i;
+
+ itups = gistExtractEntries(buildstate->giststate, index,
+ values, isnull, &nitups);
+
+ oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
+
+ for (i = 0; i < nitups; i++)
+ {
+ itups[i]->t_tid = *tid;
+
+ /* Update tuple count and total size */
+ buildstate->indtuples += 1;
+ buildstate->indtuplesSize += IndexTupleSize(itups[i]);
+
+ if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
+ gistBufferingBuildInsert(buildstate, itups[i]);
+ else
+ gistdoinsert(index, itups[i], buildstate->freespace,
+ buildstate->giststate, buildstate->heaprel, true);
+ }
}
else
{
- /*
- * There's no buffers (yet). Since we already have the index relation
- * locked, we call gistdoinsert directly.
- */
- gistdoinsert(index, itup, buildstate->freespace,
- buildstate->giststate, buildstate->heaprel, true);
+ IndexTuple itup;
+
+ oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
+
+ /* form an index tuple and point it at the heap tuple */
+ itup = gistFormTuple(buildstate->giststate, index,
+ values, isnull,
+ true);
+ itup->t_tid = *tid;
+
+ /* Update tuple count and total size. */
+ buildstate->indtuples += 1;
+ buildstate->indtuplesSize += IndexTupleSize(itup);
+
+ if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
+ gistBufferingBuildInsert(buildstate, itup);
+ else
+ gistdoinsert(index, itup, buildstate->freespace,
+ buildstate->giststate, buildstate->heaprel, true);
}
MemoryContextSwitchTo(oldCtx);
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 4d7c100d737..a039cfd4575 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -17,6 +17,7 @@
#include "access/genam.h"
#include "access/gist_private.h"
#include "access/relscan.h"
+#include "common/hashfn.h"
#include "executor/instrument_node.h"
#include "lib/pairingheap.h"
#include "miscadmin.h"
@@ -26,6 +27,49 @@
#include "utils/memutils.h"
#include "utils/rel.h"
+/*
+ * Simplehash implementation for TID deduplication in multi-entry scans.
+ *
+ * When an opclass provides an extractValue function, each heap tuple produces
+ * multiple index entries. During scans, we must deduplicate results so that
+ * each heap TID is returned only once.
+ */
+
+/* Hash table entry for basic TID dedup */
+typedef struct GISTTIDHashEntry
+{
+ ItemPointerData tid; /* TID (hashtable key) */
+ uint32 hash; /* hash value (cached) */
+ char status; /* hash status */
+} GISTTIDHashEntry;
+
+static inline uint32
+gist_tid_hash_fn(ItemPointerData tid)
+{
+ uint32 h = murmurhash32(ItemPointerGetBlockNumber(&tid));
+
+ return murmurhash32(h + ItemPointerGetOffsetNumber(&tid));
+}
+
+static inline bool
+gist_tid_match_fn(ItemPointerData a, ItemPointerData b)
+{
+ return ItemPointerEquals(&a, &b);
+}
+
+/* --- gisttid hash table (declare + define) --- */
+#define SH_PREFIX gisttid
+#define SH_ELEMENT_TYPE GISTTIDHashEntry
+#define SH_KEY_TYPE ItemPointerData
+#define SH_KEY tid
+#define SH_HASH_KEY(tb, key) gist_tid_hash_fn(key)
+#define SH_EQUAL(tb, a, b) gist_tid_match_fn(a, b)
+#define SH_SCOPE static inline
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
+
/*
* gistkillitems() -- set LP_DEAD state for items an indexscan caller has
* told us were killed.
@@ -456,7 +500,8 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
{
/*
* getbitmap scan, so just push heap tuple TIDs into the bitmap
- * without worrying about ordering
+ * without worrying about ordering. The bitmap itself handles
+ * deduplication, so no extra work needed for multi-entry.
*/
tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
(*ntids)++;
@@ -464,8 +509,20 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
{
/*
- * Non-ordered scan, so report tuples in so->pageData[]
+ * Non-ordered scan, so report tuples in so->pageData[].
+ *
+ * For multi-entry indexes, check the TID hash table to avoid
+ * returning duplicate heap TIDs.
*/
+ if (so->tidHash)
+ {
+ bool found;
+
+ gisttid_insert(so->tidHash, it->t_tid, &found);
+ if (found)
+ continue; /* already seen this TID */
+ }
+
so->pageData[so->nPageData].heapPtr = it->t_tid;
so->pageData[so->nPageData].recheck = recheck;
so->pageData[so->nPageData].offnum = i;
@@ -495,6 +552,20 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
oldcxt = MemoryContextSwitchTo(so->queueCxt);
+ /*
+ * For multi-entry ordered scans, skip heap tuples whose TIDs
+ * were already returned by getNextNearest. We use lookup
+ * (not insert) here: a TID must remain enqueueable until it
+ * is actually dequeued, so that the pairing heap can pick the
+ * copy with the smallest distance.
+ */
+ if (GistPageIsLeaf(page) &&
+ so->tidHash && gisttid_lookup(so->tidHash, it->t_tid))
+ {
+ MemoryContextSwitchTo(oldcxt);
+ continue;
+ }
+
/* Create new GISTSearchItem for this item */
item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
@@ -587,7 +658,27 @@ getNextNearest(IndexScanDesc scan)
if (GISTSearchItemIsHeap(*item))
{
- /* found a heap item at currently minimal distance */
+ /*
+ * Found a heap item at currently minimal distance.
+ *
+ * For multi-entry ordered scans, deduplicate using tidHash to
+ * ensure each TID is returned only once. Duplicate entries
+ * for the same TID may exist in the queue with different
+ * distances; the pairing heap ensures we see the smallest
+ * distance first, and tidHash skips subsequent duplicates.
+ */
+ if (so->tidHash)
+ {
+ bool found;
+
+ gisttid_insert(so->tidHash, item->data.heap.heapPtr, &found);
+ if (found)
+ {
+ pfree(item);
+ continue; /* already returned this TID */
+ }
+ }
+
scan->xs_heaptid = item->data.heap.heapPtr;
scan->xs_recheck = item->data.heap.recheck;
@@ -643,6 +734,30 @@ gistgettuple(IndexScanDesc scan, ScanDirection dir)
if (so->pageDataCxt)
MemoryContextReset(so->pageDataCxt);
+ /*
+ * For multi-entry indexes, set up TID deduplication hash tables.
+ * We check column 0 for extractValueFn as a proxy for multi-entry.
+ */
+ if (OidIsValid(so->giststate->extractValueFn[0].fn_oid))
+ {
+ MemoryContext oldHashCxt;
+
+ /*
+ * Create a dedicated context for the hash tables so they can
+ * be reset independently.
+ */
+ if (so->tidHashCxt == so->giststate->scanCxt)
+ so->tidHashCxt = AllocSetContextCreate(so->giststate->scanCxt,
+ "GiST TID hash context",
+ ALLOCSET_DEFAULT_SIZES);
+ else
+ MemoryContextReset(so->tidHashCxt);
+
+ oldHashCxt = MemoryContextSwitchTo(so->tidHashCxt);
+ so->tidHash = gisttid_create(so->tidHashCxt, 256, NULL);
+ MemoryContextSwitchTo(oldHashCxt);
+ }
+
fakeItem.blkno = GIST_ROOT_BLKNO;
memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
@@ -805,6 +920,15 @@ gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
bool
gistcanreturn(Relation index, int attno)
{
+ /*
+ * Multi-entry indexes store decomposed sub-entries in key columns, not the
+ * original datum, so key columns cannot be returned in an index-only scan.
+ * INCLUDE columns are still returnable.
+ */
+ if (attno <= IndexRelationGetNumberOfKeyAttributes(index) &&
+ OidIsValid(index_getprocid(index, attno, GIST_EXTRACTVALUE_PROC)))
+ return false;
+
if (attno > IndexRelationGetNumberOfKeyAttributes(index) ||
OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) ||
!OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC)))
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index c65f93abdae..4d9a4a148cd 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -96,6 +96,10 @@ gistbeginscan(Relation r, int nkeys, int norderbys)
so->queue = NULL;
so->queueCxt = giststate->scanCxt; /* see gistrescan */
+ /* Initialize multi-entry TID dedup fields (NULL if not multi-entry) */
+ so->tidHash = NULL;
+ so->tidHashCxt = giststate->scanCxt;
+
/* workspaces with size dependent on numberOfOrderBys: */
so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
so->qual_ok = true; /* in case there are zero keys */
diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c
index 0f58f61879f..42ab801f7bf 100644
--- a/src/backend/access/gist/gistutil.c
+++ b/src/backend/access/gist/gistutil.c
@@ -1007,6 +1007,74 @@ gistproperty(Oid index_oid, int attno,
return true;
}
+/*
+ * gistExtractEntries -- extract multiple index entries from one heap tuple.
+ *
+ * Calls the opclass's extractValue function to decompose the indexed datum
+ * into multiple sub-entries. Returns an array of IndexTuples, one per
+ * sub-entry.
+ *
+ * Currently only single-key-column indexes are supported (enforced by
+ * initGISTstate). INCLUDE columns are preserved on every entry.
+ * If the datum is NULL or extractValue returns no entries, a single NULL
+ * index entry is produced.
+ */
+IndexTuple *
+gistExtractEntries(GISTSTATE *giststate, Relation index,
+ Datum *values, bool *isnull, int32 *nentries)
+{
+ Datum *entries;
+ bool *nullFlags;
+ IndexTuple *result;
+ int i;
+
+ Assert(IndexRelationGetNumberOfKeyAttributes(index) == 1);
+
+ /* NULL datum produces a single NULL index entry */
+ if (isnull[0])
+ {
+ *nentries = 1;
+ result = palloc(sizeof(IndexTuple));
+ result[0] = gistFormTuple(giststate, index, values, isnull, true);
+ return result;
+ }
+
+ /* Call the opclass's extractValue function */
+ nullFlags = NULL;
+ entries = (Datum *)
+ DatumGetPointer(FunctionCall3Coll(&giststate->extractValueFn[0],
+ giststate->supportCollation[0],
+ values[0],
+ PointerGetDatum(nentries),
+ PointerGetDatum(&nullFlags)));
+
+ /* Handle empty or NULL result: produce a single NULL entry */
+ if (entries == NULL || *nentries <= 0)
+ {
+ *nentries = 1;
+ values[0] = (Datum) 0;
+ isnull[0] = true;
+ result = palloc(sizeof(IndexTuple));
+ result[0] = gistFormTuple(giststate, index, values, isnull, true);
+ return result;
+ }
+
+ /* Create nullFlags array if the function didn't */
+ if (nullFlags == NULL)
+ nullFlags = palloc0_array(bool, *nentries);
+
+ /* Form one index tuple per extracted entry */
+ result = palloc_array(IndexTuple, *nentries);
+ for (i = 0; i < *nentries; i++)
+ {
+ values[0] = entries[i];
+ isnull[0] = nullFlags[i];
+ result[i] = gistFormTuple(giststate, index, values, isnull, true);
+ }
+
+ return result;
+}
+
/*
* This is a stratnum translation support function for GiST opclasses that use
* the RT*StrategyNumber constants.
diff --git a/src/backend/access/gist/gistvalidate.c b/src/backend/access/gist/gistvalidate.c
index 56feb8d8400..bffb048b1a9 100644
--- a/src/backend/access/gist/gistvalidate.c
+++ b/src/backend/access/gist/gistvalidate.c
@@ -144,6 +144,11 @@ gistvalidate(Oid opclassoid)
procform->amproclefttype == ANYOID &&
procform->amprocrighttype == ANYOID;
break;
+ case GIST_EXTRACTVALUE_PROC:
+ ok = check_amproc_signature(procform->amproc, INTERNALOID, true,
+ 3, 3, INTERNALOID, INTERNALOID,
+ INTERNALOID);
+ break;
default:
ereport(INFO,
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -265,7 +270,8 @@ gistvalidate(Oid opclassoid)
if (i == GIST_DISTANCE_PROC || i == GIST_FETCH_PROC ||
i == GIST_COMPRESS_PROC || i == GIST_DECOMPRESS_PROC ||
i == GIST_OPTIONS_PROC || i == GIST_SORTSUPPORT_PROC ||
- i == GIST_TRANSLATE_CMPTYPE_PROC)
+ i == GIST_TRANSLATE_CMPTYPE_PROC ||
+ i == GIST_EXTRACTVALUE_PROC)
continue; /* optional methods */
ereport(INFO,
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -337,6 +343,7 @@ gistadjustmembers(Oid opfamilyoid,
case GIST_OPTIONS_PROC:
case GIST_SORTSUPPORT_PROC:
case GIST_TRANSLATE_CMPTYPE_PROC:
+ case GIST_EXTRACTVALUE_PROC:
/* Optional, so force it to be a soft family dependency */
op->ref_is_hard = false;
op->ref_is_family = true;
diff --git a/src/include/access/gist.h b/src/include/access/gist.h
index 9b385b13a88..68f8eca550e 100644
--- a/src/include/access/gist.h
+++ b/src/include/access/gist.h
@@ -41,7 +41,8 @@
#define GIST_OPTIONS_PROC 10
#define GIST_SORTSUPPORT_PROC 11
#define GIST_TRANSLATE_CMPTYPE_PROC 12
-#define GISTNProcs 12
+#define GIST_EXTRACTVALUE_PROC 13
+#define GISTNProcs 13
/*
* Page opaque data in a GiST index page.
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
index 44514f1cb8d..5caf7a1956e 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -92,6 +92,7 @@ typedef struct GISTSTATE
FmgrInfo equalFn[INDEX_MAX_KEYS];
FmgrInfo distanceFn[INDEX_MAX_KEYS];
FmgrInfo fetchFn[INDEX_MAX_KEYS];
+ FmgrInfo extractValueFn[INDEX_MAX_KEYS];
/* Collations to pass to the support functions */
Oid supportCollation[INDEX_MAX_KEYS];
@@ -156,6 +157,14 @@ typedef struct GISTScanOpaqueData
GISTSTATE *giststate; /* index information, see above */
Oid *orderByTypes; /* datatypes of ORDER BY expressions */
+ /*
+ * For multi-entry indexes: hash table for TID deduplication. Each heap
+ * tuple produces multiple index entries, so we track which TIDs have been
+ * returned. NULL for standard (non-multi-entry) indexes.
+ */
+ struct gisttid_hash *tidHash;
+ MemoryContext tidHashCxt; /* context holding the hash table */
+
pairingheap *queue; /* queue of unvisited items */
MemoryContext queueCxt; /* context holding the queue */
bool qual_ok; /* false if qual can never be satisfied */
@@ -547,6 +556,11 @@ extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
extern IndexBuildResult *gistbuild(Relation heap, Relation index,
struct IndexInfo *indexInfo);
+/* gistutil.c */
+extern IndexTuple *gistExtractEntries(GISTSTATE *giststate, Relation index,
+ Datum *values, bool *isnull,
+ int32 *nentries);
+
/* gistbuildbuffers.c */
extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,
int maxLevel);
--
2.50.1 (Apple Git-155)
[application/octet-stream] v1-0002-Add-multirange_me_ops-GiST-opclass-using-multi-en.patch (52.7K, 3-v1-0002-Add-multirange_me_ops-GiST-opclass-using-multi-en.patch)
download | inline diff:
From 18f4cb4bd7af1c7d7763262a7465431cbde46379 Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <[email protected]>
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)
[application/octet-stream] v1-0003-Add-multi-entry-support-to-SP-GiST.patch (18.1K, 4-v1-0003-Add-multi-entry-support-to-SP-GiST.patch)
download | inline diff:
From f1377d894d5cf9c1feb56ad2e375fb041f6e2e0f Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <[email protected]>
Date: Fri, 3 Apr 2026 18:43:29 +0200
Subject: [PATCH v1 3/4] Add multi-entry support to SP-GiST
Extend SP-GiST to support an optional extractValue support function
(SPGIST_EXTRACTVALUE_PROC, number 8) that decomposes a single indexed
value into multiple sub-entries, each stored as a separate index entry.
This mirrors the multi-entry support previously added to GiST.
Infrastructure changes:
spgist.h: Define SPGIST_EXTRACTVALUE_PROC (8), bump SPGISTNProc to 8.
spgist_private.h: Add tidHash field to SpGistScanOpaqueData for TID
deduplication during multi-entry scans.
spginsert.c: Add spgExtractEntries() helper. Modify spgistBuildCallback
and spginsert to call extractValue and loop over the returned entries.
spgscan.c: Implement TID deduplication via simplehash to ensure each
heap TID is returned only once when multiple index entries match.
Handles both ordered and non-ordered scans. Bitmap scans rely on the
bitmap's inherent deduplication. Disable index-only scans for the key
column of multi-entry indexes since the stored entries don't represent
the original datum.
spgvalidate.c: Register extractValue as an optional support function.
Allow compress to be absent when extractValue is present (extractValue
handles the type conversion).
spgutils.c: Accept extractValue as an alternative to compress when
the leaf type differs from the input type.
---
src/backend/access/spgist/spginsert.c | 97 +++++++++++++---
src/backend/access/spgist/spgscan.c | 146 +++++++++++++++++++++---
src/backend/access/spgist/spgutils.c | 61 +++++++++-
src/backend/access/spgist/spgvalidate.c | 12 +-
src/include/access/spgist.h | 3 +-
src/include/access/spgist_private.h | 9 ++
6 files changed, 295 insertions(+), 33 deletions(-)
diff --git a/src/backend/access/spgist/spginsert.c b/src/backend/access/spgist/spginsert.c
index 780ef646a54..0e9e4e845c8 100644
--- a/src/backend/access/spgist/spginsert.c
+++ b/src/backend/access/spgist/spginsert.c
@@ -44,23 +44,60 @@ spgistBuildCallback(Relation index, ItemPointer tid, Datum *values,
SpGistBuildState *buildstate = (SpGistBuildState *) state;
MemoryContext oldCtx;
- /* Work in temp context, and reset it after each tuple */
- oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
-
/*
* Even though no concurrent insertions can be happening, we still might
* get a buffer-locking failure due to bgwriter or checkpointer taking a
* lock on some buffer. So we need to be willing to retry. We can flush
* any temp data when retrying.
+ *
+ * If the opclass provides an extractValue function, extract multiple
+ * entries and insert each one. Otherwise, insert a single entry.
+ *
+ * We extract entries in the caller's memory context so that the entries
+ * array survives MemoryContextReset(tmpCtx) in the retry loop.
*/
- while (!spgdoinsert(index, &buildstate->spgstate, tid,
- values, isnull))
+ if (OidIsValid(index_getprocid(index, 1, SPGIST_EXTRACTVALUE_PROC)))
{
- MemoryContextReset(buildstate->tmpCtx);
+ Datum *entries;
+ bool *nullFlags;
+ int32 nentries;
+ int i;
+
+ entries = spgExtractEntries(index, values[spgKeyColumn],
+ isnull[spgKeyColumn],
+ &nentries, &nullFlags);
+
+ oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
+
+ for (i = 0; i < nentries; i++)
+ {
+ values[spgKeyColumn] = entries[i];
+ isnull[spgKeyColumn] = nullFlags[i];
+
+ while (!spgdoinsert(index, &buildstate->spgstate, tid,
+ values, isnull))
+ {
+ MemoryContextReset(buildstate->tmpCtx);
+ }
+ }
+
+ /* Update total tuple count */
+ buildstate->indtuples += nentries;
}
+ else
+ {
+ /* Work in temp context, and reset it after each tuple */
+ oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
+
+ while (!spgdoinsert(index, &buildstate->spgstate, tid,
+ values, isnull))
+ {
+ MemoryContextReset(buildstate->tmpCtx);
+ }
- /* Update total tuple count */
- buildstate->indtuples += 1;
+ /* Update total tuple count */
+ buildstate->indtuples += 1;
+ }
MemoryContextSwitchTo(oldCtx);
MemoryContextReset(buildstate->tmpCtx);
@@ -193,20 +230,54 @@ spginsert(Relation index, Datum *values, bool *isnull,
insertCtx = AllocSetContextCreate(CurrentMemoryContext,
"SP-GiST insert temporary context",
ALLOCSET_DEFAULT_SIZES);
- oldCtx = MemoryContextSwitchTo(insertCtx);
-
- initSpGistState(&spgstate, index);
/*
* We might have to repeat spgdoinsert() multiple times, if conflicts
* occur with concurrent insertions. If so, reset the insertCtx each time
* to avoid cumulative memory consumption. That means we also have to
* redo initSpGistState(), but it's cheap enough not to matter.
+ *
+ * If the opclass provides an extractValue function, extract multiple
+ * entries and insert each one separately. We extract entries in the
+ * caller's memory context so that the entries array survives
+ * MemoryContextReset(insertCtx) in the retry loop.
*/
- while (!spgdoinsert(index, &spgstate, ht_ctid, values, isnull))
+ if (OidIsValid(index_getprocid(index, 1, SPGIST_EXTRACTVALUE_PROC)))
+ {
+ Datum *entries;
+ bool *nullFlags;
+ int32 nentries;
+ int i;
+
+ entries = spgExtractEntries(index, values[spgKeyColumn],
+ isnull[spgKeyColumn],
+ &nentries, &nullFlags);
+
+ oldCtx = MemoryContextSwitchTo(insertCtx);
+ initSpGistState(&spgstate, index);
+
+ for (i = 0; i < nentries; i++)
+ {
+ values[spgKeyColumn] = entries[i];
+ isnull[spgKeyColumn] = nullFlags[i];
+
+ while (!spgdoinsert(index, &spgstate, ht_ctid, values, isnull))
+ {
+ MemoryContextReset(insertCtx);
+ initSpGistState(&spgstate, index);
+ }
+ }
+ }
+ else
{
- MemoryContextReset(insertCtx);
+ oldCtx = MemoryContextSwitchTo(insertCtx);
initSpGistState(&spgstate, index);
+
+ while (!spgdoinsert(index, &spgstate, ht_ctid, values, isnull))
+ {
+ MemoryContextReset(insertCtx);
+ initSpGistState(&spgstate, index);
+ }
}
SpGistUpdateMetaPage(index);
diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c
index 2cc5f06f5d7..398a93a7dd9 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -18,6 +18,7 @@
#include "access/genam.h"
#include "access/relscan.h"
#include "access/spgist_private.h"
+#include "common/hashfn.h"
#include "executor/instrument_node.h"
#include "miscadmin.h"
#include "pgstat.h"
@@ -28,6 +29,49 @@
#include "utils/memutils.h"
#include "utils/rel.h"
+/*
+ * Simplehash implementation for TID deduplication in multi-entry scans.
+ *
+ * When an opclass provides an extractValue function, each heap tuple produces
+ * multiple index entries. During scans, we must deduplicate results so that
+ * each heap TID is returned only once.
+ */
+
+/* Hash table entry for basic TID dedup */
+typedef struct SPGTIDHashEntry
+{
+ ItemPointerData tid; /* TID (hashtable key) */
+ uint32 hash; /* hash value (cached) */
+ char status; /* hash status */
+} SPGTIDHashEntry;
+
+static inline uint32
+spg_tid_hash_fn(ItemPointerData tid)
+{
+ uint32 h = murmurhash32(ItemPointerGetBlockNumber(&tid));
+
+ return murmurhash32(h + ItemPointerGetOffsetNumber(&tid));
+}
+
+static inline bool
+spg_tid_match_fn(ItemPointerData a, ItemPointerData b)
+{
+ return ItemPointerEquals(&a, &b);
+}
+
+/* --- spgtid hash table (declare + define) --- */
+#define SH_PREFIX spgtid
+#define SH_ELEMENT_TYPE SPGTIDHashEntry
+#define SH_KEY_TYPE ItemPointerData
+#define SH_KEY tid
+#define SH_HASH_KEY(tb, key) spg_tid_hash_fn(key)
+#define SH_EQUAL(tb, a, b) spg_tid_match_fn(a, b)
+#define SH_SCOPE static inline
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
+
typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr,
Datum leafValue, bool isNull,
SpGistLeafTuple leafTuple, bool recheck,
@@ -158,6 +202,14 @@ resetSpGistScanOpaque(SpGistScanOpaque so)
MemoryContextReset(so->traversalCxt);
+ /*
+ * For multi-entry indexes, set up TID deduplication hash table. The hash
+ * table lives in traversalCxt and is destroyed/recreated on each rescan.
+ */
+ if (OidIsValid(index_getprocid(so->state.index, 1,
+ SPGIST_EXTRACTVALUE_PROC)))
+ so->tidHash = spgtid_create(so->traversalCxt, 256, NULL);
+
oldCtx = MemoryContextSwitchTo(so->traversalCxt);
/* initialize queue only for distance-ordered scans */
@@ -364,6 +416,9 @@ spgbeginscan(Relation rel, int keysz, int orderbysz)
index_getprocinfo(rel, 1, SPGIST_LEAF_CONSISTENT_PROC),
CurrentMemoryContext);
+ /* tidHash will be set up by resetSpGistScanOpaque if needed */
+ so->tidHash = NULL;
+
so->indexCollation = rel->rd_indcollation[0];
scan->opaque = so;
@@ -571,25 +626,53 @@ spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item,
{
/* the scan is ordered -> add the item to the queue */
MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt);
- SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
- leafTuple,
- leafValue,
- recheck,
- recheckDistances,
- isnull,
- distances);
-
- spgAddSearchItemToQueue(so, heapItem);
- MemoryContextSwitchTo(oldCxt);
+ /*
+ * For multi-entry ordered scans, skip leaf entries whose TIDs
+ * have already been returned by the ordered dequeue path. We
+ * use lookup (not insert) here: a TID must remain enqueueable
+ * until it is actually dequeued, so that the pairing heap can
+ * pick the copy with the smallest distance.
+ */
+ if (so->tidHash &&
+ spgtid_lookup(so->tidHash, leafTuple->heapPtr))
+ {
+ MemoryContextSwitchTo(oldCxt);
+ }
+ else
+ {
+ SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
+ leafTuple,
+ leafValue,
+ recheck,
+ recheckDistances,
+ isnull,
+ distances);
+
+ spgAddSearchItemToQueue(so, heapItem);
+ MemoryContextSwitchTo(oldCxt);
+ }
}
else
{
- /* non-ordered scan, so report the item right away */
- Assert(!recheckDistances);
- storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
- leafTuple, recheck, false, NULL);
- *reportedSome = true;
+ /*
+ * Non-ordered scan, so report the item right away.
+ *
+ * For multi-entry indexes, check the TID hash table to avoid
+ * returning duplicate heap TIDs.
+ */
+ bool found = false;
+
+ if (so->tidHash)
+ spgtid_insert(so->tidHash, leafTuple->heapPtr, &found);
+
+ if (!found)
+ {
+ Assert(!recheckDistances);
+ storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
+ leafTuple, recheck, false, NULL);
+ *reportedSome = true;
+ }
}
}
@@ -830,6 +913,25 @@ redirect:
{
/* We store heap items in the queue only in case of ordered search */
Assert(so->numberOfNonNullOrderBys > 0);
+
+ /*
+ * For multi-entry ordered scans, deduplicate using tidHash.
+ * The pairing heap ensures we see the smallest distance first;
+ * tidHash skips subsequent duplicates for the same TID.
+ */
+ if (so->tidHash)
+ {
+ bool found;
+
+ spgtid_insert(so->tidHash, item->heapPtr, &found);
+ if (found)
+ {
+ spgFreeSearchItem(so, item);
+ MemoryContextReset(so->tempCxt);
+ continue; /* already returned this TID */
+ }
+ }
+
storeRes(so, &item->heapPtr, item->value, item->isNull,
item->leafTuple, item->recheck,
item->recheckDistances, item->distances);
@@ -921,7 +1023,11 @@ redirect:
}
-/* storeRes subroutine for getbitmap case */
+/*
+ * storeRes subroutine for getbitmap case.
+ * The bitmap itself handles deduplication, so no extra work needed for
+ * multi-entry.
+ */
static void
storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
Datum leafValue, bool isnull,
@@ -1083,6 +1189,14 @@ spgcanreturn(Relation index, int attno)
if (attno > 1)
return true;
+ /*
+ * Multi-entry indexes store decomposed sub-entries in the key column,
+ * not the original datum, so the key column cannot be returned in an
+ * index-only scan.
+ */
+ if (OidIsValid(index_getprocid(index, 1, SPGIST_EXTRACTVALUE_PROC)))
+ return false;
+
/* We can do it if the opclass config function says so */
cache = spgGetCache(index);
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c
index f2ee333f60d..ce30d76e8f5 100644
--- a/src/backend/access/spgist/spgutils.c
+++ b/src/backend/access/spgist/spgutils.c
@@ -246,10 +246,11 @@ spgGetCache(Relation index)
if (cache->config.leafType != atttype)
{
- if (!OidIsValid(index_getprocid(index, 1, SPGIST_COMPRESS_PROC)))
+ if (!OidIsValid(index_getprocid(index, 1, SPGIST_COMPRESS_PROC)) &&
+ !OidIsValid(index_getprocid(index, 1, SPGIST_EXTRACTVALUE_PROC)))
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
- errmsg("compress method must be defined when leaf type is different from input type")));
+ errmsg("compress or extractValue method must be defined when leaf type is different from input type")));
fillTypeDesc(&cache->attLeafType, cache->config.leafType);
}
@@ -1365,3 +1366,59 @@ spgproperty(Oid index_oid, int attno,
return true;
}
+
+/*
+ * spgExtractEntries -- extract multiple index entries from one heap tuple.
+ *
+ * Calls the opclass's extractValue function to decompose the indexed datum
+ * into multiple sub-entries. Returns an array of Datum values and sets
+ * *nentries to the count. *nullFlags is set to a boolean array indicating
+ * which entries are NULL (or NULL if none are).
+ *
+ * If the datum is NULL or extractValue returns no entries, a single NULL
+ * entry is produced.
+ */
+Datum *
+spgExtractEntries(Relation index, Datum value, bool isnull,
+ int32 *nentries, bool **nullFlags)
+{
+ Datum *entries;
+
+ /* NULL datum produces a single NULL entry */
+ if (isnull)
+ {
+ *nentries = 1;
+ entries = palloc(sizeof(Datum));
+ entries[0] = (Datum) 0;
+ *nullFlags = palloc(sizeof(bool));
+ (*nullFlags)[0] = true;
+ return entries;
+ }
+
+ /* Call the opclass's extractValue function */
+ *nullFlags = NULL;
+ entries = (Datum *)
+ DatumGetPointer(FunctionCall3Coll(index_getprocinfo(index, 1,
+ SPGIST_EXTRACTVALUE_PROC),
+ index->rd_indcollation[0],
+ value,
+ PointerGetDatum(nentries),
+ PointerGetDatum(nullFlags)));
+
+ /* Handle empty or NULL result: produce a single NULL entry */
+ if (entries == NULL || *nentries <= 0)
+ {
+ *nentries = 1;
+ entries = palloc(sizeof(Datum));
+ entries[0] = (Datum) 0;
+ *nullFlags = palloc(sizeof(bool));
+ (*nullFlags)[0] = true;
+ return entries;
+ }
+
+ /* Create nullFlags array if the function didn't */
+ if (*nullFlags == NULL)
+ *nullFlags = palloc0_array(bool, *nentries);
+
+ return entries;
+}
diff --git a/src/backend/access/spgist/spgvalidate.c b/src/backend/access/spgist/spgvalidate.c
index 27c855921e6..34111058f24 100644
--- a/src/backend/access/spgist/spgvalidate.c
+++ b/src/backend/access/spgist/spgvalidate.c
@@ -175,6 +175,11 @@ spgvalidate(Oid opclassoid)
case SPGIST_OPTIONS_PROC:
ok = check_amoptsproc_signature(procform->amproc);
break;
+ case SPGIST_EXTRACTVALUE_PROC:
+ ok = check_amproc_signature(procform->amproc, INTERNALOID, true,
+ 3, 3, INTERNALOID, INTERNALOID,
+ INTERNALOID);
+ break;
default:
ereport(INFO,
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -287,8 +292,12 @@ spgvalidate(Oid opclassoid)
{
if ((thisgroup->functionset & (((uint64) 1) << i)) != 0)
continue; /* got it */
- if (i == SPGIST_OPTIONS_PROC)
+ if (i == SPGIST_OPTIONS_PROC ||
+ i == SPGIST_EXTRACTVALUE_PROC)
continue; /* optional method */
+ if (i == SPGIST_COMPRESS_PROC &&
+ (thisgroup->functionset & (((uint64) 1) << SPGIST_EXTRACTVALUE_PROC)) != 0)
+ continue; /* extractValue handles type conversion */
ereport(INFO,
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
errmsg("operator family \"%s\" of access method %s is missing support function %d for type %s",
@@ -367,6 +376,7 @@ spgadjustmembers(Oid opfamilyoid,
break;
case SPGIST_COMPRESS_PROC:
case SPGIST_OPTIONS_PROC:
+ case SPGIST_EXTRACTVALUE_PROC:
/* Optional, so force it to be a soft family dependency */
op->ref_is_hard = false;
op->ref_is_family = true;
diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h
index 083d93f8ffd..efa7aa2d63b 100644
--- a/src/include/access/spgist.h
+++ b/src/include/access/spgist.h
@@ -27,8 +27,9 @@
#define SPGIST_LEAF_CONSISTENT_PROC 5
#define SPGIST_COMPRESS_PROC 6
#define SPGIST_OPTIONS_PROC 7
+#define SPGIST_EXTRACTVALUE_PROC 8
#define SPGISTNRequiredProc 5
-#define SPGISTNProc 7
+#define SPGISTNProc 8
/*
* Argument structs for spg_config method
diff --git a/src/include/access/spgist_private.h b/src/include/access/spgist_private.h
index ec6d6f5f74d..f6e29acea8a 100644
--- a/src/include/access/spgist_private.h
+++ b/src/include/access/spgist_private.h
@@ -193,6 +193,13 @@ typedef struct SpGistScanOpaqueData
MemoryContext tempCxt; /* short-lived memory context */
MemoryContext traversalCxt; /* single scan lifetime memory context */
+ /*
+ * For multi-entry indexes: hash table for TID deduplication. Each heap
+ * tuple produces multiple index entries, so we track which TIDs have been
+ * returned. NULL for standard (non-multi-entry) indexes.
+ */
+ struct spgtid_hash *tidHash;
+
/* Control flags showing whether to search nulls and/or non-nulls */
bool searchNulls; /* scan matches (all) null entries */
bool searchNonNulls; /* scan matches (some) non-null entries */
@@ -532,6 +539,8 @@ extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page,
extern bool spgproperty(Oid index_oid, int attno,
IndexAMProperty prop, const char *propname,
bool *res, bool *isnull);
+extern Datum *spgExtractEntries(Relation index, Datum value, bool isnull,
+ int32 *nentries, bool **nullFlags);
/* spgdoinsert.c */
extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN,
--
2.50.1 (Apple Git-155)
[application/octet-stream] v1-0004-Add-multirange_me_ops-SP-GiST-opclass-using-multi.patch (54.1K, 5-v1-0004-Add-multirange_me_ops-SP-GiST-opclass-using-multi.patch)
download | inline diff:
From d6d2c121554a523b09e9f4698a200a71d934a9c1 Mon Sep 17 00:00:00 2001
From: Maxime Schoemans <[email protected]>
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, ¢roidLower, ¢roidUpper,
+ ¢roidEmpty);
+
+ 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,
+ ¢roidUpper,
+ 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,
+ ¢roidLower,
+ 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, ¢roidLower, minLower) <= 0)
+ which &= (1 << 1) | (1 << 2) | (1 << 5);
+ }
+ if (maxLower)
+ {
+ cmp = range_cmp_bounds(typcache, ¢roidLower, maxLower);
+ if (cmp > 0 || (!inclusive && cmp == 0))
+ which &= (1 << 3) | (1 << 4) | (1 << 5);
+ }
+ if (minUpper)
+ {
+ if (range_cmp_bounds(typcache, ¢roidUpper, minUpper) <= 0)
+ which &= (1 << 1) | (1 << 4) | (1 << 5);
+ }
+ if (maxUpper)
+ {
+ cmp = range_cmp_bounds(typcache, ¢roidUpper, 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)
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected]
Subject: Re: Multi-Entry Indexing for GiST & SP-GiST
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox