*** a/src/backend/utils/adt/Makefile --- b/src/backend/utils/adt/Makefile *************** *** 30,36 **** OBJS = acl.o arrayfuncs.o array_selfuncs.o array_typanalyze.o \ tsginidx.o tsgistidx.o tsquery.o tsquery_cleanup.o tsquery_gist.o \ tsquery_op.o tsquery_rewrite.o tsquery_util.o tsrank.o \ tsvector.o tsvector_op.o tsvector_parser.o \ ! txid.o uuid.o windowfuncs.o xml.o like.o: like.c like_match.c --- 30,37 ---- tsginidx.o tsgistidx.o tsquery.o tsquery_cleanup.o tsquery_gist.o \ tsquery_op.o tsquery_rewrite.o tsquery_util.o tsrank.o \ tsvector.o tsvector_op.o tsvector_parser.o \ ! txid.o uuid.o windowfuncs.o xml.o rangetypes_gist2.o \ ! rangetypes_spgist.o rangetypes_spgistkd.o like.o: like.c like_match.c *** a/src/backend/utils/adt/rangetypes.c --- b/src/backend/utils/adt/rangetypes.c *************** *** 40,60 **** #include "utils/rangetypes.h" #include "utils/timestamp.h" - - #define RANGE_EMPTY_LITERAL "empty" - - /* fn_extra cache entry for one of the range I/O functions */ - typedef struct RangeIOData - { - TypeCacheEntry *typcache; /* range type's typcache entry */ - Oid typiofunc; /* element type's I/O function */ - Oid typioparam; /* element type's I/O parameter */ - FmgrInfo proc; /* lookup result for typiofunc */ - } RangeIOData; - - - static RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, - IOFuncSelector func); static char range_parse_flags(const char *flags_str); static void range_parse(const char *input_str, char *flags, char **lbound_str, char **ubound_str); --- 40,45 ---- *************** *** 62,76 **** static const char *range_parse_bound(const char *string, const char *ptr, char **bound_str, bool *infinite); static char *range_deparse(char flags, const char *lbound_str, const char *ubound_str); - static char *range_bound_escape(const char *value); static bool range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2); static bool range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val); - static Size datum_compute_size(Size sz, Datum datum, bool typbyval, - char typalign, int16 typlen, char typstorage); - static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval, - char typalign, int16 typlen, char typstorage); /* --- 47,56 ---- *************** *** 292,298 **** range_send(PG_FUNCTION_ARGS) * functions, so they store a RangeIOData struct in fn_extra, not just a * pointer to a type cache entry. */ ! static RangeIOData * get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, IOFuncSelector func) { RangeIOData *cache = (RangeIOData *) fcinfo->flinfo->fn_extra; --- 272,278 ---- * functions, so they store a RangeIOData struct in fn_extra, not just a * pointer to a type cache entry. */ ! RangeIOData * get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, IOFuncSelector func) { RangeIOData *cache = (RangeIOData *) fcinfo->flinfo->fn_extra; *************** *** 2103,2109 **** range_deparse(char flags, const char *lbound_str, const char *ubound_str) * * Result is a palloc'd string */ ! static char * range_bound_escape(const char *value) { bool nq; --- 2083,2089 ---- * * Result is a palloc'd string */ ! char * range_bound_escape(const char *value) { bool nq; *************** *** 2238,2244 **** range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val) * Increment data_length by the space needed by the datum, including any * preceding alignment padding. */ ! static Size datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign, int16 typlen, char typstorage) { --- 2218,2224 ---- * Increment data_length by the space needed by the datum, including any * preceding alignment padding. */ ! Size datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign, int16 typlen, char typstorage) { *************** *** 2264,2270 **** datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign, * Write the given datum beginning at ptr (after advancing to correct * alignment, if needed). Return the pointer incremented by space used. */ ! static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval, char typalign, int16 typlen, char typstorage) { --- 2244,2250 ---- * Write the given datum beginning at ptr (after advancing to correct * alignment, if needed). Return the pointer incremented by space used. */ ! Pointer datum_write(Pointer ptr, Datum datum, bool typbyval, char typalign, int16 typlen, char typstorage) { *** a/src/backend/utils/adt/rangetypes_gist.c --- b/src/backend/utils/adt/rangetypes_gist.c *************** *** 20,39 **** #include "utils/datum.h" #include "utils/rangetypes.h" - - /* Operator strategy numbers used in the GiST range opclass */ - /* Numbers are chosen to match up operator names with existing usages */ - #define RANGESTRAT_BEFORE 1 - #define RANGESTRAT_OVERLEFT 2 - #define RANGESTRAT_OVERLAPS 3 - #define RANGESTRAT_OVERRIGHT 4 - #define RANGESTRAT_AFTER 5 - #define RANGESTRAT_ADJACENT 6 - #define RANGESTRAT_CONTAINS 7 - #define RANGESTRAT_CONTAINED_BY 8 - #define RANGESTRAT_CONTAINS_ELEM 16 - #define RANGESTRAT_EQ 18 - /* * Range class properties used to segregate different classes of ranges in * GiST. Each unique combination of properties is a class. CLS_EMPTY cannot --- 20,25 ---- *************** *** 792,798 **** range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2) * part of the relcache entry for the index, typically) this essentially * eliminates lookup overhead during operations on a GiST range index. */ ! static Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2) { FunctionCallInfoData fcinfo; --- 778,784 ---- * part of the relcache entry for the index, typically) this essentially * eliminates lookup overhead during operations on a GiST range index. */ ! Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2) { FunctionCallInfoData fcinfo; *** /dev/null --- b/src/backend/utils/adt/rangetypes_gist2.c *************** *** 0 **** --- 1,1597 ---- + /*------------------------------------------------------------------------- + * + * rangetypes_gist2.c + * GiST support for range types based on mapping range to 2d-space. + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * src/backend/utils/adt/rangetypes_gist2.c + * + *------------------------------------------------------------------------- + */ + #include "postgres.h" + + #include "access/gist.h" + #include "access/tupmacs.h" + #include "access/skey.h" + #include "utils/builtins.h" + #include "utils/datum.h" + #include "utils/rangetypes.h" + + /* Flags for GiST key representation */ + #define RANGE_GIST_KEY_EMPTY 0x0001 /* all ranges in subtree are + * empty */ + #define RANGE_GIST_KEY_CONTAIN_EMPTY 0x0002 /* subtree may contain some + * empty ranges */ + #define RANGE_GIST_KEY_LEAF 0x0004 /* key are in short + * representation for leaf + * pages: single values for + * both lower and upper bounds */ + #define RANGE_GIST_KEY_LOWER_MIN_INC 0x0008 /* minimum value of lower + * bound in subtree is + * inclusive */ + #define RANGE_GIST_KEY_LOWER_MIN_INF 0x0010 /* minimum value of lower + * bound in subtree is + * infinite */ + #define RANGE_GIST_KEY_LOWER_MAX_INC 0x0020 /* maximum value of lower + * bound in subtree is + * inclusive */ + #define RANGE_GIST_KEY_LOWER_MAX_INF 0x0040 /* maximum value of lower + * bound in subtree is + * infinite */ + #define RANGE_GIST_KEY_UPPER_MIN_INC 0x0080 /* minimum value of upper + * bound in subtree is + * inclusive */ + #define RANGE_GIST_KEY_UPPER_MIN_INF 0x0100 /* minimum value of upper + * bound in subtree is + * infinite */ + #define RANGE_GIST_KEY_UPPER_MAX_INC 0x0200 /* maximum value of upper + * bound in subtree is + * inclusive */ + #define RANGE_GIST_KEY_UPPER_MAX_INF 0x0400 /* maximum value of upper + * bound in subtree is + * infinite */ + + #define LIMIT_RATIO 0.3 + + /* + * GiST index key datatype. Represents box in virtual 2d-space. + */ + typedef struct + { + int32 vl_len_; /* varlena header (do not touch directly!) */ + Oid rangetypid; /* range type's own OID */ + + /* + * Following the OID are zero to four bound values, then a two bytes of + * flags + */ + } RangeGiSTKey; + + #define DatumGetRangeGiSTKey(X) ((RangeGiSTKey *) PG_DETOAST_DATUM(X)) + + /* Structure of minimum and maximum values of bound in subtree */ + typedef struct + { + RangeBound min; + RangeBound max; + } RangeBoundMinMax; + + /* Deserialized representation of GiST key */ + typedef struct + { + bool empty; /* all ranges in subtree are empty */ + bool containEmpty; /* subtree may contain some empty ranges */ + bool leaf; /* key is leaf: minimum and maximum values are + * equal */ + RangeBoundMinMax lower; /* minimum and maximum for lower bound value */ + RangeBoundMinMax upper; /* minimum and maximum for upper bound value */ + } RangeGiSTKeyDeserialized; + + #define RangeBoundIntervalBoundHasValue(b) (!(b).infinite) + + #define RangeBoundIntervalBoundAddValueSize(b) \ + if (RangeBoundIntervalBoundHasValue(b)) \ + { \ + if (typlen == -1) \ + b.val = PointerGetDatum(PG_DETOAST_DATUM_PACKED(b.val)); \ + msize = datum_compute_size(msize, b.val, typbyval, typalign, \ + typlen, typstorage); \ + } + + #define RangeBoundIntervalBoundWriteValue(b) \ + if (RangeBoundIntervalBoundHasValue(b)) \ + { \ + ptr = datum_write(ptr, b.val, typbyval, typalign, typlen, \ + typstorage); \ + } + + static void range_gist_key_deserialize(TypeCacheEntry *typcache, + RangeGiSTKey * gistKey, RangeGiSTKeyDeserialized * key); + static RangeGiSTKey *range_gist_key_serialize(TypeCacheEntry *typcache, + RangeGiSTKeyDeserialized * key); + static RangeGiSTKey *range_get_gist_key(TypeCacheEntry *typcache, + RangeType *range); + static void extend_gist_key(TypeCacheEntry *typcache, + RangeGiSTKeyDeserialized * target, RangeGiSTKeyDeserialized * new); + static float8 get_bounds_extension(TypeCacheEntry *typcache, RangeBound *min, + RangeBound *max, RangeBound *newmin, RangeBound *newmax); + static float8 get_bounds_size(TypeCacheEntry *typcache, RangeBound *min, + RangeBound *max); + + /* + * Input function for GiST key type. We never allow to construct key from a + * string, so trigger an error. + */ + Datum + grange_in(PG_FUNCTION_ARGS) + { + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("grange_it not implemented"))); + PG_RETURN_DATUM(0); + } + + /* + * Output function for GiST key type. Can be useful for debugging. + */ + Datum + grange_out(PG_FUNCTION_ARGS) + { + RangeGiSTKey *gistKey = DatumGetRangeGiSTKey(PG_GETARG_DATUM(0)); + RangeIOData *cache; + char *lbound_min_str = NULL; + char *lbound_max_str = NULL; + char *ubound_min_str = NULL; + char *ubound_max_str = NULL; + RangeGiSTKeyDeserialized key; + StringInfoData buf; + + cache = get_range_io_data(fcinfo, gistKey->rangetypid, IOFunc_output); + + /* deserialize */ + range_gist_key_deserialize(cache->typcache, gistKey, &key); + + if (key.empty) + PG_RETURN_CSTRING(pstrdup(RANGE_EMPTY_LITERAL)); + + /* call element type's output function */ + if (!key.lower.min.infinite) + lbound_min_str = OutputFunctionCall(&cache->proc, key.lower.min.val); + if (!key.lower.max.infinite) + lbound_max_str = OutputFunctionCall(&cache->proc, key.lower.max.val); + if (!key.lower.min.infinite) + ubound_min_str = OutputFunctionCall(&cache->proc, key.upper.min.val); + if (!key.lower.max.infinite) + ubound_max_str = OutputFunctionCall(&cache->proc, key.upper.max.val); + + initStringInfo(&buf); + appendStringInfoChar(&buf, '<'); + appendStringInfoChar(&buf, key.lower.min.inclusive ? '[' : '('); + if (!key.lower.min.infinite) + appendStringInfoString(&buf, range_bound_escape(lbound_min_str)); + appendStringInfoString(&buf, " - "); + if (!key.lower.max.infinite) + appendStringInfoString(&buf, range_bound_escape(lbound_max_str)); + appendStringInfoChar(&buf, key.lower.max.inclusive ? '[' : '('); + appendStringInfoString(&buf, ">, <"); + appendStringInfoChar(&buf, key.upper.min.inclusive ? '[' : '('); + if (!key.upper.min.infinite) + appendStringInfoString(&buf, range_bound_escape(ubound_min_str)); + appendStringInfoString(&buf, " - "); + if (!key.upper.max.infinite) + appendStringInfoString(&buf, range_bound_escape(ubound_max_str)); + appendStringInfoChar(&buf, key.upper.max.inclusive ? '[' : '('); + appendStringInfoChar(&buf, '>'); + + if (key.containEmpty) + { + appendStringInfoString(&buf, " | "); + appendStringInfoString(&buf, RANGE_EMPTY_LITERAL); + } + + PG_RETURN_CSTRING(buf.data); + } + + /* + * Get deserialized representation of GiST key. + */ + static void + range_gist_key_deserialize(TypeCacheEntry *typcache, RangeGiSTKey * gistKey, + RangeGiSTKeyDeserialized * key) + { + uint16 flags; + Pointer ptr; + int16 typlen; + bool typbyval; + char typalign; + + memset(key, 0, sizeof(RangeGiSTKeyDeserialized)); + + /* get flags from end of key */ + flags = *((uint16 *) ((char *) gistKey + VARSIZE(gistKey)) - 1); + + /* if empty flag is set no useful information in the rest of key */ + if (flags & RANGE_GIST_KEY_EMPTY) + { + key->empty = true; + key->containEmpty = true; + return; + } + + /* read other flag values */ + if (flags & RANGE_GIST_KEY_CONTAIN_EMPTY) + key->containEmpty = true; + + if (flags & RANGE_GIST_KEY_LOWER_MIN_INC) + key->lower.min.inclusive = true; + if (flags & RANGE_GIST_KEY_LOWER_MIN_INF) + key->lower.min.infinite = true; + key->lower.min.lower = true; + + if (flags & RANGE_GIST_KEY_LOWER_MAX_INC) + key->lower.max.inclusive = true; + if (flags & RANGE_GIST_KEY_LOWER_MAX_INF) + key->lower.max.infinite = true; + key->lower.max.lower = true; + + if (flags & RANGE_GIST_KEY_UPPER_MIN_INC) + key->upper.min.inclusive = true; + if (flags & RANGE_GIST_KEY_UPPER_MIN_INF) + key->upper.min.infinite = true; + key->upper.min.lower = false; + + if (flags & RANGE_GIST_KEY_UPPER_MAX_INC) + key->upper.max.inclusive = true; + if (flags & RANGE_GIST_KEY_UPPER_MAX_INF) + key->upper.max.infinite = true; + key->upper.max.lower = false; + + /* Fetch information about range's element type */ + typlen = typcache->rngelemtype->typlen; + typbyval = typcache->rngelemtype->typbyval; + typalign = typcache->rngelemtype->typalign; + + /* read bound values */ + ptr = (Pointer) (gistKey + 1); + if (flags & RANGE_GIST_KEY_LEAF) + { + /* Leaf key contain single values for lower and upper bounds. */ + key->leaf = true; + if (RangeBoundIntervalBoundHasValue(key->lower.min)) + { + key->lower.min.val = fetch_att(ptr, typbyval, typlen); + key->lower.max.val = key->lower.min.val; + ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); + } + if (RangeBoundIntervalBoundHasValue(key->upper.min)) + { + ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); + key->upper.min.val = fetch_att(ptr, typbyval, typlen); + key->upper.max.val = key->upper.min.val; + } + } + else + { + /* + * Internal key contain minimum and maximum bounds for lower and upper + * bounds. + */ + if (RangeBoundIntervalBoundHasValue(key->lower.min)) + { + key->lower.min.val = fetch_att(ptr, typbyval, typlen); + ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); + } + if (RangeBoundIntervalBoundHasValue(key->lower.max)) + { + ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); + key->lower.max.val = fetch_att(ptr, typbyval, typlen); + ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); + } + if (RangeBoundIntervalBoundHasValue(key->upper.min)) + { + ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); + key->upper.min.val = fetch_att(ptr, typbyval, typlen); + ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr); + } + if (RangeBoundIntervalBoundHasValue(key->upper.max)) + { + ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr); + key->upper.max.val = fetch_att(ptr, typbyval, typlen); + } + } + } + + /* + * Get serialized representation of GiST key. + */ + static RangeGiSTKey * + range_gist_key_serialize(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * key) + { + uint16 flags = 0; + Size msize; + int16 typlen; + bool typbyval; + char typalign; + char typstorage; + RangeGiSTKey *gistKey; + Pointer ptr; + + /* Set flags */ + if (key->empty) + { + flags |= RANGE_GIST_KEY_EMPTY; + flags |= RANGE_GIST_KEY_CONTAIN_EMPTY; + } + else + { + if (key->containEmpty) + flags |= RANGE_GIST_KEY_CONTAIN_EMPTY; + + if (key->lower.min.inclusive) + flags |= RANGE_GIST_KEY_LOWER_MIN_INC; + if (key->lower.min.infinite) + flags |= RANGE_GIST_KEY_LOWER_MIN_INF; + + if (key->lower.max.inclusive) + flags |= RANGE_GIST_KEY_LOWER_MAX_INC; + if (key->lower.max.infinite) + flags |= RANGE_GIST_KEY_LOWER_MAX_INF; + + if (key->upper.min.inclusive) + flags |= RANGE_GIST_KEY_UPPER_MIN_INC; + if (key->upper.min.infinite) + flags |= RANGE_GIST_KEY_UPPER_MIN_INF; + + if (key->upper.max.inclusive) + flags |= RANGE_GIST_KEY_UPPER_MAX_INC; + if (key->upper.max.infinite) + flags |= RANGE_GIST_KEY_UPPER_MAX_INF; + } + + /* Fetch information about range's element type */ + typlen = typcache->rngelemtype->typlen; + typbyval = typcache->rngelemtype->typbyval; + typalign = typcache->rngelemtype->typalign; + typstorage = typcache->rngelemtype->typstorage; + + /* Calculate required memory size */ + msize = sizeof(RangeGiSTKey); + if (!key->empty) + { + RangeBoundIntervalBoundAddValueSize(key->lower.min); + RangeBoundIntervalBoundAddValueSize(key->lower.max); + RangeBoundIntervalBoundAddValueSize(key->upper.min); + RangeBoundIntervalBoundAddValueSize(key->upper.max); + } + msize = SHORTALIGN(msize); + msize += sizeof(flags); + + /* Allocate memory and write serialized value */ + gistKey = (RangeGiSTKey *) palloc0(msize); + SET_VARSIZE(gistKey, msize); + + gistKey->rangetypid = typcache->type_id; + + ptr = (Pointer) (gistKey + 1); + + if (!key->empty) + { + RangeBoundIntervalBoundWriteValue(key->lower.min); + RangeBoundIntervalBoundWriteValue(key->lower.max); + RangeBoundIntervalBoundWriteValue(key->upper.min); + RangeBoundIntervalBoundWriteValue(key->upper.max); + } + + ptr = (Pointer) SHORTALIGN(ptr); + *((uint16 *) ptr) = flags; + + return gistKey; + } + + /* + * Get leaf GiST key by range value. + */ + static RangeGiSTKey * + range_get_gist_key(TypeCacheEntry *typcache, RangeType *range) + { + uint16 flags = 0; + Size msize; + int16 typlen; + bool typbyval; + char typalign; + char typstorage; + Pointer ptr; + RangeBound upper, + lower; + bool empty; + RangeGiSTKey *gistKey; + + range_deserialize(typcache, range, &lower, &upper, &empty); + + /* Fill flags */ + if (empty) + { + flags |= RANGE_GIST_KEY_EMPTY; + flags |= RANGE_GIST_KEY_CONTAIN_EMPTY; + } + else + { + flags |= RANGE_GIST_KEY_LEAF; + if (lower.inclusive) + { + flags |= RANGE_GIST_KEY_LOWER_MIN_INC; + flags |= RANGE_GIST_KEY_LOWER_MAX_INC; + } + if (lower.infinite) + { + flags |= RANGE_GIST_KEY_LOWER_MIN_INF; + flags |= RANGE_GIST_KEY_LOWER_MAX_INF; + } + if (upper.inclusive) + { + flags |= RANGE_GIST_KEY_UPPER_MIN_INC; + flags |= RANGE_GIST_KEY_UPPER_MAX_INC; + } + if (upper.infinite) + { + flags |= RANGE_GIST_KEY_UPPER_MIN_INF; + flags |= RANGE_GIST_KEY_UPPER_MAX_INF; + } + } + + /* Fetch information about range's element type */ + typlen = typcache->rngelemtype->typlen; + typbyval = typcache->rngelemtype->typbyval; + typalign = typcache->rngelemtype->typalign; + typstorage = typcache->rngelemtype->typstorage; + + /* Calculate required memory size */ + msize = sizeof(RangeGiSTKey); + + if (!empty) + { + RangeBoundIntervalBoundAddValueSize(lower); + RangeBoundIntervalBoundAddValueSize(upper); + } + + msize = SHORTALIGN(msize); + msize += sizeof(flags); + + /* Allocate memory and write value */ + gistKey = (RangeGiSTKey *) palloc0(msize); + SET_VARSIZE(gistKey, msize); + + gistKey->rangetypid = typcache->type_id; + + ptr = (Pointer) (gistKey + 1); + + if (!empty) + { + RangeBoundIntervalBoundWriteValue(lower); + RangeBoundIntervalBoundWriteValue(upper); + } + + ptr = (Pointer) SHORTALIGN(ptr); + *((uint16 *) ptr) = flags; + + return gistKey; + } + + /* + * GiST compress function. Converts input ranges to key type. + */ + Datum + range_gist2_compress(PG_FUNCTION_ARGS) + { + GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); + GISTENTRY *retval = entry; + + if (entry->leafkey) + { + RangeType *range; + RangeGiSTKey *key; + TypeCacheEntry *typcache; + + range = DatumGetRangeType(entry->key); + typcache = range_get_typcache(fcinfo, RangeTypeGetOid(range)); + key = range_get_gist_key(typcache, range); + retval = (GISTENTRY *) palloc(sizeof(GISTENTRY)); + gistentryinit(*retval, PointerGetDatum(key), + entry->rel, entry->page, + entry->offset, FALSE); + } + PG_RETURN_POINTER(retval); + } + + /* + * GiST decompress function. Do nothing. + */ + Datum + range_gist2_decompress(PG_FUNCTION_ARGS) + { + GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); + + PG_RETURN_POINTER(entry); + } + + /* + * Extends deserialized GiST key with another deserialized GiST key. As the + * result "target" key will contain "new" key. + */ + static void + extend_gist_key(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * target, + RangeGiSTKeyDeserialized * new) + { + /* Take care about "empty" and "containEmpty" flags */ + if (new->empty) + { + target->containEmpty = true; + return; + } + if (target->empty) + { + target->lower = new->lower; + target->upper = new->upper; + target->empty = false; + target->containEmpty = true; + return; + } + if (new->containEmpty) + target->containEmpty = true; + + /* Replace interval values with wider ones */ + if (range_cmp_bounds(typcache, &target->lower.min, &new->lower.min) > 0) + target->lower.min = new->lower.min; + if (range_cmp_bounds(typcache, &target->lower.max, &new->lower.max) < 0) + target->lower.max = new->lower.max; + if (range_cmp_bounds(typcache, &target->upper.min, &new->upper.min) > 0) + target->upper.min = new->upper.min; + if (range_cmp_bounds(typcache, &target->upper.max, &new->upper.max) < 0) + target->upper.max = new->upper.max; + } + + /* + * GiST union function. + */ + Datum + range_gist2_union(PG_FUNCTION_ARGS) + { + GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); + GISTENTRY *ent = entryvec->vector; + RangeGiSTKeyDeserialized target, + new; + TypeCacheEntry *typcache; + int i; + + typcache = range_get_typcache(fcinfo, DatumGetRangeGiSTKey(ent[0].key)->rangetypid); + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(ent[0].key), &target); + + for (i = 1; i < entryvec->n; i++) + { + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(ent[i].key), &new); + extend_gist_key(typcache, &target, &new); + } + + PG_RETURN_POINTER(range_gist_key_serialize(typcache, &target)); + } + + /* + * Represents information about an entry that can be placed to either group + * without affecting overlap over selected axis ("common entry"). + */ + typedef struct + { + /* Index of entry in the initial array */ + int index; + /* Delta between penalties of entry insertion into different groups */ + float8 delta; + } CommonEntry; + + /* + * Context for g_box_consider_split. Contains information about currently + * selected split and some general information. + */ + typedef struct + { + int entriesCount; /* total number of entries being split */ + TypeCacheEntry *typcache; + bool has_subtype_diff; + RangeGiSTKeyDeserialized boundingBox; /* minimum bounding box across + * all entries */ + + /* Information about currently selected split follows */ + + bool first; /* true if no split was selected yet */ + + RangeBound leftMax; /* upper bound of left interval */ + RangeBound rightMin; /* lower bound of right interval */ + + float4 ratio; + float8 overlap; + int dim; /* axis of this split */ + double range; /* width of general MBR projection to the + * selected axis */ + } ConsiderSplitContext; + + /* + * Interval comparison function by lower bound of the interval; + */ + static int + interval_cmp_lower(const void *i1, const void *i2, void *arg) + { + RangeBound *min1 = &((RangeBoundMinMax *) i1)->min, + *min2 = &((RangeBoundMinMax *) i2)->min; + + return range_cmp_bounds((TypeCacheEntry *) arg, min1, min2); + } + + /* + * Interval comparison function by upper bound of the interval; + */ + static int + interval_cmp_upper(const void *i1, const void *i2, void *arg) + { + RangeBound *max1 = &((RangeBoundMinMax *) i1)->max, + *max2 = &((RangeBoundMinMax *) i2)->max; + + return range_cmp_bounds((TypeCacheEntry *) arg, max1, max2); + } + + /* + * Replace negative value with zero. + */ + static inline float8 + non_negative(float8 val) + { + if (val >= 0.0f) + return val; + else + return 0.0f; + } + + /* + * Convenience function to invoke type-specific subtype_diff function. + * Caller must have already checked that there is one for the range type. + */ + static float8 + call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2) + { + float8 value; + + value = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo, + typcache->rng_collation, + val1, val2)); + /* Cope with buggy subtype_diff function by returning zero */ + if (value >= 0.0) + return value; + return 0.0; + } + + /* + * Consider replacement of currently selected split with the better one. + */ + static void inline + range_gist2_consider_split(ConsiderSplitContext *context, int dimNum, + RangeBound rightMin, int minLeftCount, + RangeBound leftMax, int maxLeftCount, + float8 range) + { + int leftCount, + rightCount; + float4 ratio; + float8 overlap; + + /* + * Calculate entries distribution ratio assuming most uniform distribution + * of common entries. + */ + if (minLeftCount >= (context->entriesCount + 1) / 2) + { + leftCount = minLeftCount; + } + else + { + if (maxLeftCount <= context->entriesCount / 2) + leftCount = maxLeftCount; + else + leftCount = context->entriesCount / 2; + } + rightCount = context->entriesCount - leftCount; + + /* + * Ratio of split - quotient between size of lesser group and total + * entries count. + */ + ratio = ((float4) Min(leftCount, rightCount)) / + ((float4) context->entriesCount); + + if (ratio > LIMIT_RATIO) + { + bool selectthis = false; + + /* + * The ratio is acceptable, so compare current split with previously + * selected one. Between splits of one dimension we search for minimal + * overlap (allowing negative values) and minimal ration (between same + * overlaps. We switch dimension if find less overlap (non-negative) + * or less range with same overlap. + */ + if (range_cmp_bounds(context->typcache, &leftMax, &rightMin) > 0) + overlap = get_bounds_size(context->typcache, &leftMax, &rightMin) / range; + else + overlap = 0.0; + + /* If there is no previous selection, select this */ + if (context->first) + selectthis = true; + else if (context->dim == dimNum) + { + /* + * Within the same dimension, choose the new split if it has a + * smaller overlap, or same overlap but better ratio. + */ + if (overlap < context->overlap || + (overlap == context->overlap && ratio > context->ratio)) + selectthis = true; + } + else + { + /* + * Across dimensions, choose the new split if it has a smaller + * *non-negative* overlap, or same *non-negative* overlap but + * bigger range. This condition differs from the one described in + * the article. On the datasets where leaf MBRs don't overlap + * themselves, non-overlapping splits (i.e. splits which have zero + * *non-negative* overlap) are frequently possible. In this case + * splits tends to be along one dimension, because most distant + * non-overlapping splits (i.e. having lowest negative overlap) + * appears to be in the same dimension as in the previous split. + * Therefore MBRs appear to be very prolonged along another + * dimension, which leads to bad search performance. Using range + * as the second split criteria makes MBRs more quadratic. Using + * *non-negative* overlap instead of overlap as the first split + * criteria gives to range criteria a chance to matter, because + * non-overlapping splits are equivalent in this criteria. + */ + if (non_negative(overlap) < non_negative(context->overlap) || + (range > context->range && + non_negative(overlap) <= non_negative(context->overlap))) + selectthis = true; + } + + if (selectthis) + { + /* save information about selected split */ + context->first = false; + context->ratio = ratio; + context->range = range; + context->overlap = overlap; + context->rightMin = rightMin; + context->leftMax = leftMax; + context->dim = dimNum; + } + } + } + + /* + * Return increase of original GiST key "area" by new range insertion. + */ + static float8 + range_gist_key_penalty(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * orig, RangeGiSTKeyDeserialized * new) + { + float8 lower_size, upper_size, lower_extent, upper_extent; + + lower_size = get_bounds_size(typcache, &orig->lower.min, &orig->lower.max); + upper_size = get_bounds_size(typcache, &orig->upper.min, &orig->upper.max); + + lower_extent = get_bounds_extension(typcache, &orig->lower.min, &orig->lower.max, + &new->lower.min, &new->lower.max); + upper_extent = get_bounds_extension(typcache, &orig->upper.min, &orig->upper.max, + &new->upper.min, &new->upper.max); + + /* get area of extension with accurate handling of infinities */ + if (lower_extent > 0 && upper_extent > 0) + { + if (is_infinite(lower_size) || is_infinite(upper_size)) + return get_float8_infinity(); + else + return (lower_size + lower_extent) * (upper_size + upper_extent) + - lower_size * upper_size; + } + else if (lower_extent > 0) + { + if (upper_size > 0) + return lower_extent * upper_size; + else + return 0.0; + } + else if (upper_extent > 0) + { + if (lower_size > 0) + return upper_extent * lower_size; + else + return 0.0; + } + else + { + return 0.0; + } + } + + /* + * Compare common entries by their deltas. + */ + static int + common_entry_cmp(const void *i1, const void *i2) + { + double delta1 = ((const CommonEntry *) i1)->delta, + delta2 = ((const CommonEntry *) i2)->delta; + + if (delta1 < delta2) + return -1; + else if (delta1 > delta2) + return 1; + else + return 0; + } + + /* Helper macros to place an entry in the left or right group */ + #define PLACE_LEFT(key, off) \ + do { \ + if (v->spl_nleft > 0) \ + extend_gist_key(typcache, &leftKey, &key); \ + else \ + leftKey = key; \ + v->spl_left[v->spl_nleft++] = off; \ + } while(0) + + #define PLACE_RIGHT(key, off) \ + do { \ + if (v->spl_nright > 0) \ + extend_gist_key(typcache, &rightKey, &key); \ + else \ + rightKey = key; \ + v->spl_right[v->spl_nright++] = off; \ + } while(0) + + /* + * Trivial split: half of entries will be placed on one page + * and the other half on the other page. + */ + static void + range_gist2_fallback_split(TypeCacheEntry *typcache, + GistEntryVector *entryvec, + GIST_SPLITVEC *v) + { + RangeGiSTKeyDeserialized leftKey; + RangeGiSTKeyDeserialized rightKey; + OffsetNumber i, + maxoff, + splitIdx; + + maxoff = entryvec->n - 1; + /* Split entries before this to left page, after to right: */ + splitIdx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber; + + v->spl_nleft = 0; + v->spl_nright = 0; + for (i = FirstOffsetNumber; i <= maxoff; i++) + { + RangeGiSTKeyDeserialized key; + + range_gist_key_deserialize(typcache, + DatumGetRangeGiSTKey(entryvec->vector[i].key), &key); + + if (i < splitIdx) + PLACE_LEFT(key, i); + else + PLACE_RIGHT(key, i); + } + + v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey)); + v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey)); + } + + /* + * Empty entries will be placed to one page and non-empty entries will be + * placed to another page. + */ + static void + range_gist2_empty_split(TypeCacheEntry *typcache, + GistEntryVector *entryvec, + GIST_SPLITVEC *v) + { + RangeGiSTKeyDeserialized leftKey; + RangeGiSTKeyDeserialized rightKey; + OffsetNumber i, + maxoff; + + maxoff = entryvec->n - 1; + v->spl_nleft = 0; + v->spl_nright = 0; + for (i = FirstOffsetNumber; i <= maxoff; i++) + { + RangeGiSTKeyDeserialized key; + + range_gist_key_deserialize(typcache, + DatumGetRangeGiSTKey(entryvec->vector[i].key), &key); + + if (key.empty) + PLACE_LEFT(key, i); + else + PLACE_RIGHT(key, i); + } + + v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey)); + v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey)); + } + + /* + * GiST picksplit function. + */ + Datum + range_gist2_picksplit(PG_FUNCTION_ARGS) + { + GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); + GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); + OffsetNumber i, + maxoff; + ConsiderSplitContext context; + RangeGiSTKeyDeserialized key, + leftKey, + rightKey; + int dim, + commonEntriesCount; + RangeBoundMinMax *intervalsLower, + *intervalsUpper; + CommonEntry *commonEntries; + int nentries, + emptyCount = 0; + TypeCacheEntry *typcache; + + typcache = range_get_typcache(fcinfo, DatumGetRangeGiSTKey( + entryvec->vector[FirstOffsetNumber].key)->rangetypid); + + memset(&context, 0, sizeof(ConsiderSplitContext)); + + maxoff = entryvec->n - 1; + nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1; + + /* + * Calculate the overall minimum bounding box over all the entries. + */ + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key); + + if (key.empty) + emptyCount++; + + if (i == FirstOffsetNumber) + context.boundingBox = key; + else + extend_gist_key(typcache, &context.boundingBox, &key); + } + + /* Allocate vectors for results */ + v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber)); + v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber)); + v->spl_nleft = 0; + v->spl_nright = 0; + + if (emptyCount > 0) + { + if (emptyCount == nentries) + { + range_gist2_fallback_split(typcache, entryvec, v); + PG_RETURN_POINTER(v); + } + else + { + range_gist2_empty_split(typcache, entryvec, v); + PG_RETURN_POINTER(v); + } + } + + + /* + * Iterate over axes for optimal split searching. + */ + context.first = true; /* nothing selected yet */ + context.typcache = typcache; + context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid); + /* Allocate arrays for intervals along axes */ + intervalsLower = (RangeBoundMinMax *) palloc(nentries * sizeof(RangeBoundMinMax)); + intervalsUpper = (RangeBoundMinMax *) palloc(nentries * sizeof(RangeBoundMinMax)); + + for (dim = 0; dim < 2; dim++) + { + RangeBound leftUpper, + rightLower; + int i1, + i2; + float8 range; + + if (dim == 0) + range = get_bounds_size(typcache, + &context.boundingBox.lower.max, + &context.boundingBox.lower.min); + else + range = get_bounds_size(typcache, + &context.boundingBox.upper.max, + &context.boundingBox.upper.min); + + /* Project each entry as an interval on the selected axis. */ + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key); + + if (dim == 0) + intervalsLower[i - FirstOffsetNumber] = key.lower; + else + intervalsLower[i - FirstOffsetNumber] = key.upper; + } + + /* + * Make two arrays of intervals: one sorted by lower bound and another + * sorted by upper bound. + */ + memcpy(intervalsUpper, intervalsLower, + sizeof(RangeBoundMinMax) * nentries); + qsort_arg(intervalsLower, nentries, sizeof(RangeBoundMinMax), + interval_cmp_lower, typcache); + qsort_arg(intervalsUpper, nentries, sizeof(RangeBoundMinMax), + interval_cmp_upper, typcache); + + /*---- + * The goal is to form a left and right interval, so that every entry + * interval is contained by either left or right interval (or both). + * + * For example, with the intervals (0,1), (1,3), (2,3), (2,4): + * + * 0 1 2 3 4 + * +-+ + * +---+ + * +-+ + * +---+ + * + * The left and right intervals are of the form (0,a) and (b,4). + * We first consider splits where b is the lower bound of an entry. + * We iterate through all entries, and for each b, calculate the + * smallest possible a. Then we consider splits where a is the + * uppper bound of an entry, and for each a, calculate the greatest + * possible b. + * + * In the above example, the first loop would consider splits: + * b=0: (0,1)-(0,4) + * b=1: (0,1)-(1,4) + * b=2: (0,3)-(2,4) + * + * And the second loop: + * a=1: (0,1)-(1,4) + * a=3: (0,3)-(2,4) + * a=4: (0,4)-(2,4) + */ + + /* + * Iterate over lower bound of right group, finding smallest possible + * upper bound of left group. + */ + i1 = 0; + i2 = 0; + rightLower = intervalsLower[i1].min; + leftUpper = intervalsUpper[i2].min; + while (true) + { + /* + * Find next lower bound of right group. + */ + while (i1 < nentries && range_cmp_bounds(typcache, &rightLower, &intervalsLower[i1].min) == 0) + { + if (range_cmp_bounds(typcache, &leftUpper, &intervalsLower[i1].max) < 0) + leftUpper = intervalsLower[i1].max; + i1++; + } + if (i1 >= nentries) + break; + rightLower = intervalsLower[i1].min; + + /* + * Find count of intervals which anyway should be placed to the + * left group. + */ + while (i2 < nentries && range_cmp_bounds(typcache, &intervalsUpper[i2].max, &leftUpper) <= 0) + i2++; + + /* + * Consider found split. + */ + range_gist2_consider_split(&context, dim, rightLower, i1, leftUpper, i2, range); + } + + /* + * Iterate over upper bound of left group finding greates possible + * lower bound of right group. + */ + i1 = nentries - 1; + i2 = nentries - 1; + rightLower = intervalsLower[i1].max; + leftUpper = intervalsUpper[i2].max; + while (true) + { + /* + * Find next upper bound of left group. + */ + while (i2 >= 0 && range_cmp_bounds(typcache, &leftUpper, &intervalsUpper[i2].max) == 0) + { + if (range_cmp_bounds(typcache, &rightLower, &intervalsUpper[i2].min) > 0) + rightLower = intervalsUpper[i2].min; + i2--; + } + if (i2 < 0) + break; + leftUpper = intervalsUpper[i2].max; + + /* + * Find count of intervals which anyway should be placed to the + * right group. + */ + while (i1 >= 0 && + range_cmp_bounds(typcache, &intervalsLower[i1].min, &rightLower) >= 0) + i1--; + + /* + * Consider found split. + */ + range_gist2_consider_split(&context, dim, + rightLower, i1 + 1, leftUpper, i2 + 1, range); + } + } + + /* + * If we failed to find any acceptable splits, use trivial split. + */ + if (context.first) + { + range_gist2_fallback_split(typcache, entryvec, v); + PG_RETURN_POINTER(v); + } + + /* + * Ok, we have now selected the split across one axis. + * + * While considering the splits, we already determined that there will be + * enough entries in both groups to reach the desired ratio, but we did + * not memorize which entries go to which group. So determine that now. + */ + + /* + * Allocate an array for "common entries" - entries which can be placed to + * either group without affecting overlap along selected axis. + */ + commonEntriesCount = 0; + commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry)); + + /* + * Distribute entries which can be distributed unambiguously, and collect + * common entries. + */ + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + RangeBound lower, + upper; + + /* + * Get upper and lower bounds along selected axis. + */ + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key); + if (context.dim == 0) + { + lower = key.lower.min; + upper = key.lower.max; + } + else + { + lower = key.upper.min; + upper = key.upper.max; + } + + if (range_cmp_bounds(typcache, &upper, &context.leftMax) <= 0) + { + /* Fits to the left group */ + if (range_cmp_bounds(typcache, &lower, &context.rightMin) >= 0) + { + /* Fits also to the right group, so "common entry" */ + commonEntries[commonEntriesCount++].index = i; + } + else + { + /* Doesn't fit to the right group, so join to the left group */ + PLACE_LEFT(key, i); + } + } + else + { + /* + * Each entry should fit on either left or right group. Since this + * entry didn't fit on the left group, it better fit in the right + * group. + */ + Assert(range_cmp_bounds(typcache, &lower, &context.rightMin) >= 0); + + /* Doesn't fit to the left group, so join to the right group */ + PLACE_RIGHT(key, i); + } + } + + /* + * Distribute "common entries", if any. + */ + if (commonEntriesCount > 0) + { + /* + * Calculate minimum number of entries that must be placed in both + * groups, to reach LIMIT_RATIO. + */ + int m = ceil(LIMIT_RATIO * (double) nentries); + + /* + * Calculate delta between penalties of join "common entries" to + * different groups. + */ + for (i = 0; i < commonEntriesCount; i++) + { + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[commonEntries[i].index].key), &key); + commonEntries[i].delta = Abs(range_gist_key_penalty(typcache, &leftKey, &key) - + range_gist_key_penalty(typcache, &rightKey, &key)); + } + + /* + * Sort "common entries" by calculated deltas in order to distribute + * the most ambiguous entries first. + */ + qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp); + + /* + * Distribute "common entries" between groups. + */ + for (i = 0; i < commonEntriesCount; i++) + { + range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[commonEntries[i].index].key), &key); + + /* + * Check if we have to place this entry in either group to achieve + * LIMIT_RATIO. + */ + if (v->spl_nleft + (commonEntriesCount - i) <= m) + PLACE_LEFT(key, commonEntries[i].index); + else if (v->spl_nright + (commonEntriesCount - i) <= m) + PLACE_RIGHT(key, commonEntries[i].index); + else + { + /* Otherwise select the group by minimal penalty */ + if (range_gist_key_penalty(typcache, &leftKey, &key) < + range_gist_key_penalty(typcache, &rightKey, &key)) + PLACE_LEFT(key, commonEntries[i].index); + else + PLACE_RIGHT(key, commonEntries[i].index); + } + } + } + + v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey)); + v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey)); + PG_RETURN_POINTER(v); + } + + /* + * Get extension of bounds by inclusion of new bound value using subtype_diff + * function. + */ + static float8 + get_bounds_extension(TypeCacheEntry *typcache, RangeBound *min, + RangeBound *max, RangeBound *newmin, RangeBound *newmax) + { + if (range_cmp_bounds(typcache, newmin, min) < 0) + { + if ((newmin->infinite && !min->infinite) || (!newmin->infinite && min->infinite)) + return get_float8_infinity(); + if (!OidIsValid(typcache->rng_subdiff_finfo.fn_oid)) + return 1.0; + return call_subtype_diff(typcache, min->val, newmin->val); + } + else if (range_cmp_bounds(typcache, newmax, max) > 0) + { + if ((newmax->infinite && !max->infinite) || (!newmax->infinite && max->infinite)) + return get_float8_infinity(); + if (!OidIsValid(typcache->rng_subdiff_finfo.fn_oid)) + return 1.0; + return call_subtype_diff(typcache, newmax->val, max->val); + } + else + return 0.0; + } + + /* + * Get size of space between range bounds using subtype_diff function. + */ + static float8 + get_bounds_size(TypeCacheEntry *typcache, RangeBound *min, + RangeBound *max) + { + if ((min->infinite && !max->infinite) || (!min->infinite && max->infinite)) + return get_float8_infinity(); + else if (min->infinite && max->infinite) + return 0.0; + else + return call_subtype_diff(typcache, max->val, min->val); + } + + /* + * GiST penalty function + */ + Datum + range_gist2_penalty(PG_FUNCTION_ARGS) + { + GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); + GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); + float *penalty = (float *) PG_GETARG_POINTER(2); + TypeCacheEntry *typcache; + + RangeGiSTKey *origkey = DatumGetRangeGiSTKey(origentry->key); + RangeGiSTKey *newkey = DatumGetRangeGiSTKey(newentry->key); + RangeGiSTKeyDeserialized orig, + new; + + typcache = range_get_typcache(fcinfo, origkey->rangetypid); + + range_gist_key_deserialize(typcache, origkey, &orig); + range_gist_key_deserialize(typcache, newkey, &new); + + *penalty = range_gist_key_penalty(typcache, &orig, &new); + + PG_RETURN_POINTER(penalty); + } + + /* GiST query consistency check */ + Datum + range_gist2_consistent(PG_FUNCTION_ARGS) + { + GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); + Datum query = PG_GETARG_DATUM(1); + StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); + + /* Oid subtype = PG_GETARG_OID(3); */ + bool *recheck = (bool *) PG_GETARG_POINTER(4); + RangeGiSTKey *gistkey = DatumGetRangeGiSTKey(entry->key); + RangeGiSTKeyDeserialized key; + TypeCacheEntry *typcache; + RangeBound lower, + upper; + bool empty; + int32 cmp; + + typcache = range_get_typcache(fcinfo, gistkey->rangetypid); + range_gist_key_deserialize(typcache, gistkey, &key); + + if (strategy != RANGESTRAT_CONTAINS_ELEM) + { + range_deserialize(typcache, DatumGetRangeType(query), &lower, &upper, &empty); + } + + /* All operators served by this function are exact */ + *recheck = false; + + switch (strategy) + { + case RANGESTRAT_BEFORE: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for upper bound inside subtree to be + * lower than query lower bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.upper.min, &lower) < 0); + break; + case RANGESTRAT_AFTER: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for lower bound inside subtree to be + * greater than query upper bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.lower.max, &upper) > 0); + break; + case RANGESTRAT_OVERLEFT: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for upper bound inside subtree to be + * lower than query lower bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0); + break; + case RANGESTRAT_OVERRIGHT: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0); + break; + case RANGESTRAT_ADJACENT: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + if (!key.leaf) + { + /* + * It should be possible for upper bound inside subtree to be + * equal to query lower bound or for lower bound inside subtree + * to be equal to query upper bound. + */ + PG_RETURN_BOOL( + (range_cmp_bound_values(typcache, &key.lower.min, &upper) <= 0 && + range_cmp_bound_values(typcache, &key.lower.max, &upper) >= 0) || + (range_cmp_bound_values(typcache, &key.upper.min, &lower) <= 0 && + range_cmp_bound_values(typcache, &key.upper.max, &lower) >= 0) + ); + } + else + { + /* Do direct check for leaf key */ + PG_RETURN_DATUM( + TrickFunctionCall2(range_adjacent, fcinfo->flinfo, + RangeTypeGetDatum(range_serialize(typcache, &key.lower.min, + &key.upper.max, key.empty)), + query) + ); + } + break; + case RANGESTRAT_EQ: + /* Subtree can contain empty only if key have "containEmpty" flag */ + if (empty) + PG_RETURN_BOOL(key.containEmpty); + /* + * It should be possible for lower bound inside subtree to be + * equal to query lower bound and for upper bound inside subtree + * to be equal to query upper bound. + */ + PG_RETURN_BOOL( + (range_cmp_bounds(typcache, &key.lower.min, &lower) <= 0 && + range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0) || + (range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0 && + range_cmp_bounds(typcache, &key.upper.max, &upper) >= 0) + ); + break; + case RANGESTRAT_CONTAINS_ELEM: + /* + * If whole subtree contain only empty elements then it can't + * contain any element. + */ + if (key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for lower bound inside subtree to be less + * than query element. + */ + if (!key.lower.min.infinite) + { + cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, + typcache->rng_collation, + key.lower.min.val, query)); + if (cmp > 0) + PG_RETURN_BOOL(false); + if (cmp == 0 && !key.lower.min.inclusive) + PG_RETURN_BOOL(false); + } + /* + * It should be possible for lower bound inside subtree to be + * greater than query element. + */ + if (!key.upper.max.infinite) + { + cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, + typcache->rng_collation, + key.upper.max.val, query)); + if (cmp < 0) + PG_RETURN_BOOL(false); + if (cmp == 0 && !key.upper.max.inclusive) + PG_RETURN_BOOL(false); + } + PG_RETURN_BOOL(true); + break; + case RANGESTRAT_OVERLAPS: + /* If query is empty or all keys in subtree are empty, then skip */ + if (empty || key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for lower bound inside subtree to be less + * or equal to query upper bound and for upper bound inside subtree + * to be greater or equal to query lower bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.lower.min, &upper) <= 0 && + range_cmp_bounds(typcache, &key.upper.max, &lower) >= 0); + break; + case RANGESTRAT_CONTAINS: + /* Empty query is contained in everything */ + if (empty) + PG_RETURN_BOOL(true); + /* If all key in subtree are empty then it can contain anything */ + if (key.empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for lower bound inside subtree to be less + * or equal to query lower bound and for upper bound inside subtree + * to be greater or equal to query upper bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.lower.min, &lower) <= 0 && + range_cmp_bounds(typcache, &key.upper.max, &upper) >= 0); + break; + case RANGESTRAT_CONTAINED_BY: + /* Empty keys are contained in everything */ + if (key.containEmpty) + PG_RETURN_BOOL(true); + /* Empty query can't contain anything */ + if (empty) + PG_RETURN_BOOL(false); + /* + * It should be possible for lower bound inside subtree to be + * greater or equal to query lower bound and for upper bound inside + * subtree to be less or equal to query upper bound. + */ + PG_RETURN_BOOL( + range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0 && + range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0); + break; + default: + elog(ERROR, "unrecognized range strategy: %d", strategy); + break; + } + + PG_RETURN_BOOL(true); + } + + /* equality comparator for GiST */ + Datum + range_gist2_same(PG_FUNCTION_ARGS) + { + RangeGiSTKey *gistKey1 = DatumGetRangeGiSTKey(PG_GETARG_DATUM(0)); + RangeGiSTKey *gistKey2 = DatumGetRangeGiSTKey(PG_GETARG_DATUM(1)); + bool *result = (bool *) PG_GETARG_POINTER(2); + RangeGiSTKeyDeserialized key1, key2; + TypeCacheEntry *typcache; + + typcache = range_get_typcache(fcinfo, gistKey1->rangetypid); + + /* deserialize gist keys */ + range_gist_key_deserialize(typcache, gistKey1, &key1); + range_gist_key_deserialize(typcache, gistKey2, &key2); + + /* compare flags first, then compare bounds */ + if (key1.containEmpty != key2.containEmpty || key1.empty != key2.empty) + *result = false; + else if (range_cmp_bounds(typcache, &key1.lower.min, &key2.lower.min) != 0) + *result = false; + else if (range_cmp_bounds(typcache, &key1.lower.max, &key2.lower.max) != 0) + *result = false; + else if (range_cmp_bounds(typcache, &key1.upper.min, &key2.upper.min) != 0) + *result = false; + else if (range_cmp_bounds(typcache, &key1.upper.max, &key2.upper.max) != 0) + *result = false; + else + *result = true; + + PG_RETURN_POINTER(result); + } *** /dev/null --- b/src/backend/utils/adt/rangetypes_spgist.c *************** *** 0 **** --- 1,807 ---- + /*------------------------------------------------------------------------- + * + * rangetypes_spgist.c + * implementation of quad tree over ranges mapped to 2d-points for SP-GiST + * + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/utils/adt/rangetypes_spgist.c + * + *------------------------------------------------------------------------- + */ + + #include "postgres.h" + + #include "access/spgist.h" + #include "access/skey.h" + #include "catalog/pg_type.h" + #include "utils/builtins.h" + #include "utils/datum.h" + #include "utils/rangetypes.h" + + Datum spg_range_quad_config(PG_FUNCTION_ARGS); + Datum spg_range_quad_choose(PG_FUNCTION_ARGS); + Datum spg_range_quad_picksplit(PG_FUNCTION_ARGS); + Datum spg_range_quad_inner_consistent(PG_FUNCTION_ARGS); + Datum spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS); + + static int16 getQuadrant(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst); + static int bound_cmp(const void *a, const void *b, void *arg); + static bool bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper); + + + /* + * Config SP-GiST interface function. + */ + Datum + spg_range_quad_config(PG_FUNCTION_ARGS) + { + /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */ + spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1); + + cfg->prefixType = ANYRANGEOID; + cfg->labelType = VOIDOID; /* we don't need node labels */ + cfg->canReturnData = true; + cfg->longValuesOK = false; + PG_RETURN_VOID(); + } + + /* + * Determine which quadrant a 2d-mapped range falls into, relative to the + * centroid. Lower bound of range assumed to be the horizontal axis. Upper + * bound of range assumed to be the vertical axis. + * + * Quadrants are identified like this: + * + * 4 | 1 + * ----+----- + * 3 | 2 + * + * Ranges on one of the axes are taken to lie in the quadrant with higher value + * along perpendicular axis. Range equal to centroid is taken to lie in the + * quadrant 1. Empty ranges are taken to lie in the quadrant 5. + */ + static int16 + getQuadrant(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst) + { + RangeBound centroidLower, centroidUpper, lower, upper; + bool centroidEmpty, empty; + + range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper, + ¢roidEmpty); + range_deserialize(typcache, tst, &lower, &upper, &empty); + + if (empty) + return 5; + + if (range_cmp_bounds(typcache, &lower, ¢roidLower) >= 0) + { + if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0) + return 1; + else + return 2; + } + else + { + if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0) + return 4; + else + return 3; + } + + elog(ERROR, "getQuadrant: impossible case"); + return 0; + } + + + /* + * Choose SP-GiST function: choose path for addition of new range. + */ + Datum + spg_range_quad_choose(PG_FUNCTION_ARGS) + { + spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0); + spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1); + RangeType *inRange = DatumGetRangeType(in->datum), *centroid; + int16 quadrant; + TypeCacheEntry *typcache; + + if (in->allTheSame) + { + out->resultType = spgMatchNode; + /* nodeN will be set by core */ + out->result.matchNode.levelAdd = 0; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + PG_RETURN_VOID(); + } + + typcache = range_get_typcache(fcinfo, RangeTypeGetOid(inRange)); + + Assert(in->hasPrefix); + centroid = DatumGetRangeType(in->prefixDatum); + + /* + * Empty prefix datum divides ranges by empty sign. All empty ranges are + * taken into node 0, all non-empty ranges are taken into node 1. + */ + if (RangeIsEmpty(centroid)) + { + out->resultType = spgMatchNode; + if (RangeIsEmpty(inRange)) + out->result.matchNode.nodeN = 0; + else + out->result.matchNode.nodeN = 1; + out->result.matchNode.levelAdd = 0; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + PG_RETURN_VOID(); + } + + quadrant = getQuadrant(typcache, centroid, inRange); + + /* Node for empty range is possibly not exist, create it if so */ + if (quadrant == 5 && in->nNodes == 4) + { + out->resultType = spgAddNode; + out->result.addNode.nodeN = quadrant - 1; + } + + Assert(quadrant <= in->nNodes); + + /* Select node matching to quadrant number */ + out->resultType = spgMatchNode; + out->result.matchNode.nodeN = quadrant - 1; + out->result.matchNode.levelAdd = 0; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + + PG_RETURN_VOID(); + } + + /* + * Bound comparison for sorting. + */ + static int + bound_cmp(const void *a, const void *b, void *arg) + { + RangeBound *ba = (RangeBound *) a; + RangeBound *bb = (RangeBound *) b; + TypeCacheEntry *typcache = (TypeCacheEntry *)arg; + + return range_cmp_bounds(typcache, ba, bb); + } + + /* + * Picksplit SP-GiST function: split ranges into nodes. Select "centroid" + * range and distribute ranges according to quadrants. + */ + Datum + spg_range_quad_picksplit(PG_FUNCTION_ARGS) + { + spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0); + spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1); + int i, j, nonEmptyCount; + RangeType *centroid; + bool empty; + TypeCacheEntry *typcache; + + /* Use the median values of lower and upper bounds as the centroid range */ + RangeBound *lowerBounds, *upperBounds; + + typcache = range_get_typcache(fcinfo, + RangeTypeGetOid(DatumGetRangeType(in->datums[0]))); + + /* Allocate memory for bounds */ + lowerBounds = palloc(sizeof(RangeBound) * in->nTuples); + upperBounds = palloc(sizeof(RangeBound) * in->nTuples); + j = 0; + + /* Deserialize bounds of ranges, count non-empty ranges */ + for (i = 0; i < in->nTuples; i++) + { + range_deserialize(typcache, DatumGetRangeType(in->datums[i]), + &lowerBounds[j], &upperBounds[j], &empty); + if (!empty) + j++; + } + nonEmptyCount = j; + + /* + * All the ranges are empty. We've nothing better than put all the ranges + * into node 0. Non-empty range will be routed to node 1. + */ + if (nonEmptyCount == 0) + { + out->nNodes = 2; + out->hasPrefix = true; + /* Prefix is empty */ + out->prefixDatum = RangeTypeGetDatum( + range_serialize(typcache, NULL, NULL, true)); + out->nodeLabels = NULL; + + out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples); + out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples); + + /* Place all ranges into node 0 */ + for (i = 0; i < in->nTuples; i++) + { + RangeType *range = DatumGetRangeType(in->datums[i]); + + out->leafTupleDatums[i] = RangeTypeGetDatum(range); + out->mapTuplesToNodes[i] = 0; + } + PG_RETURN_VOID(); + } + + /* Sort range bounds in order to find medians */ + qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound), + bound_cmp, typcache); + qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound), + bound_cmp, typcache); + + /* Construct "centroid" range from medians of lower and upper bounds */ + centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2], + &upperBounds[nonEmptyCount / 2], false); + + + out->hasPrefix = true; + out->prefixDatum = RangeTypeGetDatum(centroid); + + /* Create node for empty ranges only if it is actually needed */ + out->nNodes = (nonEmptyCount == in->nTuples) ? 4 : 5; + out->nodeLabels = NULL; /* we don't need node labels */ + + out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples); + out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples); + + /* + * Add ranges to corresponding nodes according to quadrants relative to + * "centroid" range. + */ + for (i = 0; i < in->nTuples; i++) + { + RangeType *range = DatumGetRangeType(in->datums[i]); + int16 quadrant = getQuadrant(typcache, centroid, range); + + out->leafTupleDatums[i] = RangeTypeGetDatum(range); + out->mapTuplesToNodes[i] = quadrant - 1; + } + + PG_RETURN_VOID(); + } + + /* + * Check if two bounds are "connected", i.e. there are no values which satisfy + * both bounds and there are no values between the bounds. + */ + static bool + bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper) + { + int cmp = range_cmp_bound_values(typcache, &upper, &lower); + if (cmp < 0) + { + RangeType *r; + /* in a continuous subtype, there are assumed to be points between */ + if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid)) + return false; + /* flip the inclusion flags */ + upper.inclusive = !upper.inclusive; + lower.inclusive = !lower.inclusive; + /* change upper/lower labels to avoid Assert failures */ + upper.lower = true; + lower.lower = false; + r = make_range(typcache, &upper, &lower, false); + PG_RETURN_BOOL(RangeIsEmpty(r)); + } + else if (cmp == 0) + { + PG_RETURN_BOOL(upper.inclusive != lower.inclusive); + } + else + { + PG_RETURN_BOOL(false); + } + } + + /* + * Inner consisted SP-GiST function: check which nodes are consistent with + * given set of queries. + */ + Datum + spg_range_quad_inner_consistent(PG_FUNCTION_ARGS) + { + spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0); + spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1); + RangeType *centroid; + int which; + int i; + bool needPrevious = false; + + Assert(in->hasPrefix); + centroid = DatumGetRangeType(in->prefixDatum); + + if (in->allTheSame) + { + /* Report that all nodes should be visited */ + out->nNodes = in->nNodes; + out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); + for (i = 0; i < in->nNodes; i++) + out->nodeNumbers[i] = i; + PG_RETURN_VOID(); + } + + if (RangeIsEmpty(centroid)) + { + /* + * Empty "centroid". We can use only information about emptiness of + * ranges in nodes. + */ + Assert(in->nNodes == 2); + + /* + * Nth bit of which variable means that (N - 1)th node should be + * visited. Initially all bits are set. Bits of nodes which should be + * skipped will be unset. + */ + which = (1 << 1) | (1 << 2); + for (i = 0; i < in->nkeys; i++) + { + StrategyNumber strategy; + bool empty; + + strategy = in->scankeys[i].sk_strategy; + + /* + * The only strategy when second argument of operator is not + * range is RANGESTRAT_CONTAINS_ELEM. + */ + if (strategy != RANGESTRAT_CONTAINS_ELEM) + empty = RangeIsEmpty( + DatumGetRangeType(in->scankeys[i].sk_argument)); + + switch (strategy) + { + /* These strategies return false if any argument is empty */ + case RANGESTRAT_BEFORE: + case RANGESTRAT_OVERLEFT: + case RANGESTRAT_OVERLAPS: + case RANGESTRAT_OVERRIGHT: + case RANGESTRAT_AFTER: + case RANGESTRAT_ADJACENT: + if (empty) + which = 0; + else + which &= (1 << 2); + break; + /* + * "Empty" range is contained in any range. Non-empty ranges + * can be contained in only non-empty ranges. + */ + case RANGESTRAT_CONTAINS: + if (!empty) + which &= (1 << 2); + break; + case RANGESTRAT_CONTAINED_BY: + if (empty) + which &= (1 << 1); + break; + /* Empty range can't contain any element */ + case RANGESTRAT_CONTAINS_ELEM: + which &= (1 << 2); + break; + case RANGESTRAT_EQ: + if (empty) + which &= (1 << 1); + else + which &= (1 << 2); + break; + default: + elog(ERROR, "unrecognized range strategy: %d", strategy); + break; + } + if (which == 0) + break; /* no need to consider remaining conditions */ + } + } + else + { + RangeBound centroidLower, centroidUpper; + bool centroidEmpty; + TypeCacheEntry *typcache; + + /* Centroid is not empty, get information about it. */ + typcache = range_get_typcache(fcinfo, + RangeTypeGetOid(DatumGetRangeType(centroid))); + range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper, + ¢roidEmpty); + + Assert(in->nNodes == 4 || in->nNodes == 5); + + /* + * Nth bit of which variable means that (N - 1)th node (Nth quadrant) + * should be visited. Initially all bits are set. Bits of nodes which + * should be skipped will be unset. + */ + which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5); + + for (i = 0; i < in->nkeys; i++) + { + StrategyNumber strategy; + RangeBound lower, upper; + bool empty; + RangeType *range = NULL; + + /* + * Deserialize range if argument is range. The only strategy when + * second argument of operator is not range is + * RANGESTRAT_CONTAINS_ELEM. + */ + if (strategy != RANGESTRAT_CONTAINS_ELEM) + { + range = DatumGetRangeType(in->scankeys[i].sk_argument); + range_deserialize(typcache, range, &lower, &upper, &empty); + } + + strategy = in->scankeys[i].sk_strategy; + + switch (strategy) + { + RangeBound prevLower, prevUpper; + bool prevEmpty, prevPresent; + RangeType *prevCentroid; + int cmp1, cmp2, cmp3, which1, which2; + + /* + * Range A is before range B if upper bound of A is lower than + * lower bound of B. If upper bound of "centroid" is greater + * or equal to lower bound of argument then no ranges before + * argument can be contained in quadrants 2 and 4. + */ + case RANGESTRAT_BEFORE: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, ¢roidUpper, + &lower) >= 0) + which &= (1 << 2) | (1 << 3); + else + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + break; + /* + * Range A is overleft to range B if upper bound of A is lower + * or equal to lower bound of B. If upper bound of "centroid" is + * greater to upper bound of argument then no ranges overleft + * argument can be contained in quadrants 1 and 4. + */ + case RANGESTRAT_OVERLEFT: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, ¢roidUpper, + &upper) > 0) + which = (1 << 2) | (1 << 3); + else + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + break; + /* + * Non-empty ranges overlaps if lower bound of each range is + * lower or equal to upper bound of another ranges. + */ + case RANGESTRAT_OVERLAPS: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + + /* + * If lower bound of centroid is greater than upper + * bound of argument then no overlapping ranges can be + * in 1 and 2 quadrants. + */ + if (range_cmp_bounds(typcache, ¢roidLower, + &upper) > 0) + which &= (1 << 3) | (1 << 4); + + /* + * If upper bound of centroid is lower or equal than + * lower bound of argument then no overlapping ranges + * can be in 2 and 3 quadrants. + */ + if (range_cmp_bounds(typcache, ¢roidUpper, + &lower) <= 0) + which &= (1 << 1) | (1 << 4); + } + break; + /* + * Range A is overright to range B if lower bound of A is upper + * or equal to upper bound of B. If lower bound of "centroid" is + * lower or equal to lower bound of argument then no ranges + * overright argument can be contained in quadrants 3 and 4. + */ + case RANGESTRAT_OVERRIGHT: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, ¢roidLower, &lower) <= 0) + which = (1 << 1) | (1 << 2); + else + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + break; + /* + * Range A is after range B if lower bound of A is greater than + * upper bound of B. If lower bound of "centroid" is lower + * or equal to upper bound of argument then no ranges after + * argument can be contained in quadrants 3 and 4. + */ + case RANGESTRAT_AFTER: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, ¢roidLower, &upper) <= 0) + which &= (1 << 1) | (1 << 2); + else + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + break; + /* + * Ranges are adjacent if lower bound of one range is connected + * to upper bound of another range. + */ + case RANGESTRAT_ADJACENT: + /* + * which1 is bitmask for possibility to be connected with + * lower bound of argument. which2 is bitmask for + * possibility to be connected with upper bound of + * argument. + */ + which1 = which2 = (1 >> 1) | (1 >> 2) | (1 >> 3) | (1 >> 4); + + /* Deserialize previous centroid range if present. */ + prevPresent = (in->reconstructedValue != (Datum) 0); + if (prevPresent) + { + prevCentroid = DatumGetRangeType(in->reconstructedValue); + range_deserialize(typcache, prevCentroid, &prevLower, + &prevUpper, &prevEmpty); + } + + cmp2 = range_cmp_bounds(typcache, &upper, ¢roidLower); + if (prevPresent) + { + /* Do comparison with previous centroid */ + cmp1 = range_cmp_bounds(typcache, &upper, &prevLower); + cmp3 = range_cmp_bounds(typcache, ¢roidLower, + &prevLower); + + /* + * Check if lower bound of argument is not in + * a quadrant we visit in previous step. + */ + if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0)) + which1 = 0; + } + + if (cmp2 >= 0) + which1 &= (1 >> 1) | (1 >> 2); + else if (!bounds_connected(typcache, centroidLower, upper)) + which1 &= (1 >> 3) | (1 >> 4); + + cmp2 = range_cmp_bounds(typcache, &lower, ¢roidUpper); + if (prevPresent) + { + /* Do comparison with previous centroid */ + cmp1 = range_cmp_bounds(typcache, &lower, &prevUpper); + cmp3 = range_cmp_bounds(typcache, ¢roidUpper, &prevUpper); + /* + * Check if upper bound of argument is not in + * a quadrant we visit in previous step. + */ + if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0)) + which2 = 0; + } + + if (cmp2 > 0) + which2 &= (1 >> 1) | (1 >> 4); + else if (cmp2 < 0) + which2 &= (1 >> 2) | (1 >> 3); + + which &= which1 | which2; + + needPrevious = true; + break; + /* + * Non-empty range A contains non-empty range B if lower bound + * of A is lower or equal to lower bound of range B and upper + * bound of range A is greater or equal to upper bound of range + * A. + */ + case RANGESTRAT_CONTAINS: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + /* + * If lower bound of centroid is greater than lower + * bound of argument then no ranges which contain + * argument can be in quadrants 1 and 2. + */ + if (range_cmp_bounds(typcache, ¢roidLower, + &lower) > 0) + which &= (1 << 3) | (1 << 4); + /* + * If upper bound of centroid is lower or equal to upper + * bound of argument then no ranges which contain + * argument can be in quadrants 2 and 3. + */ + if (range_cmp_bounds(typcache, ¢roidUpper, + &upper) <= 0) + which &= (1 << 1) | (1 << 4); + } + break; + case RANGESTRAT_CONTAINED_BY: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + /* + * If lower bound of centroid is lower or equal to lower + * bound of argument then no ranges which are contained + * in argument can be in quadrants 3 and 4. + */ + if (range_cmp_bounds(typcache, ¢roidLower, + &lower) <= 0) + which &= (1 << 1) | (1 << 2); + /* + * If upper bound of centroid is greater than upper + * bound of argument then no ranges which are contained + * in argument can be in quadrants 1 and 4. + */ + if (range_cmp_bounds(typcache, ¢roidUpper, + &upper) > 0) + which &= (1 << 2) | (1 << 3); + } + break; + case RANGESTRAT_CONTAINS_ELEM: + /* + * Construct bound to pass then to bound comparison + * functions + */ + lower.inclusive = true; + lower.infinite = false; + lower.lower = true; + lower.val = in->scankeys[i].sk_argument; + + upper.inclusive = true; + upper.infinite = false; + upper.lower = false; + upper.val = in->scankeys[i].sk_argument; + + which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4); + + /* + * If lower bound of centroid is greater than lower bound of + * argument then ranges containing element can't be in 1 and 2 + * quadrants. + */ + if (range_cmp_bound_values(typcache, ¢roidLower, + &lower) > 0) + which &= (1 << 3) | (1 << 4); + + /* + * If upper bound of centroid is lower or equal than upper + * bound of argument then ranges containing element can't be + * in 2 and 3 quadrants. + */ + if (range_cmp_bound_values(typcache, ¢roidUpper, + &upper) <= 0) + which &= (1 << 1) | (1 << 4); + + break; + /* + * Equal range can be only in the same quadrant where argument + * would be placed to. + */ + case RANGESTRAT_EQ: + which &= (1 << getQuadrant(typcache, centroid, range)); + break; + default: + elog(ERROR, "unrecognized range strategy: %d", strategy); + break; + } + + if (which == 0) + break; /* no need to consider remaining conditions */ + } + } + + /* We must descend into the quadrant(s) identified by which */ + out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); + if (needPrevious) + out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes); + out->nNodes = 0; + for (i = 1; i <= in->nNodes; i++) + { + if (which & (1 << i)) + { + /* Save previous prefix if needed */ + if (needPrevious) + out->reconstructedValues[out->nNodes] = RangeTypeGetDatum(centroid); + out->nodeNumbers[out->nNodes++] = i - 1; + } + } + + PG_RETURN_VOID(); + } + + /* + * Leaf consistent SP-GiST function: check leaf value against query using + * corresponding function. + */ + Datum + spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS) + { + spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0); + spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1); + bool res; + int i; + + /* all tests are exact */ + out->recheck = false; + + /* leafDatum is what it is... */ + out->leafValue = in->leafDatum; + + /* Perform the required comparison(s) */ + res = true; + for (i = 0; i < in->nkeys; i++) + { + PGFunction proc; + + /* Find the function which is corresponding to the scan strategy */ + switch (in->scankeys[i].sk_strategy) + { + case RANGESTRAT_BEFORE: + proc = range_before; + break; + case RANGESTRAT_OVERLEFT: + proc = range_overleft; + break; + case RANGESTRAT_OVERLAPS: + proc = range_overlaps; + break; + case RANGESTRAT_OVERRIGHT: + proc = range_overright; + break; + case RANGESTRAT_AFTER: + proc = range_after; + break; + case RANGESTRAT_ADJACENT: + proc = range_adjacent; + break; + case RANGESTRAT_CONTAINS: + proc = range_contains; + break; + case RANGESTRAT_CONTAINED_BY: + proc = range_contained_by; + break; + case RANGESTRAT_CONTAINS_ELEM: + proc = range_contains_elem; + break; + case RANGESTRAT_EQ: + proc = range_eq; + break; + default: + elog(ERROR, "unrecognized range strategy: %d", + in->scankeys[i].sk_strategy); + proc = InvalidOid; + break; + } + res = DatumGetBool(TrickFunctionCall2(proc, fcinfo->flinfo, + in->leafDatum, in->scankeys[i].sk_argument)); + + /* If leaf datum don't match to one query, we can don't check another */ + if (!res) + break; + } + + PG_RETURN_BOOL(res); + } *** /dev/null --- b/src/backend/utils/adt/rangetypes_spgistkd.c *************** *** 0 **** --- 1,860 ---- + /*------------------------------------------------------------------------- + * + * rangetypes_spgistkd.c + * implementation of k-d tree over ranges mapped to 2d-points for SP-GiST + * + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/utils/adt/rangetypes_spgistkd.c + * + *------------------------------------------------------------------------- + */ + + #include "postgres.h" + + #include "access/spgist.h" + #include "access/skey.h" + #include "catalog/pg_type.h" + #include "utils/builtins.h" + #include "utils/datum.h" + #include "utils/rangetypes.h" + + static int16 getNodeNumber(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst, int level); + static int bound_cmp(const void *a, const void *b, void *arg); + static bool bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper); + + /* + * Config SP-GiST interface function. + */ + Datum + spg_range_kd_config(PG_FUNCTION_ARGS) + { + /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */ + spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1); + + cfg->prefixType = ANYRANGEOID; + cfg->labelType = VOIDOID; /* we don't need node labels */ + cfg->canReturnData = true; + cfg->longValuesOK = false; + PG_RETURN_VOID(); + } + + /* + * Returns node number for k-d tree by given coordinate of split. + */ + static int16 + getNodeNumber(TypeCacheEntry *typcache, RangeType *coord, + RangeType *tst, int level) + { + RangeBound centroidLower, centroidUpper, lower, upper; + bool centroidEmpty, empty; + + range_deserialize(typcache, tst, &lower, &upper, &empty); + + /* Empty ranges are going to node 3 */ + if (empty) + return 3; + + range_deserialize(typcache, coord, ¢roidLower, ¢roidUpper, + ¢roidEmpty); + + if (level % 2 == 0) + { + /* Even level number, split by lower bound of range */ + if (range_cmp_bounds(typcache, &lower, ¢roidLower) < 0) + return 1; + else + return 2; + } + else + { + /* Odd level number, split by lower bound of range */ + if (range_cmp_bounds(typcache, &upper, ¢roidUpper) < 0) + return 1; + else + return 2; + } + + elog(ERROR, "getQuadrant: impossible case"); + return 0; + } + + + /* + * Choose SP-GiST function: choose path for addition of new range. + */ + Datum + spg_range_kd_choose(PG_FUNCTION_ARGS) + { + spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0); + spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1); + RangeType *inRange = DatumGetRangeType(in->datum), *centroid; + int16 nodeNumber; + TypeCacheEntry *typcache; + + if (in->allTheSame) + { + out->resultType = spgMatchNode; + /* nodeN will be set by core */ + out->result.matchNode.levelAdd = 0; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + PG_RETURN_VOID(); + } + + typcache = range_get_typcache(fcinfo, RangeTypeGetOid(inRange)); + + Assert(in->hasPrefix); + centroid = DatumGetRangeType(in->prefixDatum); + + /* + * Empty prefix datum divides ranges by empty sign. All empty ranges are + * taken into node 0, all non-empty ranges are taken into node 1. + */ + if (RangeIsEmpty(centroid)) + { + out->resultType = spgMatchNode; + if (RangeIsEmpty(inRange)) + out->result.matchNode.nodeN = 0; + else + out->result.matchNode.nodeN = 1; + out->result.matchNode.levelAdd = 0; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + PG_RETURN_VOID(); + } + + nodeNumber = getNodeNumber(typcache, centroid, inRange, in->level); + + /* Node for empty range is possibly not exist, create it if so */ + if (nodeNumber == 3 && in->nNodes == 2) + { + out->resultType = spgAddNode; + out->result.addNode.nodeN = nodeNumber - 1; + } + + Assert(nodeNumber <= in->nNodes); + + /* Select node */ + out->resultType = spgMatchNode; + out->result.matchNode.nodeN = nodeNumber - 1; + out->result.matchNode.levelAdd = 1; + out->result.matchNode.restDatum = RangeTypeGetDatum(inRange); + + PG_RETURN_VOID(); + } + + /* + * Bound comparison for sorting. + */ + static int + bound_cmp(const void *a, const void *b, void *arg) + { + RangeBound *ba = (RangeBound *) a; + RangeBound *bb = (RangeBound *) b; + TypeCacheEntry *typcache = (TypeCacheEntry *)arg; + + return range_cmp_bounds(typcache, ba, bb); + } + + /* + * Picksplit SP-GiST function: split ranges into nodes. Select "median" + * of bound corresponding to level number. + */ + Datum + spg_range_kd_picksplit(PG_FUNCTION_ARGS) + { + spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0); + spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1); + int i, j, nonEmptyCount; + RangeType *coord; + bool empty; + TypeCacheEntry *typcache; + + /* Use the median values of lower or upper bounds for split */ + RangeBound *bounds, otherBound; + + typcache = range_get_typcache(fcinfo, + RangeTypeGetOid(DatumGetRangeType(in->datums[0]))); + + /* Allocate memory for bounds */ + bounds = palloc(sizeof(RangeBound) * in->nTuples); + j = 0; + + /* Deserialize bounds of ranges, count non-empty ranges */ + for (i = 0; i < in->nTuples; i++) + { + if (in->level % 2 == 0) + range_deserialize(typcache, DatumGetRangeType(in->datums[i]), + &bounds[j], &otherBound, &empty); + else + range_deserialize(typcache, DatumGetRangeType(in->datums[i]), + &otherBound, &bounds[j], &empty); + + if (!empty) + j++; + } + nonEmptyCount = j; + + /* + * All the ranges are empty. We've nothing better than put all the ranges + * into node 0. Non-empty range will be routed to node 1. + */ + if (nonEmptyCount == 0) + { + out->nNodes = 2; + out->hasPrefix = true; + /* Prefix is empty */ + out->prefixDatum = RangeTypeGetDatum( + range_serialize(typcache, NULL, NULL, true)); + out->nodeLabels = NULL; + + out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples); + out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples); + + /* Place all ranges into node 0 */ + for (i = 0; i < in->nTuples; i++) + { + RangeType *range = DatumGetRangeType(in->datums[i]); + + out->leafTupleDatums[i] = RangeTypeGetDatum(range); + out->mapTuplesToNodes[i] = 0; + } + PG_RETURN_VOID(); + } + + /* Sort range bounds in order to find median */ + qsort_arg(bounds, nonEmptyCount, sizeof(RangeBound), bound_cmp, typcache); + + + otherBound.inclusive = false; + otherBound.infinite = true; + otherBound.val = PointerGetDatum(NULL); + + /* + * Construct range representing coordinate of split, another bound of this + * range is infinity for space saving. + */ + if (in->level % 2 == 0) + { + otherBound.lower = false; + coord = range_serialize(typcache, &bounds[nonEmptyCount / 2], + &otherBound, false); + } + else + { + otherBound.lower = true; + coord = range_serialize(typcache, &otherBound, + &bounds[nonEmptyCount / 2], false); + } + + + out->hasPrefix = true; + out->prefixDatum = RangeTypeGetDatum(coord); + + /* Create node for empty ranges only if it is actually needed */ + out->nNodes = (nonEmptyCount == in->nTuples) ? 2 : 3; + out->nodeLabels = NULL; /* we don't need node labels */ + + out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples); + out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples); + + /* + * Add ranges to corresponding nodes according to their position relative + * to split coordinate + */ + for (i = 0; i < in->nTuples; i++) + { + RangeType *range = DatumGetRangeType(in->datums[i]); + int16 nodeNumber = getNodeNumber(typcache, coord, range, in->level); + + out->leafTupleDatums[i] = RangeTypeGetDatum(range); + out->mapTuplesToNodes[i] = nodeNumber - 1; + } + + PG_RETURN_VOID(); + } + + /* + * Check if two bounds are "connected", i.e. there are no values which satisfy + * both bounds and there are no values between the bounds. + */ + static bool + bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper) + { + int cmp = range_cmp_bound_values(typcache, &upper, &lower); + if (cmp < 0) + { + RangeType *r; + /* in a continuous subtype, there are assumed to be points between */ + if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid)) + return false; + /* flip the inclusion flags */ + upper.inclusive = !upper.inclusive; + lower.inclusive = !lower.inclusive; + /* change upper/lower labels to avoid Assert failures */ + upper.lower = true; + lower.lower = false; + r = make_range(typcache, &upper, &lower, false); + PG_RETURN_BOOL(RangeIsEmpty(r)); + } + else if (cmp == 0) + { + PG_RETURN_BOOL(upper.inclusive != lower.inclusive); + } + else + { + PG_RETURN_BOOL(false); + } + } + + /* + * Inner consisted SP-GiST function: check which nodes are consistent with + * given set of queries. + */ + Datum + spg_range_kd_inner_consistent(PG_FUNCTION_ARGS) + { + spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0); + spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1); + RangeBound prevLower, prevUpper, coordLower, coordUpper; + RangeType *coord, *reconstructed = NULL; + bool centroidEmpty; + TypeCacheEntry *typcache; + int which, i; + bool needPrevious = false; + + Assert(in->hasPrefix); + coord = DatumGetRangeType(in->prefixDatum); + + if (in->allTheSame) + { + /* Report that all nodes should be visited */ + out->nNodes = in->nNodes; + out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); + for (i = 0; i < in->nNodes; i++) + out->nodeNumbers[i] = i; + PG_RETURN_VOID(); + } + + if (RangeIsEmpty(coord)) + { + /* + * Empty "coordinate". We can use only information about emptiness of + * ranges in nodes. + */ + Assert(in->nNodes == 2); + + /* + * Nth bit of which variable means that (N - 1)th node should be + * visited. Initially all bits are set. Bits of nodes which should be + * skipped will be unset. + */ + which = (1 << 1) | (1 << 2); + for (i = 0; i < in->nkeys; i++) + { + StrategyNumber strategy; + bool empty; + + strategy = in->scankeys[i].sk_strategy; + + /* + * The only strategy when second argument of operator is not + * range is RANGESTRAT_CONTAINS_ELEM. + */ + if (strategy != RANGESTRAT_CONTAINS_ELEM) + empty = RangeIsEmpty( + DatumGetRangeType(in->scankeys[i].sk_argument)); + + switch (strategy) + { + /* These strategies return false if any argument is empty */ + case RANGESTRAT_BEFORE: + case RANGESTRAT_OVERLEFT: + case RANGESTRAT_OVERLAPS: + case RANGESTRAT_OVERRIGHT: + case RANGESTRAT_AFTER: + case RANGESTRAT_ADJACENT: + if (empty) + which = 0; + else + which &= (1 << 2); + break; + /* + * "Empty" range is contained in any range. Non-empty ranges + * can be contained in only non-empty ranges. + */ + case RANGESTRAT_CONTAINS: + if (!empty) + which &= (1 << 2); + break; + case RANGESTRAT_CONTAINED_BY: + if (empty) + which &= (1 << 1); + break; + /* Empty range can't contain any element */ + case RANGESTRAT_CONTAINS_ELEM: + which &= (1 << 2); + break; + case RANGESTRAT_EQ: + if (empty) + which &= (1 << 1); + else + which &= (1 << 2); + break; + default: + elog(ERROR, "unrecognized range strategy: %d", strategy); + break; + } + if (which == 0) + break; /* no need to consider remaining conditions */ + } + } + else + { + + /* Coordinate is not empty, get information about it. */ + typcache = range_get_typcache(fcinfo, + RangeTypeGetOid(DatumGetRangeType(coord))); + range_deserialize(typcache, coord, &coordLower, &coordUpper, + ¢roidEmpty); + + Assert(in->nNodes == 2 || in->nNodes == 3); + + /* + * Nth bit of which variable means that (N - 1)th node (Nth quadrant) + * should be visited. Initially all bits are set. Bits of nodes which + * should be skipped will be unset. + */ + which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5); + + for (i = 0; i < in->nkeys; i++) + { + StrategyNumber strategy; + RangeBound lower, upper; + bool empty; + RangeType *range = NULL; + + strategy = in->scankeys[i].sk_strategy; + + /* + * Deserialize range if argument is range. The only strategy when + * second argument of operator is not range is + * RANGESTRAT_CONTAINS_ELEM. + */ + if (strategy != RANGESTRAT_CONTAINS_ELEM) + { + range = DatumGetRangeType(in->scankeys[i].sk_argument); + range_deserialize(typcache, range, &lower, &upper, &empty); + } + + switch (strategy) + { + bool prevEmpty, prevPresent; + RangeType *prevCentroid; + int cmp1, cmp2, cmp3; + + /* + * Range A is before range B if upper bound of A is lower than + * lower bound of B. If upper bound "coordinate" is greater + * or equal to lower bound of argument then no ranges before + * argument can be contained in node 2. + */ + case RANGESTRAT_BEFORE: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, &coordUpper, + &lower) >= 0 && in->level % 2 == 1) + which &= (1 << 1); + else + which &= (1 << 1) | (1 << 2); + break; + /* + * Range A is overleft to range B if upper bound of A is lower + * or equal to lower bound of B. If upper bound "coordinate" is + * greater to upper bound of argument then no ranges overleft + * argument can be contained in node 2. + */ + case RANGESTRAT_OVERLEFT: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, &coordUpper, + &upper) > 0 && in->level % 2 == 1) + which = (1 << 1); + else + which &= (1 << 1) | (1 << 2); + break; + /* + * Non-empty ranges overlaps if lower bound of each range is + * lower or equal to upper bound of another ranges. + */ + case RANGESTRAT_OVERLAPS: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2); + + if (in->level % 2 == 0) + { + /* + * If lower bound "coordinate" is greater than upper + * bound of argument then no overlapping ranges can + * be in node 2. + */ + if (range_cmp_bounds(typcache, &coordLower, + &upper) > 0) + which &= (1 << 1); + } + else + { + /* + * If upper bound "coordinate" is lower or equal than + * lower bound of argument then no overlapping + * ranges can be in node 1. + */ + if (range_cmp_bounds(typcache, &coordUpper, + &lower) <= 0) + which &= (1 << 2); + } + } + break; + /* + * Range A is overright to range B if lower bound of A is upper + * or equal to upper bound of B. If lower bound "coordinate" is + * lower or equal to lower bound of argument then no ranges + * overright argument can be contained in node 1. + */ + case RANGESTRAT_OVERRIGHT: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, &coordLower, + &lower) <= 0 && in->level % 2 == 0) + which = (1 << 2); + else + which &= (1 << 1) | (1 << 2); + break; + /* + * Range A is after range B if lower bound of A is greater than + * upper bound of B. If lower bound "coordinate" is lower + * or equal to upper bound of argument then no ranges after + * argument can be contained in node 1. + */ + case RANGESTRAT_AFTER: + if (empty) + which = 0; + else if (range_cmp_bounds(typcache, &coordLower, + &upper) <= 0 && in->level % 2 == 0) + which &= (1 << 2); + else + which &= (1 << 1) | (1 << 2); + break; + /* + * Ranges are adjacent if lower bound of one range is connected + * to upper bound of another range. + */ + case RANGESTRAT_ADJACENT: + /* Deserialize previous "coordinate" if present. */ + prevPresent = (in->reconstructedValue != (Datum) 0); + if (prevPresent) + { + prevCentroid = DatumGetRangeType(in->reconstructedValue); + range_deserialize(typcache, prevCentroid, &prevLower, + &prevUpper, &prevEmpty); + } + + if (in->level %2 == 0) + { + cmp2 = range_cmp_bounds(typcache, &upper, &coordLower); + if (prevPresent) + { + /* + * Do comparison with previous "coordinate" of + * lower bound. + */ + cmp1 = range_cmp_bounds(typcache, &upper, &prevLower); + cmp3 = range_cmp_bounds(typcache, &coordLower, + &prevLower); + + /* + * Check if lower bound of argument is not in + * a quadrant we visit in previous step. + */ + if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0)) + which = 0; + } + + if (cmp2 >= 0) + which &= (1 >> 2); + else if (!bounds_connected(typcache, coordLower, upper)) + which &= (1 >> 1); + } + else + { + cmp2 = range_cmp_bounds(typcache, &lower, &coordUpper); + if (prevPresent) + { + /* + * Do comparison with previous "coordinate" of + * upper bound. + */ + cmp1 = range_cmp_bounds(typcache, &lower, &prevUpper); + cmp3 = range_cmp_bounds(typcache, &coordUpper, &prevUpper); + /* + * Check if upper bound of argument is not in + * a quadrant we visit in previous step. + */ + if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0)) + which = 0; + } + + if (cmp2 > 0) + which &= (1 >> 2); + else if (cmp2 < 0) + which &= (1 >> 1); + } + + needPrevious = true; + break; + /* + * Non-empty range A contains non-empty range B if lower bound + * of A is lower or equal to lower bound of range B and upper + * bound of range A is greater or equal to upper bound of range + * A. + */ + case RANGESTRAT_CONTAINS: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2); + if (in->level % 2 == 0) + { + /* + * If lower bound "coordinate" is greater than lower + * bound of argument then no ranges which contain + * argument can be in node 2. + */ + if (range_cmp_bounds(typcache, &coordLower, + &lower) > 0) + which &= (1 << 1); + } + else + { + /* + * If upper bound "coordinate" is lower or equal to + * upper bound of argument then no ranges which + * contain argument can be in node 1. + */ + if (range_cmp_bounds(typcache, &coordUpper, + &upper) <= 0) + which &= (1 << 2); + } + } + break; + case RANGESTRAT_CONTAINED_BY: + if (empty) + which = 0; + else + { + which &= (1 << 1) | (1 << 2); + if (in->level % 2 == 0) + { + /* + * If lower bound "coordinate" is lower or equal to + * lower bound of argument then no ranges which are + * contained in argument can be in node 1. + */ + if (range_cmp_bounds(typcache, &coordLower, + &lower) <= 0) + which &= (1 << 2); + } + else + { + /* + * If upper bound "coordinate" is greater than upper + * bound of argument then no ranges which are + * contained in argument can be in node 2. + */ + if (range_cmp_bounds(typcache, &coordUpper, + &upper) > 0) + which &= (1 << 1); + } + } + break; + case RANGESTRAT_CONTAINS_ELEM: + which &= (1 << 1) | (1 << 2); + + if (in->level % 2 == 0) + { + /* + * Construct bound to pass then to bound comparison + * functions + */ + lower.inclusive = true; + lower.infinite = false; + lower.lower = true; + lower.val = in->scankeys[i].sk_argument; + + /* + * If lower bound "coordinate" is greater than element + * then ranges containing element can't be in node 2. + */ + if (range_cmp_bound_values(typcache, &coordLower, + &lower) > 0) + which &= (1 << 1); + } + else + { + /* + * Construct bound to pass then to bound comparison + * functions + */ + upper.inclusive = true; + upper.infinite = false; + upper.lower = false; + upper.val = in->scankeys[i].sk_argument; + + /* + * If upper bound "coordinate" is lower or equal than + * element then ranges containing element can't be in + * node 1. + */ + if (range_cmp_bound_values(typcache, &coordUpper, + &upper) <= 0) + which &= (1 << 2); + } + + break; + /* + * Equal range can be only in the same node where argument + * would be placed to. + */ + case RANGESTRAT_EQ: + which &= (1 << getNodeNumber(typcache, coord, range, + in->level)); + break; + default: + elog(ERROR, "unrecognized range strategy: %d", strategy); + break; + } + + if (which == 0) + break; /* no need to consider remaining conditions */ + } + } + + /* We must descend into the node(s) identified by which */ + out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); + out->levelAdds = (int *) palloc(sizeof(int) * in->nNodes); + + /* Need to save this coordinate in reconstructed value for next checks? */ + if (needPrevious) + { + out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes); + if (in->level == 0) + { + reconstructed = coord; + } + else + { + /* Replace corresponding bound of current reconstructed value*/ + if (in->level % 2 == 0) + reconstructed = range_serialize(typcache, &coordLower, + &prevUpper, false); + else + reconstructed = range_serialize(typcache, &coordUpper, + &prevLower, false); + } + } + out->nNodes = 0; + for (i = 1; i <= in->nNodes; i++) + { + if (which & (1 << i)) + { + /* Save this "coordinate" if needed */ + if (needPrevious) + out->reconstructedValues[out->nNodes] = + RangeTypeGetDatum(reconstructed); + out->nodeNumbers[out->nNodes++] = i - 1; + out->levelAdds[out->nNodes] = RangeIsEmpty(coord) ? 0 : 1; + } + } + + PG_RETURN_VOID(); + } + + /* + * Leaf consistent SP-GiST function: check leaf value against query using + * corresponding function. + */ + Datum + spg_range_kd_leaf_consistent(PG_FUNCTION_ARGS) + { + spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0); + spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1); + bool res; + int i; + + /* all tests are exact */ + out->recheck = false; + + /* leafDatum is what it is... */ + out->leafValue = in->leafDatum; + + /* Perform the required comparison(s) */ + res = true; + for (i = 0; i < in->nkeys; i++) + { + PGFunction proc; + + /* Find the function which is corresponding to the scan strategy */ + switch (in->scankeys[i].sk_strategy) + { + case RANGESTRAT_BEFORE: + proc = range_before; + break; + case RANGESTRAT_OVERLEFT: + proc = range_overleft; + break; + case RANGESTRAT_OVERLAPS: + proc = range_overlaps; + break; + case RANGESTRAT_OVERRIGHT: + proc = range_overright; + break; + case RANGESTRAT_AFTER: + proc = range_after; + break; + case RANGESTRAT_ADJACENT: + proc = range_adjacent; + break; + case RANGESTRAT_CONTAINS: + proc = range_contains; + break; + case RANGESTRAT_CONTAINED_BY: + proc = range_contained_by; + break; + case RANGESTRAT_CONTAINS_ELEM: + proc = range_contains_elem; + break; + case RANGESTRAT_EQ: + proc = range_eq; + break; + default: + elog(ERROR, "unrecognized range strategy: %d", + in->scankeys[i].sk_strategy); + proc = InvalidOid; + break; + } + res = DatumGetBool(TrickFunctionCall2(proc, fcinfo->flinfo, + in->leafDatum, in->scankeys[i].sk_argument)); + + /* If leaf datum don't match to one query, we can don't check another */ + if (!res) + break; + } + + PG_RETURN_BOOL(res); + } *** a/src/include/catalog/pg_amop.h --- b/src/include/catalog/pg_amop.h *************** *** 734,739 **** DATA(insert ( 3919 3831 3831 8 s 3892 783 0 )); --- 734,750 ---- DATA(insert ( 3919 3831 2283 16 s 3889 783 0 )); DATA(insert ( 3919 3831 3831 18 s 3882 783 0 )); + DATA(insert ( 3457 3831 3831 1 s 3893 783 0 )); + DATA(insert ( 3457 3831 3831 2 s 3895 783 0 )); + DATA(insert ( 3457 3831 3831 3 s 3888 783 0 )); + DATA(insert ( 3457 3831 3831 4 s 3896 783 0 )); + DATA(insert ( 3457 3831 3831 5 s 3894 783 0 )); + DATA(insert ( 3457 3831 3831 6 s 3897 783 0 )); + DATA(insert ( 3457 3831 3831 7 s 3890 783 0 )); + DATA(insert ( 3457 3831 3831 8 s 3892 783 0 )); + DATA(insert ( 3457 3831 2283 16 s 3889 783 0 )); + DATA(insert ( 3457 3831 3831 18 s 3882 783 0 )); + /* * SP-GiST quad_point_ops */ *************** *** 767,770 **** DATA(insert ( 4017 25 25 12 s 665 4000 0 )); --- 778,805 ---- DATA(insert ( 4017 25 25 14 s 667 4000 0 )); DATA(insert ( 4017 25 25 15 s 666 4000 0 )); + /* + * SP-GiST range_ops + */ + DATA(insert ( 3474 3831 3831 1 s 3893 4000 0 )); + DATA(insert ( 3474 3831 3831 2 s 3895 4000 0 )); + DATA(insert ( 3474 3831 3831 3 s 3888 4000 0 )); + DATA(insert ( 3474 3831 3831 4 s 3896 4000 0 )); + DATA(insert ( 3474 3831 3831 5 s 3894 4000 0 )); + DATA(insert ( 3474 3831 3831 6 s 3897 4000 0 )); + DATA(insert ( 3474 3831 3831 7 s 3890 4000 0 )); + DATA(insert ( 3474 3831 3831 8 s 3892 4000 0 )); + DATA(insert ( 3474 3831 2283 16 s 3889 4000 0 )); + DATA(insert ( 3474 3831 3831 18 s 3882 4000 0 )); + DATA(insert ( 3475 3831 3831 1 s 3893 4000 0 )); + DATA(insert ( 3475 3831 3831 2 s 3895 4000 0 )); + DATA(insert ( 3475 3831 3831 3 s 3888 4000 0 )); + DATA(insert ( 3475 3831 3831 4 s 3896 4000 0 )); + DATA(insert ( 3475 3831 3831 5 s 3894 4000 0 )); + DATA(insert ( 3475 3831 3831 6 s 3897 4000 0 )); + DATA(insert ( 3475 3831 3831 7 s 3890 4000 0 )); + DATA(insert ( 3475 3831 3831 8 s 3892 4000 0 )); + DATA(insert ( 3475 3831 2283 16 s 3889 4000 0 )); + DATA(insert ( 3475 3831 3831 18 s 3882 4000 0 )); + #endif /* PG_AMOP_H */ *** a/src/include/catalog/pg_amproc.h --- b/src/include/catalog/pg_amproc.h *************** *** 355,360 **** DATA(insert ( 3919 3831 3831 4 3878 )); --- 355,367 ---- DATA(insert ( 3919 3831 3831 5 3879 )); DATA(insert ( 3919 3831 3831 6 3880 )); DATA(insert ( 3919 3831 3831 7 3881 )); + DATA(insert ( 3457 3831 3831 1 3458 )); + DATA(insert ( 3457 3831 3831 2 3459 )); + DATA(insert ( 3457 3831 3831 3 3460 )); + DATA(insert ( 3457 3831 3831 4 3461 )); + DATA(insert ( 3457 3831 3831 5 3462 )); + DATA(insert ( 3457 3831 3831 6 3463 )); + DATA(insert ( 3457 3831 3831 7 3464 )); /* sp-gist */ *************** *** 373,377 **** DATA(insert ( 4017 25 25 2 4028 )); --- 380,394 ---- DATA(insert ( 4017 25 25 3 4029 )); DATA(insert ( 4017 25 25 4 4030 )); DATA(insert ( 4017 25 25 5 4031 )); + DATA(insert ( 3474 3831 3831 1 3469 )); + DATA(insert ( 3474 3831 3831 2 3470 )); + DATA(insert ( 3474 3831 3831 3 3471 )); + DATA(insert ( 3474 3831 3831 4 3472 )); + DATA(insert ( 3474 3831 3831 5 3473 )); + DATA(insert ( 3475 3831 3831 1 3476 )); + DATA(insert ( 3475 3831 3831 2 3477 )); + DATA(insert ( 3475 3831 3831 3 3478 )); + DATA(insert ( 3475 3831 3831 4 3479 )); + DATA(insert ( 3475 3831 3831 5 3480 )); #endif /* PG_AMPROC_H */ *** a/src/include/catalog/pg_opclass.h --- b/src/include/catalog/pg_opclass.h *************** *** 223,228 **** DATA(insert ( 783 tsquery_ops PGNSP PGUID 3702 3615 t 20 )); --- 223,231 ---- DATA(insert ( 403 range_ops PGNSP PGUID 3901 3831 t 0 )); DATA(insert ( 405 range_ops PGNSP PGUID 3903 3831 t 0 )); DATA(insert ( 783 range_ops PGNSP PGUID 3919 3831 t 0 )); + DATA(insert ( 783 range_ops2 PGNSP PGUID 3457 3831 f 3465 )); + DATA(insert ( 4000 range_ops_quad PGNSP PGUID 3474 3831 t 0 )); + DATA(insert ( 4000 range_ops_kd PGNSP PGUID 3475 3831 f 0 )); DATA(insert ( 4000 quad_point_ops PGNSP PGUID 4015 600 t 0 )); DATA(insert ( 4000 kd_point_ops PGNSP PGUID 4016 600 f 0 )); DATA(insert ( 4000 text_ops PGNSP PGUID 4017 25 t 0 )); *** a/src/include/catalog/pg_opfamily.h --- b/src/include/catalog/pg_opfamily.h *************** *** 142,147 **** DATA(insert OID = 3702 ( 783 tsquery_ops PGNSP PGUID )); --- 142,150 ---- DATA(insert OID = 3901 ( 403 range_ops PGNSP PGUID )); DATA(insert OID = 3903 ( 405 range_ops PGNSP PGUID )); DATA(insert OID = 3919 ( 783 range_ops PGNSP PGUID )); + DATA(insert OID = 3457 ( 783 range_ops2 PGNSP PGUID )); + DATA(insert OID = 3474 ( 4000 range_ops_quad PGNSP PGUID )); + DATA(insert OID = 3475 ( 4000 range_ops_kd PGNSP PGUID )); DATA(insert OID = 4015 ( 4000 quad_point_ops PGNSP PGUID )); DATA(insert OID = 4016 ( 4000 kd_point_ops PGNSP PGUID )); DATA(insert OID = 4017 ( 4000 text_ops PGNSP PGUID )); *** a/src/include/catalog/pg_proc.h --- b/src/include/catalog/pg_proc.h *************** *** 4165,4170 **** DATA(insert OID = 3646 ( gtsvectorin PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 --- 4165,4174 ---- DESCR("I/O"); DATA(insert OID = 3647 ( gtsvectorout PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2275 "3642" _null_ _null_ _null_ _null_ gtsvectorout _null_ _null_ _null_ )); DESCR("I/O"); + DATA(insert OID = 3467 ( grange_in PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 3465 "2275" _null_ _null_ _null_ _null_ grange_in _null_ _null_ _null_ )); + DESCR("I/O"); + DATA(insert OID = 3468 ( grange_out PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2275 "3465" _null_ _null_ _null_ _null_ grange_out _null_ _null_ _null_ )); + DESCR("I/O"); DATA(insert OID = 3616 ( tsvector_lt PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "3614 3614" _null_ _null_ _null_ _null_ tsvector_lt _null_ _null_ _null_ )); DATA(insert OID = 3617 ( tsvector_le PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "3614 3614" _null_ _null_ _null_ _null_ tsvector_le _null_ _null_ _null_ )); *************** *** 4532,4537 **** DATA(insert OID = 3880 ( range_gist_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t --- 4536,4555 ---- DESCR("GiST support"); DATA(insert OID = 3881 ( range_gist_same PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "3831 3831 2281" _null_ _null_ _null_ _null_ range_gist_same _null_ _null_ _null_ )); DESCR("GiST support"); + DATA(insert OID = 3458 ( range_gist2_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 5 0 16 "2281 3831 23 26 2281" _null_ _null_ _null_ _null_ range_gist2_consistent _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3459 ( range_gist2_union PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ range_gist2_union _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3460 ( range_gist2_compress PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ range_gist2_compress _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3461 ( range_gist2_decompress PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ range_gist2_decompress _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3462 ( range_gist2_penalty PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "2281 2281 2281" _null_ _null_ _null_ _null_ range_gist2_penalty _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3463 ( range_gist2_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ range_gist2_picksplit _null_ _null_ _null_ )); + DESCR("GiST support"); + DATA(insert OID = 3464 ( range_gist2_same PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "3831 3831 2281" _null_ _null_ _null_ _null_ range_gist2_same _null_ _null_ _null_ )); + DESCR("GiST support"); DATA(insert OID = 3902 ( hash_range PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 23 "3831" _null_ _null_ _null_ _null_ hash_range _null_ _null_ _null_ )); DESCR("hash a range"); DATA(insert OID = 3916 ( range_typanalyze PGNSP PGUID 12 1 0 0 0 f f f f t f s 1 0 16 "2281" _null_ _null_ _null_ _null_ range_typanalyze _null_ _null_ _null_ )); *************** *** 4645,4650 **** DESCR("SP-GiST support for suffix tree over text"); --- 4663,4689 ---- DATA(insert OID = 4031 ( spg_text_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_text_leaf_consistent _null_ _null_ _null_ )); DESCR("SP-GiST support for suffix tree over text"); + DATA(insert OID = 3469 ( spg_range_quad_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_config _null_ _null_ _null_ )); + DESCR("SP-GiST support for quad tree over range"); + DATA(insert OID = 3470 ( spg_range_quad_choose PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_choose _null_ _null_ _null_ )); + DESCR("SP-GiST support for quad tree over range"); + DATA(insert OID = 3471 ( spg_range_quad_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_picksplit _null_ _null_ _null_ )); + DESCR("SP-GiST support for quad tree over range"); + DATA(insert OID = 3472 ( spg_range_quad_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_inner_consistent _null_ _null_ _null_ )); + DESCR("SP-GiST support for quad tree over range"); + DATA(insert OID = 3473 ( spg_range_quad_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_leaf_consistent _null_ _null_ _null_ )); + DESCR("SP-GiST support for quad tree over range"); + DATA(insert OID = 3476 ( spg_range_kd_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_kd_config _null_ _null_ _null_ )); + DESCR("SP-GiST support for k-d tree over range"); + DATA(insert OID = 3477 ( spg_range_kd_choose PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_kd_choose _null_ _null_ _null_ )); + DESCR("SP-GiST support for k-d tree over range"); + DATA(insert OID = 3478 ( spg_range_kd_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_kd_picksplit _null_ _null_ _null_ )); + DESCR("SP-GiST support for k-d tree over range"); + DATA(insert OID = 3479 ( spg_range_kd_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_kd_inner_consistent _null_ _null_ _null_ )); + DESCR("SP-GiST support for k-d tree over range"); + DATA(insert OID = 3480 ( spg_range_kd_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_range_kd_leaf_consistent _null_ _null_ _null_ )); + DESCR("SP-GiST support for k-d tree over range"); + /* * Symbolic values for provolatile column: these indicate whether the result *** a/src/include/catalog/pg_type.h --- b/src/include/catalog/pg_type.h *************** *** 582,587 **** DESCR("text representation for text search"); --- 582,590 ---- DATA(insert OID = 3642 ( gtsvector PGNSP PGUID -1 f b U f t \054 0 0 3644 gtsvectorin gtsvectorout - - - - - i p f 0 -1 0 0 _null_ _null_ _null_ )); DESCR("GiST index internal text representation for text search"); #define GTSVECTOROID 3642 + DATA(insert OID = 3465 ( grange PGNSP PGUID -1 f b U f t \054 0 0 3466 grange_in grange_out - - - - - i p f 0 -1 0 0 _null_ _null_ _null_ )); + DESCR("GiST index key type for ranges"); + #define GRANGEOID 3465 DATA(insert OID = 3615 ( tsquery PGNSP PGUID -1 f b U f t \054 0 0 3645 tsqueryin tsqueryout tsqueryrecv tsquerysend - - - i p f 0 -1 0 0 _null_ _null_ _null_ )); DESCR("query representation for text search"); #define TSQUERYOID 3615 *************** *** 594,599 **** DESCR("registered text search dictionary"); --- 597,603 ---- DATA(insert OID = 3643 ( _tsvector PGNSP PGUID -1 f b A f t \054 0 3614 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); DATA(insert OID = 3644 ( _gtsvector PGNSP PGUID -1 f b A f t \054 0 3642 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); + DATA(insert OID = 3466 ( _grange PGNSP PGUID -1 f b A f t \054 0 3465 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); DATA(insert OID = 3645 ( _tsquery PGNSP PGUID -1 f b A f t \054 0 3615 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); DATA(insert OID = 3735 ( _regconfig PGNSP PGUID -1 f b A f t \054 0 3734 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); DATA(insert OID = 3770 ( _regdictionary PGNSP PGUID -1 f b A f t \054 0 3769 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ )); *** a/src/include/utils/rangetypes.h --- b/src/include/utils/rangetypes.h *************** *** 15,20 **** --- 15,21 ---- #define RANGETYPES_H #include "utils/typcache.h" + #include "utils/lsyscache.h" /* *************** *** 65,70 **** typedef struct --- 66,82 ---- bool lower; /* this is the lower (vs upper) bound */ } RangeBound; + #define RANGE_EMPTY_LITERAL "empty" + + /* fn_extra cache entry for one of the range I/O functions */ + typedef struct RangeIOData + { + TypeCacheEntry *typcache; /* range type's typcache entry */ + Oid typiofunc; /* element type's I/O function */ + Oid typioparam; /* element type's I/O parameter */ + FmgrInfo proc; /* lookup result for typiofunc */ + } RangeIOData; + /* * fmgr macros for range type objects */ *************** *** 75,80 **** typedef struct --- 87,105 ---- #define PG_GETARG_RANGE_COPY(n) DatumGetRangeTypeCopy(PG_GETARG_DATUM(n)) #define PG_RETURN_RANGE(x) return RangeTypeGetDatum(x) + /* Operator strategy numbers used in the GiST range opclass */ + /* Numbers are chosen to match up operator names with existing usages */ + #define RANGESTRAT_BEFORE 1 + #define RANGESTRAT_OVERLEFT 2 + #define RANGESTRAT_OVERLAPS 3 + #define RANGESTRAT_OVERRIGHT 4 + #define RANGESTRAT_AFTER 5 + #define RANGESTRAT_ADJACENT 6 + #define RANGESTRAT_CONTAINS 7 + #define RANGESTRAT_CONTAINED_BY 8 + #define RANGESTRAT_CONTAINS_ELEM 16 + #define RANGESTRAT_EQ 18 + /* * prototypes for functions defined in rangetypes.c */ *************** *** 84,89 **** extern Datum range_in(PG_FUNCTION_ARGS); --- 109,123 ---- extern Datum range_out(PG_FUNCTION_ARGS); extern Datum range_recv(PG_FUNCTION_ARGS); extern Datum range_send(PG_FUNCTION_ARGS); + extern Size datum_compute_size(Size data_length, Datum val, bool typbyval, + char typalign, int16 typlen, char typstorage); + extern Pointer datum_write(Pointer ptr, Datum datum, bool typbyval, + char typalign, int16 typlen, char typstorage); + extern RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, + IOFuncSelector func); + char *range_bound_escape(const char *value); + + /* constructors */ extern Datum range_constructor2(PG_FUNCTION_ARGS); *************** *** 165,171 **** extern int range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1, --- 199,223 ---- RangeBound *b2); extern RangeType *make_empty_range(TypeCacheEntry *typcache); + /* Operator strategy numbers used in the GiST range opclass */ + /* Numbers are chosen to match up operator names with existing usages */ + #define RANGESTRAT_BEFORE 1 + #define RANGESTRAT_OVERLEFT 2 + #define RANGESTRAT_OVERLAPS 3 + #define RANGESTRAT_OVERRIGHT 4 + #define RANGESTRAT_AFTER 5 + #define RANGESTRAT_ADJACENT 6 + #define RANGESTRAT_CONTAINS 7 + #define RANGESTRAT_CONTAINED_BY 8 + #define RANGESTRAT_CONTAINS_ELEM 16 + #define RANGESTRAT_EQ 18 + + Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2); + + /* GiST support (in rangetypes_gist.c) */ + extern Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2); + extern Datum range_gist_consistent(PG_FUNCTION_ARGS); extern Datum range_gist_compress(PG_FUNCTION_ARGS); extern Datum range_gist_decompress(PG_FUNCTION_ARGS); *************** *** 174,177 **** extern Datum range_gist_penalty(PG_FUNCTION_ARGS); --- 226,246 ---- extern Datum range_gist_picksplit(PG_FUNCTION_ARGS); extern Datum range_gist_same(PG_FUNCTION_ARGS); + /* GiST support (in rangetypes_gist2.c) */ + extern Datum grange_in(PG_FUNCTION_ARGS); + extern Datum grange_out(PG_FUNCTION_ARGS); + extern Datum range_gist2_consistent(PG_FUNCTION_ARGS); + extern Datum range_gist2_compress(PG_FUNCTION_ARGS); + extern Datum range_gist2_decompress(PG_FUNCTION_ARGS); + extern Datum range_gist2_union(PG_FUNCTION_ARGS); + extern Datum range_gist2_penalty(PG_FUNCTION_ARGS); + extern Datum range_gist2_picksplit(PG_FUNCTION_ARGS); + extern Datum range_gist2_same(PG_FUNCTION_ARGS); + /* SP-GiST k-d tree support (in rangetypes_spgistkd.c */ + Datum spg_range_kd_config(PG_FUNCTION_ARGS); + Datum spg_range_kd_choose(PG_FUNCTION_ARGS); + Datum spg_range_kd_picksplit(PG_FUNCTION_ARGS); + Datum spg_range_kd_inner_consistent(PG_FUNCTION_ARGS); + Datum spg_range_kd_leaf_consistent(PG_FUNCTION_ARGS); + #endif /* RANGETYPES_H */ *** a/src/test/regress/expected/opr_sanity.out --- b/src/test/regress/expected/opr_sanity.out *************** *** 1068,1079 **** ORDER BY 1, 2, 3; --- 1068,1084 ---- 2742 | 4 | = 4000 | 1 | << 4000 | 1 | ~<~ + 4000 | 2 | &< 4000 | 2 | ~<=~ + 4000 | 3 | && 4000 | 3 | = + 4000 | 4 | &> 4000 | 4 | ~>=~ 4000 | 5 | >> 4000 | 5 | ~>~ + 4000 | 6 | -|- 4000 | 6 | ~= + 4000 | 7 | @> 4000 | 8 | <@ 4000 | 10 | <^ 4000 | 11 | < *************** *** 1081,1087 **** ORDER BY 1, 2, 3; 4000 | 12 | <= 4000 | 14 | >= 4000 | 15 | > ! (55 rows) -- Check that all opclass search operators have selectivity estimators. -- This is not absolutely required, but it seems a reasonable thing --- 1086,1094 ---- 4000 | 12 | <= 4000 | 14 | >= 4000 | 15 | > ! 4000 | 16 | @> ! 4000 | 18 | = ! (62 rows) -- Check that all opclass search operators have selectivity estimators. -- This is not absolutely required, but it seems a reasonable thing