PostgreSQL Source Code  git master
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_penalty (PG_FUNCTION_ARGS)
 
Datum range_gist_picksplit (PG_FUNCTION_ARGS)
 
Datum range_gist_same (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

◆ CLS_CONTAIN_EMPTY

#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().

◆ CLS_COUNT

#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().

◆ CLS_EMPTY

#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().

◆ CLS_LOWER_INF

#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().

◆ CLS_NORMAL

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

Definition at line 29 of file rangetypes_gist.c.

Referenced by range_gist_picksplit().

◆ CLS_UPPER_INF

#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().

◆ CONTAIN_EMPTY_PENALTY

#define CONTAIN_EMPTY_PENALTY   1.0

Definition at line 48 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

◆ DEFAULT_SUBTYPE_DIFF_PENALTY

#define DEFAULT_SUBTYPE_DIFF_PENALTY   1.0

Definition at line 49 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

◆ INFINITE_BOUND_PENALTY

#define INFINITE_BOUND_PENALTY   2.0

Definition at line 47 of file rangetypes_gist.c.

Referenced by range_gist_penalty().

◆ LIMIT_RATIO

#define LIMIT_RATIO   0.3

Definition at line 44 of file rangetypes_gist.c.

Referenced by range_gist_consider_split().

◆ PLACE_LEFT

#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().

◆ PLACE_RIGHT

#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().

◆ rangeCopy

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

Definition at line 132 of file rangetypes_gist.c.

Referenced by range_super_union().

Enumeration Type Documentation

◆ SplitLR

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

◆ call_subtype_diff()

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

Definition at line 1520 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().

1521 {
1522  float8 value;
1523 
1525  typcache->rng_collation,
1526  val1, val2));
1527  /* Cope with buggy subtype_diff function by returning zero */
1528  if (value >= 0.0)
1529  return value;
1530  return 0.0;
1531 }
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1042
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:95
double float8
Definition: c.h:429
static struct @121 value
#define DatumGetFloat8(X)
Definition: postgres.h:734
Oid rng_collation
Definition: typcache.h:92

◆ common_entry_cmp()

static int common_entry_cmp ( const void *  i1,
const void *  i2 
)
static

Definition at line 1502 of file rangetypes_gist.c.

Referenced by range_gist_double_sorting_split().

1503 {
1504  double delta1 = ((CommonEntry *) i1)->delta;
1505  double delta2 = ((CommonEntry *) i2)->delta;
1506 
1507  if (delta1 < delta2)
1508  return -1;
1509  else if (delta1 > delta2)
1510  return 1;
1511  else
1512  return 0;
1513 }

◆ get_gist_range_class()

static int get_gist_range_class ( RangeType range)
static

Definition at line 1436 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().

1437 {
1438  int classNumber;
1439  char flags;
1440 
1441  flags = range_get_flags(range);
1442  if (flags & RANGE_EMPTY)
1443  {
1444  classNumber = CLS_EMPTY;
1445  }
1446  else
1447  {
1448  classNumber = 0;
1449  if (flags & RANGE_LB_INF)
1450  classNumber |= CLS_LOWER_INF;
1451  if (flags & RANGE_UB_INF)
1452  classNumber |= CLS_UPPER_INF;
1453  if (flags & RANGE_CONTAIN_EMPTY)
1454  classNumber |= CLS_CONTAIN_EMPTY;
1455  }
1456  return classNumber;
1457 }
#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:1763

◆ interval_cmp_lower()

static int interval_cmp_lower ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1476 of file rangetypes_gist.c.

References NonEmptyRange::lower, and range_cmp_bounds().

Referenced by range_gist_double_sorting_split().

1477 {
1478  NonEmptyRange *i1 = (NonEmptyRange *) a;
1479  NonEmptyRange *i2 = (NonEmptyRange *) b;
1480  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1481 
1482  return range_cmp_bounds(typcache, &i1->lower, &i2->lower);
1483 }
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1832
RangeBound lower
void * arg

