PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
rangetypes_gist.c File Reference
#include "postgres.h"
#include "access/gist.h"
#include "access/stratnum.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/rangetypes.h"
Include dependency graph for rangetypes_gist.c:

Go to the source code of this file.

Data Structures

struct  SingleBoundSortItem
 
struct  ConsiderSplitContext
 
struct  NonEmptyRange
 
struct  CommonEntry
 

Macros

#define CLS_NORMAL   0 /* Ordinary finite range (no bits set) */
 
#define CLS_LOWER_INF   1 /* Lower bound is infinity */
 
#define CLS_UPPER_INF   2 /* Upper bound is infinity */
 
#define CLS_CONTAIN_EMPTY   4 /* Contains underlying empty ranges */
 
#define CLS_EMPTY   8 /* Special class for empty ranges */
 
#define CLS_COUNT
 
#define LIMIT_RATIO   0.3
 
#define INFINITE_BOUND_PENALTY   2.0
 
#define CONTAIN_EMPTY_PENALTY   1.0
 
#define DEFAULT_SUBTYPE_DIFF_PENALTY   1.0
 
#define PLACE_LEFT(range, off)
 
#define PLACE_RIGHT(range, off)
 
#define rangeCopy(r)
 

Enumerations

enum  SplitLR { SPLIT_LEFT = 0, SPLIT_RIGHT }
 

Functions

static RangeTyperange_super_union (TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 
static bool range_gist_consistent_int (TypeCacheEntry *typcache, StrategyNumber strategy, RangeType *key, Datum query)
 
static bool range_gist_consistent_leaf (TypeCacheEntry *typcache, StrategyNumber strategy, RangeType *key, Datum query)
 
static void range_gist_fallback_split (TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v)
 
static void range_gist_class_split (TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, SplitLR *classes_groups)
 
static void range_gist_single_sorting_split (TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, bool use_upper_bound)
 
static void range_gist_double_sorting_split (TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v)
 
static void range_gist_consider_split (ConsiderSplitContext *context, RangeBound *right_lower, int min_left_count, RangeBound *left_upper, int max_left_count)
 
static int get_gist_range_class (RangeType *range)
 
static int single_bound_cmp (const void *a, const void *b, void *arg)
 
static int interval_cmp_lower (const void *a, const void *b, void *arg)
 
static int interval_cmp_upper (const void *a, const void *b, void *arg)
 
static int common_entry_cmp (const void *i1, const void *i2)
 
static float8 call_subtype_diff (TypeCacheEntry *typcache, Datum val1, Datum val2)
 
Datum range_gist_consistent (PG_FUNCTION_ARGS)
 
Datum range_gist_union (PG_FUNCTION_ARGS)
 
Datum range_gist_compress (PG_FUNCTION_ARGS)
 
Datum range_gist_decompress (PG_FUNCTION_ARGS)
 
Datum range_gist_fetch (PG_FUNCTION_ARGS)
 
Datum range_gist_penalty (PG_FUNCTION_ARGS)
 
Datum range_gist_picksplit (PG_FUNCTION_ARGS)
 
Datum range_gist_same (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

#define CLS_CONTAIN_EMPTY   4 /* Contains underlying empty ranges */

Definition at line 32 of file rangetypes_gist.c.

Referenced by get_gist_range_class(), and range_gist_picksplit().

#define CLS_COUNT
Value:
9 /* # of classes; includes all combinations of
* properties. CLS_EMPTY doesn't combine with
* anything else, so it's only 2^3 + 1. */

Definition at line 35 of file rangetypes_gist.c.

Referenced by range_gist_picksplit().

#define CLS_EMPTY   8 /* Special class for empty ranges */

Definition at line 33 of file rangetypes_gist.c.

Referenced by get_gist_range_class(), and range_gist_picksplit().

#define CLS_LOWER_INF   1 /* Lower bound is infinity */

Definition at line 30 of file rangetypes_gist.c.

Referenced by get_gist_range_class(), and range_gist_picksplit().

#define CLS_NORMAL   0 /* Ordinary finite range (no bits set) */

Definition at line 29 of file rangetypes_gist.c.

Referenced by range_gist_picksplit().

#define CLS_UPPER_INF   2 /* Upper bound is infinity */

Definition at line 31 of file rangetypes_gist.c.

Referenced by get_gist_range_class(), and range_gist_picksplit().

#define CONTAIN_EMPTY_PENALTY   1.0

Definition at line 48 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

#define DEFAULT_SUBTYPE_DIFF_PENALTY   1.0

Definition at line 49 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

#define INFINITE_BOUND_PENALTY   2.0

Definition at line 47 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

#define LIMIT_RATIO   0.3

Definition at line 44 of file rangetypes_gist.c.

Referenced by range_gist_consider_split().

#define PLACE_LEFT (   range,
  off 
)
Value:
do { \
if (v->spl_nleft > 0) \
left_range = range_super_union(typcache, left_range, range); \
else \
left_range = (range); \
v->spl_left[v->spl_nleft++] = (off); \
} while(0)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
static RangeType * range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)

Definition at line 113 of file rangetypes_gist.c.

Referenced by range_gist_class_split(), range_gist_double_sorting_split(), range_gist_fallback_split(), and range_gist_single_sorting_split().

#define PLACE_RIGHT (   range,
  off 
)
Value:
do { \
if (v->spl_nright > 0) \
right_range = range_super_union(typcache, right_range, range); \
else \
right_range = (range); \
v->spl_right[v->spl_nright++] = (off); \
} while(0)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
static RangeType * range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)

Definition at line 122 of file rangetypes_gist.c.

Referenced by range_gist_class_split(), range_gist_double_sorting_split(), range_gist_fallback_split(), and range_gist_single_sorting_split().

#define rangeCopy (   r)
Value:
false, -1)))
#define PointerGetDatum(X)
Definition: postgres.h:564
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
#define DatumGetPointer(X)
Definition: postgres.h:557

Definition at line 132 of file rangetypes_gist.c.

Referenced by range_super_union().

Enumeration Type Documentation

enum SplitLR
Enumerator
SPLIT_LEFT 
SPLIT_RIGHT 

Definition at line 61 of file rangetypes_gist.c.

62 {
63  SPLIT_LEFT = 0, /* makes initialization to SPLIT_LEFT easier */
65 } SplitLR;
SplitLR

Function Documentation

static float8 call_subtype_diff ( TypeCacheEntry typcache,
Datum  val1,
Datum  val2 
)
static

Definition at line 1539 of file rangetypes_gist.c.

References DatumGetFloat8, FunctionCall2Coll(), TypeCacheEntry::rng_collation, TypeCacheEntry::rng_subdiff_finfo, and value.

Referenced by range_gist_consider_split(), range_gist_double_sorting_split(), and range_gist_penalty().

1540 {
1541  float8 value;
1542 
1544  typcache->rng_collation,
1545  val1, val2));
1546  /* Cope with buggy subtype_diff function by returning zero */
1547  if (value >= 0.0)
1548  return value;
1549  return 0.0;
1550 }
static struct @76 value
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1306
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:88
double float8
Definition: c.h:378
#define DatumGetFloat8(X)
Definition: postgres.h:736
Oid rng_collation
Definition: typcache.h:85
static int common_entry_cmp ( const void *  i1,
const void *  i2 
)
static

Definition at line 1521 of file rangetypes_gist.c.

Referenced by range_gist_double_sorting_split().

1522 {
1523  double delta1 = ((CommonEntry *) i1)->delta;
1524  double delta2 = ((CommonEntry *) i2)->delta;
1525 
1526  if (delta1 < delta2)
1527  return -1;
1528  else if (delta1 > delta2)
1529  return 1;
1530  else
1531  return 0;
1532 }
static int get_gist_range_class ( RangeType range)
static

Definition at line 1455 of file rangetypes_gist.c.

