Thread

Multi-Entry Indexing for GiST & SP-GiST

Maxime Schoemans <maxime.schoemans@enterprisedb.com> — 2026-05-20T17:44:52Z

Hi hackers,

This patch set adds multi-entry support to the GiST and SP-GiST access
methods, allowing a single heap tuple to produce multiple index entries --
similar to how GIN decomposes values via extractValue, but within the
R-tree (GiST) and quad-tree (SP-GiST) frameworks.

I presented the concept and an extension-based prototype (MEST) at
PGConf.dev 2024 [1]. This patch set integrates the feature directly into
the GiST and SP-GiST access methods rather than maintaining a separate
forked AM.

Motivation
----------

The existing GiST multirange opclass compresses a multirange into its
bounding union range, losing information about gaps. This makes operators
like @> and <@ imprecise at the index level, requiring many false-positive
rechecks. Multi-entry GiST instead stores each component range as a
separate index entry, giving the R-tree much tighter bounds and
significantly reducing rechecks for multiranges with gaps.

SP-GiST currently has no multirange opclass at all. The multi-entry
infrastructure lets us add one: multiranges are decomposed into component
ranges and indexed using the existing range quad-tree, providing SP-GiST
multirange support for the first time.

The approach generalizes beyond multiranges: any composite data type that
can be meaningfully decomposed into simpler sub-entries can benefit (e.g.,
arrays of geometric types, route geometries).

Design
------

A new optional support function, extractValue, is added to both GiST
(proc 13) and SP-GiST (proc 8). When an opclass provides it, the insert
and build paths call it to decompose each datum into multiple sub-entries,
each stored as a separate index tuple pointing to the same heap TID.
The signature mirrors GIN's:

Datum *extractValue(Datum value, int32 *nentries, bool **nullFlags)

The opclass returns a palloc'd array of sub-entries (typed as the index
key column's type), sets *nentries, and optionally fills *nullFlags.
If it returns zero entries for a non-NULL input, the AM falls back to a
single NULL index entry (matching only IS NULL); opclasses that want
such values to remain visible to operator queries should return a
sentinel instead -- e.g., multirange_me_ops stores an empty range for
empty multiranges.

On the scan side, a simplehash-based TID hash deduplicates results so
each heap tuple is returned only once. For ordered (KNN) scans the
same hash is also consulted before enqueuing leaf items as an early
filter, but the dedup insert happens at dequeue time so the pairing
heap can pick the copy with the smallest distance.

Semantics for the opclass author:

- Leaf consistent functions see one sub-entry at a time, not the full
value, so most strategies must set recheck=true. Strategies that
are exact per-component (for multiranges: OVERLAPS and
CONTAINS_ELEM) can skip it.

- Internal-node keys are unions of sub-entries drawn from many heap
tuples, so containment-style strategies (CONTAINS, EQ) must relax
to OVERLAPS during descent: a matching value's components may live
in multiple subtrees, and requiring the union key to fully contain
the query would prune valid ones.

Other design decisions:

- extractValue is fully optional; existing opclasses are unaffected.
- Multi-entry is restricted to single-key-column indexes (INCLUDE
columns are fine); multi-column support can be added later.
- Index-only scans are disabled on a multi-entry key column, since
the stored sub-entries do not represent the original datum.
- For SP-GiST, compress becomes optional when extractValue is present:
extractValue produces the leaf-typed values directly, and leafType
may differ from the input type (e.g., anymultirange -> anyrange).
- Since leaf consistent functions see components, a separate opclass
(multirange_me_ops) is provided alongside the existing multirange_ops.

Patch overview
--------------

0001 - GiST AM infrastructure (gist.h, gist_private.h, gist.c,
gistbuild.c, gistget.c, gistscan.c, gistutil.c, gistvalidate.c): new
extractValue support function (proc 13), multi-entry insert/build paths,
TID deduplication during scans using simplehash.

0002 - Built-in GiST multirange_me_ops opclass (rangetypes_gist.c, catalog
files): decomposes multiranges into component ranges, with multi-entry
consistent functions. Empty multiranges are stored as empty range
sentinels to remain visible to operator queries. Regression tests verify
index correctness against sequential scan results for all operators across
index scan and bitmap scan, including empty range/multirange edge cases,
multi-column restriction, and NULL handling.

0003 - SP-GiST AM infrastructure (spgist.h, spgist_private.h, spginsert.c,
spgscan.c, spgvalidate.c, spgutils.c): new extractValue support function
(proc 8), multi-entry insert/build paths, TID deduplication during scans
using simplehash, compress made optional when extractValue is present.