◆ interval_cmp_upper()

static int interval_cmp_upper ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1489 of file rangetypes_gist.c.

References range_cmp_bounds(), and NonEmptyRange::upper.

Referenced by range_gist_double_sorting_split().

1490 {
1491  NonEmptyRange *i1 = (NonEmptyRange *) a;
1492  NonEmptyRange *i2 = (NonEmptyRange *) b;
1493  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1494 
1495  return range_cmp_bounds(typcache, &i1->upper, &i2->upper);
1496 }
RangeBound upper
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1832
void * arg

◆ range_gist_class_split()

static void range_gist_class_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v,
SplitLR classes_groups 
)
static

Definition at line 919 of file rangetypes_gist.c.

References Assert, DatumGetRangeTypeP, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, OffsetNumberNext, PLACE_LEFT, PLACE_RIGHT, range(), RangeTypePGetDatum, 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().

923 {
924  RangeType *left_range = NULL;
925  RangeType *right_range = NULL;
926  OffsetNumber i,
927  maxoff;
928 
929  maxoff = entryvec->n - 1;
930 
931  v->spl_nleft = 0;
932  v->spl_nright = 0;
933  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
934  {
935  RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
936  int class;
937 
938  /* Get class of range */
939  class = get_gist_range_class(range);
940 
941  /* Place range to appropriate page */
942  if (classes_groups[class] == SPLIT_LEFT)
943  PLACE_LEFT(range, i);
944  else
945  {
946  Assert(classes_groups[class] == SPLIT_RIGHT);
947  PLACE_RIGHT(range, i);
948  }
949  }
950 
951  v->spl_ldatum = RangeTypePGetDatum(left_range);
952  v->spl_rdatum = RangeTypePGetDatum(right_range);
953 }
Datum spl_rdatum
Definition: gist.h:112
int32 n
Definition: gist.h:160
int spl_nleft
Definition: gist.h:106
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:73
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 Assert(condition)
Definition: c.h:670
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
int i

◆ range_gist_consider_split()

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 1353 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().

1356 {
1357  int left_count,
1358  right_count;
1359  float4 ratio,
1360  overlap;
1361 
1362  /*
1363  * Calculate entries distribution ratio assuming most uniform distribution
1364  * of common entries.
1365  */
1366  if (min_left_count >= (context->entries_count + 1) / 2)
1367  left_count = min_left_count;
1368  else if (max_left_count <= context->entries_count / 2)
1369  left_count = max_left_count;
1370  else
1371  left_count = context->entries_count / 2;
1372  right_count = context->entries_count - left_count;
1373 
1374  /*
1375  * Ratio of split: quotient between size of smaller group and total
1376  * entries count. This is necessarily 0.5 or less; if it's less than
1377  * LIMIT_RATIO then we will never accept the new split.
1378  */
1379  ratio = ((float4) Min(left_count, right_count)) /
1380  ((float4) context->entries_count);
1381 
1382  if (ratio > LIMIT_RATIO)
1383  {
1384  bool selectthis = false;
1385 
1386  /*
1387  * The ratio is acceptable, so compare current split with previously
1388  * selected one. We search for minimal overlap (allowing negative
1389  * values) and minimal ratio secondarily. If subtype_diff is
1390  * available, it's used for overlap measure. Without subtype_diff we
1391  * use number of "common entries" as an overlap measure.
1392  */
1393  if (context->has_subtype_diff)
1394  overlap = call_subtype_diff(context->typcache,
1395  left_upper->val,
1396  right_lower->val);
1397  else
1398  overlap = max_left_count - min_left_count;
1399 
1400  /* If there is no previous selection, select this split */
1401  if (context->first)
1402  selectthis = true;
1403  else
1404  {
1405  /*
1406  * Choose the new split if it has a smaller overlap, or same
1407  * overlap but better ratio.
1408  */
1409  if (overlap < context->overlap ||
1410  (overlap == context->overlap && ratio > context->ratio))
1411  selectthis = true;
1412  }
1413 
1414  if (selectthis)
1415  {
1416  /* save information about selected split */
1417  context->first = false;
1418  context->ratio = ratio;
1419  context->overlap = overlap;
1420  context->right_lower = right_lower;
1421  context->left_upper = left_upper;
1422  context->common_left = max_left_count - left_count;
1423  context->common_right = left_count - min_left_count;
1424  }
1425  }
1426 }
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:428
TypeCacheEntry * typcache

