Multi-Entry Indexing for GiST & SP-GiST: Deep Technical Analysis

Core Problem

PostgreSQL's GiST (Generalized Search Tree) and SP-GiST (Space-Partitioned GiST) access methods fundamentally assume a one-to-one mapping between heap tuples and index entries. This constraint becomes a severe performance liability for composite data types like multiranges, where the indexed value has internal structure that is lost when compressed into a single bounding representation.

The Multirange Bounding Box Problem

The current GiST multirange_ops opclass handles multiranges by computing their bounding union range — collapsing a multirange like {[1,10), [100000,100010)} into a single range [1, 100010). This bounding box is stored as the index key. The fundamental issue is that this bounding representation loses all information about gaps between component ranges.

For containment operators (@>, <@), this gap information is critical. A query like mr @> 100000 must check whether 100000 falls within any component range. The bounding box [1, 100010) trivially contains 100000, so the index returns a match — but the actual multirange has a gap from 10 to 100000, making it a false positive. In the benchmark scenario with 100k rows, this results in 99,990 false-positive heap rechecks, making the index scan slower than a sequential scan.

SP-GiST has an even more fundamental limitation: it has no multirange opclass at all, because its quad-tree partitioning scheme has no natural way to handle a composite range value.

Architectural Significance

This problem generalizes beyond multiranges. Any composite data type that can be meaningfully decomposed — arrays of geometric points, route geometries (polylines decomposed into segments), temporal data with gaps — suffers the same bounding-box information loss in GiST. The solution establishes infrastructure for a whole class of future opclasses.

Proposed Solution: Multi-Entry Decomposition

The patch introduces an optional extractValue support function (mirroring GIN's approach) that decomposes a single datum into multiple index entries, each pointing back to the same heap TID. This gives GiST and SP-GiST the decomposition capability that GIN has always had, but within the R-tree and quad-tree frameworks that support range queries and KNN ordering.

Key Design Decisions

1. extractValue as Optional Support Function

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

• GiST: Registered as proc 13
• SP-GiST: Registered as proc 8

The function is entirely optional; existing opclasses are completely unaffected. This is a crucial backward-compatibility decision — it means zero risk to existing installations and a clean upgrade path.

2. TID Deduplication via simplehash

Since one heap tuple now produces N index entries, scans must deduplicate results. The implementation uses PostgreSQL's simplehash infrastructure to maintain a TID hash during scanning. This is the same approach used in other parts of the executor and provides O(1) amortized lookup.

For ordered (KNN) scans, the design is more nuanced: the TID hash is consulted as an early filter before enqueuing leaf items into the pairing heap, but the actual dedup insertion happens at dequeue time. This ensures the pairing heap can correctly select the copy with the smallest distance — if you deduplicated at enqueue time, you might keep a farther copy and discard a nearer one that arrives later during tree traversal.

3. Separate Opclass (multirange_me_ops)

Rather than modifying the existing multirange_ops, a new multirange_me_ops opclass is introduced. This is necessary because:

• Leaf consistent functions see individual sub-entries (component ranges), not the full multirange
• The semantics of consistency checking change fundamentally
• Strategies like OVERLAPS and CONTAINS_ELEM are exact per-component (no recheck needed)
• Strategies like CONTAINS and EQ must set recheck=true because no single component proves containment of the full query

The new opclass is marked non-default, so users must explicitly request it via USING gist (col multirange_me_ops).

4. Internal Node Descent Strategy Relaxation

This is perhaps the most subtle design aspect. In a standard GiST, internal node keys represent bounding unions of their subtree's entries. With multi-entry indexing, a single multirange's components may be scattered across multiple subtrees.

For containment strategies (CONTAINS, EQ), the consistent function at internal nodes must relax to OVERLAPS during descent. If it required the union key to fully contain the query, it could incorrectly prune subtrees that contain some (but not all) components of a matching multirange. Since rechecks happen at the leaf/heap level anyway, this relaxation is safe — it may visit extra subtrees but won't miss valid results.

5. SP-GiST: compress Made Optional

When extractValue is present, the compress function becomes optional for SP-GiST. This is because extractValue directly produces leaf-typed values — for multiranges, it outputs individual ranges that can be fed directly into the existing range quad-tree. The leafType can differ from the input type (e.g., anymultirange → anyrange), enabling elegant type-level decomposition.

6. Single-Column Restriction

Multi-entry indexing is restricted to single-key-column indexes (INCLUDE columns are permitted). This simplifies the initial implementation significantly — multi-column support would require defining semantics for how decomposition interacts with composite index keys, which can be addressed in a future patch.

7. Index-Only Scans Disabled

Since stored sub-entries don't represent the original datum, index-only scans cannot return the correct value from the index alone. This is an inherent limitation of the decomposition approach (GIN has the same constraint).

Empty Multirange Handling

A notable edge case: when extractValue returns zero entries for a non-NULL input, the AM falls back to storing a single NULL index entry (matchable only by IS NULL). However, for multirange semantics, an empty multirange should still be findable by operator queries (e.g., an empty multirange is contained by everything). The opclass handles this by returning an empty range sentinel instead of zero entries, keeping the value visible to operator scans.

Performance Implications

The benchmark demonstrates the extreme case:

The multi-entry approach is ~170x faster than the standard GiST opclass and ~138x faster than sequential scan. The buffer count (6 vs 2311) shows the dramatic I/O reduction.

The tradeoff is index size: storing N entries per multirange means the index is roughly N times larger than a standard GiST index. For multiranges with many components, this could be significant. However, for the common case of multiranges with a small number of wide-gap components, the tradeoff strongly favors multi-entry.

Relationship to GIN

This work fills a design-space gap in PostgreSQL's index AM taxonomy:

• GIN: Decomposition + inverted index (exact match on keys, posting lists for TIDs)
• GiST multi-entry: Decomposition + R-tree (range/spatial queries, KNN ordering)
• SP-GiST multi-entry: Decomposition + quad-tree (range queries, space partitioning)

GIN cannot support KNN or efficient range-overlap queries on decomposed components. GiST/SP-GiST multi-entry enables decomposition while preserving the spatial/range query capabilities of these AMs.

Open Questions and Future Work

1. Multi-column support: Currently restricted; semantics need definition for how decomposition interacts with composite keys
2. Index size management: No discussion yet of compression or deduplication strategies for the enlarged indexes
3. VACUUM/HOT implications: Multiple index entries per heap tuple affect HOT chain eligibility and vacuum costs
4. Parallel build: Whether the multi-entry path works correctly with parallel GiST build
5. Generalization to other types: Arrays of geometric types, PostGIS geometries, etc.