8000 Improve implementation of range-contains-element tests. · postwait/postgres@cddc819 · GitHub
[go: up one dir, main page]
Skip to content

Commit cddc819

Browse files
tglsfdctglsfdc
committed
Improve implementation of range-contains-element tests.
Implement these tests directly instead of constructing a singleton range and then applying range-contains. This saves a range serialize/deserialize cycle as well as a couple of redundant bound-comparison steps, and adds very little code on net. Remove elem_contained_by_range from the GiST opclass: it doesn't belong there because there is no way to use it in an index clause (where the indexed column would have to be on the left). Its commutator is in the opclass, and that's what counts.
1 parent f1b4aa2 commit cddc819

File tree

5 files changed

+92
-84
lines changed

5 files changed

+92
-84
lines changed

‎src/backend/utils/adt/rangetypes.c

Lines changed: 49 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,8 @@ static char *range_deparse(char flags, const char *lbound_str,
6565
static char *range_bound_escape(const char *value);
6666
static bool range_contains_internal(TypeCacheEntry *typcache,
6767
RangeType *r1, RangeType *r2);
68+
static bool range_contains_elem_internal(TypeCacheEntry *typcache,
69+
RangeType *r, Datum val);
6870
static Size datum_compute_size(Size sz, Datum datum, bool typbyval,
6971
char typalign, int16 typlen, char typstorage);
7072
static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval,
@@ -555,36 +557,26 @@ range_upper_inf(PG_FUNCTION_ARGS)
555557
Datum
556558
range_contains_elem(PG_FUNCTION_ARGS)
557559
{
558-
RangeType *r1 = PG_GETARG_RANGE(0);
560+
RangeType *r = PG_GETARG_RANGE(0);
559561
Datum val = PG_GETARG_DATUM(1);
560562
TypeCacheEntry *typcache;
561-
RangeType *r2;
562563

563-
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
564-
565-
/* Construct a singleton range representing just "val" */
566-
r2 = make_singleton_range(typcache, val);
564+
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
567565

568-
/* And use range_contains */
569-
PG_RETURN_BOOL(range_contains_internal(typcache, r1, r2));
566+
PG_RETURN_BOOL(range_contains_elem_internal(typcache, r, val));
570567
}
571568

572569
/* contained by? */
573570
Datum
574571
elem_contained_by_range(PG_FUNCTION_ARGS)
575572
{
576573
Datum val = PG_GETARG_DATUM(0);
577-
RangeType *r1 = PG_GETARG_RANGE(1);
574+
RangeType *r = PG_GETARG_RANGE(1);
578575
TypeCacheEntry *typcache;
579-
RangeType *r2;
580-
581-
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
582576

583-
/* Construct a singleton range representing just "val" */
584-
r2 = make_singleton_range(typcache, val);
577+
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
585578

586-
/* And use range_contains */
587-
PG_RETURN_BOOL(range_contains_internal(typcache, r1, r2));
579+
PG_RETURN_BOOL(range_contains_elem_internal(typcache, r, val));
588580
}
589581

590582

@@ -2173,6 +2165,47 @@ range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
21732165
return true;
21742166
}
21752167

2168+
/*
2169+
* Test whether range r contains a specific element value.
2170+
*/
2171+
static bool
2172+
range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val)
2173+
{
2174+
RangeBound lower;
2175+
RangeBound upper;
2176+
bool empty;
2177+
int32 cmp;
2178+
2179+
range_deserialize(typcache, r, &lower, &upper, &empty);
2180+
2181+
if (empty)
2182+
return false;
2183+
2184+
if (!lower.infinite)
2185+
{
2186+
cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
2187+
typcache->rng_collation,
2188+
lower.val, val));
2189+
if (cmp > 0)
2190+
return false;
2191+
if (cmp == 0 && !lower.inclusive)
2192+
return false;
2193+
}
2194+
2195+
if (!upper.infinite)
2196+
{
2197+
cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
2198+
typcache->rng_collation,
2199+
upper.val, val));
2200+
if (cmp < 0)
2201+
return false;
2202+
if (cmp == 0 && !upper.inclusive)
2203+
return false;
2204+
}
2205+
2206+
return true;
2207+
}
2208+
21762209