◆ range_gist_consistent()

Datum range_gist_consistent ( PG_FUNCTION_ARGS  )

Definition at line 172 of file rangetypes_gist.c.

References DatumGetRangeTypeP, 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 = DatumGetRangeTypeP(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:1543
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:233
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
Datum key
Definition: gist.h:123
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:319
uintptr_t Datum
Definition: postgres.h:372
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
static bool range_gist_consistent_int(TypeCacheEntry *typcache, StrategyNumber strategy, RangeType *key, Datum query)
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:237

◆ range_gist_consistent_int()

static bool range_gist_consistent_int ( TypeCacheEntry typcache,
StrategyNumber  strategy,
RangeType key,
Datum  query 
)
static

Definition at line 765 of file rangetypes_gist.c.

References DatumGetRangeTypeP, 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().

767 {
768  switch (strategy)
769  {
770  case RANGESTRAT_BEFORE:
771  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeTypeP(query)))
772  return false;
773  return (!range_overright_internal(typcache, key,
774  DatumGetRangeTypeP(query)));
775  case RANGESTRAT_OVERLEFT:
776  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeTypeP(query)))
777  return false;
778  return (!range_after_internal(typcache, key,
779  DatumGetRangeTypeP(query)));
780  case RANGESTRAT_OVERLAPS:
781  return range_overlaps_internal(typcache, key,
782  DatumGetRangeTypeP(query));
784  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeTypeP(query)))
785  return false;
786  return (!range_before_internal(typcache, key,
787  DatumGetRangeTypeP(query)));
788  case RANGESTRAT_AFTER:
789  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeTypeP(query)))
790  return false;
791  return (!range_overleft_internal(typcache, key,
792  DatumGetRangeTypeP(query)));
793  case RANGESTRAT_ADJACENT:
794  if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeTypeP(query)))
795  return false;
796  if (range_adjacent_internal(typcache, key,
797  DatumGetRangeTypeP(query)))
798  return true;
799  return range_overlaps_internal(typcache, key,
800  DatumGetRangeTypeP(query));
801  case RANGESTRAT_CONTAINS:
802  return range_contains_internal(typcache, key,
803  DatumGetRangeTypeP(query));
805 
806  /*
807  * Empty ranges are contained by anything, so if key is or
808  * contains any empty ranges, we must descend into it. Otherwise,
809  * descend only if key overlaps the query.
810  */
811  if (RangeIsOrContainsEmpty(key))
812  return true;
813  return range_overlaps_internal(typcache, key,
814  DatumGetRangeTypeP(query));
816  return range_contains_elem_internal(typcache, key, query);
817  case RANGESTRAT_EQ:
818 
819  /*
820  * If query is empty, descend only if the key is or contains any
821  * empty ranges. Otherwise, descend if key contains query.
822  */
823  if (RangeIsEmpty(DatumGetRangeTypeP(query)))
824  return RangeIsOrContainsEmpty(key);
825  return range_contains_internal(typcache, key,
826  DatumGetRangeTypeP(query));
827  default:
828  elog(ERROR, "unrecognized range strategy: %d", strategy);
829  return false; /* keep compiler quiet */
830  }
831 }
#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
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 DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
#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:2341
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:2300

◆ range_gist_consistent_leaf()

