Re: Covering GiST indexes

Hi, Andrey!

On Thu, Apr 12, 2018 at 2:00 PM, Andrey Borodin <x4mmm(at)yandex-team(dot)ru>
wrote:

> Looks like we finally have covering indexes! And that's cool!
>

Thank you!

So I decided to create a thread to discuss covering GiST indexes.
> Here's a prototype patch implementing this functionality.
> It is quite small (+80 -30) and lacks tests and docs. But it creates a
> context.
>
> I have two concerns.
> First one is about INDEX_AM_RESERVED_BIT.
> B-tree uses it as a base for prefix truncation (I'm not quite sure why it
> is usually called suffix truncation, but this is a matter for other thread).
> GiST , probably, will not use [pre\su]fix truncation. But I'd like to use
> that 13th bit to implement intra-page indexing - a way to improve search
> within gist page. See [0,1]
>

I also think that GiST isn't going to do suffix truncation of keys, because
GiST
is composing keys for every attribute and trying to use them in queries if
even GiST didn't use those attributes in any split. Depending on data
distribution,
key representation, query and so on that keys may appear useful or not.
And GiST doesn't have any legal interface to determine that in advance.

I think that GiST needs another feature: not suffix truncation, but
different
attribute representation in leaf pages and internal pages. For example,
now GiST on points stores boxes in leafs. That's a great waste of space.
So, we might just have different tuple descriptors for internal and leaf
pages of GiST, which could have both different attribute types and
different counts of attributes. Thankfully GiST pages don't have high keys
and we don't have to mix tuples of different types on the same page
(unlike B-tree).

Second, currently including indexes do not allow same attributes in both
> keys and include parts.
> # create index on x using gist(c) include (c);
> ERROR: included columns must not intersect with key columns
>
> But it makes sense for example for geometries like PostGIS. Index keys are
> truncated to small MBRs while having whole complex geometry right in an
> index could be handy.
>

The issue discovered in [1] seems to be related. Thus, after fix provided
there when
column is indexed without index-only scan support, then it can't be used in
index-only
scan anyway (if even it's indexed another time with index-only scan
support).
So, I think we need a better fix for [1] first.

Another thing that could be done for PostGIS geometries is just another
opclass which
stores geometries "as is" in leafs. As I know, geometries contain MBRs
inside their
own, so there is no need to store extra MBR. I think the reason why PostGIS
doesn't have such opclass yet is that geometries are frequently large and
easily
can exceed maximum size of index tuple. The same problem applies to
coverting
indexes too. Possible solution here might be to support external toasted
attributes
in covering indexes. But I think that still requires quite amount of work.

1.
https://www.postgresql.org/message-id/1516210494.1798.16.camel%40nlpgo.com

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company