References CLS_CONTAIN_EMPTY, CLS_EMPTY, CLS_LOWER_INF, CLS_UPPER_INF, RANGE_CONTAIN_EMPTY, RANGE_EMPTY, range_get_flags(), RANGE_LB_INF, and RANGE_UB_INF.

Referenced by range_gist_picksplit().

1456 {
1457  int classNumber;
1458  char flags;
1459 
1460  flags = range_get_flags(range);
1461  if (flags & RANGE_EMPTY)
1462  {
1463  classNumber = CLS_EMPTY;
1464  }
1465  else
1466  {
1467  classNumber = 0;
1468  if (flags & RANGE_LB_INF)
1469  classNumber |= CLS_LOWER_INF;
1470  if (flags & RANGE_UB_INF)
1471  classNumber |= CLS_UPPER_INF;
1472  if (flags & RANGE_CONTAIN_EMPTY)
1473  classNumber |= CLS_CONTAIN_EMPTY;
1474  }
1475  return classNumber;
1476 }
#define CLS_EMPTY
#define RANGE_EMPTY
Definition: rangetypes.h:36
#define RANGE_LB_INF
Definition: rangetypes.h:39
#define CLS_CONTAIN_EMPTY
#define CLS_LOWER_INF
#define RANGE_CONTAIN_EMPTY
Definition: rangetypes.h:43
#define CLS_UPPER_INF
#define RANGE_UB_INF
Definition: rangetypes.h:40
char range_get_flags(RangeType *range)
Definition: rangetypes.c:1699
static int interval_cmp_lower ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1495 of file rangetypes_gist.c.

References NonEmptyRange::lower, and range_cmp_bounds().

Referenced by range_gist_double_sorting_split().

1496 {
1497  NonEmptyRange *i1 = (NonEmptyRange *) a;
1498  NonEmptyRange *i2 = (NonEmptyRange *) b;
1499  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1500 
1501  return range_cmp_bounds(typcache, &i1->lower, &i2->lower);
1502 }
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
RangeBound lower
void * arg
static int interval_cmp_upper ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1508 of file rangetypes_gist.c.

References range_cmp_bounds(), and NonEmptyRange::upper.

Referenced by range_gist_double_sorting_split().

1509 {
1510  NonEmptyRange *i1 = (NonEmptyRange *) a;
1511  NonEmptyRange *i2 = (NonEmptyRange *) b;
1512  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1513 
1514  return range_cmp_bounds(typcache, &i1->upper, &i2->upper);
1515 }
RangeBound upper
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
void * arg
static void range_gist_class_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v,
SplitLR classes_groups 
)
static

Definition at line 938 of file rangetypes_gist.c.

References Assert, DatumGetRangeType, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, NULL, OffsetNumberNext, PLACE_LEFT, PLACE_RIGHT, range(), RangeTypeGetDatum, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, SPLIT_LEFT, SPLIT_RIGHT, and GistEntryVector::vector.

Referenced by range_gist_picksplit().

942 {
943  RangeType *left_range = NULL;
944  RangeType *right_range = NULL;
945  OffsetNumber i,
946  maxoff;
947 
948  maxoff = entryvec->n - 1;
949 
950  v->spl_nleft = 0;
951  v->spl_nright = 0;
952  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
953  {
954  RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
955  int class;
956 
957  /* Get class of range */
958  class = get_gist_range_class(range);
959 
960  /* Place range to appropriate page */
961  if (classes_groups[class] == SPLIT_LEFT)
962  PLACE_LEFT(range, i);
963  else
964  {
965  Assert(classes_groups[class] == SPLIT_RIGHT);
966  PLACE_RIGHT(range, i);
967  }
968  }
969 
970  v->spl_ldatum = RangeTypeGetDatum(left_range);
971  v->spl_rdatum = RangeTypeGetDatum(right_range);
972 }
#define RangeTypeGetDatum(X)
Definition: rangetypes.h:73
Datum spl_rdatum
Definition: gist.h:112
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
int32 n
Definition: gist.h:160
int spl_nleft
Definition: gist.h:106
uint16 OffsetNumber
Definition: off.h:24
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
#define PLACE_LEFT(range, off)
int spl_nright
Definition: gist.h:111
Datum key
Definition: gist.h:123
#define FirstOffsetNumber
Definition: off.h:27
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
#define PLACE_RIGHT(range, off)
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
int i
Datum range_gist_compress ( PG_FUNCTION_ARGS  )

Definition at line 221 of file rangetypes_gist.c.

References PG_GETARG_POINTER, and PG_RETURN_POINTER.