21772210
/*
21782211
* datum_compute_size() and datum_write() are used to insert the bound

‎src/backend/utils/adt/rangetypes_gist.c

Lines changed: 41 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,6 @@
3131
#define RANGESTRAT_CONTAINS 7
3232
#define RANGESTRAT_CONTAINED_BY 8
3333
#define RANGESTRAT_CONTAINS_ELEM 16
34-
#define RANGESTRAT_ELEM_CONTAINED_BY 17
3534
#define RANGESTRAT_EQ 18
3635
#define RANGESTRAT_NE 19
3736

@@ -48,11 +47,11 @@ typedef struct
4847
static RangeType *range_super_union(TypeCacheEntry *typcache, RangeType * r1,
4948
RangeType * r2);
5049
static bool range_gist_consistent_int(FmgrInfo *flinfo,
51-
StrategyNumber strategy, RangeType * key,
52-
RangeType * query);
50+
StrategyNumber strategy, RangeType *key,
51+
Datum query);
5352
static bool range_gist_consistent_leaf(FmgrInfo *flinfo,
54-
StrategyNumber strategy, RangeType * key,
55-
RangeType * query);
53+
StrategyNumber strategy, RangeType *key,
54+
Datum query);
5655
static int sort_item_cmp(const void *a, const void *b);
5756

5857

@@ -61,39 +60,15 @@ Datum
6160
range_gist_consistent(PG_FUNCTION_ARGS)
6261
{
6362
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
64-
Datum dquery = PG_GETARG_DATUM(1);
63+
Datum query = PG_GETARG_DATUM(1);
6564
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
6665
/* Oid subtype = PG_GETARG_OID(3); */
6766
bool *recheck = (bool *) PG_GETARG_POINTER(4);
6867
RangeType *key = DatumGetRangeType(entry->key);
69-
TypeCacheEntry *typcache;
70-
RangeType *query;
7168

7269
/* All operators served by this function are exact */
7370
*recheck = false;
7471

75-
switch (strategy)
76-
{
77-
/*
78-
* For element contains and contained by operators, the other operand
79-
* is a "point" of the subtype. Construct a singleton range
80-
* containing just that value. (Since range_contains_elem and
81-
* elem_contained_by_range would do that anyway, it's actually more
82-
* efficient not less so to merge these cases into range containment
83-
* at this step. But revisit this if we ever change the implementation
84-
* of those functions.)
85-
*/
86-
case RANGESTRAT_CONTAINS_ELEM:
87-
case RANGESTRAT_ELEM_CONTAINED_BY:
88-
typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
89-
query = make_singleton_range(typcache, dquery);
90-
break;
91-
92-
default:
93-
query = DatumGetRangeType(dquery);
94-
break;
95-
}
96-
9772
if (GIST_LEAF(entry))
9873
PG_RETURN_BOOL(range_gist_consistent_leaf(fcinfo->flinfo, strategy,
9974
key, query));
@@ -170,21 +145,23 @@ range_gist_penalty(PG_FUNCTION_ARGS)
170145

171146
subtype_diff = &typcache->rng_subdiff_finfo;
172147

173-
/* we want to compare the size of "orig" to size of "orig union new" */
148+
/*
149+
* We want to compare the size of "orig" to size of "orig union new".
150+
* The penalty will be the sum of the reduction in the lower bound plus
151+
* the increase in the upper bound.
152+
*/
174153
s_union = range_super_union(typcache, orig, new);
175154

176155
range_deserialize(typcache, orig, &lower1, &upper1, &empty1);
177156
range_deserialize(typcache, s_union, &lower2, &upper2, &empty2);
178157

179-
/* if orig isn't empty, s_union can't be either */
180-
Assert(empty1 || !empty2);
181-
158+
/* handle cases where orig is empty */
182159
if (empty1 && empty2)
183160
{
184161
*penalty = 0;
185162
PG_RETURN_POINTER(penalty);
186163
}
187-
else if (empty1 && !empty2)
164+
else if (empty1)
188165
{
189166
if (lower2.infinite || upper2.infinite)
190167
{
@@ -199,6 +176,7 @@ range_gist_penalty(PG_FUNCTION_ARGS)
199176
typcache->rng_collation,
200177
upper2.val,
201178
lower2.val));
179+
/* upper2 must be >= lower2 */
202180
if (*penalty < 0)
203181
*penalty = 0; /* subtype_diff is broken */
204182
PG_RETURN_POINTER(penalty);
@@ -211,46 +189,53 @@ range_gist_penalty(PG_FUNCTION_ARGS)
211189
}
212190
}
213191

