*** a/src/backend/utils/adt/rangetypes_gist.c --- b/src/backend/utils/adt/rangetypes_gist.c *************** *** 39,45 **** ((RangeType *) DatumGetPointer(datumCopy(PointerGetDatum(r), \ false, -1))) ! /* Minimum accepted ratio of split */ #define LIMIT_RATIO 0.3 /* Helper macros to place an entry in the left or right group */ --- 39,49 ---- ((RangeType *) DatumGetPointer(datumCopy(PointerGetDatum(r), \ false, -1))) ! /* ! * Minimum accepted ratio of split for items of the same class. If the items ! * are of different classes, it will separate along those lines regardless of ! * the ratio. ! */ #define LIMIT_RATIO 0.3 /* Helper macros to place an entry in the left or right group */ *************** *** 66,72 **** * GiST. Each unique combination of properties is a class. CLS_EMPTY cannot be * combined with anything else. */ ! #define CLS_ORDINAL 0 /* Ordinal ranges (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 */ --- 70,76 ---- * GiST. Each unique combination of properties is a class. CLS_EMPTY cannot be * combined with anything else. */ ! #define CLS_NORMAL 0 /* Normal ranges (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 */ *************** *** 76,81 **** --- 80,102 ---- * of properties. CLS_EMPTY doesn't combine with * anything else, so it's only 2^3 + 1. */ + /* + * Auxiliary structure for picksplit based on single sorting. + */ + typedef struct + { + int index; + RangeBound bound; + TypeCacheEntry *typcache; + } PickSplitSortItem; + + /* place on left or right side of split? */ + typedef enum + { + SPLIT_LEFT = 0, /* makes initialization to SPLIT_LEFT easier */ + SPLIT_RIGHT + } SplitLR; + static RangeType *range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2); static bool range_gist_consistent_int(FmgrInfo *flinfo, *************** *** 97,103 **** static int sort_item_cmp(const void *a, const void *b); static void range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, ! int classesGroups[CLS_COUNT]); static void range_gist_double_sorting_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v); --- 118,124 ---- static void range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v, ! SplitLR *classes_groups); static void range_gist_double_sorting_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, GIST_SPLITVEC *v); *************** *** 106,121 **** static int interval_cmp_upper(const void *a, const void *b); static int common_entry_cmp(const void *i1, const void *i2); static float8 non_negative(float8 value); - /* - * Auxiliary structure for picksplit based on single sorting. - */ - typedef struct - { - int index; - RangeBound bound; - TypeCacheEntry *typcache; - } PickSplitSortItem; - /* GiST query consistency check */ Datum range_gist_consistent(PG_FUNCTION_ARGS) --- 127,132 ---- *************** *** 247,260 **** range_gist_penalty(PG_FUNCTION_ARGS) { /* * It's better to mix empty range with infinities (i.e. with ! * another special cases) than with ordinal ranges. */ *penalty = 2.0; } else if (orig_lower.infinite || orig_upper.infinite) { /* ! * (-inf, x) or (x, +inf) original ranges are closer to ordinal * ranges, so it's worse to mix it with empty ranges. */ *penalty = 3.0; --- 258,271 ---- { /* * It's better to mix empty range with infinities (i.e. with ! * another special cases) than with normal ranges. */ *penalty = 2.0; } 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.0; *************** *** 262,268 **** range_gist_penalty(PG_FUNCTION_ARGS) else { /* ! * The least prefered case is to mix empty ranges with ordinal * non-empty and non-infinite ranges. */ *penalty = 4.0; --- 273,279 ---- else { /* ! * The least prefered case is to mix empty ranges with normal * non-empty and non-infinite ranges. */ *penalty = 4.0; *************** *** 291,297 **** range_gist_penalty(PG_FUNCTION_ARGS) else { /* ! * Insertion to ordinal original range gives us the worst * extention. */ *penalty = 4.0; --- 302,308 ---- else { /* ! * Insertion to normal original range gives us the worst * extention. */ *penalty = 4.0; *************** *** 398,408 **** range_gist_penalty(PG_FUNCTION_ARGS) } else { ! /* Handle insertion of ordinal non-empty and non-infinite range */ if (orig_empty || orig_lower.infinite || orig_upper.infinite) { /* ! * Avoid mixing ordinal ranges with infinite and empty ranges. */ *penalty = get_float8_infinity(); } --- 409,419 ---- } else { ! /* Handle insertion of normal non-empty and non-infinite range */ if (orig_empty || orig_lower.infinite || orig_upper.infinite) { /* ! * Avoid mixing normal ranges with infinite and empty ranges. */ *penalty = get_float8_infinity(); } *************** *** 554,565 **** range_gist_single_sorting_split(TypeCacheEntry *typcache, /* * Split algorithm based on classes of ranges. See getRangeClass for classes ! * definition. classes_groups array defines the number of page (1 or 2) where ! * to place corresponding class of ranges. */ static void range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, ! GIST_SPLITVEC *v, int classes_groups[CLS_COUNT]) { RangeType *left_range = NULL; RangeType *right_range = NULL; --- 565,576 ---- /* * Split algorithm based on classes of ranges. See getRangeClass for classes ! * definition. classes_groups is an array of length CLS_COUNT indicating the ! * side of the split to which each class should go. */ static void range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, ! GIST_SPLITVEC *v, SplitLR *classes_groups) { RangeType *left_range = NULL; RangeType *right_range = NULL; *************** *** 583,592 **** range_gist_class_split(TypeCacheEntry *typcache, GistEntryVector *entryvec, class = get_gist_range_class(typcache, range); /* Place range to appropriate page */ ! if (classes_groups[class] == 1) PLACE_LEFT(range, i); ! else PLACE_RIGHT(range, i); } v->spl_ldatum = RangeTypeGetDatum(left_range); --- 594,605 ---- class = get_gist_range_class(typcache, range); /* Place range to appropriate page */ ! if (classes_groups[class] == SPLIT_LEFT) PLACE_LEFT(range, i); ! else if (classes_groups[class] == SPLIT_RIGHT) PLACE_RIGHT(range, i); + else + Assert(false); } v->spl_ldatum = RangeTypeGetDatum(left_range); *************** *** 654,680 **** typedef struct RangeBound *left_upper; /* upper bound of left interval */ RangeBound *right_lower; /* lower bound of right interval */ ! float4 ratio; float4 overlap; int common_left, common_right; } ConsiderSplitContext; /* ! * Interval represents projection of box to axis. */ typedef struct { RangeBound lower, upper; TypeCacheEntry *typcache; ! } RangeBounds; /* * Consider replacement of currently selected split with the better one. */ static void inline range_gist_consider_split(ConsiderSplitContext *context, ! RangeBound *right_lower, int min_left_count, ! RangeBound *left_upper, int max_left_count) { int left_count, right_count; --- 667,696 ---- RangeBound *left_upper; /* upper bound of left interval */ RangeBound *right_lower; /* lower bound of right interval */ ! float4 ratio; /* split ratio */ ! /* amount of overlap between left and right page predicate */ float4 overlap; + /* common entries destined for each side */ int common_left, common_right; } ConsiderSplitContext; /* ! * Interval represents projection of box to axis. Cannot represent empty ! * ranges. */ typedef struct { RangeBound lower, upper; TypeCacheEntry *typcache; ! } NonEmptyRange; /* * Consider replacement of currently selected split with the better one. */ static void inline range_gist_consider_split(ConsiderSplitContext *context, ! RangeBound *right_lower, int min_left_count, ! RangeBound *left_upper, int max_left_count) { int left_count, right_count; *************** *** 712,720 **** range_gist_consider_split(ConsiderSplitContext *context, /* * The ratio is acceptable, so compare current split with previously * selected one. We search for minimal overlap (allowing negative ! * values) and minimal ration (between same overlaps). 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->subtype_diff) --- 728,736 ---- /* * 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->subtype_diff) *************** *** 808,815 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, *left_range = NULL, *right_range = NULL; int common_entries_count; ! RangeBounds *bounds_lower, ! *bounds_upper; CommonEntry *common_entries; int nentries, i1, i2; RangeBound *right_lower, *left_upper; --- 824,831 ---- *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; *************** *** 821,828 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, context.first = true; /* Allocate arrays for sorted range bounds */ ! bounds_lower = (RangeBounds *) palloc(nentries * sizeof(RangeBounds)); ! bounds_upper = (RangeBounds *) palloc(nentries * sizeof(RangeBounds)); /* Fill arrays of bounds */ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) --- 837,844 ---- 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)) *************** *** 832,843 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, range = DatumGetRangeType(entryvec->vector[i].key); ! bounds_lower[i - FirstOffsetNumber].typcache = typcache; range_deserialize( typcache, range, ! &bounds_lower[i - FirstOffsetNumber].lower, ! &bounds_lower[i - FirstOffsetNumber].upper, &empty); } --- 848,859 ---- range = DatumGetRangeType(entryvec->vector[i].key); ! by_lower[i - FirstOffsetNumber].typcache = typcache; range_deserialize( typcache, range, ! &by_lower[i - FirstOffsetNumber].lower, ! &by_lower[i - FirstOffsetNumber].upper, &empty); } *************** *** 847,857 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, * Make two arrays of range bounds: one sorted by lower bound and another * sorted by upper bound. */ ! memcpy(bounds_upper, bounds_lower, ! sizeof(RangeBounds) * nentries); ! qsort(bounds_lower, nentries, sizeof(RangeBounds), interval_cmp_lower); ! qsort(bounds_upper, nentries, sizeof(RangeBounds), interval_cmp_upper); /*---- --- 863,873 ---- * Make two arrays of range bounds: one sorted by lower bound and another * sorted by upper bound. */ ! memcpy(by_upper, by_lower, ! sizeof(NonEmptyRange) * nentries); ! qsort(by_lower, nentries, sizeof(NonEmptyRange), interval_cmp_lower); ! qsort(by_upper, nentries, sizeof(NonEmptyRange), interval_cmp_upper); /*---- *************** *** 890,920 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, */ i1 = 0; i2 = 0; ! right_lower = &bounds_lower[i1].lower; ! left_upper = &bounds_upper[i2].lower; while (true) { /* * Find next lower bound of right group. */ while (i1 < nentries && range_cmp_bounds(typcache, right_lower, ! &bounds_lower[i1].lower) == 0) { ! if (range_cmp_bounds(typcache, &bounds_lower[i1].upper, left_upper) > 0) ! left_upper = &bounds_lower[i1].upper; i1++; } if (i1 >= nentries) break; ! right_lower = &bounds_lower[i1].lower; /* * Find count of ranges which anyway should be placed to the * left group. */ while (i2 < nentries && range_cmp_bounds(typcache, ! &bounds_upper[i2].upper, left_upper) <= 0) i2++; /* --- 906,936 ---- */ 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++; /* *************** *** 929,959 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, */ i1 = nentries - 1; i2 = nentries - 1; ! right_lower = &bounds_lower[i1].upper; ! left_upper = &bounds_upper[i2].upper; while (true) { /* * Find next upper bound of left group. */ while (i2 >= 0 && range_cmp_bounds(typcache, left_upper, ! &bounds_upper[i2].upper) == 0) { ! if (range_cmp_bounds(typcache, &bounds_upper[i2].lower, ! right_lower) < 0) ! right_lower = &bounds_upper[i2].lower; i2--; } if (i2 < 0) break; ! left_upper = &bounds_upper[i2].upper; /* * Find count of intervals which anyway should be placed to the * right group. */ ! while (i1 >= 0 && range_cmp_bounds(typcache, &bounds_lower[i1].lower, ! right_lower) >= 0) i1--; /* --- 945,975 ---- */ 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--; /* *************** *** 1009,1021 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, if (range_cmp_bounds(typcache, &upper, context.left_upper) <= 0) { ! /* Fits to the left group */ if (range_cmp_bounds(typcache, &lower, context.right_lower) >= 0) { ! /* Fits also to the right group, so "common entry" */ common_entries[common_entries_count].index = i; if (context.subtype_diff) { common_entries[common_entries_count].delta = Abs( DatumGetFloat8(FunctionCall2(context.subtype_diff, lower.val, context.right_lower->val)) - --- 1025,1041 ---- 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.subtype_diff) { + /* + * delta = abs((lower - context.right_lower) - + * (context.left_upper - upper)) + */ common_entries[common_entries_count].delta = Abs( DatumGetFloat8(FunctionCall2(context.subtype_diff, lower.val, context.right_lower->val)) - *************** *** 1041,1046 **** range_gist_double_sorting_split(TypeCacheEntry *typcache, --- 1061,1068 ---- * entry didn't fit on the left group, it better fit in the right * group. */ + Assert(range_cmp_bounds( + typcache, &lower, context.right_lower) >= 0); PLACE_RIGHT(range, i); } } *************** *** 1140,1151 **** range_gist_picksplit(PG_FUNCTION_ARGS) } } if (non_empty_classes_count == 1) { /* One non-empty class, so split inside class */ if (biggest_class == 0 || biggest_class == CLS_CONTAIN_EMPTY) { ! /* double sorting split for ordinal ranges*/ range_gist_double_sorting_split(typcache, entryvec, v); } else if (biggest_class == CLS_LOWER_INF || --- 1162,1175 ---- } } + Assert(non_empty_classes_count > 0); + if (non_empty_classes_count == 1) { /* One non-empty class, so split inside class */ if (biggest_class == 0 || biggest_class == CLS_CONTAIN_EMPTY) { ! /* double sorting split for normal ranges*/ range_gist_double_sorting_split(typcache, entryvec, v); } else if (biggest_class == CLS_LOWER_INF || *************** *** 1168,1182 **** range_gist_picksplit(PG_FUNCTION_ARGS) } else { ! /* There are different classes, split between classes */ ! int classes_groups[CLS_COUNT] = {1, 1, 1, 1, 1, 1, 1, 1, 1}; ! if (count_in_classes[CLS_ORDINAL] > 0) { ! /* ! * Separate ordinal ranges if any; ! */ ! classes_groups[CLS_ORDINAL] = 2; } else { --- 1192,1207 ---- } else { ! /* ! * To which side of the split should each class go? Initialize them all ! * to go to the left side. ! */ ! SplitLR classes_groups[CLS_COUNT] = {SPLIT_LEFT}; ! if (count_in_classes[CLS_NORMAL] > 0) { ! /* separate normal ranges if any */ ! classes_groups[CLS_NORMAL] = SPLIT_RIGHT; } else { *************** *** 1189,1200 **** range_gist_picksplit(PG_FUNCTION_ARGS) * 3 classes. Then just separate biggest class. */ int nonInfCount = ! count_in_classes[CLS_ORDINAL] + count_in_classes[CLS_CONTAIN_EMPTY] + count_in_classes[CLS_EMPTY]; int nonEmptyCount = ! count_in_classes[CLS_ORDINAL] + count_in_classes[CLS_LOWER_INF] + count_in_classes[CLS_UPPER_INF] + count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF]; --- 1214,1225 ---- * 3 classes. Then just separate biggest class. */ int nonInfCount = ! count_in_classes[CLS_NORMAL] + count_in_classes[CLS_CONTAIN_EMPTY] + count_in_classes[CLS_EMPTY]; int 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]; *************** *** 1202,1221 **** range_gist_picksplit(PG_FUNCTION_ARGS) Abs(total_count - 2 * nonInfCount) <= Abs(total_count - 2 * nonEmptyCount))) { ! classes_groups[CLS_ORDINAL] = 2; ! classes_groups[CLS_CONTAIN_EMPTY] = 2; ! classes_groups[CLS_EMPTY] = 2; } else if (nonEmptyCount > 0 && nonEmptyCount < total_count) { ! classes_groups[CLS_ORDINAL] = 2; ! classes_groups[CLS_LOWER_INF] = 2; ! classes_groups[CLS_UPPER_INF] = 2; ! classes_groups[CLS_LOWER_INF | CLS_UPPER_INF] = 2; } else { ! classes_groups[biggest_class] = 2; } } /* Class based split */ --- 1227,1246 ---- Abs(total_count - 2 * nonInfCount) <= Abs(total_count - 2 * nonEmptyCount))) { ! classes_groups[CLS_NORMAL] = SPLIT_RIGHT; ! classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT; ! classes_groups[CLS_EMPTY] = SPLIT_RIGHT; } else if (nonEmptyCount > 0 && nonEmptyCount < total_count) { ! 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 { ! classes_groups[biggest_class] = SPLIT_RIGHT; } } /* Class based split */ *************** *** 1540,1547 **** sort_item_cmp(const void *a, const void *b) static int interval_cmp_lower(const void *a, const void *b) { ! RangeBounds *i1 = (RangeBounds *)a; ! RangeBounds *i2 = (RangeBounds *)b; return range_cmp_bounds(i1->typcache, &i1->lower, &i2->lower); } --- 1565,1572 ---- static int interval_cmp_lower(const void *a, const void *b) { ! NonEmptyRange *i1 = (NonEmptyRange *)a; ! NonEmptyRange *i2 = (NonEmptyRange *)b; return range_cmp_bounds(i1->typcache, &i1->lower, &i2->lower); } *************** *** 1552,1559 **** interval_cmp_lower(const void *a, const void *b) static int interval_cmp_upper(const void *a, const void *b) { ! RangeBounds *i1 = (RangeBounds *)a; ! RangeBounds *i2 = (RangeBounds *)b; return range_cmp_bounds(i1->typcache, &i1->upper, &i2->upper); } --- 1577,1584 ---- static int interval_cmp_upper(const void *a, const void *b) { ! NonEmptyRange *i1 = (NonEmptyRange *)a; ! NonEmptyRange *i2 = (NonEmptyRange *)b; return range_cmp_bounds(i1->typcache, &i1->upper, &i2->upper); }