222 {
223  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
224 
225  PG_RETURN_POINTER(entry);
226 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
static void range_gist_consider_split ( ConsiderSplitContext context,
RangeBound right_lower,
int  min_left_count,
RangeBound left_upper,
int  max_left_count 
)
static

Definition at line 1372 of file rangetypes_gist.c.

References call_subtype_diff(), ConsiderSplitContext::common_left, ConsiderSplitContext::common_right, ConsiderSplitContext::entries_count, ConsiderSplitContext::first, ConsiderSplitContext::has_subtype_diff, ConsiderSplitContext::left_upper, LIMIT_RATIO, Min, ConsiderSplitContext::overlap, ConsiderSplitContext::ratio, ConsiderSplitContext::right_lower, ConsiderSplitContext::typcache, and RangeBound::val.

Referenced by range_gist_double_sorting_split().

1375 {
1376  int left_count,
1377  right_count;
1378  float4 ratio,
1379  overlap;
1380 
1381  /*
1382  * Calculate entries distribution ratio assuming most uniform distribution
1383  * of common entries.
1384  */
1385  if (min_left_count >= (context->entries_count + 1) / 2)
1386  left_count = min_left_count;
1387  else if (max_left_count <= context->entries_count / 2)
1388  left_count = max_left_count;
1389  else
1390  left_count = context->entries_count / 2;
1391  right_count = context->entries_count - left_count;
1392 
1393  /*
1394  * Ratio of split: quotient between size of smaller group and total
1395  * entries count. This is necessarily 0.5 or less; if it's less than
1396  * LIMIT_RATIO then we will never accept the new split.
1397  */
1398  ratio = ((float4) Min(left_count, right_count)) /
1399  ((float4) context->entries_count);
1400 
1401  if (ratio > LIMIT_RATIO)
1402  {
1403  bool selectthis = false;
1404 
1405  /*
1406  * The ratio is acceptable, so compare current split with previously
1407  * selected one. We search for minimal overlap (allowing negative
1408  * values) and minimal ratio secondarily. If subtype_diff is
1409  * available, it's used for overlap measure. Without subtype_diff we
1410  * use number of "common entries" as an overlap measure.
1411  */
1412  if (context->has_subtype_diff)
1413  overlap = call_subtype_diff(context->typcache,
1414  left_upper->val,
1415  right_lower->val);
1416  else
1417  overlap = max_left_count - min_left_count;
1418 
1419  /* If there is no previous selection, select this split */
1420  if (context->first)
1421  selectthis = true;
1422  else
1423  {
1424  /*
1425  * Choose the new split if it has a smaller overlap, or same
1426  * overlap but better ratio.
1427  */
1428  if (overlap < context->overlap ||
1429  (overlap == context->overlap && ratio > context->ratio))
1430  selectthis = true;
1431  }
1432 
1433  if (selectthis)
1434  {
1435  /* save information about selected split */
1436  context->first = false;
1437  context->ratio = ratio;
1438  context->overlap = overlap;
1439  context->right_lower = right_lower;
1440  context->left_upper = left_upper;
1441  context->common_left = max_left_count - left_count;
1442  context->common_right = left_count - min_left_count;
1443  }
1444  }
1445 }
RangeBound * right_lower
RangeBound * left_upper
#define Min(x, y)
Definition: c.h:802
Datum val
Definition: rangetypes.h:62
static float8 call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
#define LIMIT_RATIO
float float4
Definition: c.h:377
TypeCacheEntry * typcache
Datum range_gist_consistent ( PG_FUNCTION_ARGS  )

Definition at line 172 of file rangetypes_gist.c.

References DatumGetRangeType, GIST_LEAF, GISTENTRY::key, PG_GETARG_DATUM, PG_GETARG_POINTER, PG_GETARG_UINT16, PG_RETURN_BOOL, range_get_typcache(), range_gist_consistent_int(), range_gist_consistent_leaf(), and RangeTypeGetOid.

173 {
174  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
175  Datum query = PG_GETARG_DATUM(1);
177 
178  /* Oid subtype = PG_GETARG_OID(3); */
179  bool *recheck = (bool *) PG_GETARG_POINTER(4);
180  RangeType *key = DatumGetRangeType(entry->key);
181  TypeCacheEntry *typcache;
182 
183  /* All operators served by this function are exact */
184  *recheck = false;
185 
186  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
187 
188  if (GIST_LEAF(entry))
189  PG_RETURN_BOOL(range_gist_consistent_leaf(typcache, strategy,
190  key, query));
191  else
192  PG_RETURN_BOOL(range_gist_consistent_int(typcache, strategy,
193  key, query));
194 }
#define GIST_LEAF(entry)
Definition: gist.h:133
static bool range_gist_consistent_leaf(TypeCacheEntry *typcache, StrategyNumber strategy, RangeType *key, Datum query)
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1479
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:224
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
Datum key
Definition: gist.h:123
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:303
uintptr_t Datum
Definition: postgres.h:374
static bool range_gist_consistent_int(TypeCacheEntry *typcache, StrategyNumber strategy, RangeType *key, Datum query)
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:228
static bool range_gist_consistent_int ( TypeCacheEntry typcache,
StrategyNumber  strategy,
RangeType key,
Datum  query 
)
static

Definition at line 784 of file rangetypes_gist.c.

References DatumGetRangeType, elog, ERROR, range_adjacent_internal(), range_after_internal(), range_before_internal(), range_contains_elem_internal(), range_contains_internal(), range_overlaps_internal(), range_overleft_internal(), range_overright_internal(), RangeIsEmpty, RangeIsOrContainsEmpty, RANGESTRAT_ADJACENT, RANGESTRAT_AFTER, RANGESTRAT_BEFORE, RANGESTRAT_CONTAINED_BY, RANGESTRAT_CONTAINS, RANGESTRAT_CONTAINS_ELEM, RANGESTRAT_EQ, RANGESTRAT_OVERLAPS, RANGESTRAT_OVERLEFT, and RANGESTRAT_OVERRIGHT.

Referenced by range_gist_consistent().

786 {
787  switch (strategy)
788  {
789  case RANGESTRAT_BEFORE:
790  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
791  return false;
792  return (!range_overright_internal(typcache, key,
793  DatumGetRangeType(query)));
794  case RANGESTRAT_OVERLEFT:
795  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
796  return false;
797  return (!range_after_internal(typcache, key,
798  DatumGetRangeType(query)));
799  case RANGESTRAT_OVERLAPS:
800  return range_overlaps_internal(typcache, key,
801  DatumGetRangeType(query));
803  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
804  return false;
805  return (!range_before_internal(typcache, key,
806  DatumGetRangeType(query)));
807  case RANGESTRAT_AFTER:
808  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
809  return false;
810  return (!range_overleft_internal(typcache, key,
811  DatumGetRangeType(query)));
812  case RANGESTRAT_ADJACENT:
813  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
814  return false;
815  if (range_adjacent_internal(typcache, key,
816  DatumGetRangeType(query)))
817  return true;
818  return range_overlaps_internal(typcache, key,
819  DatumGetRangeType(query));
820  case RANGESTRAT_CONTAINS:
821  return range_contains_internal(typcache, key,
822  DatumGetRangeType(query));
824 
825  /*
826  * Empty ranges are contained by anything, so if key is or
827  * contains any empty ranges, we must descend into it. Otherwise,
828  * descend only if key overlaps the query.
829  */
830  if (RangeIsOrContainsEmpty(key))
831  return true;
832  return range_overlaps_internal(typcache, key,
833  DatumGetRangeType(query));
835  return range_contains_elem_internal(typcache, key, query);
836  case RANGESTRAT_EQ:
837 
838  /*
839  * If query is empty, descend only if the key is or contains any
840  * empty ranges. Otherwise, descend if key contains query.
841  */
842  if (RangeIsEmpty(DatumGetRangeType(query)))
843  return RangeIsOrContainsEmpty(key);
844  return range_contains_internal(typcache, key,
845  DatumGetRangeType(query));
846  default:
847  elog(ERROR, "unrecognized range strategy: %d", strategy);
848  return false; /* keep compiler quiet */
849  }
850 }
#define RangeIsEmpty(r)
Definition: rangetypes.h:54
#define RANGESTRAT_OVERRIGHT
Definition: rangetypes.h:83
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:85
bool range_before_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:647
bool range_overleft_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:870
bool range_overright_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:911
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
bool range_after_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:685
#define ERROR
Definition: elog.h:43
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:88
#define RANGESTRAT_BEFORE
Definition: rangetypes.h:80
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:86
bool range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:781
#define RANGESTRAT_CONTAINED_BY
Definition: rangetypes.h:87
#define RANGESTRAT_OVERLEFT
Definition: rangetypes.h:81
#define RANGESTRAT_EQ
Definition: rangetypes.h:89
#define RangeIsOrContainsEmpty(r)
Definition: rangetypes.h:55
#define RANGESTRAT_OVERLAPS
Definition: rangetypes.h:82
#define RANGESTRAT_AFTER
Definition: rangetypes.h:84
#define elog
Definition: elog.h:219
bool range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val)
Definition: rangetypes.c:2277
bool range_overlaps_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:824
bool range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:2236
static bool range_gist_consistent_leaf ( TypeCacheEntry typcache,
StrategyNumber  strategy,
RangeType key,
Datum  query 
)
static

Definition at line 856 of file rangetypes_gist.c.

References DatumGetRangeType, elog, ERROR, range_adjacent_internal(), range_after_internal(), range_before_internal(), range_contained_by_internal(), range_contains_elem_internal(), range_contains_internal(), range_eq_internal(), range_overlaps_internal(), range_overleft_internal(), range_overright_internal(), RANGESTRAT_ADJACENT, RANGESTRAT_AFTER, RANGESTRAT_BEFORE, RANGESTRAT_CONTAINED_BY, RANGESTRAT_CONTAINS, RANGESTRAT_CONTAINS_ELEM, RANGESTRAT_EQ, RANGESTRAT_OVERLAPS, RANGESTRAT_OVERLEFT, and RANGESTRAT_OVERRIGHT.

Referenced by range_gist_consistent().