192+
/* if orig isn't empty, s_union can't be either */
193+
Assert(!empty2);
194+
195+
/* similarly, if orig's lower bound is infinite, s_union's must be too */
214196
Assert(lower2.infinite || !lower1.infinite);
21519 F438 7

216-
if (lower2.infinite && !lower1.infinite)
217-
lower_diff = get_float8_infinity();
218-
else if (lower2.infinite && lower1.infinite)
198+
if (lower2.infinite && lower1.infinite)
219199
lower_diff = 0;
200+
else if (lower2.infinite)
201+
lower_diff = get_float8_infinity();
220202
else if (OidIsValid(subtype_diff->fn_oid))
221203
{
222204
lower_diff = DatumGetFloat8(FunctionCall2Coll(subtype_diff,
223205
typcache->rng_collation,
224206
lower1.val,
225207
lower2.val));
208+
/* orig's lower bound must be >= s_union's */
226209
if (lower_diff < 0)
227210
lower_diff = 0; /* subtype_diff is broken */
228211
}
229212
else
230213
{
231214
/* only know whether there is a difference or not */
232-
lower_diff = (float) range_cmp_bounds(typcache, &lower1, &lower2);
215+
lower_diff = range_cmp_bounds(typcache, &lower1, &lower2) > 0 ? 1 : 0;
233216
}
234217

218+
/* similarly, if orig's upper bound is infinite, s_union's must be too */
235219
Assert(upper2.infinite || !upper1.infinite);
236220

237-
if (upper2.infinite && !upper1.infinite)
238-
upper_diff = get_float8_infinity();
239-
else if (upper2.infinite && upper1.infinite)
221+
if (upper2.infinite && upper1.infinite)
240222
upper_diff = 0;
223+
else if (upper2.infinite)
224+
upper_diff = get_float8_infinity();
241225
else if (OidIsValid(subtype_diff->fn_oid))
242226
{
243227
upper_diff = DatumGetFloat8(FunctionCall2Coll(subtype_diff,
244228
typcache->rng_collation,
245229
upper2.val,
246230
upper1.val));
231+
/* orig's upper bound must be <= s_union's */
247232
if (upper_diff < 0)
248233
upper_diff = 0; /* subtype_diff is broken */
249234
}
250235
else
251236
{
252237
/* only know whether there is a difference or not */
253-
upper_diff = (float) range_cmp_bounds(typcache, &upper2, &upper1);
238+
upper_diff = range_cmp_bounds(typcache, &upper2, &upper1) > 0 ? 1 : 0;
254239
}
255240

256241
Assert(lower_diff >= 0 && upper_diff >= 0);
@@ -450,7 +435,7 @@ TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2)
450435
*/
451436
static bool
452437
range_gist_consistent_int(FmgrInfo *flinfo, StrategyNumber strategy,
453-
RangeType * key, RangeType * query)
438+
RangeType *key, Datum query)
454439
{
455440
PGFunction proc;
456441
bool negate = false;
@@ -486,22 +471,23 @@ range_gist_consistent_int(FmgrInfo *flinfo, StrategyNumber strategy,
486471
negate = true;
487472
break;
488473
case RANGESTRAT_ADJACENT:
489-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
474+
if (RangeIsEmpty(key) || RangeIsEmpty(DatumGetRangeType(query)))
490475
return false;
491476
if (DatumGetBool(TrickFunctionCall2(range_adjacent, flinfo,
492477
RangeTypeGetDatum(key),
493-
RangeTypeGetDatum(query))))
478+
query)))
494479
return true;
495480
proc = range_overlaps;
496481
break;
497482
case RANGESTRAT_CONTAINS:
498-
case RANGESTRAT_CONTAINS_ELEM:
499483
proc = range_contains;
500484
break;
501485
case RANGESTRAT_CONTAINED_BY:
502-
case RANGESTRAT_ELEM_CONTAINED_BY:
503486
return true;
504487
break;
488+
case RANGESTRAT_CONTAINS_ELEM:
489+
proc = range_contains_elem;
490+
break;
505491
case RANGESTRAT_EQ:
506492
proc = range_contains;
507493
break;
@@ -516,7 +502,7 @@ range_gist_consistent_int(FmgrInfo *flinfo, StrategyNumber strategy,
516502

517503
retval = DatumGetBool(TrickFunctionCall2(proc, flinfo,
518504
RangeTypeGetDatum(key),
519-
RangeTypeGetDatum(query)));
505+
query));
520506
if (negate)
521507
retval = !retval;
522508

