Improve GiST range-contained-by searches by adding a flag for empty ranges.
authorTom Lane <tgl@sss.pgh.pa.us>
Sun, 27 Nov 2011 21:50:37 +0000 (16:50 -0500)
committerTom Lane <tgl@sss.pgh.pa.us>
Sun, 27 Nov 2011 21:51:29 +0000 (16:51 -0500)
commitc66e4f138b04d749a713ad075e16f3d60975f5ad
tree6e784a8191049cb7583c3f2c9b3649bc2c8624a0
parent08da2d282f1c3cbff141ecd218d737990cf6d234
Improve GiST range-contained-by searches by adding a flag for empty ranges.

In the original implementation, a range-contained-by search had to scan
the entire index because an empty range could be lurking anywhere.
Improve that by adding a flag to upper GiST entries that says whether the
represented subtree contains any empty ranges.

Also, make a simple mod to the penalty function to discourage empty ranges
from getting pushed into subtrees without any.  This needs more work, and
the picksplit function should be taught about it too, but that code can be
improved without causing an on-disk compatibility break; so we'll leave it
for another day.

Since we're breaking on-disk compatibility of range values anyway, I took
the opportunity to reorganize the range flags bits; the unused
RANGE_xB_NULL bits are now adjacent, which might open the door for using
them in some other way later.

In passing, remove the GiST range opclass entry for <>, which doesn't seem
like it can really be indexed usefully.

Alexander Korotkov, with some editorializing by Tom
src/backend/utils/adt/rangetypes.c
src/backend/utils/adt/rangetypes_gist.c
src/include/catalog/catversion.h
src/include/catalog/pg_amop.h
src/include/utils/rangetypes.h
src/test/regress/expected/opr_sanity.out