858 {
859  switch (strategy)
860  {
861  case RANGESTRAT_BEFORE:
862  return range_before_internal(typcache, key,
863  DatumGetRangeType(query));
864  case RANGESTRAT_OVERLEFT:
865  return range_overleft_internal(typcache, key,
866  DatumGetRangeType(query));
867  case RANGESTRAT_OVERLAPS:
868  return range_overlaps_internal(typcache, key,
869  DatumGetRangeType(query));
871  return range_overright_internal(typcache, key,
872  DatumGetRangeType(query));
873  case RANGESTRAT_AFTER:
874  return range_after_internal(typcache, key,
875  DatumGetRangeType(query));
876  case RANGESTRAT_ADJACENT:
877  return range_adjacent_internal(typcache, key,
878  DatumGetRangeType(query));
879  case RANGESTRAT_CONTAINS:
880  return range_contains_internal(typcache, key,
881  DatumGetRangeType(query));
883  return range_contained_by_internal(typcache, key,
884  DatumGetRangeType(query));
886  return range_contains_elem_internal(typcache, key, query);
887  case RANGESTRAT_EQ:
888  return range_eq_internal(typcache, key, DatumGetRangeType(query));
889  default:
890  elog(ERROR, "unrecognized range strategy: %d", strategy);
891  return false; /* keep compiler quiet */
892  }
893 }
#define RANGESTRAT_OVERRIGHT
Definition: rangetypes.h:83
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:85
bool range_eq_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:556
bool range_before_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:647
bool range_overleft_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:870
bool range_overright_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:911
bool range_contained_by_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:2268
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
bool range_after_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:685
#define ERROR
Definition: elog.h:43
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:88
#define RANGESTRAT_BEFORE
Definition: rangetypes.h:80
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:86
bool range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:781
#define RANGESTRAT_CONTAINED_BY
Definition: rangetypes.h:87
#define RANGESTRAT_OVERLEFT
Definition: rangetypes.h:81
#define RANGESTRAT_EQ
Definition: rangetypes.h:89
#define RANGESTRAT_OVERLAPS
Definition: rangetypes.h:82
#define RANGESTRAT_AFTER
Definition: rangetypes.h:84
#define elog
Definition: elog.h:219
bool range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val)
Definition: rangetypes.c:2277
bool range_overlaps_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:824
bool range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:2236
Datum range_gist_decompress ( PG_FUNCTION_ARGS  )

Definition at line 229 of file rangetypes_gist.c.

References PG_GETARG_POINTER, and PG_RETURN_POINTER.

230 {
231  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
232 
233  PG_RETURN_POINTER(entry);
234 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
static void range_gist_double_sorting_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v 
)
static

Definition at line 1070 of file rangetypes_gist.c.

References Assert, call_subtype_diff(), common_entry_cmp(), ConsiderSplitContext::common_left, DatumGetRangeType, CommonEntry::delta, ConsiderSplitContext::entries_count, ConsiderSplitContext::first, FirstOffsetNumber, FmgrInfo::fn_oid, ConsiderSplitContext::has_subtype_diff, i, idx(), CommonEntry::index, interval_cmp_lower(), interval_cmp_upper(), GISTENTRY::key, ConsiderSplitContext::left_upper, lower(), NonEmptyRange::lower, GistEntryVector::n, NULL, OffsetNumberNext, OidIsValid, palloc(), PLACE_LEFT, PLACE_RIGHT, PointerGetDatum, qsort, qsort_arg(), range(), range_cmp_bounds(), range_deserialize(), range_gist_consider_split(), range_gist_fallback_split(), ConsiderSplitContext::right_lower, TypeCacheEntry::rng_subdiff_finfo, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, ConsiderSplitContext::typcache, upper(), NonEmptyRange::upper, RangeBound::val, and GistEntryVector::vector.

Referenced by range_gist_picksplit().