@@ -528,48 +514,39 @@ range_gist_consistent_int(FmgrInfo *flinfo, StrategyNumber strategy,
528514
*/
529515
static bool
530516
range_gist_consistent_leaf(FmgrInfo *flinfo, StrategyNumber strategy,
531-
RangeType * key, RangeType * query)
517+
RangeType *key, Datum query)
532518
{
533519
PGFunction proc;
534520

535521
switch (strategy)
536522
{
537523
case RANGESTRAT_BEFORE:
538-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
539-
return false;
540524
proc = range_before;
541525
break;
542526
case RANGESTRAT_OVERLEFT:
543-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
544-
return false;
545527
proc = range_overleft;
546528
break;
547529
case RANGESTRAT_OVERLAPS:
548530
proc = range_overlaps;
549531
break;
550532
case RANGESTRAT_OVERRIGHT:
551-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
552-
return false;
553533
proc = range_overright;
554534
break;
555535
case RANGESTRAT_AFTER:
556-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
557-
return false;
558536
proc = range_after;
559537
break;
560538
case RANGESTRAT_ADJACENT:
561-
if (RangeIsEmpty(key) || RangeIsEmpty(query))
562-
return false;
563539
proc = range_adjacent;
564540
break;
565541
case RANGESTRAT_CONTAINS:
566-
case RANGESTRAT_CONTAINS_ELEM:
567542
proc = range_contains;
568543
break;
569544
case RANGESTRAT_CONTAINED_BY:
570-
case RANGESTRAT_ELEM_CONTAINED_BY:
571545
proc = range_contained_by;
572546
break;
547+
case RANGESTRAT_CONTAINS_ELEM:
548+
proc = range_contains_elem;
549+
break;
573550
case RANGESTRAT_EQ:
574551
proc = range_eq;
575552
break;
@@ -584,7 +561,7 @@ range_gist_consistent_leaf(FmgrInfo *flinfo, StrategyNumber strategy,
584561

585562
return DatumGetBool(TrickFunctionCall2(proc, flinfo,
586563
RangeTypeGetDatum(key),
587-
RangeTypeGetDatum(query)));
564+
query));
588565
}
589566

590567
/*
@@ -649,7 +626,7 @@ sort_item_cmp(const void *a, const void *b)
649626
else if (lower2.infinite)
650627
return 1;
651628
else if (upper1.infinite && upper2.infinite)
652-
return -1 * range_cmp_bounds(typcache, &lower1, &lower2);
629+
return -(range_cmp_bounds(typcache, &lower1, &lower2));
653630
else if (upper1.infinite)
654631
return 1;
655632
else if (upper2.infinite)

‎src/include/catalog/catversion.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,6 @@
5353
*/
5454

5555
/* yyyymmddN */
56-
#define CATALOG_VERSION_NO 201111211
56+
#define CATALOG_VERSION_NO 201111221
5757

5858
#endif

‎src/include/catalog/pg_amop.h

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -735,7 +735,6 @@ DATA(insert ( 3919 3831 3831 6 s 3897 783 0 ));
735735
DATA(insert ( 3919 3831 3831 7 s 3890 783 0 ));
736736
DATA(insert ( 3919 3831 3831 8 s 3892 783 0 ));
737737
DATA(insert ( 3919 3831 2283 16 s 3889 783 0 ));
738-
DATA(insert ( 3919 2283 3831 17 s 3891 783 0 ));
739738
DATA(insert ( 3919 3831 3831 18 s 3882 783 0 ));
740739
DATA(insert ( 3919 3831 3831 19 s 3883 783 0 ));
741740

0 commit comments

Comments
 (0)
0