Re: GiST range-contained-by searches versus empty ranges

Alexander Korotkov <aekorotkov@gmail.com> writes:
>> The first solution that comes to mind is to make the penalty and
>> picksplit functions forcibly segregate empty ranges from others, that is
>> a split will never put empty ranges together with non-empty ones.

> Have you seen my patch about GiST for range types?
> https://commitfest.postgresql.org/action/patch_view?id=682
> There mentioned problem is solved by introduction of RANGE_CONTAIN_EMPTY
> bit in range flags. This bit is only used in GiST index and means that
> there are underlying empty ranges.

Yeah, I had been coming around to the idea that we'd need some kluge
like that.  The forcible-segregation idea falls apart as soon as you
start thinking about multiple-column indexes --- if you have several
columns each demanding to segregate a certain kind of data, you can
easily overrun the space available in the root page, whereupon it's no
longer possible to guarantee anything about the contents of child
pages.

I think this is a "must fix" for 9.2, because once we release it will
be too late to do anything without invalidating existing indexes.
        regards, tom lane