1073 {
1074  ConsiderSplitContext context;
1075  OffsetNumber i,
1076  maxoff;
1077  RangeType *range,
1078  *left_range = NULL,
1079  *right_range = NULL;
1080  int common_entries_count;
1081  NonEmptyRange *by_lower,
1082  *by_upper;
1083  CommonEntry *common_entries;
1084  int nentries,
1085  i1,
1086  i2;
1087  RangeBound *right_lower,
1088  *left_upper;
1089 
1090  memset(&context, 0, sizeof(ConsiderSplitContext));
1091  context.typcache = typcache;
1092  context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
1093 
1094  maxoff = entryvec->n - 1;
1095  nentries = context.entries_count = maxoff - FirstOffsetNumber + 1;
1096  context.first = true;
1097 
1098  /* Allocate arrays for sorted range bounds */
1099  by_lower = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
1100  by_upper = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
1101 
1102  /* Fill arrays of bounds */
1103  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1104  {
1105  RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
1106  bool empty;
1107 
1108  range_deserialize(typcache, range,
1109  &by_lower[i - FirstOffsetNumber].lower,
1110  &by_lower[i - FirstOffsetNumber].upper,
1111  &empty);
1112  Assert(!empty);
1113  }
1114 
1115  /*
1116  * Make two arrays of range bounds: one sorted by lower bound and another
1117  * sorted by upper bound.
1118  */
1119  memcpy(by_upper, by_lower, nentries * sizeof(NonEmptyRange));
1120  qsort_arg(by_lower, nentries, sizeof(NonEmptyRange),
1121  interval_cmp_lower, typcache);
1122  qsort_arg(by_upper, nentries, sizeof(NonEmptyRange),
1123  interval_cmp_upper, typcache);
1124 
1125  /*----------
1126  * The goal is to form a left and right range, so that every entry
1127  * range is contained by either left or right interval (or both).
1128  *
1129  * For example, with the ranges (0,1), (1,3), (2,3), (2,4):
1130  *
1131  * 0 1 2 3 4
1132  * +-+
1133  * +---+
1134  * +-+
1135  * +---+
1136  *
1137  * The left and right ranges are of the form (0,a) and (b,4).
1138  * We first consider splits where b is the lower bound of an entry.
1139  * We iterate through all entries, and for each b, calculate the
1140  * smallest possible a. Then we consider splits where a is the
1141  * upper bound of an entry, and for each a, calculate the greatest
1142  * possible b.
1143  *
1144  * In the above example, the first loop would consider splits:
1145  * b=0: (0,1)-(0,4)
1146  * b=1: (0,1)-(1,4)
1147  * b=2: (0,3)-(2,4)
1148  *
1149  * And the second loop:
1150  * a=1: (0,1)-(1,4)
1151  * a=3: (0,3)-(2,4)
1152  * a=4: (0,4)-(2,4)
1153  *----------
1154  */
1155 
1156  /*
1157  * Iterate over lower bound of right group, finding smallest possible
1158  * upper bound of left group.
1159  */
1160  i1 = 0;
1161  i2 = 0;
1162  right_lower = &by_lower[i1].lower;
1163  left_upper = &by_upper[i2].lower;
1164  while (true)
1165  {
1166  /*
1167  * Find next lower bound of right group.
1168  */
1169  while (i1 < nentries &&
1170  range_cmp_bounds(typcache, right_lower,
1171  &by_lower[i1].lower) == 0)
1172  {
1173  if (range_cmp_bounds(typcache, &by_lower[i1].upper,
1174  left_upper) > 0)
1175  left_upper = &by_lower[i1].upper;
1176  i1++;
1177  }
1178  if (i1 >= nentries)
1179  break;
1180  right_lower = &by_lower[i1].lower;
1181 
1182  /*
1183  * Find count of ranges which anyway should be placed to the left
1184  * group.
1185  */
1186  while (i2 < nentries &&
1187  range_cmp_bounds(typcache, &by_upper[i2].upper,
1188  left_upper) <= 0)
1189  i2++;
1190 
1191  /*
1192  * Consider found split to see if it's better than what we had.
1193  */
1194  range_gist_consider_split(&context, right_lower, i1, left_upper, i2);
1195  }
1196 
1197  /*
1198  * Iterate over upper bound of left group finding greatest possible lower
1199  * bound of right group.
1200  */
1201  i1 = nentries - 1;
1202  i2 = nentries - 1;
1203  right_lower = &by_lower[i1].upper;
1204  left_upper = &by_upper[i2].upper;
1205  while (true)
1206  {
1207  /*
1208  * Find next upper bound of left group.
1209  */
1210  while (i2 >= 0 &&
1211  range_cmp_bounds(typcache, left_upper,
1212  &by_upper[i2].upper) == 0)
1213  {
1214  if (range_cmp_bounds(typcache, &by_upper[i2].lower,
1215  right_lower) < 0)
1216  right_lower = &by_upper[i2].lower;
1217  i2--;
1218  }
1219  if (i2 < 0)
1220  break;
1221  left_upper = &by_upper[i2].upper;
1222 
1223  /*
1224  * Find count of intervals which anyway should be placed to the right
1225  * group.
1226  */
1227  while (i1 >= 0 &&
1228  range_cmp_bounds(typcache, &by_lower[i1].lower,
1229  right_lower) >= 0)
1230  i1--;
1231 
1232  /*
1233  * Consider found split to see if it's better than what we had.
1234  */
1235  range_gist_consider_split(&context, right_lower, i1 + 1,
1236  left_upper, i2 + 1);
1237  }
1238 
1239  /*
1240  * If we failed to find any acceptable splits, use trivial split.
1241  */
1242  if (context.first)
1243  {
1244  range_gist_fallback_split(typcache, entryvec, v);
1245  return;
1246  }
1247 
1248  /*
1249  * Ok, we have now selected bounds of the groups. Now we have to
1250  * distribute entries themselves. At first we distribute entries which can
1251  * be placed unambiguously and collect "common entries" to array.
1252  */
1253 
1254  /* Allocate vectors for results */
1255  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1256  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1257  v->spl_nleft = 0;
1258  v->spl_nright = 0;
1259 
1260  /*
1261  * Allocate an array for "common entries" - entries which can be placed to
1262  * either group without affecting overlap along selected axis.
1263  */
1264  common_entries_count = 0;
1265  common_entries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
1266 
1267  /*
1268  * Distribute entries which can be distributed unambiguously, and collect
1269  * common entries.
1270  */
1271  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1272  {
1273  RangeBound lower,
1274  upper;
1275  bool empty;
1276 
1277  /*
1278  * Get upper and lower bounds along selected axis.
1279  */
1280  range = DatumGetRangeType(entryvec->vector[i].key);
1281 
1282  range_deserialize(typcache, range, &lower, &upper, &empty);
1283 
1284  if (range_cmp_bounds(typcache, &upper, context.left_upper) <= 0)
1285  {
1286  /* Fits in the left group */
1287  if (range_cmp_bounds(typcache, &lower, context.right_lower) >= 0)
1288  {
1289  /* Fits also in the right group, so "common entry" */
1290  common_entries[common_entries_count].index = i;
1291  if (context.has_subtype_diff)
1292  {
1293  /*
1294  * delta = (lower - context.right_lower) -
1295  * (context.left_upper - upper)
1296  */
1297  common_entries[common_entries_count].delta =
1298  call_subtype_diff(typcache,
1299  lower.val,
1300  context.right_lower->val) -
1301  call_subtype_diff(typcache,
1302  context.left_upper->val,
1303  upper.val);
1304  }
1305  else
1306  {
1307  /* Without subtype_diff, take all deltas as zero */
1308  common_entries[common_entries_count].delta = 0;
1309  }
1310  common_entries_count++;
1311  }
1312  else
1313  {
1314  /* Doesn't fit to the right group, so join to the left group */
1315  PLACE_LEFT(range, i);
1316  }
1317  }
1318  else
1319  {
1320  /*
1321  * Each entry should fit on either left or right group. Since this
1322  * entry didn't fit in the left group, it better fit in the right
1323  * group.
1324  */
1325  Assert(range_cmp_bounds(typcache, &lower,
1326  context.right_lower) >= 0);
1327  PLACE_RIGHT(range, i);
1328  }
1329  }
1330 
1331  /*
1332  * Distribute "common entries", if any.
1333  */
1334  if (common_entries_count > 0)
1335  {
1336  /*
1337  * Sort "common entries" by calculated deltas in order to distribute
1338  * the most ambiguous entries first.
1339  */
1340  qsort(common_entries, common_entries_count, sizeof(CommonEntry),
1342 
1343  /*
1344  * Distribute "common entries" between groups according to sorting.
1345  */
1346  for (i = 0; i < common_entries_count; i++)
1347  {
1348  int idx = common_entries[i].index;
1349 
1350  range = DatumGetRangeType(entryvec->vector[idx].key);
1351 
1352  /*
1353  * Check if we have to place this entry in either group to achieve
1354  * LIMIT_RATIO.
1355  */
1356  if (i < context.common_left)
1357  PLACE_LEFT(range, idx);
1358  else
1359  PLACE_RIGHT(range, idx);
1360  }
1361  }
1362 
1363  v->spl_ldatum = PointerGetDatum(left_range);
1364  v->spl_rdatum = PointerGetDatum(right_range);
1365 }
RangeBound upper
static void range_gist_consider_split(ConsiderSplitContext *context, RangeBound *right_lower, int min_left_count, RangeBound *left_upper, int max_left_count)
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
#define PointerGetDatum(X)
Definition: postgres.h:564
RangeBound * right_lower
RangeBound * left_upper
OffsetNumber * spl_left
Definition: gist.h:105
Datum spl_rdatum
Definition: gist.h:112
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
Datum val
Definition: rangetypes.h:62
static float8 call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
int32 n
Definition: gist.h:160
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:264
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
int spl_nleft
Definition: gist.h:106
#define OidIsValid(objectId)
Definition: c.h:534
uint16 OffsetNumber
Definition: off.h:24
double delta
Definition: gistproc.c:302
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:88
#define PLACE_LEFT(range, off)
int spl_nright
Definition: gist.h:111
RangeBound lower
Datum key
Definition: gist.h:123
#define FirstOffsetNumber
Definition: off.h:27
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
void range_deserialize(TypeCacheEntry *typcache, RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1632
#define PLACE_RIGHT(range, off)
static void range_gist_fallback_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v)
Oid fn_oid
Definition: fmgr.h:56
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
OffsetNumber * spl_right
Definition: gist.h:110
void * palloc(Size size)
Definition: mcxt.c:891
int i
#define qsort(a, b, c, d)
Definition: port.h:440
static int interval_cmp_lower(const void *a, const void *b, void *arg)
TypeCacheEntry * typcache
static int interval_cmp_upper(const void *a, const void *b, void *arg)
static int common_entry_cmp(const void *i1, const void *i2)
static void range_gist_fallback_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v 
)
static

Definition at line 900 of file rangetypes_gist.c.

References DatumGetRangeType, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, NULL, PLACE_LEFT, PLACE_RIGHT, range(), RangeTypeGetDatum, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, and GistEntryVector::vector.

Referenced by range_gist_double_sorting_split(), and range_gist_picksplit().

903 {
904  RangeType *left_range = NULL;
905  RangeType *right_range = NULL;
906  OffsetNumber i,
907  maxoff,
908  split_idx;
909 
910  maxoff = entryvec->n - 1;
911  /* Split entries before this to left page, after to right: */
912  split_idx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
913 
914  v->spl_nleft = 0;
915  v->spl_nright = 0;
916  for (i = FirstOffsetNumber; i <= maxoff; i++)
917  {
918  RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
919 
920  if (i < split_idx)
921  PLACE_LEFT(range, i);
922  else
923  PLACE_RIGHT(range, i);
924  }
925 
926  v->spl_ldatum = RangeTypeGetDatum(left_range);
927  v->spl_rdatum = RangeTypeGetDatum(right_range);
928 }
#define RangeTypeGetDatum(X)
Definition: rangetypes.h:73
Datum spl_rdatum
Definition: gist.h:112
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
int32 n
Definition: gist.h:160
int spl_nleft
Definition: gist.h:106
uint16 OffsetNumber
Definition: off.h:24
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
#define PLACE_LEFT(range, off)
int spl_nright
Definition: gist.h:111
Datum key
Definition: gist.h:123
#define FirstOffsetNumber
Definition: off.h:27
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
#define PLACE_RIGHT(range, off)
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:226
int i
Datum range_gist_fetch ( PG_FUNCTION_ARGS  )

Definition at line 237 of file rangetypes_gist.c.

References PG_GETARG_POINTER, and PG_RETURN_POINTER.

