Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nbtcompare.c
4 : * Comparison functions for btree access method.
5 : *
6 : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : *
10 : * IDENTIFICATION
11 : * src/backend/access/nbtree/nbtcompare.c
12 : *
13 : * NOTES
14 : *
15 : * These functions are stored in pg_amproc. For each operator class
16 : * defined on btrees, they compute
17 : *
18 : * compare(a, b):
19 : * < 0 if a < b,
20 : * = 0 if a == b,
21 : * > 0 if a > b.
22 : *
23 : * The result is always an int32 regardless of the input datatype.
24 : *
25 : * Although any negative int32 is acceptable for reporting "<",
26 : * and any positive int32 is acceptable for reporting ">", routines
27 : * that work on 32-bit or wider datatypes can't just return "a - b".
28 : * That could overflow and give the wrong answer.
29 : *
30 : * NOTE: it is critical that the comparison function impose a total order
31 : * on all non-NULL values of the data type, and that the datatype's
32 : * boolean comparison operators (= < >= etc) yield results consistent
33 : * with the comparison routine. Otherwise bad behavior may ensue.
34 : * (For example, the comparison operators must NOT punt when faced with
35 : * NAN or other funny values; you must devise some collation sequence for
36 : * all such values.) If the datatype is not trivial, this is most
37 : * reliably done by having the boolean operators invoke the same
38 : * three-way comparison code that the btree function does. Therefore,
39 : * this file contains only btree support for "trivial" datatypes ---
40 : * all others are in the /utils/adt/ files that implement their datatypes.
41 : *
42 : * NOTE: these routines must not leak memory, since memory allocated
43 : * during an index access won't be recovered till end of query. This
44 : * primarily affects comparison routines for toastable datatypes;
45 : * they have to be careful to free any detoasted copy of an input datum.
46 : *
47 : * NOTE: we used to forbid comparison functions from returning INT_MIN,
48 : * but that proves to be too error-prone because some platforms' versions
49 : * of memcmp() etc can return INT_MIN. As a means of stress-testing
50 : * callers, this file can be compiled with STRESS_SORT_INT_MIN defined
51 : * to cause many of these functions to return INT_MIN or INT_MAX instead of
52 : * their customary -1/+1. For production, though, that's not a good idea
53 : * since users or third-party code might expect the traditional results.
54 : *-------------------------------------------------------------------------
55 : */
56 : #include "postgres.h"
57 :
58 : #include <limits.h>
59 :
60 : #include "utils/fmgrprotos.h"
61 : #include "utils/skipsupport.h"
62 : #include "utils/sortsupport.h"
63 :
64 : #ifdef STRESS_SORT_INT_MIN
65 : #define A_LESS_THAN_B INT_MIN
66 : #define A_GREATER_THAN_B INT_MAX
67 : #else
68 : #define A_LESS_THAN_B (-1)
69 : #define A_GREATER_THAN_B 1
70 : #endif
71 :
72 :
73 : Datum
74 62289034 : btboolcmp(PG_FUNCTION_ARGS)
75 : {
76 62289034 : bool a = PG_GETARG_BOOL(0);
77 62289034 : bool b = PG_GETARG_BOOL(1);
78 :
79 62289034 : PG_RETURN_INT32((int32) a - (int32) b);
80 : }
81 :
82 : static Datum
83 0 : bool_decrement(Relation rel, Datum existing, bool *underflow)
84 : {
85 0 : bool bexisting = DatumGetBool(existing);
86 :
87 0 : if (bexisting == false)
88 : {
89 : /* return value is undefined */
90 0 : *underflow = true;
91 0 : return (Datum) 0;
92 : }
93 :
94 0 : *underflow = false;
95 0 : return BoolGetDatum(bexisting - 1);
96 : }
97 :
98 : static Datum
99 0 : bool_increment(Relation rel, Datum existing, bool *overflow)
100 : {
101 0 : bool bexisting = DatumGetBool(existing);
102 :
103 0 : if (bexisting == true)
104 : {
105 : /* return value is undefined */
106 0 : *overflow = true;
107 0 : return (Datum) 0;
108 : }
109 :
110 0 : *overflow = false;
111 0 : return BoolGetDatum(bexisting + 1);
112 : }
113 :
114 : Datum
115 0 : btboolskipsupport(PG_FUNCTION_ARGS)
116 : {
117 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
118 :
119 0 : sksup->decrement = bool_decrement;
120 0 : sksup->increment = bool_increment;
121 0 : sksup->low_elem = BoolGetDatum(false);
122 0 : sksup->high_elem = BoolGetDatum(true);
123 :
124 0 : PG_RETURN_VOID();
125 : }
126 :
127 : Datum
128 13024190 : btint2cmp(PG_FUNCTION_ARGS)
129 : {
130 13024190 : int16 a = PG_GETARG_INT16(0);
131 13024190 : int16 b = PG_GETARG_INT16(1);
132 :
133 13024190 : PG_RETURN_INT32((int32) a - (int32) b);
134 : }
135 :
136 : static int
137 44669004 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
138 : {
139 44669004 : int16 a = DatumGetInt16(x);
140 44669004 : int16 b = DatumGetInt16(y);
141 :
142 44669004 : return (int) a - (int) b;
143 : }
144 :
145 : Datum
146 12078 : btint2sortsupport(PG_FUNCTION_ARGS)
147 : {
148 12078 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
149 :
150 12078 : ssup->comparator = btint2fastcmp;
151 12078 : PG_RETURN_VOID();
152 : }
153 :
154 : static Datum
155 0 : int2_decrement(Relation rel, Datum existing, bool *underflow)
156 : {
157 0 : int16 iexisting = DatumGetInt16(existing);
158 :
159 0 : if (iexisting == PG_INT16_MIN)
160 : {
161 : /* return value is undefined */
162 0 : *underflow = true;
163 0 : return (Datum) 0;
164 : }
165 :
166 0 : *underflow = false;
167 0 : return Int16GetDatum(iexisting - 1);
168 : }
169 :
170 : static Datum
171 4 : int2_increment(Relation rel, Datum existing, bool *overflow)
172 : {
173 4 : int16 iexisting = DatumGetInt16(existing);
174 :
175 4 : if (iexisting == PG_INT16_MAX)
176 : {
177 : /* return value is undefined */
178 0 : *overflow = true;
179 0 : return (Datum) 0;
180 : }
181 :
182 4 : *overflow = false;
183 4 : return Int16GetDatum(iexisting + 1);
184 : }
185 :
186 : Datum
187 188 : btint2skipsupport(PG_FUNCTION_ARGS)
188 : {
189 188 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
190 :
191 188 : sksup->decrement = int2_decrement;
192 188 : sksup->increment = int2_increment;
193 188 : sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
194 188 : sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
195 :
196 188 : PG_RETURN_VOID();
197 : }
198 :
199 : Datum
200 97957438 : btint4cmp(PG_FUNCTION_ARGS)
201 : {
202 97957438 : int32 a = PG_GETARG_INT32(0);
203 97957438 : int32 b = PG_GETARG_INT32(1);
204 :
205 97957438 : if (a > b)
206 37358002 : PG_RETURN_INT32(A_GREATER_THAN_B);
207 60599436 : else if (a == b)
208 20322986 : PG_RETURN_INT32(0);
209 : else
210 40276450 : PG_RETURN_INT32(A_LESS_THAN_B);
211 : }
212 :
213 : Datum
214 175332 : btint4sortsupport(PG_FUNCTION_ARGS)
215 : {
216 175332 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
217 :
218 175332 : ssup->comparator = ssup_datum_int32_cmp;
219 175332 : PG_RETURN_VOID();
220 : }
221 :
222 : static Datum
223 3966 : int4_decrement(Relation rel, Datum existing, bool *underflow)
224 : {
225 3966 : int32 iexisting = DatumGetInt32(existing);
226 :
227 3966 : if (iexisting == PG_INT32_MIN)
228 : {
229 : /* return value is undefined */
230 0 : *underflow = true;
231 0 : return (Datum) 0;
232 : }
233 :
234 3966 : *underflow = false;
235 3966 : return Int32GetDatum(iexisting - 1);
236 : }
237 :
238 : static Datum
239 3822 : int4_increment(Relation rel, Datum existing, bool *overflow)
240 : {
241 3822 : int32 iexisting = DatumGetInt32(existing);
242 :
243 3822 : if (iexisting == PG_INT32_MAX)
244 : {
245 : /* return value is undefined */
246 30 : *overflow = true;
247 30 : return (Datum) 0;
248 : }
249 :
250 3792 : *overflow = false;
251 3792 : return Int32GetDatum(iexisting + 1);
252 : }
253 :
254 : Datum
255 246 : btint4skipsupport(PG_FUNCTION_ARGS)
256 : {
257 246 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
258 :
259 246 : sksup->decrement = int4_decrement;
260 246 : sksup->increment = int4_increment;
261 246 : sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
262 246 : sksup->high_elem = Int32GetDatum(PG_INT32_MAX);
263 :
264 246 : PG_RETURN_VOID();
265 : }
266 :
267 : Datum
268 16637392 : btint8cmp(PG_FUNCTION_ARGS)
269 : {
270 16637392 : int64 a = PG_GETARG_INT64(0);
271 16637392 : int64 b = PG_GETARG_INT64(1);
272 :
273 16637392 : if (a > b)
274 9721766 : PG_RETURN_INT32(A_GREATER_THAN_B);
275 6915626 : else if (a == b)
276 845134 : PG_RETURN_INT32(0);
277 : else
278 6070492 : PG_RETURN_INT32(A_LESS_THAN_B);
279 : }
280 :
281 : Datum
282 3478 : btint8sortsupport(PG_FUNCTION_ARGS)
283 : {
284 3478 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
285 :
286 3478 : ssup->comparator = ssup_datum_signed_cmp;
287 3478 : PG_RETURN_VOID();
288 : }
289 :
290 : static Datum
291 0 : int8_decrement(Relation rel, Datum existing, bool *underflow)
292 : {
293 0 : int64 iexisting = DatumGetInt64(existing);
294 :
295 0 : if (iexisting == PG_INT64_MIN)
296 : {
297 : /* return value is undefined */
298 0 : *underflow = true;
299 0 : return (Datum) 0;
300 : }
301 :
302 0 : *underflow = false;
303 0 : return Int64GetDatum(iexisting - 1);
304 : }
305 :
306 : static Datum
307 0 : int8_increment(Relation rel, Datum existing, bool *overflow)
308 : {
309 0 : int64 iexisting = DatumGetInt64(existing);
310 :
311 0 : if (iexisting == PG_INT64_MAX)
312 : {
313 : /* return value is undefined */
314 0 : *overflow = true;
315 0 : return (Datum) 0;
316 : }
317 :
318 0 : *overflow = false;
319 0 : return Int64GetDatum(iexisting + 1);
320 : }
321 :
322 : Datum
323 0 : btint8skipsupport(PG_FUNCTION_ARGS)
324 : {
325 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
326 :
327 0 : sksup->decrement = int8_decrement;
328 0 : sksup->increment = int8_increment;
329 0 : sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
330 0 : sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
331 :
332 0 : PG_RETURN_VOID();
333 : }
334 :
335 : Datum
336 1486 : btint48cmp(PG_FUNCTION_ARGS)
337 : {
338 1486 : int32 a = PG_GETARG_INT32(0);
339 1486 : int64 b = PG_GETARG_INT64(1);
340 :
341 1486 : if (a > b)
342 510 : PG_RETURN_INT32(A_GREATER_THAN_B);
343 976 : else if (a == b)
344 76 : PG_RETURN_INT32(0);
345 : else
346 900 : PG_RETURN_INT32(A_LESS_THAN_B);
347 : }
348 :
349 : Datum
350 220 : btint84cmp(PG_FUNCTION_ARGS)
351 : {
352 220 : int64 a = PG_GETARG_INT64(0);
353 220 : int32 b = PG_GETARG_INT32(1);
354 :
355 220 : if (a > b)
356 78 : PG_RETURN_INT32(A_GREATER_THAN_B);
357 142 : else if (a == b)
358 58 : PG_RETURN_INT32(0);
359 : else
360 84 : PG_RETURN_INT32(A_LESS_THAN_B);
361 : }
362 :
363 : Datum
364 49396 : btint24cmp(PG_FUNCTION_ARGS)
365 : {
366 49396 : int16 a = PG_GETARG_INT16(0);
367 49396 : int32 b = PG_GETARG_INT32(1);
368 :
369 49396 : if (a > b)
370 27380 : PG_RETURN_INT32(A_GREATER_THAN_B);
371 22016 : else if (a == b)
372 7090 : PG_RETURN_INT32(0);
373 : else
374 14926 : PG_RETURN_INT32(A_LESS_THAN_B);
375 : }
376 :
377 : Datum
378 1612 : btint42cmp(PG_FUNCTION_ARGS)
379 : {
380 1612 : int32 a = PG_GETARG_INT32(0);
381 1612 : int16 b = PG_GETARG_INT16(1);
382 :
383 1612 : if (a > b)
384 254 : PG_RETURN_INT32(A_GREATER_THAN_B);
385 1358 : else if (a == b)
386 324 : PG_RETURN_INT32(0);
387 : else
388 1034 : PG_RETURN_INT32(A_LESS_THAN_B);
389 : }
390 :
391 : Datum
392 70 : btint28cmp(PG_FUNCTION_ARGS)
393 : {
394 70 : int16 a = PG_GETARG_INT16(0);
395 70 : int64 b = PG_GETARG_INT64(1);
396 :
397 70 : if (a > b)
398 12 : PG_RETURN_INT32(A_GREATER_THAN_B);
399 58 : else if (a == b)
400 10 : PG_RETURN_INT32(0);
401 : else
402 48 : PG_RETURN_INT32(A_LESS_THAN_B);
403 : }
404 :
405 : Datum
406 34 : btint82cmp(PG_FUNCTION_ARGS)
407 : {
408 34 : int64 a = PG_GETARG_INT64(0);
409 34 : int16 b = PG_GETARG_INT16(1);
410 :
411 34 : if (a > b)
412 12 : PG_RETURN_INT32(A_GREATER_THAN_B);
413 22 : else if (a == b)
414 10 : PG_RETURN_INT32(0);
415 : else
416 12 : PG_RETURN_INT32(A_LESS_THAN_B);
417 : }
418 :
419 : Datum
420 229754188 : btoidcmp(PG_FUNCTION_ARGS)
421 : {
422 229754188 : Oid a = PG_GETARG_OID(0);
423 229754188 : Oid b = PG_GETARG_OID(1);
424 :
425 229754188 : if (a > b)
426 62047936 : PG_RETURN_INT32(A_GREATER_THAN_B);
427 167706252 : else if (a == b)
428 54789290 : PG_RETURN_INT32(0);
429 : else
430 112916962 : PG_RETURN_INT32(A_LESS_THAN_B);
431 : }
432 :
433 : static int
434 266770946 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
435 : {
436 266770946 : Oid a = DatumGetObjectId(x);
437 266770946 : Oid b = DatumGetObjectId(y);
438 :
439 266770946 : if (a > b)
440 65110130 : return A_GREATER_THAN_B;
441 201660816 : else if (a == b)
442 137241988 : return 0;
443 : else
444 64418828 : return A_LESS_THAN_B;
445 : }
446 :
447 : Datum
448 124552 : btoidsortsupport(PG_FUNCTION_ARGS)
449 : {
450 124552 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
451 :
452 124552 : ssup->comparator = btoidfastcmp;
453 124552 : PG_RETURN_VOID();
454 : }
455 :
456 : static Datum
457 0 : oid_decrement(Relation rel, Datum existing, bool *underflow)
458 : {
459 0 : Oid oexisting = DatumGetObjectId(existing);
460 :
461 0 : if (oexisting == InvalidOid)
462 : {
463 : /* return value is undefined */
464 0 : *underflow = true;
465 0 : return (Datum) 0;
466 : }
467 :
468 0 : *underflow = false;
469 0 : return ObjectIdGetDatum(oexisting - 1);
470 : }
471 :
472 : static Datum
473 424 : oid_increment(Relation rel, Datum existing, bool *overflow)
474 : {
475 424 : Oid oexisting = DatumGetObjectId(existing);
476 :
477 424 : if (oexisting == OID_MAX)
478 : {
479 : /* return value is undefined */
480 0 : *overflow = true;
481 0 : return (Datum) 0;
482 : }
483 :
484 424 : *overflow = false;
485 424 : return ObjectIdGetDatum(oexisting + 1);
486 : }
487 :
488 : Datum
489 3198 : btoidskipsupport(PG_FUNCTION_ARGS)
490 : {
491 3198 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
492 :
493 3198 : sksup->decrement = oid_decrement;
494 3198 : sksup->increment = oid_increment;
495 3198 : sksup->low_elem = ObjectIdGetDatum(InvalidOid);
496 3198 : sksup->high_elem = ObjectIdGetDatum(OID_MAX);
497 :
498 3198 : PG_RETURN_VOID();
499 : }
500 :
501 : Datum
502 18 : btoid8cmp(PG_FUNCTION_ARGS)
503 : {
504 18 : Oid8 a = PG_GETARG_OID8(0);
505 18 : Oid8 b = PG_GETARG_OID8(1);
506 :
507 18 : if (a > b)
508 6 : PG_RETURN_INT32(A_GREATER_THAN_B);
509 12 : else if (a == b)
510 6 : PG_RETURN_INT32(0);
511 : else
512 6 : PG_RETURN_INT32(A_LESS_THAN_B);
513 : }
514 :
515 : static int
516 4374 : btoid8fastcmp(Datum x, Datum y, SortSupport ssup)
517 : {
518 4374 : Oid8 a = DatumGetObjectId8(x);
519 4374 : Oid8 b = DatumGetObjectId8(y);
520 :
521 4374 : if (a > b)
522 2634 : return A_GREATER_THAN_B;
523 1740 : else if (a == b)
524 0 : return 0;
525 : else
526 1740 : return A_LESS_THAN_B;
527 : }
528 :
529 : Datum
530 12 : btoid8sortsupport(PG_FUNCTION_ARGS)
531 : {
532 12 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
533 :
534 12 : ssup->comparator = btoid8fastcmp;
535 12 : PG_RETURN_VOID();
536 : }
537 :
538 : static Datum
539 0 : oid8_decrement(Relation rel, Datum existing, bool *underflow)
540 : {
541 0 : Oid8 oexisting = DatumGetObjectId8(existing);
542 :
543 0 : if (oexisting == InvalidOid8)
544 : {
545 : /* return value is undefined */
546 0 : *underflow = true;
547 0 : return (Datum) 0;
548 : }
549 :
550 0 : *underflow = false;
551 0 : return ObjectId8GetDatum(oexisting - 1);
552 : }
553 :
554 : static Datum
555 0 : oid8_increment(Relation rel, Datum existing, bool *overflow)
556 : {
557 0 : Oid8 oexisting = DatumGetObjectId8(existing);
558 :
559 0 : if (oexisting == OID8_MAX)
560 : {
561 : /* return value is undefined */
562 0 : *overflow = true;
563 0 : return (Datum) 0;
564 : }
565 :
566 0 : *overflow = false;
567 0 : return ObjectId8GetDatum(oexisting + 1);
568 : }
569 :
570 : Datum
571 0 : btoid8skipsupport(PG_FUNCTION_ARGS)
572 : {
573 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
574 :
575 0 : sksup->decrement = oid8_decrement;
576 0 : sksup->increment = oid8_increment;
577 0 : sksup->low_elem = ObjectId8GetDatum(InvalidOid8);
578 0 : sksup->high_elem = ObjectId8GetDatum(OID8_MAX);
579 :
580 0 : PG_RETURN_VOID();
581 : }
582 :
583 : Datum
584 8284626 : btoidvectorcmp(PG_FUNCTION_ARGS)
585 : {
586 8284626 : oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
587 8284626 : oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
588 : int i;
589 :
590 : /* We arbitrarily choose to sort first by vector length */
591 8284626 : if (a->dim1 != b->dim1)
592 1581386 : PG_RETURN_INT32(a->dim1 - b->dim1);
593 :
594 11861878 : for (i = 0; i < a->dim1; i++)
595 : {
596 9053442 : if (a->values[i] != b->values[i])
597 : {
598 3894804 : if (a->values[i] > b->values[i])
599 1850006 : PG_RETURN_INT32(A_GREATER_THAN_B);
600 : else
601 2044798 : PG_RETURN_INT32(A_LESS_THAN_B);
602 : }
603 : }
604 2808436 : PG_RETURN_INT32(0);
605 : }
606 :
607 : Datum
608 63007368 : btcharcmp(PG_FUNCTION_ARGS)
609 : {
610 63007368 : char a = PG_GETARG_CHAR(0);
611 63007368 : char b = PG_GETARG_CHAR(1);
612 :
613 : /* Be careful to compare chars as unsigned */
614 63007368 : PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
615 : }
616 :
617 : static Datum
618 0 : char_decrement(Relation rel, Datum existing, bool *underflow)
619 : {
620 0 : uint8 cexisting = DatumGetUInt8(existing);
621 :
622 0 : if (cexisting == 0)
623 : {
624 : /* return value is undefined */
625 0 : *underflow = true;
626 0 : return (Datum) 0;
627 : }
628 :
629 0 : *underflow = false;
630 0 : return CharGetDatum((uint8) cexisting - 1);
631 : }
632 :
633 : static Datum
634 0 : char_increment(Relation rel, Datum existing, bool *overflow)
635 : {
636 0 : uint8 cexisting = DatumGetUInt8(existing);
637 :
638 0 : if (cexisting == UCHAR_MAX)
639 : {
640 : /* return value is undefined */
641 0 : *overflow = true;
642 0 : return (Datum) 0;
643 : }
644 :
645 0 : *overflow = false;
646 0 : return CharGetDatum((uint8) cexisting + 1);
647 : }
648 :
649 : Datum
650 0 : btcharskipsupport(PG_FUNCTION_ARGS)
651 : {
652 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
653 :
654 0 : sksup->decrement = char_decrement;
655 0 : sksup->increment = char_increment;
656 :
657 : /* btcharcmp compares chars as unsigned */
658 0 : sksup->low_elem = UInt8GetDatum(0);
659 0 : sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
660 :
661 0 : PG_RETURN_VOID();
662 : }
|