static bool range_gist_consistent_leaf ( TypeCacheEntry typcache,
StrategyNumber  strategy,
RangeType key,
Datum  query 
)
static

Definition at line 837 of file rangetypes_gist.c.

References DatumGetRangeTypeP, 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().

839 {
840  switch (strategy)
841  {
842  case RANGESTRAT_BEFORE:
843  return range_before_internal(typcache, key,
844  DatumGetRangeTypeP(query));
845  case RANGESTRAT_OVERLEFT:
846  return range_overleft_internal(typcache, key,
847  DatumGetRangeTypeP(query));
848  case RANGESTRAT_OVERLAPS:
849  return range_overlaps_internal(typcache, key,
850  DatumGetRangeTypeP(query));
852  return range_overright_internal(typcache, key,
853  DatumGetRangeTypeP(query));
854  case RANGESTRAT_AFTER:
855  return range_after_internal(typcache, key,
856  DatumGetRangeTypeP(query));
857  case RANGESTRAT_ADJACENT:
858  return range_adjacent_internal(typcache, key,
859  DatumGetRangeTypeP(query));
860  case RANGESTRAT_CONTAINS:
861  return range_contains_internal(typcache, key,
862  DatumGetRangeTypeP(query));
864  return range_contained_by_internal(typcache, key,
865  DatumGetRangeTypeP(query));
867  return range_contains_elem_internal(typcache, key, query);
868  case RANGESTRAT_EQ:
869  return range_eq_internal(typcache, key, DatumGetRangeTypeP(query));
870  default:
871  elog(ERROR, "unrecognized range strategy: %d", strategy);
872  return false; /* keep compiler quiet */
873  }
874 }
#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:2332
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 DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
#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:2341
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:2300

◆ range_gist_double_sorting_split()

static void range_gist_double_sorting_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v 
)
static

Definition at line 1051 of file rangetypes_gist.c.

References Assert, call_subtype_diff(), common_entry_cmp(), ConsiderSplitContext::common_left, DatumGetRangeTypeP, 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, 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().

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

◆ range_gist_fallback_split()

static void range_gist_fallback_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v 
)
static

Definition at line 881 of file rangetypes_gist.c.

References DatumGetRangeTypeP, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, PLACE_LEFT, PLACE_RIGHT, range(), RangeTypePGetDatum, 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().

884 {
885  RangeType *left_range = NULL;
886  RangeType *right_range = NULL;
887  OffsetNumber i,
888  maxoff,
889  split_idx;
890 
891  maxoff = entryvec->n - 1;
892  /* Split entries before this to left page, after to right: */
893  split_idx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
894 
895  v->spl_nleft = 0;
896  v->spl_nright = 0;
897  for (i = FirstOffsetNumber; i <= maxoff; i++)
898  {
899  RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
900 
901  if (i < split_idx)
902  PLACE_LEFT(range, i);
903  else
904  PLACE_RIGHT(range, i);
905  }
906 
907  v->spl_ldatum = RangeTypePGetDatum(left_range);
908  v->spl_rdatum = RangeTypePGetDatum(right_range);
909 }
Datum spl_rdatum
Definition: gist.h:112
int32 n
Definition: gist.h:160
int spl_nleft
Definition: gist.h:106
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:73
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 DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
int i

◆ range_gist_penalty()

Datum range_gist_penalty ( PG_FUNCTION_ARGS  )

Definition at line 236 of file rangetypes_gist.c.

References call_subtype_diff(), CONTAIN_EMPTY_PENALTY, DatumGetRangeTypeP, 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.

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

◆ range_gist_picksplit()

Datum range_gist_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 493 of file rangetypes_gist.c.

References Abs, Assert, CLS_CONTAIN_EMPTY, CLS_COUNT, CLS_EMPTY, CLS_LOWER_INF, CLS_NORMAL, CLS_UPPER_INF, DatumGetRangeTypeP, 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.

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

◆ range_gist_same()