238 {
239  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
240 
241  PG_RETURN_POINTER(entry);
242 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
Datum range_gist_penalty ( PG_FUNCTION_ARGS  )

Definition at line 255 of file rangetypes_gist.c.

References call_subtype_diff(), CONTAIN_EMPTY_PENALTY, DatumGetRangeType, DEFAULT_SUBTYPE_DIFF_PENALTY, elog, ERROR, FmgrInfo::fn_oid, get_float4_infinity(), RangeBound::infinite, INFINITE_BOUND_PENALTY, GISTENTRY::key, OidIsValid, PG_GETARG_POINTER, PG_RETURN_POINTER, range_cmp_bounds(), range_deserialize(), range_get_typcache(), RangeIsOrContainsEmpty, RangeTypeGetOid, TypeCacheEntry::rng_subdiff_finfo, and RangeBound::val.

256 {
257  GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
258  GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
259  float *penalty = (float *) PG_GETARG_POINTER(2);
260  RangeType *orig = DatumGetRangeType(origentry->key);
261  RangeType *new = DatumGetRangeType(newentry->key);
262  TypeCacheEntry *typcache;
263  bool has_subtype_diff;
264  RangeBound orig_lower,
265  new_lower,
266  orig_upper,
267  new_upper;
268  bool orig_empty,
269  new_empty;
270 
271  if (RangeTypeGetOid(orig) != RangeTypeGetOid(new))
272  elog(ERROR, "range types do not match");
273 
274  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(orig));
275 
276  has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
277 
278  range_deserialize(typcache, orig, &orig_lower, &orig_upper, &orig_empty);
279  range_deserialize(typcache, new, &new_lower, &new_upper, &new_empty);
280 
281  /*
282  * Distinct branches for handling distinct classes of ranges. Note that
283  * penalty values only need to be commensurate within the same class of
284  * new range.
285  */
286  if (new_empty)
287  {
288  /* Handle insertion of empty range */
289  if (orig_empty)
290  {
291  /*
292  * The best case is to insert it to empty original range.
293  * Insertion here means no broadening of original range. Also
294  * original range is the most narrow.
295  */
296  *penalty = 0.0;
297  }
298  else if (RangeIsOrContainsEmpty(orig))
299  {
300  /*
301  * The second case is to insert empty range into range which
302  * contains at least one underlying empty range. There is still
303  * no broadening of original range, but original range is not as
304  * narrow as possible.
305  */
306  *penalty = CONTAIN_EMPTY_PENALTY;
307  }
308  else if (orig_lower.infinite && orig_upper.infinite)
309  {
310  /*
311  * Original range requires broadening. (-inf; +inf) is most far
312  * from normal range in this case.
313  */
314  *penalty = 2 * CONTAIN_EMPTY_PENALTY;
315  }
316  else if (orig_lower.infinite || orig_upper.infinite)
317  {
318  /*
319  * (-inf, x) or (x, +inf) original ranges are closer to normal
320  * ranges, so it's worse to mix it with empty ranges.
321  */
322  *penalty = 3 * CONTAIN_EMPTY_PENALTY;
323  }
324  else
325  {
326  /*
327  * The least preferred case is broadening of normal range.
328  */
329  *penalty = 4 * CONTAIN_EMPTY_PENALTY;
330  }
331  }
332  else if (new_lower.infinite && new_upper.infinite)
333  {
334  /* Handle insertion of (-inf, +inf) range */
335  if (orig_lower.infinite && orig_upper.infinite)
336  {
337  /*
338  * Best case is inserting to (-inf, +inf) original range.
339  */
340  *penalty = 0.0;
341  }
342  else if (orig_lower.infinite || orig_upper.infinite)
343  {
344  /*
345  * When original range is (-inf, x) or (x, +inf) it requires
346  * broadening of original range (extension of one bound to
347  * infinity).
348  */
349  *penalty = INFINITE_BOUND_PENALTY;
350  }
351  else
352  {
353  /*
354  * Insertion to normal original range is least preferred.
355  */
356  *penalty = 2 * INFINITE_BOUND_PENALTY;
357  }
358 
359  if (RangeIsOrContainsEmpty(orig))
360  {
361  /*
362  * Original range is narrower when it doesn't contain empty
363  * ranges. Add additional penalty otherwise.
364  */
365  *penalty += CONTAIN_EMPTY_PENALTY;
366  }
367  }
368  else if (new_lower.infinite)
369  {
370  /* Handle insertion of (-inf, x) range */
371  if (!orig_empty && orig_lower.infinite)
372  {
373  if (orig_upper.infinite)
374  {
375  /*
376  * (-inf, +inf) range won't be extended by insertion of (-inf,
377  * x) range. It's a less desirable case than insertion to
378  * (-inf, y) original range without extension, because in that
379  * case original range is narrower. But we can't express that
380  * in single float value.
381  */
382  *penalty = 0.0;
383  }
384  else
385  {
386  if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
387  {
388  /*
389  * Get extension of original range using subtype_diff. Use
390  * constant if subtype_diff unavailable.
391  */
392  if (has_subtype_diff)
393  *penalty = call_subtype_diff(typcache,
394  new_upper.val,
395  orig_upper.val);
396  else
397  *penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
398  }
399  else
400  {
401  /* No extension of original range */
402  *penalty = 0.0;
403  }
404  }
405  }
406  else
407  {
408  /*
409  * If lower bound of original range is not -inf, then extension of
410  * it is infinity.
411  */
412  *penalty = get_float4_infinity();
413  }
414  }
415  else if (new_upper.infinite)
416  {
417  /* Handle insertion of (x, +inf) range */
418  if (!orig_empty && orig_upper.infinite)
419  {
420  if (orig_lower.infinite)
421  {
422  /*
423  * (-inf, +inf) range won't be extended by insertion of (x,
424  * +inf) range. It's a less desirable case than insertion to
425  * (y, +inf) original range without extension, because in that
426  * case original range is narrower. But we can't express that
427  * in single float value.
428  */
429  *penalty = 0.0;
430  }
431  else
432  {
433  if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
434  {
435  /*
436  * Get extension of original range using subtype_diff. Use
437  * constant if subtype_diff unavailable.
438  */
439  if (has_subtype_diff)
440  *penalty = call_subtype_diff(typcache,
441  orig_lower.val,
442  new_lower.val);
443  else
444  *penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
445  }
446  else
447  {
448  /* No extension of original range */
449  *penalty = 0.0;
450  }
451  }
452  }
453  else
454  {
455  /*
456  * If upper bound of original range is not +inf, then extension of
457  * it is infinity.
458  */
459  *penalty = get_float4_infinity();
460  }
461  }
462  else
463  {
464  /* Handle insertion of normal (non-empty, non-infinite) range */
465  if (orig_empty || orig_lower.infinite || orig_upper.infinite)
466  {
467  /*
468  * Avoid mixing normal ranges with infinite and empty ranges.
469  */
470  *penalty = get_float4_infinity();
471  }
472  else
473  {
474  /*
475  * Calculate extension of original range by calling subtype_diff.
476  * Use constant if subtype_diff unavailable.
477  */
478  float8 diff = 0.0;
479 
480  if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
481  {
482  if (has_subtype_diff)
483  diff += call_subtype_diff(typcache,
484  orig_lower.val,
485  new_lower.val);
486  else
488  }
489  if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
490  {
491  if (has_subtype_diff)
492  diff += call_subtype_diff(typcache,
493  new_upper.val,
494  orig_upper.val);
495  else
497  }
498  *penalty = diff;
499  }
500  }
501 
502  PG_RETURN_POINTER(penalty);
503 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1479
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
#define CONTAIN_EMPTY_PENALTY
#define INFINITE_BOUND_PENALTY
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
Datum val
Definition: rangetypes.h:62
static float8 call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
#define OidIsValid(objectId)
Definition: c.h:534
float get_float4_infinity(void)
Definition: float.c:146
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:88
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:378
Datum key
Definition: gist.h:123
void range_deserialize(TypeCacheEntry *typcache, RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1632
Oid fn_oid
Definition: fmgr.h:56
bool infinite
Definition: rangetypes.h:63
#define DEFAULT_SUBTYPE_DIFF_PENALTY
#define RangeIsOrContainsEmpty(r)
Definition: rangetypes.h:55
#define elog
Definition: elog.h:219
Datum range_gist_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 512 of file rangetypes_gist.c.

References Abs, Assert, CLS_CONTAIN_EMPTY, CLS_COUNT, CLS_EMPTY, CLS_LOWER_INF, CLS_NORMAL, CLS_UPPER_INF, DatumGetRangeType, FirstOffsetNumber, get_gist_range_class(), i, GISTENTRY::key, GistEntryVector::n, OffsetNumberNext, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, range(), range_get_typcache(), range_gist_class_split(), range_gist_double_sorting_split(), range_gist_fallback_split(), range_gist_single_sorting_split(), RangeTypeGetOid, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_right, SPLIT_RIGHT, and GistEntryVector::vector.

513 {
516  TypeCacheEntry *typcache;
517  OffsetNumber i;
518  RangeType *pred_left;
519  int nbytes;
520  OffsetNumber maxoff;
521  int count_in_classes[CLS_COUNT];
522  int j;
523  int non_empty_classes_count = 0;
524  int biggest_class = -1;
525  int biggest_class_count = 0;
526  int total_count;
527 
528  /* use first item to look up range type's info */
529  pred_left = DatumGetRangeType(entryvec->vector[FirstOffsetNumber].key);
530  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(pred_left));
531 
532  maxoff = entryvec->n - 1;
533  nbytes = (maxoff + 1) * sizeof(OffsetNumber);
534  v->spl_left = (OffsetNumber *) palloc(nbytes);
535  v->spl_right = (OffsetNumber *) palloc(nbytes);
536 
537  /*
538  * Get count distribution of range classes.
539  */
540  memset(count_in_classes, 0, sizeof(count_in_classes));
541  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
542  {
543  RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
544 
545  count_in_classes[get_gist_range_class(range)]++;
546  }
547 
548  /*
549  * Count non-empty classes and find biggest class.
550  */
551  total_count = maxoff;
552  for (j = 0; j < CLS_COUNT; j++)
553  {
554  if (count_in_classes[j] > 0)
555  {
556  if (count_in_classes[j] > biggest_class_count)
557  {
558  biggest_class_count = count_in_classes[j];
559  biggest_class = j;
560  }
561  non_empty_classes_count++;
562  }
563  }
564 
565  Assert(non_empty_classes_count > 0);
566 
567  if (non_empty_classes_count == 1)
568  {
569  /* One non-empty class, so split inside class */
570  if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_NORMAL)
571  {
572  /* double sorting split for normal ranges */
573  range_gist_double_sorting_split(typcache, entryvec, v);
574  }
575  else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_LOWER_INF)
576  {
577  /* upper bound sorting split for (-inf, x) ranges */
578  range_gist_single_sorting_split(typcache, entryvec, v, true);
579  }
580  else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_UPPER_INF)
581  {
582  /* lower bound sorting split for (x, +inf) ranges */
583  range_gist_single_sorting_split(typcache, entryvec, v, false);
584  }
585  else
586  {
587  /* trivial split for all (-inf, +inf) or all empty ranges */
588  range_gist_fallback_split(typcache, entryvec, v);
589  }
590  }
591  else
592  {
593  /*
594  * Class based split.
595  *
596  * To which side of the split should each class go? Initialize them
597  * all to go to the left side.
598  */
599  SplitLR classes_groups[CLS_COUNT];
600 
601  memset(classes_groups, 0, sizeof(classes_groups));
602 
603  if (count_in_classes[CLS_NORMAL] > 0)
604  {
605  /* separate normal ranges if any */
606  classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
607  }
608  else
609  {
610  /*----------
611  * Try to split classes in one of two ways:
612  * 1) containing infinities - not containing infinities
613  * 2) containing empty - not containing empty
614  *
615  * Select the way which balances the ranges between left and right
616  * the best. If split in these ways is not possible, there are at
617  * most 3 classes, so just separate biggest class.
618  *----------
619  */
620  int infCount,
621  nonInfCount;
622  int emptyCount,
623  nonEmptyCount;
624 
625  nonInfCount =
626  count_in_classes[CLS_NORMAL] +
627  count_in_classes[CLS_CONTAIN_EMPTY] +
628  count_in_classes[CLS_EMPTY];
629  infCount = total_count - nonInfCount;
630 
631  nonEmptyCount =
632  count_in_classes[CLS_NORMAL] +
633  count_in_classes[CLS_LOWER_INF] +
634  count_in_classes[CLS_UPPER_INF] +
635  count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF];
636  emptyCount = total_count - nonEmptyCount;
637 
638  if (infCount > 0 && nonInfCount > 0 &&
639  (Abs(infCount - nonInfCount) <=
640  Abs(emptyCount - nonEmptyCount)))
641  {
642  classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
643  classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT;
644  classes_groups[CLS_EMPTY] = SPLIT_RIGHT;
645  }
646  else if (emptyCount > 0 && nonEmptyCount > 0)
647  {
648  classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
649  classes_groups[CLS_LOWER_INF] = SPLIT_RIGHT;
650  classes_groups[CLS_UPPER_INF] = SPLIT_RIGHT;
651  classes_groups[CLS_LOWER_INF | CLS_UPPER_INF] = SPLIT_RIGHT;
652  }
653  else
654  {
655  /*
656  * Either total_count == emptyCount or total_count ==
657  * infCount.
658  */
659  classes_groups[biggest_class] = SPLIT_RIGHT;
660  }
661  }
662 
663  range_gist_class_split(typcache, entryvec, v, classes_groups);
664  }
665 
667 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
#define CLS_EMPTY
#define CLS_COUNT
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1479
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
static void range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, SplitLR *classes_groups)
OffsetNumber * spl_left
Definition: gist.h:105
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
int32 n
Definition: gist.h:160
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
#define CLS_CONTAIN_EMPTY
uint16 OffsetNumber
Definition: off.h:24
#define Abs(x)
Definition: c.h:808
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
static int get_gist_range_class(RangeType *range)
Datum key
Definition: gist.h:123
#define FirstOffsetNumber
Definition: off.h:27
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
SplitLR
static void range_gist_fallback_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v)
#define CLS_LOWER_INF
#define Assert(condition)
Definition: c.h:671
#define CLS_UPPER_INF
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
OffsetNumber * spl_right
Definition: gist.h:110
static void range_gist_double_sorting_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v)
void * palloc(Size size)
Definition: mcxt.c:891
int i
static void range_gist_single_sorting_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, bool use_upper_bound)
#define CLS_NORMAL
Datum range_gist_same ( PG_FUNCTION_ARGS  )

