From: Maxime Schoemans <maxime.schoemans@enterprisedb.com>
Content-Type: text/plain;
	charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3864.500.181\))
Subject: Multi-Entry Indexing for GiST & SP-GiST
Message-Id: <8E23543E-F1E4-40AE-BDA0-8A5BEA7DADA1@enterprisedb.com>
Date: Wed, 20 May 2026 10:44:52 -0700
To: pgsql-hackers@lists.postgresql.org
Archived-At: 
 <https://www.postgresql.org/message-id/8E23543E-F1E4-40AE-BDA0-8A5BEA7DADA1%40enterprisedb.com>
Precedence: bulk

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=3Dtrue.  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-en=
try-generalized-search-trees/

--
Maxime Schoemans=