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

Hi Andrey, hi Matthias,

Thank you both for the reviews. A lot of the points overlap, so I'm
answering both here and grouping by topic instead of by message. v2 is
attached, with the changes I describe below. The first four patches are
the proposal. The last two are a separate suggestion for the sorted build,
which I'd be happy to drop if you'd rather leave it for later.

-- Multi-entry in core vs. a specialized AM

Matthias:
> I'm not sure this is preferable over a specialized AM (comparable to
> what GIN is to btree), but cool!

The prototype I presented at PGConf.dev 2024 (MEST) was a separate forked
AM, so I did start there. The trouble is that multi-entry as it stands adds
no new on-disk structure. It reuses the existing GiST R-tree (and SP-GiST
quad-tree) unchanged and just feeds it decomposed entries, so a separate AM
would duplicate almost all of GiST/SP-GiST with little of its own. GIN can
justify its own AM because it adds posting lists on top of a btree.
Multi-entry could grow something comparable one day (merging near-duplicate
entries, with recheck), but that is a much larger change and nothing here
needs it. extractValue as an optional support proc reuses all the existing
machinery, is opt-in per opclass, and costs existing opclasses nothing.

Moving it into core also helps adoption. Heavy GiST users like PostGIS are
more likely to add an extractValue function to their opclasses than to
depend on an out-of-tree AM.

-- extractValue vs. compress

Andrey:
> Conceptually compress is just extractValue constrained to nentries == 1
> [...] Was unifying the two considered, rather than carrying two parallel
> support procs?

Matthias:
> I don't think it's generally safe to remove compression even when
> extractValue is present.

Two reasons I kept them separate.

First, unifying them would mean changing compress's signature, which is
strictly 1->1 in both AMs (GiST GISTENTRY* -> GISTENTRY*, SP-GiST input
-> leaf), so every existing opclass with a compress function would break.

Second, they do two different jobs and they compose. extractValue splits a
value into leaf entries, and compress decides how each one is stored. When
an opclass has both, the insert/build path runs every extracted entry
through the normal tuple-forming path, so compress still runs per entry and
is not dropped when present (Matthias). We only omit it when the split
already produces leaf-typed values, as multirange_me_ops does. It returns
ranges directly, so there is nothing for compress to do. An opclass that
wanted both could decompose with extractValue and compress each part. A
GeometryCollection opclass, for example, could have extractValue return the
member geometries, and compress reduce each one to its bounding box for
storage.

-- TID deduplication and scan memory

Matthias:
> Could you help me understand how this deduplication works? Wouldn't
> this possibly use ~ unbounded memory [...]? [...] we can't use lossy
> checks for amgettuple() without losing correctness

Andrey:
> [...] set INDEX_AM_RESERVED_BIT [...] only when extractValue returns
> nentries > 1, and skip the hash on scan for entries without the bit

For bitmap scans there is no extra memory, the TID bitmap deduplicates on
its own. The hash is only used for amgettuple (plain and KNN ordered
scans), and you are right that it cannot go lossy without breaking
amgettuple, so the GIN trick does not carry over.

Two things keep it bounded. v2 adopts Andrey's reserved-bit idea, so the
hash only ever holds TIDs that extractValue actually multiplied (the bit is
set only when nentries > 1), and single-entry values skip it entirely. And
the planner only chooses amgettuple when it expects few matching rows. A
query that would return many rows gets a bitmap scan instead, where the TID
bitmap deduplicates for free, so the hash only grows when the result is
already expected to be small. As Andrey said, for practical scans this
should not be a concern.

For the worst case there are ways to bound it, like Andrey's suggestion of
spilling to a unique tuplestore once the hash goes over work_mem. v2 does
not do this yet. Matthias, are you thinking along those lines, or did you
have another idea in mind? And does it need handling before this goes in,
or is it fine as a follow-up?

-- Index-only scans

Matthias:
> [Index-only scans are disabled on a multi-entry key column.] How is
> this done? Surely it's not through a planner check of GiST opclasses?

No planner check. It's amcanreturn (gistcanreturn), which returns false
for a key column that has an extractValue proc, since the stored
sub-entries don't represent the original datum. INCLUDE columns stay
returnable.

-- Single-key-column restriction

Andrey:
> I am not a big fan of the single-key-column restriction [...] "throws an
> error on more than one column" tends to calcify into a permanent
> limitation

Fair point. The restriction is not fundamental, I just wanted to keep the
first version simple. v2 lifts it. It allows several key columns as long
as only one of them has extractValue, and duplicates the other key
columns across the extracted entries the same way we already do for
INCLUDE columns. The one thing to watch is that this can make the index
much larger, since every extracted entry then carries a copy of the other
columns. That is already true for INCLUDE columns today.

-- Sorted build

Andrey:
> BTW sorting build ignores extract_value.

You're right, and it was latent, the sorted path is only chosen when every
key column has sortsupport, which the multirange opclasses don't, so it
isn't reached today. To stop it biting a future opclass that has both, in
v2 the main GiST patch (0001) refuses the sorted path when extractValue is
present rather than silently building a single-entry index.

Patches 0005 and 0006 are a possible implementation of the real support,
sent as a separate suggestion. 0005 lets tuplesort_putindextuplevalues set
the reserved bit so it survives the sort, and 0006 makes the sorted build
call extractValue. The bit has to ride through the sort because, unlike
btree posting lists, a heap tuple's entries are scattered by key and can't
be regrouped afterwards. No in-core opclass has both procs, so the tests
don't reach this, but I checked it by hand by giving multirange_me_ops a
range sortsupport and comparing scans against a sequential scan.

Worth carrying these two, or better left for later?

-- PostGIS

Andrey:
> the compelling case is multi-part geometries (MultiPolygon with holes,
> routes, regions with exclaves) [...] I am adding Darafei and Paul to CC

Agreed, I expect PostGIS geometries could be a good case for multi-entry.

Darafei, Paul: do you know specific cases where it would help? I'm
thinking of things like multi-polygons whose parts are far apart, or long
linestrings, where the single bounding box ends up very loose. But you
would know far better than me where that actually comes up in practice.

Regards,
Maxime