Definition at line 671 of file rangetypes_gist.c.

References PG_GETARG_POINTER, PG_GETARG_RANGE, PG_RETURN_POINTER, range_eq_internal(), range_get_flags(), range_get_typcache(), and RangeTypeGetOid.

672 {
673  RangeType *r1 = PG_GETARG_RANGE(0);
674  RangeType *r2 = PG_GETARG_RANGE(1);
675  bool *result = (bool *) PG_GETARG_POINTER(2);
676 
677  /*
678  * range_eq will ignore the RANGE_CONTAIN_EMPTY flag, so we have to check
679  * that for ourselves. More generally, if the entries have been properly
680  * normalized, then unequal flags bytes must mean unequal ranges ... so
681  * let's just test all the flag bits at once.
682  */
683  if (range_get_flags(r1) != range_get_flags(r2))
684  *result = false;
685  else
686  {
687  TypeCacheEntry *typcache;
688 
689  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
690 
691  *result = range_eq_internal(typcache, r1, r2);
692  }
693 
694  PG_RETURN_POINTER(result);
695 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:305
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1479
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
bool range_eq_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
Definition: rangetypes.c:556
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
#define PG_GETARG_RANGE(n)
Definition: rangetypes.h:74
char range_get_flags(RangeType *range)
Definition: rangetypes.c:1699
static void range_gist_single_sorting_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v,
bool  use_upper_bound 
)
static

