Header And Logo
|
#include "postgres.h"#include "access/gist.h"#include "access/skey.h"#include "utils/builtins.h"#include "utils/datum.h"#include "utils/rangetypes.h"
Go to the source code of this file.
| #define CLS_CONTAIN_EMPTY 4 |
Definition at line 32 of file rangetypes_gist.c.
Referenced by range_gist_picksplit().
| #define CLS_COUNT 9 |
Definition at line 35 of file rangetypes_gist.c.
| #define CLS_EMPTY 8 |
Definition at line 33 of file rangetypes_gist.c.
| #define CLS_LOWER_INF 1 |
Definition at line 30 of file rangetypes_gist.c.
Referenced by range_gist_picksplit().
| #define CLS_NORMAL 0 |
Definition at line 29 of file rangetypes_gist.c.
Referenced by range_gist_picksplit().
| #define CLS_UPPER_INF 2 |
Definition at line 31 of file rangetypes_gist.c.
Referenced by range_gist_picksplit().
| #define CONTAIN_EMPTY_PENALTY 1.0 |
Definition at line 48 of file rangetypes_gist.c.
| #define DEFAULT_SUBTYPE_DIFF_PENALTY 1.0 |
Definition at line 49 of file rangetypes_gist.c.
| #define INFINITE_BOUND_PENALTY 2.0 |
Definition at line 47 of file rangetypes_gist.c.
| #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 | ||||
| ) |
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)
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 | ||||
| ) |
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)
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 | ) |
((RangeType *) DatumGetPointer(datumCopy(PointerGetDatum(r), \ false, -1)))
Definition at line 132 of file rangetypes_gist.c.
Referenced by range_super_union().
| enum SplitLR |
Definition at line 61 of file rangetypes_gist.c.
{
SPLIT_LEFT = 0, /* makes initialization to SPLIT_LEFT easier */
SPLIT_RIGHT
} SplitLR;
| static float8 call_subtype_diff | ( | TypeCacheEntry * | typcache, | |
| Datum | val1, | |||
| Datum | val2 | |||
| ) | [static] |
Definition at line 1530 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().
{
float8 value;
value = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
typcache->rng_collation,
val1, val2));
/* Cope with buggy subtype_diff function by returning zero */
if (value >= 0.0)
return value;
return 0.0;
}
| static int common_entry_cmp | ( | const void * | i1, | |
| const void * | i2 | |||
| ) | [static] |
Definition at line 1512 of file rangetypes_gist.c.
Referenced by range_gist_double_sorting_split().
{
double delta1 = ((CommonEntry *) i1)->delta;
double delta2 = ((CommonEntry *) i2)->delta;
if (delta1 < delta2)
return -1;
else if (delta1 > delta2)
return 1;
else
return 0;
}
| static int get_gist_range_class | ( | RangeType * | range | ) | [static] |
Definition at line 1446 of file rangetypes_gist.c.
References RANGE_CONTAIN_EMPTY, RANGE_EMPTY, range_get_flags(), RANGE_LB_INF, and RANGE_UB_INF.
Referenced by range_gist_class_split(), and range_gist_picksplit().
{
int classNumber;
char flags;
flags = range_get_flags(range);
if (flags & RANGE_EMPTY)
{
classNumber = CLS_EMPTY;
}
else
{
classNumber = 0;
if (flags & RANGE_LB_INF)
classNumber |= CLS_LOWER_INF;
if (flags & RANGE_UB_INF)
classNumber |= CLS_UPPER_INF;
if (flags & RANGE_CONTAIN_EMPTY)
classNumber |= CLS_CONTAIN_EMPTY;
}
return classNumber;
}
| static int interval_cmp_lower | ( | const void * | a, | |
| const void * | b, | |||
| void * | arg | |||
| ) | [static] |
Definition at line 1486 of file rangetypes_gist.c.
References NonEmptyRange::lower, and range_cmp_bounds().
Referenced by range_gist_double_sorting_split().
{
NonEmptyRange *i1 = (NonEmptyRange *) a;
NonEmptyRange *i2 = (NonEmptyRange *) b;
TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
return range_cmp_bounds(typcache, &i1->lower, &i2->lower);
}
| static int interval_cmp_upper | ( | const void * | a, | |
| const void * | b, | |||
| void * | arg | |||
| ) | [static] |
Definition at line 1499 of file rangetypes_gist.c.
References range_cmp_bounds(), and NonEmptyRange::upper.
Referenced by range_gist_double_sorting_split().
{
NonEmptyRange *i1 = (NonEmptyRange *) a;
NonEmptyRange *i2 = (NonEmptyRange *) b;
TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
return range_cmp_bounds(typcache, &i1->upper, &i2->upper);
}
| static void range_gist_class_split | ( | TypeCacheEntry * | typcache, | |
| GistEntryVector * | entryvec, | |||
| GIST_SPLITVEC * | v, | |||
| SplitLR * | classes_groups | |||
| ) | [static] |
Definition at line 929 of file rangetypes_gist.c.
References Assert, DatumGetRangeType, FirstOffsetNumber, get_gist_range_class(), i, GISTENTRY::key, GistEntryVector::n, 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().
{
RangeType *left_range = NULL;
RangeType *right_range = NULL;
OffsetNumber i,
maxoff;
maxoff = entryvec->n - 1;
v->spl_nleft = 0;
v->spl_nright = 0;
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
int class;
/* Get class of range */
class = get_gist_range_class(range);
/* Place range to appropriate page */
if (classes_groups[class] == SPLIT_LEFT)
PLACE_LEFT(range, i);
else
{
Assert(classes_groups[class] == SPLIT_RIGHT);
PLACE_RIGHT(range, i);
}
}
v->spl_ldatum = RangeTypeGetDatum(left_range);
v->spl_rdatum = RangeTypeGetDatum(right_range);
}
| Datum range_gist_compress | ( | PG_FUNCTION_ARGS | ) |
Definition at line 221 of file rangetypes_gist.c.
References PG_GETARG_POINTER, and PG_RETURN_POINTER.
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
PG_RETURN_POINTER(entry);
}
| 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 1363 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().
{
int left_count,
right_count;
float4 ratio,
overlap;
/*
* Calculate entries distribution ratio assuming most uniform distribution
* of common entries.
*/
if (min_left_count >= (context->entries_count + 1) / 2)
left_count = min_left_count;
else if (max_left_count <= context->entries_count / 2)
left_count = max_left_count;
else
left_count = context->entries_count / 2;
right_count = context->entries_count - left_count;
/*
* Ratio of split: quotient between size of smaller group and total
* entries count. This is necessarily 0.5 or less; if it's less than
* LIMIT_RATIO then we will never accept the new split.
*/
ratio = ((float4) Min(left_count, right_count)) /
((float4) context->entries_count);
if (ratio > LIMIT_RATIO)
{
bool selectthis = false;
/*
* The ratio is acceptable, so compare current split with previously
* selected one. We search for minimal overlap (allowing negative
* values) and minimal ratio secondarily. If subtype_diff is
* available, it's used for overlap measure. Without subtype_diff we
* use number of "common entries" as an overlap measure.
*/
if (context->has_subtype_diff)
overlap = call_subtype_diff(context->typcache,
left_upper->val,
right_lower->val);
else
overlap = max_left_count - min_left_count;
/* If there is no previous selection, select this split */
if (context->first)
selectthis = true;
else
{
/*
* Choose the new split if it has a smaller overlap, or same
* overlap but better ratio.
*/
if (overlap < context->overlap ||
(overlap == context->overlap && ratio > context->ratio))
selectthis = true;
}
if (selectthis)
{
/* save information about selected split */
context->first = false;
context->ratio = ratio;
context->overlap = overlap;
context->right_lower = right_lower;
context->left_upper = left_upper;
context->common_left = max_left_count - left_count;
context->common_right = left_count - min_left_count;
}
}
}
| 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.
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
Datum query = PG_GETARG_DATUM(1);
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
RangeType *key = DatumGetRangeType(entry->key);
TypeCacheEntry *typcache;
/* All operators served by this function are exact */
*recheck = false;
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
if (GIST_LEAF(entry))
PG_RETURN_BOOL(range_gist_consistent_leaf(typcache, strategy,
key, query));
else
PG_RETURN_BOOL(range_gist_consistent_int(typcache, strategy,
key, query));
}
| static bool range_gist_consistent_int | ( | TypeCacheEntry * | typcache, | |
| StrategyNumber | strategy, | |||
| RangeType * | key, | |||
| Datum | query | |||
| ) | [static] |
Definition at line 775 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().
{
switch (strategy)
{
case RANGESTRAT_BEFORE:
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
return false;
return (!range_overright_internal(typcache, key,
DatumGetRangeType(query)));
case RANGESTRAT_OVERLEFT:
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
return false;
return (!range_after_internal(typcache, key,
DatumGetRangeType(query)));
case RANGESTRAT_OVERLAPS:
return range_overlaps_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_OVERRIGHT:
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
return false;
return (!range_before_internal(typcache, key,
DatumGetRangeType(query)));
case RANGESTRAT_AFTER:
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
return false;
return (!range_overleft_internal(typcache, key,
DatumGetRangeType(query)));
case RANGESTRAT_ADJACENT:
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
return false;
if (range_adjacent_internal(typcache, key,
DatumGetRangeType(query)))
return true;
return range_overlaps_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINS:
return range_contains_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINED_BY:
/*
* Empty ranges are contained by anything, so if key is or
* contains any empty ranges, we must descend into it. Otherwise,
* descend only if key overlaps the query.
*/
if (RangeIsOrContainsEmpty(key))
return true;
return range_overlaps_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINS_ELEM:
return range_contains_elem_internal(typcache, key, query);
case RANGESTRAT_EQ:
/*
* If query is empty, descend only if the key is or contains any
* empty ranges. Otherwise, descend if key contains query.
*/
if (RangeIsEmpty(DatumGetRangeType(query)))
return RangeIsOrContainsEmpty(key);
return range_contains_internal(typcache, key,
DatumGetRangeType(query));
default:
elog(ERROR, "unrecognized range strategy: %d", strategy);
return false; /* keep compiler quiet */
}
}
| static bool range_gist_consistent_leaf | ( | TypeCacheEntry * | typcache, | |
| StrategyNumber | strategy, | |||
| RangeType * | key, | |||
| Datum | query | |||
| ) | [static] |
Definition at line 847 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().
{
switch (strategy)
{
case RANGESTRAT_BEFORE:
return range_before_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_OVERLEFT:
return range_overleft_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_OVERLAPS:
return range_overlaps_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_OVERRIGHT:
return range_overright_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_AFTER:
return range_after_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_ADJACENT:
return range_adjacent_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINS:
return range_contains_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINED_BY:
return range_contained_by_internal(typcache, key,
DatumGetRangeType(query));
case RANGESTRAT_CONTAINS_ELEM:
return range_contains_elem_internal(typcache, key, query);
case RANGESTRAT_EQ:
return range_eq_internal(typcache, key, DatumGetRangeType(query));
default:
elog(ERROR, "unrecognized range strategy: %d", strategy);
return false; /* keep compiler quiet */
}
}
| Datum range_gist_decompress | ( | PG_FUNCTION_ARGS | ) |
Definition at line 229 of file rangetypes_gist.c.
References PG_GETARG_POINTER, and PG_RETURN_POINTER.
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
PG_RETURN_POINTER(entry);
}
| static void range_gist_double_sorting_split | ( | TypeCacheEntry * | typcache, | |
| GistEntryVector * | entryvec, | |||
| GIST_SPLITVEC * | v | |||
| ) | [static] |
Definition at line 1061 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, NonEmptyRange::lower, lower(), GistEntryVector::n, OffsetNumberNext, OidIsValid, palloc(), PLACE_LEFT, PLACE_RIGHT, PointerGetDatum, qsort, qsort_arg(), 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, NonEmptyRange::upper, upper(), RangeBound::val, and GistEntryVector::vector.
Referenced by range_gist_picksplit().
{
ConsiderSplitContext context;
OffsetNumber i,
maxoff;
RangeType *range,
*left_range = NULL,
*right_range = NULL;
int common_entries_count;
NonEmptyRange *by_lower,
*by_upper;
CommonEntry *common_entries;
int nentries,
i1,
i2;
RangeBound *right_lower,
*left_upper;
memset(&context, 0, sizeof(ConsiderSplitContext));
context.typcache = typcache;
context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
maxoff = entryvec->n - 1;
nentries = context.entries_count = maxoff - FirstOffsetNumber + 1;
context.first = true;
/* Allocate arrays for sorted range bounds */
by_lower = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
by_upper = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
/* Fill arrays of bounds */
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
bool empty;
range_deserialize(typcache, range,
&by_lower[i - FirstOffsetNumber].lower,
&by_lower[i - FirstOffsetNumber].upper,
&empty);
Assert(!empty);
}
/*
* Make two arrays of range bounds: one sorted by lower bound and another
* sorted by upper bound.
*/
memcpy(by_upper, by_lower, nentries * sizeof(NonEmptyRange));
qsort_arg(by_lower, nentries, sizeof(NonEmptyRange),
interval_cmp_lower, typcache);
qsort_arg(by_upper, nentries, sizeof(NonEmptyRange),
interval_cmp_upper, typcache);
/*----------
* The goal is to form a left and right range, so that every entry
* range is contained by either left or right interval (or both).
*
* For example, with the ranges (0,1), (1,3), (2,3), (2,4):
*
* 0 1 2 3 4
* +-+
* +---+
* +-+
* +---+
*
* The left and right ranges are of the form (0,a) and (b,4).
* We first consider splits where b is the lower bound of an entry.
* We iterate through all entries, and for each b, calculate the
* smallest possible a. Then we consider splits where a is the
* upper bound of an entry, and for each a, calculate the greatest
* possible b.
*
* In the above example, the first loop would consider splits:
* b=0: (0,1)-(0,4)
* b=1: (0,1)-(1,4)
* b=2: (0,3)-(2,4)
*
* And the second loop:
* a=1: (0,1)-(1,4)
* a=3: (0,3)-(2,4)
* a=4: (0,4)-(2,4)
*----------
*/
/*
* Iterate over lower bound of right group, finding smallest possible
* upper bound of left group.
*/
i1 = 0;
i2 = 0;
right_lower = &by_lower[i1].lower;
left_upper = &by_upper[i2].lower;
while (true)
{
/*
* Find next lower bound of right group.
*/
while (i1 < nentries &&
range_cmp_bounds(typcache, right_lower,
&by_lower[i1].lower) == 0)
{
if (range_cmp_bounds(typcache, &by_lower[i1].upper,
left_upper) > 0)
left_upper = &by_lower[i1].upper;
i1++;
}
if (i1 >= nentries)
break;
right_lower = &by_lower[i1].lower;
/*
* Find count of ranges which anyway should be placed to the left
* group.
*/
while (i2 < nentries &&
range_cmp_bounds(typcache, &by_upper[i2].upper,
left_upper) <= 0)
i2++;
/*
* Consider found split to see if it's better than what we had.
*/
range_gist_consider_split(&context, right_lower, i1, left_upper, i2);
}
/*
* Iterate over upper bound of left group finding greatest possible lower
* bound of right group.
*/
i1 = nentries - 1;
i2 = nentries - 1;
right_lower = &by_lower[i1].upper;
left_upper = &by_upper[i2].upper;
while (true)
{
/*
* Find next upper bound of left group.
*/
while (i2 >= 0 &&
range_cmp_bounds(typcache, left_upper,
&by_upper[i2].upper) == 0)
{
if (range_cmp_bounds(typcache, &by_upper[i2].lower,
right_lower) < 0)
right_lower = &by_upper[i2].lower;
i2--;
}
if (i2 < 0)
break;
left_upper = &by_upper[i2].upper;
/*
* Find count of intervals which anyway should be placed to the right
* group.
*/
while (i1 >= 0 &&
range_cmp_bounds(typcache, &by_lower[i1].lower,
right_lower) >= 0)
i1--;
/*
* Consider found split to see if it's better than what we had.
*/
range_gist_consider_split(&context, right_lower, i1 + 1,
left_upper, i2 + 1);
}
/*
* If we failed to find any acceptable splits, use trivial split.
*/
if (context.first)
{
range_gist_fallback_split(typcache, entryvec, v);
return;
}
/*
* Ok, we have now selected bounds of the groups. Now we have to
* distribute entries themselves. At first we distribute entries which can
* be placed unambiguously and collect "common entries" to array.
*/
/* Allocate vectors for results */
v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
v->spl_nleft = 0;
v->spl_nright = 0;
/*
* Allocate an array for "common entries" - entries which can be placed to
* either group without affecting overlap along selected axis.
*/
common_entries_count = 0;
common_entries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
/*
* Distribute entries which can be distributed unambiguously, and collect
* common entries.
*/
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
RangeBound lower,
upper;
bool empty;
/*
* Get upper and lower bounds along selected axis.
*/
range = DatumGetRangeType(entryvec->vector[i].key);
range_deserialize(typcache, range, &lower, &upper, &empty);
if (range_cmp_bounds(typcache, &upper, context.left_upper) <= 0)
{
/* Fits in the left group */
if (range_cmp_bounds(typcache, &lower, context.right_lower) >= 0)
{
/* Fits also in the right group, so "common entry" */
common_entries[common_entries_count].index = i;
if (context.has_subtype_diff)
{
/*
* delta = (lower - context.right_lower) -
* (context.left_upper - upper)
*/
common_entries[common_entries_count].delta =
call_subtype_diff(typcache,
lower.val,
context.right_lower->val) -
call_subtype_diff(typcache,
context.left_upper->val,
upper.val);
}
else
{
/* Without subtype_diff, take all deltas as zero */
common_entries[common_entries_count].delta = 0;
}
common_entries_count++;
}
else
{
/* Doesn't fit to the right group, so join to the left group */
PLACE_LEFT(range, i);
}
}
else
{
/*
* Each entry should fit on either left or right group. Since this
* entry didn't fit in the left group, it better fit in the right
* group.
*/
Assert(range_cmp_bounds(typcache, &lower,
context.right_lower) >= 0);
PLACE_RIGHT(range, i);
}
}
/*
* Distribute "common entries", if any.
*/
if (common_entries_count > 0)
{
/*
* Sort "common entries" by calculated deltas in order to distribute
* the most ambiguous entries first.
*/
qsort(common_entries, common_entries_count, sizeof(CommonEntry),
common_entry_cmp);
/*
* Distribute "common entries" between groups according to sorting.
*/
for (i = 0; i < common_entries_count; i++)
{
int idx = common_entries[i].index;
range = DatumGetRangeType(entryvec->vector[idx].key);
/*
* Check if we have to place this entry in either group to achieve
* LIMIT_RATIO.
*/
if (i < context.common_left)
PLACE_LEFT(range, idx);
else
PLACE_RIGHT(range, idx);
}
}
v->spl_ldatum = PointerGetDatum(left_range);
v->spl_rdatum = PointerGetDatum(right_range);
}
| static void range_gist_fallback_split | ( | TypeCacheEntry * | typcache, | |
| GistEntryVector * | entryvec, | |||
| GIST_SPLITVEC * | v | |||
| ) | [static] |
Definition at line 891 of file rangetypes_gist.c.
References DatumGetRangeType, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, 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().
{
RangeType *left_range = NULL;
RangeType *right_range = NULL;
OffsetNumber i,
maxoff,
split_idx;
maxoff = entryvec->n - 1;
/* Split entries before this to left page, after to right: */
split_idx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
v->spl_nleft = 0;
v->spl_nright = 0;
for (i = FirstOffsetNumber; i <= maxoff; i++)
{
RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
if (i < split_idx)
PLACE_LEFT(range, i);
else
PLACE_RIGHT(range, i);
}
v->spl_ldatum = RangeTypeGetDatum(left_range);
v->spl_rdatum = RangeTypeGetDatum(right_range);
}
| Datum range_gist_penalty | ( | PG_FUNCTION_ARGS | ) |
Definition at line 247 of file rangetypes_gist.c.
References call_subtype_diff(), DatumGetRangeType, elog, ERROR, FmgrInfo::fn_oid, get_float4_infinity(), RangeBound::infinite, 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.
{
GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
float *penalty = (float *) PG_GETARG_POINTER(2);
RangeType *orig = DatumGetRangeType(origentry->key);
RangeType *new = DatumGetRangeType(newentry->key);
TypeCacheEntry *typcache;
bool has_subtype_diff;
RangeBound orig_lower,
new_lower,
orig_upper,
new_upper;
bool orig_empty,
new_empty;
if (RangeTypeGetOid(orig) != RangeTypeGetOid(new))
elog(ERROR, "range types do not match");
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(orig));
has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
range_deserialize(typcache, orig, &orig_lower, &orig_upper, &orig_empty);
range_deserialize(typcache, new, &new_lower, &new_upper, &new_empty);
/*
* Distinct branches for handling distinct classes of ranges. Note that
* penalty values only need to be commensurate within the same class of
* new range.
*/
if (new_empty)
{
/* Handle insertion of empty range */
if (orig_empty)
{
/*
* The best case is to insert it to empty original range.
* Insertion here means no broadening of original range. Also
* original range is the most narrow.
*/
*penalty = 0.0;
}
else if (RangeIsOrContainsEmpty(orig))
{
/*
* The second case is to insert empty range into range which
* contains at least one underlying empty range. There is still
* no broadening of original range, but original range is not as
* narrow as possible.
*/
*penalty = CONTAIN_EMPTY_PENALTY;
}
else if (orig_lower.infinite && orig_upper.infinite)
{
/*
* Original range requires broadening. (-inf; +inf) is most far
* from normal range in this case.
*/
*penalty = 2 * CONTAIN_EMPTY_PENALTY;
}
else if (orig_lower.infinite || orig_upper.infinite)
{
/*
* (-inf, x) or (x, +inf) original ranges are closer to normal
* ranges, so it's worse to mix it with empty ranges.
*/
*penalty = 3 * CONTAIN_EMPTY_PENALTY;
}
else
{
/*
* The least preferred case is broadening of normal range.
*/
*penalty = 4 * CONTAIN_EMPTY_PENALTY;
}
}
else if (new_lower.infinite && new_upper.infinite)
{
/* Handle insertion of (-inf, +inf) range */
if (orig_lower.infinite && orig_upper.infinite)
{
/*
* Best case is inserting to (-inf, +inf) original range.
*/
*penalty = 0.0;
}
else if (orig_lower.infinite || orig_upper.infinite)
{
/*
* When original range is (-inf, x) or (x, +inf) it requires
* broadening of original range (extension of one bound to
* infinity).
*/
*penalty = INFINITE_BOUND_PENALTY;
}
else
{
/*
* Insertion to normal original range is least preferred.
*/
*penalty = 2 * INFINITE_BOUND_PENALTY;
}
if (RangeIsOrContainsEmpty(orig))
{
/*
* Original range is narrower when it doesn't contain empty
* ranges. Add additional penalty otherwise.
*/
*penalty += CONTAIN_EMPTY_PENALTY;
}
}
else if (new_lower.infinite)
{
/* Handle insertion of (-inf, x) range */
if (!orig_empty && orig_lower.infinite)
{
if (orig_upper.infinite)
{
/*
* (-inf, +inf) range won't be extended by insertion of (-inf,
* x) range. It's a less desirable case than insertion to
* (-inf, y) original range without extension, because in that
* case original range is narrower. But we can't express that
* in single float value.
*/
*penalty = 0.0;
}
else
{
if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
{
/*
* Get extension of original range using subtype_diff. Use
* constant if subtype_diff unavailable.
*/
if (has_subtype_diff)
*penalty = call_subtype_diff(typcache,
new_upper.val,
orig_upper.val);
else
*penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
}
else
{
/* No extension of original range */
*penalty = 0.0;
}
}
}
else
{
/*
* If lower bound of original range is not -inf, then extension of
* it is infinity.
*/
*penalty = get_float4_infinity();
}
}
else if (new_upper.infinite)
{
/* Handle insertion of (x, +inf) range */
if (!orig_empty && orig_upper.infinite)
{
if (orig_lower.infinite)
{
/*
* (-inf, +inf) range won't be extended by insertion of (x,
* +inf) range. It's a less desirable case than insertion to
* (y, +inf) original range without extension, because in that
* case original range is narrower. But we can't express that
* in single float value.
*/
*penalty = 0.0;
}
else
{
if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
{
/*
* Get extension of original range using subtype_diff. Use
* constant if subtype_diff unavailable.
*/
if (has_subtype_diff)
*penalty = call_subtype_diff(typcache,
orig_lower.val,
new_lower.val);
else
*penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
}
else
{
/* No extension of original range */
*penalty = 0.0;
}
}
}
else
{
/*
* If upper bound of original range is not +inf, then extension of
* it is infinity.
*/
*penalty = get_float4_infinity();
}
}
else
{
/* Handle insertion of normal (non-empty, non-infinite) range */
if (orig_empty || orig_lower.infinite || orig_upper.infinite)
{
/*
* Avoid mixing normal ranges with infinite and empty ranges.
*/
*penalty = get_float4_infinity();
}
else
{
/*
* Calculate extension of original range by calling subtype_diff.
* Use constant if subtype_diff unavailable.
*/
float8 diff = 0.0;
if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
{
if (has_subtype_diff)
diff += call_subtype_diff(typcache,
orig_lower.val,
new_lower.val);
else
diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
}
if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
{
if (has_subtype_diff)
diff += call_subtype_diff(typcache,
new_upper.val,
orig_upper.val);
else
diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
}
*penalty = diff;
}
}
PG_RETURN_POINTER(penalty);
}
| Datum range_gist_picksplit | ( | PG_FUNCTION_ARGS | ) |
Definition at line 504 of file rangetypes_gist.c.
References Abs, Assert, CLS_CONTAIN_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, and GistEntryVector::vector.
{
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
TypeCacheEntry *typcache;
OffsetNumber i;
RangeType *pred_left;
int nbytes;
OffsetNumber maxoff;
int count_in_classes[CLS_COUNT];
int j;
int non_empty_classes_count = 0;
int biggest_class = -1;
int biggest_class_count = 0;
int total_count;
/* use first item to look up range type's info */
pred_left = DatumGetRangeType(entryvec->vector[FirstOffsetNumber].key);
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(pred_left));
maxoff = entryvec->n - 1;
nbytes = (maxoff + 1) * sizeof(OffsetNumber);
v->spl_left = (OffsetNumber *) palloc(nbytes);
v->spl_right = (OffsetNumber *) palloc(nbytes);
/*
* Get count distribution of range classes.
*/
memset(count_in_classes, 0, sizeof(count_in_classes));
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
count_in_classes[get_gist_range_class(range)]++;
}
/*
* Count non-empty classes and find biggest class.
*/
total_count = maxoff;
for (j = 0; j < CLS_COUNT; j++)
{
if (count_in_classes[j] > 0)
{
if (count_in_classes[j] > biggest_class_count)
{
biggest_class_count = count_in_classes[j];
biggest_class = j;
}
non_empty_classes_count++;
}
}
Assert(non_empty_classes_count > 0);
if (non_empty_classes_count == 1)
{
/* One non-empty class, so split inside class */
if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_NORMAL)
{
/* double sorting split for normal ranges */
range_gist_double_sorting_split(typcache, entryvec, v);
}
else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_LOWER_INF)
{
/* upper bound sorting split for (-inf, x) ranges */
range_gist_single_sorting_split(typcache, entryvec, v, true);
}
else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_UPPER_INF)
{
/* lower bound sorting split for (x, +inf) ranges */
range_gist_single_sorting_split(typcache, entryvec, v, false);
}
else
{
/* trivial split for all (-inf, +inf) or all empty ranges */
range_gist_fallback_split(typcache, entryvec, v);
}
}
else
{
/*
* Class based split.
*
* To which side of the split should each class go? Initialize them
* all to go to the left side.
*/
SplitLR classes_groups[CLS_COUNT];
memset(classes_groups, 0, sizeof(classes_groups));
if (count_in_classes[CLS_NORMAL] > 0)
{
/* separate normal ranges if any */
classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
}
else
{
/*----------
* Try to split classes in one of two ways:
* 1) containing infinities - not containing infinities
* 2) containing empty - not containing empty
*
* Select the way which balances the ranges between left and right
* the best. If split in these ways is not possible, there are at
* most 3 classes, so just separate biggest class.
*----------
*/
int infCount,
nonInfCount;
int emptyCount,
nonEmptyCount;
nonInfCount =
count_in_classes[CLS_NORMAL] +
count_in_classes[CLS_CONTAIN_EMPTY] +
count_in_classes[CLS_EMPTY];
infCount = total_count - nonInfCount;
nonEmptyCount =
count_in_classes[CLS_NORMAL] +
count_in_classes[CLS_LOWER_INF] +
count_in_classes[CLS_UPPER_INF] +
count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF];
emptyCount = total_count - nonEmptyCount;
if (infCount > 0 && nonInfCount > 0 &&
(Abs(infCount - nonInfCount) <=
Abs(emptyCount - nonEmptyCount)))
{
classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT;
classes_groups[CLS_EMPTY] = SPLIT_RIGHT;
}
else if (emptyCount > 0 && nonEmptyCount > 0)
{
classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
classes_groups[CLS_LOWER_INF] = SPLIT_RIGHT;
classes_groups[CLS_UPPER_INF] = SPLIT_RIGHT;
classes_groups[CLS_LOWER_INF | CLS_UPPER_INF] = SPLIT_RIGHT;
}
else
{
/*
* Either total_count == emptyCount or total_count ==
* infCount.
*/
classes_groups[biggest_class] = SPLIT_RIGHT;
}
}
range_gist_class_split(typcache, entryvec, v, classes_groups);
}
PG_RETURN_POINTER(v);
}
| Datum range_gist_same | ( | PG_FUNCTION_ARGS | ) |
Definition at line 663 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.
{
RangeType *r1 = PG_GETARG_RANGE(0);
RangeType *r2 = PG_GETARG_RANGE(1);
bool *result = (bool *) PG_GETARG_POINTER(2);
/*
* range_eq will ignore the RANGE_CONTAIN_EMPTY flag, so we have to check
* that for ourselves. More generally, if the entries have been properly
* normalized, then unequal flags bytes must mean unequal ranges ... so
* let's just test all the flag bits at once.
*/
if (range_get_flags(r1) != range_get_flags(r2))
*result = false;
else
{
TypeCacheEntry *typcache;
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
*result = range_eq_internal(typcache, r1, r2);
}
PG_RETURN_POINTER(result);
}
| static void range_gist_single_sorting_split | ( | TypeCacheEntry * | typcache, | |
| GistEntryVector * | entryvec, | |||
| GIST_SPLITVEC * | v, | |||
| bool | use_upper_bound | |||
| ) | [static] |
Definition at line 972 of file rangetypes_gist.c.
References Assert, DatumGetRangeType, FirstOffsetNumber, i, idx(), SingleBoundSortItem::index, GISTENTRY::key, GistEntryVector::n, 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().
{
SingleBoundSortItem *sortItems;
RangeType *left_range = NULL;
RangeType *right_range = NULL;
OffsetNumber i,
maxoff,
split_idx;
maxoff = entryvec->n - 1;
sortItems = (SingleBoundSortItem *)
palloc(maxoff * sizeof(SingleBoundSortItem));
/*
* Prepare auxiliary array and sort the values.
*/
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
RangeType *range = DatumGetRangeType(entryvec->vector[i].key);
RangeBound bound2;
bool empty;
sortItems[i - 1].index = i;
/* Put appropriate bound into array */
if (use_upper_bound)
range_deserialize(typcache, range, &bound2,
&sortItems[i - 1].bound, &empty);
else
range_deserialize(typcache, range, &sortItems[i - 1].bound,
&bound2, &empty);
Assert(!empty);
}
qsort_arg(sortItems, maxoff, sizeof(SingleBoundSortItem),
single_bound_cmp, typcache);
split_idx = maxoff / 2;
v->spl_nleft = 0;
v->spl_nright = 0;
for (i = 0; i < maxoff; i++)
{
int idx = sortItems[i].index;
RangeType *range = DatumGetRangeType(entryvec->vector[idx].key);
if (i < split_idx)
PLACE_LEFT(range, idx);
else
PLACE_RIGHT(range, idx);
}
v->spl_ldatum = RangeTypeGetDatum(left_range);
v->spl_rdatum = RangeTypeGetDatum(right_range);
}
| 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.
{
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
GISTENTRY *ent = entryvec->vector;
RangeType *result_range;
TypeCacheEntry *typcache;
int i;
result_range = DatumGetRangeType(ent[0].key);
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(result_range));
for (i = 1; i < entryvec->n; i++)
{
result_range = range_super_union(typcache, result_range,
DatumGetRangeType(ent[i].key));
}
PG_RETURN_RANGE(result_range);
}
| static RangeType * range_super_union | ( | TypeCacheEntry * | typcache, | |
| RangeType * | r1, | |||
| RangeType * | r2 | |||
| ) | [static] |
Definition at line 705 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().
{
RangeType *result;
RangeBound lower1,
lower2;
RangeBound upper1,
upper2;
bool empty1,
empty2;
char flags1,
flags2;
RangeBound *result_lower;
RangeBound *result_upper;
range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
flags1 = range_get_flags(r1);
flags2 = range_get_flags(r2);
if (empty1)
{
/* We can return r2 as-is if it already is or contains empty */
if (flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
return r2;
/* Else we'd better copy it (modify-in-place isn't safe) */
r2 = rangeCopy(r2);
range_set_contain_empty(r2);
return r2;
}
if (empty2)
{
/* We can return r1 as-is if it already is or contains empty */
if (flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
return r1;
/* Else we'd better copy it (modify-in-place isn't safe) */
r1 = rangeCopy(r1);
range_set_contain_empty(r1);
return r1;
}
if (range_cmp_bounds(typcache, &lower1, &lower2) <= 0)
result_lower = &lower1;
else
result_lower = &lower2;
if (range_cmp_bounds(typcache, &upper1, &upper2) >= 0)
result_upper = &upper1;
else
result_upper = &upper2;
/* optimization to avoid constructing a new range */
if (result_lower == &lower1 && result_upper == &upper1 &&
((flags1 & RANGE_CONTAIN_EMPTY) || !(flags2 & RANGE_CONTAIN_EMPTY)))
return r1;
if (result_lower == &lower2 && result_upper == &upper2 &&
((flags2 & RANGE_CONTAIN_EMPTY) || !(flags1 & RANGE_CONTAIN_EMPTY)))
return r2;
result = make_range(typcache, result_lower, result_upper, false);
if ((flags1 & RANGE_CONTAIN_EMPTY) || (flags2 & RANGE_CONTAIN_EMPTY))
range_set_contain_empty(result);
return result;
}
| static int single_bound_cmp | ( | const void * | a, | |
| const void * | b, | |||
| void * | arg | |||
| ) | [static] |
Definition at line 1473 of file rangetypes_gist.c.
References SingleBoundSortItem::bound, and range_cmp_bounds().
Referenced by range_gist_single_sorting_split().
{
SingleBoundSortItem *i1 = (SingleBoundSortItem *) a;
SingleBoundSortItem *i2 = (SingleBoundSortItem *) b;
TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
return range_cmp_bounds(typcache, &i1->bound, &i2->bound);
}
1.7.1