Datum range_gist_same ( PG_FUNCTION_ARGS  )

Definition at line 652 of file rangetypes_gist.c.

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

653 {
654  RangeType *r1 = PG_GETARG_RANGE_P(0);
655  RangeType *r2 = PG_GETARG_RANGE_P(1);
656  bool *result = (bool *) PG_GETARG_POINTER(2);
657 
658  /*
659  * range_eq will ignore the RANGE_CONTAIN_EMPTY flag, so we have to check
660  * that for ourselves. More generally, if the entries have been properly
661  * normalized, then unequal flags bytes must mean unequal ranges ... so
662  * let's just test all the flag bits at once.
663  */
664  if (range_get_flags(r1) != range_get_flags(r2))
665  *result = false;
666  else
667  {
668  TypeCacheEntry *typcache;
669 
670  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
671 
672  *result = range_eq_internal(typcache, r1, r2);
673  }
674 
675  PG_RETURN_POINTER(result);
676 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1543
#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:241
#define PG_GETARG_RANGE_P(n)
Definition: rangetypes.h:74
char range_get_flags(RangeType *range)
Definition: rangetypes.c:1763

◆ range_gist_single_sorting_split()

static void range_gist_single_sorting_split ( TypeCacheEntry typcache,
GistEntryVector entryvec,
GIST_SPLITVEC v,
bool  use_upper_bound 
)
static

Definition at line 962 of file rangetypes_gist.c.

References Assert, DatumGetRangeTypeP, FirstOffsetNumber, i, idx(), SingleBoundSortItem::index, GISTENTRY::key, GistEntryVector::n, OffsetNumberNext, palloc(), PLACE_LEFT, PLACE_RIGHT, qsort_arg(), range(), range_deserialize(), RangeTypePGetDatum, 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().

966 {
967  SingleBoundSortItem *sortItems;
968  RangeType *left_range = NULL;
969  RangeType *right_range = NULL;
970  OffsetNumber i,
971  maxoff,
972  split_idx;
973 
974  maxoff = entryvec->n - 1;
975 
976  sortItems = (SingleBoundSortItem *)
977  palloc(maxoff * sizeof(SingleBoundSortItem));
978 
979  /*
980  * Prepare auxiliary array and sort the values.
981  */
982  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
983  {
984  RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
985  RangeBound bound2;
986  bool empty;
987 
988  sortItems[i - 1].index = i;
989  /* Put appropriate bound into array */
990  if (use_upper_bound)
991  range_deserialize(typcache, range, &bound2,
992  &sortItems[i - 1].bound, &empty);
993  else
994  range_deserialize(typcache, range, &sortItems[i - 1].bound,
995  &bound2, &empty);
996  Assert(!empty);
997  }
998 
999  qsort_arg(sortItems, maxoff, sizeof(SingleBoundSortItem),
1000  single_bound_cmp, typcache);
1001 
1002  split_idx = maxoff / 2;
1003 
1004  v->spl_nleft = 0;
1005  v->spl_nright = 0;
1006 
1007  for (i = 0; i < maxoff; i++)
1008  {
1009  int idx = sortItems[i].index;
1010  RangeType *range = DatumGetRangeTypeP(entryvec->vector[idx].key);
1011 
1012  if (i < split_idx)
1013  PLACE_LEFT(range, idx);
1014  else
1015  PLACE_RIGHT(range, idx);
1016  }
1017 
1018  v->spl_ldatum = RangeTypePGetDatum(left_range);
1019  v->spl_rdatum = RangeTypePGetDatum(right_range);
1020 }
Datum spl_rdatum
Definition: gist.h:112
int32 n
Definition: gist.h:160
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:264
int spl_nleft
Definition: gist.h:106
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:73
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:1696
#define PLACE_RIGHT(range, off)
Datum spl_ldatum
Definition: gist.h:107
static int single_bound_cmp(const void *a, const void *b, void *arg)
#define Assert(condition)
Definition: c.h:670
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
void * palloc(Size size)
Definition: mcxt.c:848
int i

◆ range_gist_union()

Datum range_gist_union ( PG_FUNCTION_ARGS  )

Definition at line 198 of file rangetypes_gist.c.

References DatumGetRangeTypeP, i, GistEntryVector::n, PG_GETARG_POINTER, PG_RETURN_RANGE_P, 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 = DatumGetRangeTypeP(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  DatumGetRangeTypeP(ent[i].key));
214  }
215 
216  PG_RETURN_RANGE_P(result_range);
217 }
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1543
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
int32 n
Definition: gist.h:160
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
#define PG_RETURN_RANGE_P(x)
Definition: rangetypes.h:76
static RangeType * range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
int i