0004 - Built-in SP-GiST multirange_me_ops opclass (rangetypes_spgist.c,
catalog files): reuses the range quad-tree structure with new config,
inner consistent, and leaf consistent functions that handle range,
multirange, and element query types. Marked non-default, consistent
with the GiST multirange_me_ops. Regression tests verify index
correctness against sequential scan results for all operators across
index scan and bitmap scan.

Quick benchmark
---------------

100k multiranges with wide gaps: {[g, g+10), [g+100000, g+100010)}.
Query: mr @> 100000 (matches 10 rows; value falls in the gap for most).

CREATE TABLE bench_mr (mr int4multirange);
INSERT INTO bench_mr
SELECT int4multirange(int4range(g, g+10), int4range(g+100000, g+100010))
FROM generate_series(1, 100000) g;

Method Exec time Buffers Recheck
Sequential scan 7.732 ms 834 -
GiST multirange_ops (std) 9.504 ms 2311 99990
GiST multirange_me_ops 0.056 ms 6 0
SP-GiST multirange_me_ops 0.112 ms 27 0

This is a worst case for the standard opclass: the wide gap between
components produces a bounding range [g, g+100010) that covers the query
point for nearly every row, requiring 99990 heap rechecks and making it
slower than a sequential scan. Multi-entry indexes store each component
range separately, eliminating all false positives. The improvement grows
with gap width; for multiranges with little or no gap the standard
opclass performs comparably.

[1] https://www.pgevents.ca/events/pgconfdev2024/schedule/session/171-multi-entry-generalized-search-trees/

--
Maxime Schoemans

Re: Multi-Entry Indexing for GiST & SP-GiST

Maxime Schoemans <maxime.schoemans@enterprisedb.com> — 2026-05-21T17:34:14Z
```
This time with the patches attached.

Best,
Maxime
```

Re: Multi-Entry Indexing for GiST & SP-GiST

Andrey Borodin <x4mmm@yandex-team.ru> — 2026-05-31T18:27:12Z

> On 21 May 2026, at 22:34, Maxime Schoemans <maxime.schoemans@enterprisedb.com> wrote:
> 
> patches attached

Hi Maxime,

I have been reading through the patch set.  I will focus on the GiST side
here - I know the SP-GiST internals far less well. So I would rather
discuss the architecture where I can actually be useful.

Skipping dedup for non-duplicated entries
------------------------------------------

On the scan path, once an opclass has extractValue, every leaf entry
goes through the TID hash even when the indexed value produced a single
sub-entry and therefore cannot collide.  GiST scans are CPU-bound (we
examine every tuple on the page and run consistent on each), so this
probe lands on the hot path rather than being hidden behind I/O.

Since multi-entry is gated on a new, non-default opclass, no existing
index takes this path, so the leaf format for these opclasses is
effectively new and free to extend. INDEX_AM_RESERVED_BIT (0x2000 in
t_info) is reserved for exactly such stuff and is currently unused anywhere
in the backend. We could set it at insert/build time only when extractValue
returns nentries > 1, and skip the hash on scan for entries without the
bit; the hash then grows only with genuinely multiplied TIDs.  I am not
proposing it as a must, just noting the format is new enough to allow it.

One related concern: I am not a big fan of the single-key-column
restriction. Features like this should be orthogonal to the rest of the
AM, and "throws an error on more than one column" tends to calcify into a
permanent limitation rather than a temporary one.

BTW sorting build ignores extract_value. But that's kinda not important at
current stage.

extractValue == new compress
----------------------------

What strikes me in the catalog is that multirange_me_ops drops the
compress support proc (3) and adds extractValue (13), while multirange_ops
is the reverse. So extractValue already supplants compress here: it emits
leaf-typed values directly. Conceptually compress is just extractValue
constrained to nentries == 1, and the SP-GiST side already makes compress
optional when extractValue is present, which points at the same overlap.

Was unifying the two considered, rather than carrying two parallel
support procs?  For example a single "produce leaf entries" entry point,
with a 1->1 shim over compress for the existing opclasses. That would
keep the insert/build path single rather than branching on whether
extractValue exists, and it would frame multi-entry as a generalization
of what compress already does rather than a parallel mechanism.

Is this useful to PostGIS?
--------------------------

The motivation that matters most to me is whether the real heavy users of
GiST will adopt this. Multiranges are a fairly narrow audience on their
own; the compelling case is multi-part geometries (MultiPolygon with
holes, routes, regions with exclaves), which is PostGIS territory.

I am adding Darafei and Paul to CC - it would be very helpful to
hear whether PostGIS would actually use extractValue in their GiST
opclasses, and whether the single-column restriction or the per-entry
dedup cost would be a problem in practice for them. If the GIS side is
on board, the feature is clearly worth itю If not, it is worth knowing
that when designing the AM-level machinery.

Best regards, Andrey Borodin.