Definition at line 981 of file rangetypes_gist.c.

References Assert, DatumGetRangeType, FirstOffsetNumber, i, idx(), SingleBoundSortItem::index, GISTENTRY::key, GistEntryVector::n, NULL, OffsetNumberNext, palloc(), PLACE_LEFT, PLACE_RIGHT, qsort_arg(), range(), range_deserialize(), RangeTypeGetDatum, single_bound_cmp(), GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, and GistEntryVector::vector.

Referenced by range_gist_picksplit().

985 {
986  SingleBoundSortItem *sortItems;
987  RangeType *left_range = NULL;
988  RangeType *right_range = NULL;
989  OffsetNumber i,
990  maxoff,
991  split_idx;
992 
993  maxoff = entryvec->n - 1;
994 
995  sortItems = (SingleBoundSortItem *)
996  palloc(maxoff * sizeof(SingleBoundSortItem));
997 
998  /*
999  * Prepare auxiliary array and sort the values.
1000  */
1001  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1002  {
1003  RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
1004  RangeBound bound2;
1005  bool empty;
1006 
1007  sortItems[i - 1].index = i;
1008  /* Put appropriate bound into array */
1009  if (use_upper_bound)
1010  range_deserialize(typcache, range, &bound2,
1011  &sortItems[i - 1].bound, &empty);
1012  else
1013  range_deserialize(typcache, range, &sortItems[i - 1].bound,
1014  &bound2, &empty);
1015  Assert(!empty);
1016  }
1017 
1018  qsort_arg(sortItems, maxoff, sizeof(SingleBoundSortItem),
1019  single_bound_cmp, typcache);
1020 
1021  split_idx = maxoff / 2;
1022 
1023  v->spl_nleft = 0;
1024  v->spl_nright = 0;
1025 
1026  for (i = 0; i < maxoff; i++)
1027  {
1028  int idx = sortItems[i].index;
1029  RangeType *range = DatumGetRangeType(entryvec->vector[idx].key);
1030 
1031  if (i < split_idx)
1032  PLACE_LEFT(range, idx);
1033  else
1034  PLACE_RIGHT(range, idx);
1035  }
1036 
1037  v->spl_ldatum = RangeTypeGetDatum(left_range);
1038  v->spl_rdatum = RangeTypeGetDatum(right_range);
1039 }
#define RangeTypeGetDatum(X)
Definition: rangetypes.h:73
Datum spl_rdatum
Definition: gist.h:112
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
int32 n
Definition: gist.h:160
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:264
int spl_nleft
Definition: gist.h:106
uint16 OffsetNumber
Definition: off.h:24
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
#define PLACE_LEFT(range, off)
int spl_nright
Definition: gist.h:111
Datum key
Definition: gist.h:123
#define FirstOffsetNumber
Definition: off.h:27
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
void range_deserialize(TypeCacheEntry *typcache, RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1632
#define PLACE_RIGHT(range, off)
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:226
static int single_bound_cmp(const void *a, const void *b, void *arg)
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
void * palloc(Size size)
Definition: mcxt.c:891
int i
Datum range_gist_union ( PG_FUNCTION_ARGS  )

Definition at line 198 of file rangetypes_gist.c.

References DatumGetRangeType, i, GistEntryVector::n, PG_GETARG_POINTER, PG_RETURN_RANGE, range_get_typcache(), range_super_union(), RangeTypeGetOid, and GistEntryVector::vector.

199 {
201  GISTENTRY *ent = entryvec->vector;
202  RangeType *result_range;
203  TypeCacheEntry *typcache;
204  int i;
205 
206  result_range = DatumGetRangeType(ent[0].key);
207 
208  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(result_range));
209 
210  for (i = 1; i < entryvec->n; i++)
211  {
212  result_range = range_super_union(typcache, result_range,
213  DatumGetRangeType(ent[i].key));
214  }
215 
216  PG_RETURN_RANGE(result_range);
217 }
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1479
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
#define DatumGetRangeType(X)
Definition: rangetypes.h:71
int32 n
Definition: gist.h:160
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
static RangeType * range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
#define PG_RETURN_RANGE(x)
Definition: rangetypes.h:76
int i
static RangeType * range_super_union ( TypeCacheEntry typcache,
RangeType r1,
RangeType r2 
)
static

Definition at line 714 of file rangetypes_gist.c.

References make_range(), range_cmp_bounds(), RANGE_CONTAIN_EMPTY, range_deserialize(), RANGE_EMPTY, range_get_flags(), range_set_contain_empty(), and rangeCopy.

Referenced by range_gist_union().

715 {
716  RangeType *result;
717  RangeBound lower1,
718  lower2;
719  RangeBound upper1,
720  upper2;
721  bool empty1,
722  empty2;
723  char flags1,
724  flags2;
725  RangeBound *result_lower;
726  RangeBound *result_upper;
727 
728  range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
729  range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
730  flags1 = range_get_flags(r1);
731  flags2 = range_get_flags(r2);
732 
733  if (empty1)
734  {
735  /* We can return r2 as-is if it already is or contains empty */
736  if (flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
737  return r2;
738  /* Else we'd better copy it (modify-in-place isn't safe) */
739  r2 = rangeCopy(r2);
741  return r2;
742  }
743  if (empty2)
744  {
745  /* We can return r1 as-is if it already is or contains empty */
746  if (flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
747  return r1;
748  /* Else we'd better copy it (modify-in-place isn't safe) */
749  r1 = rangeCopy(r1);
751  return r1;
752  }
753 
754  if (range_cmp_bounds(typcache, &lower1, &lower2) <= 0)
755  result_lower = &lower1;
756  else
757  result_lower = &lower2;
758 
759  if (range_cmp_bounds(typcache, &upper1, &upper2) >= 0)
760  result_upper = &upper1;
761  else
762  result_upper = &upper2;
763 
764  /* optimization to avoid constructing a new range */
765  if (result_lower == &lower1 && result_upper == &upper1 &&
766  ((flags1 & RANGE_CONTAIN_EMPTY) || !(flags2 & RANGE_CONTAIN_EMPTY)))
767  return r1;
768  if (result_lower == &lower2 && result_upper == &upper2 &&
769  ((flags2 & RANGE_CONTAIN_EMPTY) || !(flags1 & RANGE_CONTAIN_EMPTY)))
770  return r2;
771 
772  result = make_range(typcache, result_lower, result_upper, false);
773 
774  if ((flags1 & RANGE_CONTAIN_EMPTY) || (flags2 & RANGE_CONTAIN_EMPTY))
775  range_set_contain_empty(result);
776 
777  return result;
778 }
RangeType * make_range(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty)
Definition: rangetypes.c:1728
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
#define RANGE_EMPTY
Definition: rangetypes.h:36
void range_set_contain_empty(RangeType *range)
Definition: rangetypes.c:1713
void range_deserialize(TypeCacheEntry *typcache, RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1632
#define RANGE_CONTAIN_EMPTY
Definition: rangetypes.h:43
#define rangeCopy(r)
char range_get_flags(RangeType *range)
Definition: rangetypes.c:1699
static int single_bound_cmp ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1482 of file rangetypes_gist.c.

References SingleBoundSortItem::bound, and range_cmp_bounds().

Referenced by range_gist_single_sorting_split().

1483 {
1486  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1487 
1488  return range_cmp_bounds(typcache, &i1->bound, &i2->bound);
1489 }
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1768
void * arg