◆ range_super_union()

static RangeType * range_super_union ( TypeCacheEntry typcache,
RangeType r1,
RangeType r2 
)
static

Definition at line 695 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().

696 {
697  RangeType *result;
698  RangeBound lower1,
699  lower2;
700  RangeBound upper1,
701  upper2;
702  bool empty1,
703  empty2;
704  char flags1,
705  flags2;
706  RangeBound *result_lower;
707  RangeBound *result_upper;
708 
709  range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
710  range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
711  flags1 = range_get_flags(r1);
712  flags2 = range_get_flags(r2);
713 
714  if (empty1)
715  {
716  /* We can return r2 as-is if it already is or contains empty */
717  if (flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
718  return r2;
719  /* Else we'd better copy it (modify-in-place isn't safe) */
720  r2 = rangeCopy(r2);
722  return r2;
723  }
724  if (empty2)
725  {
726  /* We can return r1 as-is if it already is or contains empty */
727  if (flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
728  return r1;
729  /* Else we'd better copy it (modify-in-place isn't safe) */
730  r1 = rangeCopy(r1);
732  return r1;
733  }
734 
735  if (range_cmp_bounds(typcache, &lower1, &lower2) <= 0)
736  result_lower = &lower1;
737  else
738  result_lower = &lower2;
739 
740  if (range_cmp_bounds(typcache, &upper1, &upper2) >= 0)
741  result_upper = &upper1;
742  else
743  result_upper = &upper2;
744 
745  /* optimization to avoid constructing a new range */
746  if (result_lower == &lower1 && result_upper == &upper1 &&
747  ((flags1 & RANGE_CONTAIN_EMPTY) || !(flags2 & RANGE_CONTAIN_EMPTY)))
748  return r1;
749  if (result_lower == &lower2 && result_upper == &upper2 &&
750  ((flags2 & RANGE_CONTAIN_EMPTY) || !(flags1 & RANGE_CONTAIN_EMPTY)))
751  return r2;
752 
753  result = make_range(typcache, result_lower, result_upper, false);
754 
755  if ((flags1 & RANGE_CONTAIN_EMPTY) || (flags2 & RANGE_CONTAIN_EMPTY))
756  range_set_contain_empty(result);
757 
758  return result;
759 }
RangeType * make_range(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty)
Definition: rangetypes.c:1792
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1832
#define RANGE_EMPTY
Definition: rangetypes.h:36
void range_set_contain_empty(RangeType *range)
Definition: rangetypes.c:1777
void range_deserialize(TypeCacheEntry *typcache, RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1696
#define RANGE_CONTAIN_EMPTY
Definition: rangetypes.h:43
#define rangeCopy(r)
char range_get_flags(RangeType *range)
Definition: rangetypes.c:1763

◆ single_bound_cmp()

static int single_bound_cmp ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 1463 of file rangetypes_gist.c.

References SingleBoundSortItem::bound, and range_cmp_bounds().

Referenced by range_gist_single_sorting_split().

1464 {
1467  TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1468 
1469  return range_cmp_bounds(typcache, &i1->bound, &i2->bound);
1470 }
int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
Definition: rangetypes.c:1832
void * arg