Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * uuid.c
4 : : * Functions for the built-in type "uuid".
5 : : *
6 : : * Copyright (c) 2007-2026, PostgreSQL Global Development Group
7 : : *
8 : : * IDENTIFICATION
9 : : * src/backend/utils/adt/uuid.c
10 : : *
11 : : *-------------------------------------------------------------------------
12 : : */
13 : :
14 : : #include "postgres.h"
15 : :
16 : : #include <limits.h>
17 : : #include <time.h> /* for clock_gettime() */
18 : :
19 : : #include "common/hashfn.h"
20 : : #include "lib/hyperloglog.h"
21 : : #include "libpq/pqformat.h"
22 : : #include "nodes/miscnodes.h"
23 : : #include "port/pg_bswap.h"
24 : : #include "utils/builtins.h"
25 : : #include "utils/fmgrprotos.h"
26 : : #include "utils/guc.h"
27 : : #include "utils/skipsupport.h"
28 : : #include "utils/sortsupport.h"
29 : : #include "utils/timestamp.h"
30 : : #include "utils/uuid.h"
31 : :
32 : : /* helper macros */
33 : : #define NS_PER_S INT64CONST(1000000000)
34 : : #define NS_PER_MS INT64CONST(1000000)
35 : : #define NS_PER_US INT64CONST(1000)
36 : : #define US_PER_MS INT64CONST(1000)
37 : :
38 : : /*
39 : : * The offset between the PostgreSQL epoch (2000-01-01) and the Unix epoch
40 : : * (1970-01-01) in microseconds. Subtract this from a Unix-epoch microseconds
41 : : * to get a TimestampTz.
42 : : */
43 : : #define PG_UNIX_EPOCH_OFFSET_US \
44 : : ((int64) (POSTGRES_EPOCH_JDATE - UNIX_EPOCH_JDATE) * SECS_PER_DAY * USECS_PER_SEC)
45 : :
46 : : /*
47 : : * Valid timestamp range for UUID version 7, expressed in PostgreSQL-epoch
48 : : * microseconds. UUIDv7 uses a 48-bit unsigned millisecond field relative
49 : : * to the Unix epoch, so the representable window is [1970-01-01, ~10889].
50 : : */
51 : : #define UUIDV7_MIN_TIMESTAMP (-PG_UNIX_EPOCH_OFFSET_US)
52 : : #define UUIDV7_MAX_TIMESTAMP \
53 : : (((INT64CONST(1) << 48) - 1) * US_PER_MS - PG_UNIX_EPOCH_OFFSET_US)
54 : :
55 : : /*
56 : : * UUID version 7 uses 12 bits in "rand_a" to store 1/4096 (or 2^12) fractions of
57 : : * sub-millisecond. While most Unix-like platforms provide nanosecond-precision
58 : : * timestamps, some systems only offer microsecond precision, limiting us to 10
59 : : * bits of sub-millisecond information. For example, on macOS, real time is
60 : : * truncated to microseconds. Additionally, MSVC uses the ported version of
61 : : * gettimeofday() that returns microsecond precision.
62 : : *
63 : : * On systems with only 10 bits of sub-millisecond precision, we still use
64 : : * 1/4096 parts of a millisecond, but fill lower 2 bits with random numbers
65 : : * (see generate_uuidv7() for details).
66 : : *
67 : : * SUBMS_MINIMAL_STEP_NS defines the minimum number of nanoseconds that guarantees
68 : : * an increase in the UUID's clock precision.
69 : : */
70 : : #if defined(__darwin__) || defined(_MSC_VER)
71 : : #define SUBMS_MINIMAL_STEP_BITS 10
72 : : #else
73 : : #define SUBMS_MINIMAL_STEP_BITS 12
74 : : #endif
75 : : #define SUBMS_BITS 12
76 : : #define SUBMS_MINIMAL_STEP_NS ((NS_PER_MS / (1 << SUBMS_MINIMAL_STEP_BITS)) + 1)
77 : :
78 : : /* sortsupport for uuid */
79 : : typedef struct
80 : : {
81 : : int64 input_count; /* number of non-null values seen */
82 : : bool estimating; /* true if estimating cardinality */
83 : :
84 : : hyperLogLogState abbr_card; /* cardinality estimator */
85 : : } uuid_sortsupport_state;
86 : :
87 : : static void string_to_uuid(const char *source, pg_uuid_t *uuid, Node *escontext);
88 : : static int uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2);
89 : : static int uuid_fast_cmp(Datum x, Datum y, SortSupport ssup);
90 : : static bool uuid_abbrev_abort(int memtupcount, SortSupport ssup);
91 : : static Datum uuid_abbrev_convert(Datum original, SortSupport ssup);
92 : : static inline void uuid_set_version(pg_uuid_t *uuid, unsigned char version);
93 : : static inline int64 get_real_time_ns_ascending(void);
94 : : static pg_uuid_t *generate_uuidv7(uint64 unix_ts_ms, uint32 sub_ms);
95 : :
96 : : Datum
7175 neilc@samurai.com 97 :CBC 390678 : uuid_in(PG_FUNCTION_ARGS)
98 : : {
6884 bruce@momjian.us 99 : 390678 : char *uuid_str = PG_GETARG_CSTRING(0);
100 : : pg_uuid_t *uuid;
101 : :
284 michael@paquier.xyz 102 : 390678 : uuid = palloc_object(pg_uuid_t);
1376 tgl@sss.pgh.pa.us 103 : 390678 : string_to_uuid(uuid_str, uuid, fcinfo->context);
7175 neilc@samurai.com 104 : 390610 : PG_RETURN_UUID_P(uuid);
105 : : }
106 : :
107 : : Datum
108 : 3334 : uuid_out(PG_FUNCTION_ARGS)
109 : : {
6884 bruce@momjian.us 110 : 3334 : pg_uuid_t *uuid = PG_GETARG_UUID_P(0);
111 : : static const char hex_chars[] = "0123456789abcdef";
112 : : char *buf,
113 : : *p;
114 : : int i;
115 : :
116 : : /* counts for the four hyphens and the zero-terminator */
941 michael@paquier.xyz 117 : 3334 : buf = palloc(2 * UUID_LEN + 5);
118 : 3334 : p = buf;
7172 neilc@samurai.com 119 [ + + ]: 56678 : for (i = 0; i < UUID_LEN; i++)
120 : : {
121 : : int hi;
122 : : int lo;
123 : :
124 : : /*
125 : : * We print uuid values as a string of 8, 4, 4, 4, and then 12
126 : : * hexadecimal characters, with each group is separated by a hyphen
127 : : * ("-"). Therefore, add the hyphens at the appropriate places here.
128 : : */
129 [ + + + + : 53344 : if (i == 4 || i == 6 || i == 8 || i == 10)
+ + + + ]
941 michael@paquier.xyz 130 : 13336 : *p++ = '-';
131 : :
7172 neilc@samurai.com 132 : 53344 : hi = uuid->data[i] >> 4;
133 : 53344 : lo = uuid->data[i] & 0x0F;
134 : :
941 michael@paquier.xyz 135 : 53344 : *p++ = hex_chars[hi];
136 : 53344 : *p++ = hex_chars[lo];
137 : : }
138 : 3334 : *p = '\0';
139 : :
140 : 3334 : PG_RETURN_CSTRING(buf);
141 : : }
142 : :
143 : : /*
144 : : * Reference implementation of the UUID grammar, parsing one byte at a time.
145 : : * string_to_uuid() recognizes the common shapes more cheaply and defers to
146 : : * this function for everything else, so this is also the only place that
147 : : * reports a syntax error.
148 : : */
149 : : static void
5 msawada@postgresql.o 150 :GNC 76 : string_to_uuid_scalar(const char *source, pg_uuid_t *uuid, Node *escontext)
151 : : {
6530 peter_e@gmx.net 152 :CBC 76 : const char *src = source;
tgl@sss.pgh.pa.us 153 : 76 : bool braces = false;
154 : : int i;
155 : :
peter_e@gmx.net 156 [ + + ]: 76 : if (src[0] == '{')
157 : : {
tgl@sss.pgh.pa.us 158 : 28 : src++;
159 : 28 : braces = true;
160 : : }
161 : :
7172 neilc@samurai.com 162 [ + + ]: 672 : for (i = 0; i < UUID_LEN; i++)
163 : : {
164 : : char str_buf[3];
165 : :
6530 peter_e@gmx.net 166 [ + + - + ]: 648 : if (src[0] == '\0' || src[1] == '\0')
167 : 52 : goto syntax_error;
168 : 640 : memcpy(str_buf, src, 2);
7172 neilc@samurai.com 169 [ + + ]: 640 : if (!isxdigit((unsigned char) str_buf[0]) ||
170 [ + + ]: 624 : !isxdigit((unsigned char) str_buf[1]))
171 : 44 : goto syntax_error;
172 : :
173 : 596 : str_buf[2] = '\0';
174 : 596 : uuid->data[i] = (unsigned char) strtoul(str_buf, NULL, 16);
6530 peter_e@gmx.net 175 : 596 : src += 2;
176 [ + + + - : 596 : if (src[0] == '-' && (i % 2) == 1 && i < UUID_LEN - 1)
+ - ]
177 : 108 : src++;
178 : : }
179 : :
180 [ + + ]: 24 : if (braces)
181 : : {
tgl@sss.pgh.pa.us 182 [ + + ]: 12 : if (*src != '}')
peter_e@gmx.net 183 : 4 : goto syntax_error;
tgl@sss.pgh.pa.us 184 : 8 : src++;
185 : : }
186 : :
peter_e@gmx.net 187 [ + - ]: 20 : if (*src != '\0')
188 : 20 : goto syntax_error;
189 : :
7172 neilc@samurai.com 190 :LBC (390582) : return;
191 : :
7172 neilc@samurai.com 192 :CBC 76 : syntax_error:
1376 tgl@sss.pgh.pa.us 193 [ + + ]: 76 : ereturn(escontext,,
194 : : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
195 : : errmsg("invalid input syntax for type %s: \"%s\"",
196 : : "uuid", source)));
197 : : }
198 : :
199 : : /*
200 : : * We allow UUIDs as a series of 32 hexadecimal digits with an optional dash
201 : : * after each group of 4 hexadecimal digits, and optionally surrounded by {}.
202 : : * (The canonical format 8x-4x-4x-4x-12x, where "nx" means n hexadecimal
203 : : * digits, is the only one used for output.)
204 : : *
205 : : * The two common shapes -- a bare string of 32 hexadecimal digits and the
206 : : * canonical form, each optionally wrapped in braces -- are compacted into 32
207 : : * contiguous hex digits and decoded with hex_decode_safe(), which is much
208 : : * faster than the byte-at-a-time loop. Any other shape, or any decoding
209 : : * error, is handed off to string_to_uuid_scalar() so that the accepted
210 : : * grammar and the error messages are unchanged.
211 : : */
212 : : static void
5 msawada@postgresql.o 213 :GNC 390678 : string_to_uuid(const char *source, pg_uuid_t *uuid, Node *escontext)
214 : : {
215 : 390678 : const char *body = source;
216 : 390678 : const char *hexsrc = NULL;
217 : : char hexbuf[32];
218 : : uint64 written;
219 : : size_t len;
220 : 390678 : ErrorSaveContext private_escontext = {T_ErrorSaveContext};
221 : :
222 : : /*
223 : : * Measure the input only far enough to classify its shape. The bound must
224 : : * exceed the longest shape handled here, the braced canonical form at 38
225 : : * characters: strnlen() returns the bound for anything at least that
226 : : * long, so stopping at an accepted length would accept a longer string
227 : : * that merely starts with a valid UUID.
228 : : */
229 : 390678 : len = strnlen(source, 64);
230 : :
231 : : /* Strip one optional surrounding brace pair */
232 [ + - + + : 390678 : if (len >= 2 && source[0] == '{' && source[len - 1] == '}')
+ + ]
233 : : {
234 : 32 : body = source + 1;
235 : 32 : len -= 2;
236 : : }
237 : :
238 [ + + ]: 390678 : if (len == 32)
239 : : {
240 : : /*
241 : : * Body is already 32 contiguous hex digits -- decode straight from
242 : : * the input. hex_decode_safe() reads exactly body[0..31], so it never
243 : : * touches the trailing NUL or '}'.
244 : : */
245 : 68044 : hexsrc = body;
246 : : }
247 [ + + + - : 322634 : else if (len == 36 && body[8] == '-' && body[13] == '-' &&
+ - ]
248 [ + - + - ]: 322594 : body[18] == '-' && body[23] == '-')
249 : : {
250 : : /*
251 : : * Canonical 8x-4x-4x-4x-12x form; compact them into hexbuf with
252 : : * fixed-offset copies, dropping the dashes.
253 : : */
254 : 322594 : memcpy(&hexbuf[0], &body[0], 8);
255 : 322594 : memcpy(&hexbuf[8], &body[9], 4);
256 : 322594 : memcpy(&hexbuf[12], &body[14], 4);
257 : 322594 : memcpy(&hexbuf[16], &body[19], 4);
258 : 322594 : memcpy(&hexbuf[20], &body[24], 12);
259 : 322594 : hexsrc = hexbuf;
260 : : }
261 : :
262 [ + + ]: 390678 : if (hexsrc == NULL)
263 : : {
264 : : /* Uncommon shape; let the general parse handle it */
265 : 40 : string_to_uuid_scalar(source, uuid, escontext);
266 : 8 : return;
267 : : }
268 : :
269 : : /*
270 : : * The shape matched, so the decode is expected to succeed. Any error is
271 : : * routed into a private context and discarded, leaving
272 : : * string_to_uuid_scalar() to parse the input again and report the syntax
273 : : * error, so that the message does not depend on which path rejected the
274 : : * input.
275 : : */
276 : 390638 : written = hex_decode_safe(hexsrc, 32, (char *) uuid->data,
277 : : (Node *) &private_escontext);
278 : :
279 : : /*
280 : : * A short result must be rejected as well as an error: hex_decode_safe()
281 : : * skips whitespace, so it can succeed yet write fewer than UUID_LEN
282 : : * bytes, whereas the UUID grammar forbids whitespace.
283 : : */
284 [ + + + + ]: 390638 : if (private_escontext.error_occurred || written != UUID_LEN)
285 : 36 : string_to_uuid_scalar(source, uuid, escontext);
286 : : }
287 : :
288 : : Datum
7175 neilc@samurai.com 289 :UBC 0 : uuid_recv(PG_FUNCTION_ARGS)
290 : : {
6884 bruce@momjian.us 291 : 0 : StringInfo buffer = (StringInfo) PG_GETARG_POINTER(0);
292 : : pg_uuid_t *uuid;
293 : :
7175 neilc@samurai.com 294 : 0 : uuid = (pg_uuid_t *) palloc(UUID_LEN);
295 : 0 : memcpy(uuid->data, pq_getmsgbytes(buffer, UUID_LEN), UUID_LEN);
296 : 0 : PG_RETURN_POINTER(uuid);
297 : : }
298 : :
299 : : Datum
7175 neilc@samurai.com 300 :CBC 97 : uuid_send(PG_FUNCTION_ARGS)
301 : : {
6884 bruce@momjian.us 302 : 97 : pg_uuid_t *uuid = PG_GETARG_UUID_P(0);
303 : : StringInfoData buffer;
304 : :
7175 neilc@samurai.com 305 : 97 : pq_begintypsend(&buffer);
1314 peter@eisentraut.org 306 : 97 : pq_sendbytes(&buffer, uuid->data, UUID_LEN);
7175 neilc@samurai.com 307 : 97 : PG_RETURN_BYTEA_P(pq_endtypsend(&buffer));
308 : : }
309 : :
310 : : /* internal uuid compare function */
311 : : static int
6884 bruce@momjian.us 312 : 29404318 : uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2)
313 : : {
7175 neilc@samurai.com 314 : 29404318 : return memcmp(arg1->data, arg2->data, UUID_LEN);
315 : : }
316 : :
317 : : Datum
318 : 688319 : uuid_lt(PG_FUNCTION_ARGS)
319 : : {
6884 bruce@momjian.us 320 : 688319 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
321 : 688319 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
322 : :
7175 neilc@samurai.com 323 : 688319 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) < 0);
324 : : }
325 : :
326 : : Datum
327 : 12316 : uuid_le(PG_FUNCTION_ARGS)
328 : : {
6884 bruce@momjian.us 329 : 12316 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
330 : 12316 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
331 : :
7175 neilc@samurai.com 332 : 12316 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) <= 0);
333 : : }
334 : :
335 : : Datum
336 : 236724 : uuid_eq(PG_FUNCTION_ARGS)
337 : : {
6884 bruce@momjian.us 338 : 236724 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
339 : 236724 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
340 : :
7175 neilc@samurai.com 341 : 236724 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) == 0);
342 : : }
343 : :
344 : : Datum
345 : 8228 : uuid_ge(PG_FUNCTION_ARGS)
346 : : {
6884 bruce@momjian.us 347 : 8228 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
348 : 8228 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
349 : :
7175 neilc@samurai.com 350 : 8228 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) >= 0);
351 : : }
352 : :
353 : : Datum
354 : 10659 : uuid_gt(PG_FUNCTION_ARGS)
355 : : {
6884 bruce@momjian.us 356 : 10659 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
357 : 10659 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
358 : :
7175 neilc@samurai.com 359 : 10659 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) > 0);
360 : : }
361 : :
362 : : Datum
363 : 52 : uuid_ne(PG_FUNCTION_ARGS)
364 : : {
6884 bruce@momjian.us 365 : 52 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
366 : 52 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
367 : :
7175 neilc@samurai.com 368 : 52 : PG_RETURN_BOOL(uuid_internal_cmp(arg1, arg2) != 0);
369 : : }
370 : :
371 : : /* handler for btree index operator */
372 : : Datum
373 : 6193 : uuid_cmp(PG_FUNCTION_ARGS)
374 : : {
6884 bruce@momjian.us 375 : 6193 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
376 : 6193 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
377 : :
7175 neilc@samurai.com 378 : 6193 : PG_RETURN_INT32(uuid_internal_cmp(arg1, arg2));
379 : : }
380 : :
381 : : Datum
81 msawada@postgresql.o 382 :GNC 8 : uuid_larger(PG_FUNCTION_ARGS)
383 : : {
384 : 8 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
385 : 8 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
386 : :
387 [ - + ]: 8 : PG_RETURN_UUID_P((uuid_internal_cmp(arg1, arg2) > 0) ? arg1 : arg2);
388 : : }
389 : :
390 : : Datum
391 : 8 : uuid_smaller(PG_FUNCTION_ARGS)
392 : : {
393 : 8 : pg_uuid_t *arg1 = PG_GETARG_UUID_P(0);
394 : 8 : pg_uuid_t *arg2 = PG_GETARG_UUID_P(1);
395 : :
396 [ + - ]: 8 : PG_RETURN_UUID_P((uuid_internal_cmp(arg1, arg2) < 0) ? arg1 : arg2);
397 : : }
398 : :
399 : : /*
400 : : * Sort support strategy routine
401 : : */
402 : : Datum
3971 rhaas@postgresql.org 403 :CBC 261 : uuid_sortsupport(PG_FUNCTION_ARGS)
404 : : {
3755 405 : 261 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
406 : :
3971 407 : 261 : ssup->comparator = uuid_fast_cmp;
408 : 261 : ssup->ssup_extra = NULL;
409 : :
410 [ + + ]: 261 : if (ssup->abbreviate)
411 : : {
412 : : uuid_sortsupport_state *uss;
413 : : MemoryContext oldcontext;
414 : :
415 : 204 : oldcontext = MemoryContextSwitchTo(ssup->ssup_cxt);
416 : :
284 michael@paquier.xyz 417 : 204 : uss = palloc_object(uuid_sortsupport_state);
3971 rhaas@postgresql.org 418 : 204 : uss->input_count = 0;
419 : 204 : uss->estimating = true;
420 : 204 : initHyperLogLog(&uss->abbr_card, 10);
421 : :
422 : 204 : ssup->ssup_extra = uss;
423 : :
41 john.naylor@postgres 424 :GNC 204 : ssup->comparator = ssup_datum_uint64_cmp;
3971 rhaas@postgresql.org 425 :CBC 204 : ssup->abbrev_converter = uuid_abbrev_convert;
426 : 204 : ssup->abbrev_abort = uuid_abbrev_abort;
427 : 204 : ssup->abbrev_full_comparator = uuid_fast_cmp;
428 : :
429 : 204 : MemoryContextSwitchTo(oldcontext);
430 : : }
431 : :
432 : 261 : PG_RETURN_VOID();
433 : : }
434 : :
435 : : /*
436 : : * SortSupport comparison func
437 : : */
438 : : static int
439 : 28441811 : uuid_fast_cmp(Datum x, Datum y, SortSupport ssup)
440 : : {
441 : 28441811 : pg_uuid_t *arg1 = DatumGetUUIDP(x);
442 : 28441811 : pg_uuid_t *arg2 = DatumGetUUIDP(y);
443 : :
444 : 28441811 : return uuid_internal_cmp(arg1, arg2);
445 : : }
446 : :
447 : : /*
448 : : * Callback for estimating effectiveness of abbreviated key optimization.
449 : : *
450 : : * We pay no attention to the cardinality of the non-abbreviated data, because
451 : : * there is no equality fast-path within authoritative uuid comparator.
452 : : */
453 : : static bool
454 : 1552 : uuid_abbrev_abort(int memtupcount, SortSupport ssup)
455 : : {
3755 456 : 1552 : uuid_sortsupport_state *uss = ssup->ssup_extra;
457 : : double abbr_card;
458 : :
3971 459 [ + + + - : 1552 : if (memtupcount < 10000 || uss->input_count < 10000 || !uss->estimating)
- + ]
460 : 1424 : return false;
461 : :
462 : 128 : abbr_card = estimateHyperLogLog(&uss->abbr_card);
463 : :
464 : : /*
465 : : * If we have >100k distinct values, then even if we were sorting many
466 : : * billion rows we'd likely still break even, and the penalty of undoing
467 : : * that many rows of abbrevs would probably not be worth it. Stop even
468 : : * counting at that point.
469 : : */
470 [ - + ]: 128 : if (abbr_card > 100000.0)
471 : : {
3971 rhaas@postgresql.org 472 [ # # ]:UBC 0 : if (trace_sort)
473 [ # # ]: 0 : elog(LOG,
474 : : "uuid_abbrev: estimation ends at cardinality %f"
475 : : " after " INT64_FORMAT " values (%d rows)",
476 : : abbr_card, uss->input_count, memtupcount);
477 : 0 : uss->estimating = false;
478 : 0 : return false;
479 : : }
480 : :
481 : : /*
482 : : * Target minimum cardinality is 1 per ~2k of non-null inputs. 0.5 row
483 : : * fudge factor allows us to abort earlier on genuinely pathological data
484 : : * where we've had exactly one abbreviated value in the first 2k
485 : : * (non-null) rows.
486 : : */
3971 rhaas@postgresql.org 487 [ + + ]:CBC 128 : if (abbr_card < uss->input_count / 2000.0 + 0.5)
488 : : {
489 [ - + ]: 64 : if (trace_sort)
3971 rhaas@postgresql.org 490 [ # # ]:UBC 0 : elog(LOG,
491 : : "uuid_abbrev: aborting abbreviation at cardinality %f"
492 : : " below threshold %f after " INT64_FORMAT " values (%d rows)",
493 : : abbr_card, uss->input_count / 2000.0 + 0.5, uss->input_count,
494 : : memtupcount);
3971 rhaas@postgresql.org 495 :CBC 64 : return true;
496 : : }
497 : :
498 [ - + ]: 64 : if (trace_sort)
3971 rhaas@postgresql.org 499 [ # # ]:UBC 0 : elog(LOG,
500 : : "uuid_abbrev: cardinality %f after " INT64_FORMAT
501 : : " values (%d rows)", abbr_card, uss->input_count, memtupcount);
502 : :
3971 rhaas@postgresql.org 503 :CBC 64 : return false;
504 : : }
505 : :
506 : : /*
507 : : * Conversion routine for sortsupport. Converts original uuid representation
508 : : * to abbreviated key representation. Our encoding strategy is simple -- pack
509 : : * the first `sizeof(Datum)` bytes of uuid data into a Datum (on little-endian
510 : : * machines, the bytes are stored in reverse order), and treat it as an
511 : : * unsigned integer.
512 : : */
513 : : static Datum
514 : 2256104 : uuid_abbrev_convert(Datum original, SortSupport ssup)
515 : : {
3755 516 : 2256104 : uuid_sortsupport_state *uss = ssup->ssup_extra;
517 : 2256104 : pg_uuid_t *authoritative = DatumGetUUIDP(original);
518 : : Datum res;
519 : :
3971 520 : 2256104 : memcpy(&res, authoritative->data, sizeof(Datum));
521 : 2256104 : uss->input_count += 1;
522 : :
523 [ + - ]: 2256104 : if (uss->estimating)
524 : : {
525 : : uint32 tmp;
526 : :
403 tgl@sss.pgh.pa.us 527 : 2256104 : tmp = DatumGetUInt32(res) ^ (uint32) (DatumGetUInt64(res) >> 32);
528 : :
3971 rhaas@postgresql.org 529 : 2256104 : addHyperLogLog(&uss->abbr_card, DatumGetUInt32(hash_uint32(tmp)));
530 : : }
531 : :
532 : : /*
533 : : * Byteswap on little-endian machines.
534 : : *
535 : : * This is needed so that ssup_datum_uint64_cmp() (an unsigned integer
536 : : * 3-way comparator) works correctly on all platforms. If we didn't do
537 : : * this, the comparator would have to call memcmp() with a pair of
538 : : * pointers to the first byte of each abbreviated key, which is slower.
539 : : */
540 : 2256104 : res = DatumBigEndianToNative(res);
541 : :
542 : 2256104 : return res;
543 : : }
544 : :
545 : : static Datum
534 pg@bowt.ie 546 :UBC 0 : uuid_decrement(Relation rel, Datum existing, bool *underflow)
547 : : {
548 : : pg_uuid_t *uuid;
549 : :
550 : 0 : uuid = (pg_uuid_t *) palloc(UUID_LEN);
551 : 0 : memcpy(uuid, DatumGetUUIDP(existing), UUID_LEN);
552 [ # # ]: 0 : for (int i = UUID_LEN - 1; i >= 0; i--)
553 : : {
554 [ # # ]: 0 : if (uuid->data[i] > 0)
555 : : {
556 : 0 : uuid->data[i]--;
557 : 0 : *underflow = false;
558 : 0 : return UUIDPGetDatum(uuid);
559 : : }
560 : 0 : uuid->data[i] = UCHAR_MAX;
561 : : }
562 : :
563 : 0 : pfree(uuid); /* cannot leak memory */
564 : :
565 : : /* return value is undefined */
566 : 0 : *underflow = true;
567 : 0 : return (Datum) 0;
568 : : }
569 : :
570 : : static Datum
571 : 0 : uuid_increment(Relation rel, Datum existing, bool *overflow)
572 : : {
573 : : pg_uuid_t *uuid;
574 : :
575 : 0 : uuid = (pg_uuid_t *) palloc(UUID_LEN);
576 : 0 : memcpy(uuid, DatumGetUUIDP(existing), UUID_LEN);
577 [ # # ]: 0 : for (int i = UUID_LEN - 1; i >= 0; i--)
578 : : {
579 [ # # ]: 0 : if (uuid->data[i] < UCHAR_MAX)
580 : : {
581 : 0 : uuid->data[i]++;
582 : 0 : *overflow = false;
583 : 0 : return UUIDPGetDatum(uuid);
584 : : }
585 : 0 : uuid->data[i] = 0;
586 : : }
587 : :
588 : 0 : pfree(uuid); /* cannot leak memory */
589 : :
590 : : /* return value is undefined */
591 : 0 : *overflow = true;
592 : 0 : return (Datum) 0;
593 : : }
594 : :
595 : : Datum
596 : 0 : uuid_skipsupport(PG_FUNCTION_ARGS)
597 : : {
598 : 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
599 : 0 : pg_uuid_t *uuid_min = palloc(UUID_LEN);
600 : 0 : pg_uuid_t *uuid_max = palloc(UUID_LEN);
601 : :
602 : 0 : memset(uuid_min->data, 0x00, UUID_LEN);
603 : 0 : memset(uuid_max->data, 0xFF, UUID_LEN);
604 : :
605 : 0 : sksup->decrement = uuid_decrement;
606 : 0 : sksup->increment = uuid_increment;
607 : 0 : sksup->low_elem = UUIDPGetDatum(uuid_min);
608 : 0 : sksup->high_elem = UUIDPGetDatum(uuid_max);
609 : :
610 : 0 : PG_RETURN_VOID();
611 : : }
612 : :
613 : : /* hash index support */
614 : : Datum
7175 neilc@samurai.com 615 :CBC 1620 : uuid_hash(PG_FUNCTION_ARGS)
616 : : {
6884 bruce@momjian.us 617 : 1620 : pg_uuid_t *key = PG_GETARG_UUID_P(0);
618 : :
7172 neilc@samurai.com 619 : 1620 : return hash_any(key->data, UUID_LEN);
620 : : }
621 : :
622 : : Datum
3307 rhaas@postgresql.org 623 : 40 : uuid_hash_extended(PG_FUNCTION_ARGS)
624 : : {
625 : 40 : pg_uuid_t *key = PG_GETARG_UUID_P(0);
626 : :
627 : 40 : return hash_any_extended(key->data, UUID_LEN, PG_GETARG_INT64(1));
628 : : }
629 : :
630 : : /*
631 : : * Set the given UUID version and the variant bits
632 : : */
633 : : static inline void
648 msawada@postgresql.o 634 : 35808 : uuid_set_version(pg_uuid_t *uuid, unsigned char version)
635 : : {
636 : : /* set version field, top four bits */
637 : 35808 : uuid->data[6] = (uuid->data[6] & 0x0f) | (version << 4);
638 : :
639 : : /* set variant field, top two bits are 1, 0 */
640 : 35808 : uuid->data[8] = (uuid->data[8] & 0x3f) | 0x80;
641 : 35808 : }
642 : :
643 : : /*
644 : : * Generate UUID version 4.
645 : : *
646 : : * All UUID bytes are filled with strong random numbers except version and
647 : : * variant bits.
648 : : */
649 : : Datum
2625 peter@eisentraut.org 650 : 72 : gen_random_uuid(PG_FUNCTION_ARGS)
651 : : {
652 : 72 : pg_uuid_t *uuid = palloc(UUID_LEN);
653 : :
654 [ - + ]: 72 : if (!pg_strong_random(uuid, UUID_LEN))
2625 peter@eisentraut.org 655 [ # # ]:UBC 0 : ereport(ERROR,
656 : : (errcode(ERRCODE_INTERNAL_ERROR),
657 : : errmsg("could not generate random values")));
658 : :
659 : : /*
660 : : * Set magic numbers for a "version 4" (pseudorandom) UUID and variant,
661 : : * see https://datatracker.ietf.org/doc/html/rfc9562#name-uuid-version-4
662 : : */
648 msawada@postgresql.o 663 :CBC 72 : uuid_set_version(uuid, 4);
664 : :
2625 peter@eisentraut.org 665 : 72 : PG_RETURN_UUID_P(uuid);
666 : : }
667 : :
668 : : /*
669 : : * Get the current timestamp with nanosecond precision for UUID generation.
670 : : * The returned timestamp is ensured to be at least SUBMS_MINIMAL_STEP greater
671 : : * than the previous returned timestamp (on this backend).
672 : : */
673 : : static inline int64
291 nathan@postgresql.or 674 : 35752 : get_real_time_ns_ascending(void)
675 : : {
676 : : static int64 previous_ns = 0;
677 : : int64 ns;
678 : :
679 : : /* Get the current real timestamp */
680 : :
681 : : #ifdef _MSC_VER
682 : : struct timeval tmp;
683 : :
684 : : gettimeofday(&tmp, NULL);
685 : : ns = tmp.tv_sec * NS_PER_S + tmp.tv_usec * NS_PER_US;
686 : : #else
687 : : struct timespec tmp;
688 : :
689 : : /*
690 : : * We don't use gettimeofday(), instead use clock_gettime() with
691 : : * CLOCK_REALTIME where available in order to get a high-precision
692 : : * (nanoseconds) real timestamp.
693 : : *
694 : : * Note while a timestamp returned by clock_gettime() with CLOCK_REALTIME
695 : : * is nanosecond-precision on most Unix-like platforms, on some platforms
696 : : * such as macOS it's restricted to microsecond-precision.
697 : : */
648 msawada@postgresql.o 698 : 35752 : clock_gettime(CLOCK_REALTIME, &tmp);
699 : 35752 : ns = tmp.tv_sec * NS_PER_S + tmp.tv_nsec;
700 : : #endif
701 : :
702 : : /* Guarantee the minimal step advancement of the timestamp */
703 [ - + ]: 35752 : if (previous_ns + SUBMS_MINIMAL_STEP_NS >= ns)
648 msawada@postgresql.o 704 :UBC 0 : ns = previous_ns + SUBMS_MINIMAL_STEP_NS;
648 msawada@postgresql.o 705 :CBC 35752 : previous_ns = ns;
706 : :
707 : 35752 : return ns;
708 : : }
709 : :
710 : : /*
711 : : * Generate UUID version 7 per RFC 9562, with the given timestamp.
712 : : *
713 : : * UUID version 7 consists of a Unix timestamp in milliseconds (48 bits) and
714 : : * 74 random bits, excluding the required version and variant bits. To ensure
715 : : * monotonicity in scenarios of high-frequency UUID generation, we employ the
716 : : * method "Replace Leftmost Random Bits with Increased Clock Precision (Method 3)",
717 : : * described in the RFC. This method utilizes 12 bits from the "rand_a" bits
718 : : * to store a 1/4096 (or 2^12) fraction of sub-millisecond precision.
719 : : *
720 : : * unix_ts_ms is a number of milliseconds since start of the UNIX epoch,
721 : : * and sub_ms is a number of nanoseconds within millisecond. These values are
722 : : * used for time-dependent bits of UUID.
723 : : *
724 : : * NB: all numbers here are unsigned, unix_ts_ms cannot be negative per RFC.
725 : : */
726 : : static pg_uuid_t *
541 727 : 35736 : generate_uuidv7(uint64 unix_ts_ms, uint32 sub_ms)
728 : : {
648 729 : 35736 : pg_uuid_t *uuid = palloc(UUID_LEN);
730 : : uint32 increased_clock_precision;
731 : :
732 : : /* Fill in time part */
733 : 35736 : uuid->data[0] = (unsigned char) (unix_ts_ms >> 40);
734 : 35736 : uuid->data[1] = (unsigned char) (unix_ts_ms >> 32);
735 : 35736 : uuid->data[2] = (unsigned char) (unix_ts_ms >> 24);
736 : 35736 : uuid->data[3] = (unsigned char) (unix_ts_ms >> 16);
737 : 35736 : uuid->data[4] = (unsigned char) (unix_ts_ms >> 8);
738 : 35736 : uuid->data[5] = (unsigned char) unix_ts_ms;
739 : :
740 : : /*
741 : : * sub-millisecond timestamp fraction (SUBMS_BITS bits, not
742 : : * SUBMS_MINIMAL_STEP_BITS)
743 : : */
541 744 : 35736 : increased_clock_precision = (sub_ms * (1 << SUBMS_BITS)) / NS_PER_MS;
745 : :
746 : : /* Fill the increased clock precision to "rand_a" bits */
648 747 : 35736 : uuid->data[6] = (unsigned char) (increased_clock_precision >> 8);
748 : 35736 : uuid->data[7] = (unsigned char) (increased_clock_precision);
749 : :
750 : : /* fill everything after the increased clock precision with random bytes */
751 [ - + ]: 35736 : if (!pg_strong_random(&uuid->data[8], UUID_LEN - 8))
648 msawada@postgresql.o 752 [ # # ]:UBC 0 : ereport(ERROR,
753 : : (errcode(ERRCODE_INTERNAL_ERROR),
754 : : errmsg("could not generate random values")));
755 : :
756 : : #if SUBMS_MINIMAL_STEP_BITS == 10
757 : :
758 : : /*
759 : : * On systems that have only 10 bits of sub-ms precision, 2 least
760 : : * significant are dependent on other time-specific bits, and they do not
761 : : * contribute to uniqueness. To make these bit random we mix in two bits
762 : : * from CSPRNG. SUBMS_MINIMAL_STEP is chosen so that we still guarantee
763 : : * monotonicity despite altering these bits.
764 : : */
765 : : uuid->data[7] = uuid->data[7] ^ (uuid->data[8] >> 6);
766 : : #endif
767 : :
768 : : /*
769 : : * Set magic numbers for a "version 7" (pseudorandom) UUID and variant,
770 : : * see https://www.rfc-editor.org/rfc/rfc9562#name-version-field
771 : : */
648 msawada@postgresql.o 772 :CBC 35736 : uuid_set_version(uuid, 7);
773 : :
774 : 35736 : return uuid;
775 : : }
776 : :
777 : : /*
778 : : * Generate UUID version 7 with the current timestamp.
779 : : */
780 : : Datum
781 : 52 : uuidv7(PG_FUNCTION_ARGS)
782 : : {
541 783 : 52 : int64 ns = get_real_time_ns_ascending();
784 : 52 : pg_uuid_t *uuid = generate_uuidv7(ns / NS_PER_MS, ns % NS_PER_MS);
785 : :
648 786 : 52 : PG_RETURN_UUID_P(uuid);
787 : : }
788 : :
789 : : /*
790 : : * Similar to uuidv7() but with the timestamp adjusted by the given interval.
791 : : */
792 : : Datum
793 : 35700 : uuidv7_interval(PG_FUNCTION_ARGS)
794 : : {
795 : 35700 : Interval *shift = PG_GETARG_INTERVAL_P(0);
796 : : TimestampTz ts;
797 : : pg_uuid_t *uuid;
798 : 35700 : int64 ns = get_real_time_ns_ascending();
799 : : int64 us;
800 : :
801 : : /* Reject infinite intervals before any arithmetic */
66 802 [ + + + - : 35700 : if (INTERVAL_NOT_FINITE(shift))
- + + + +
- + - ]
803 [ + - ]: 8 : ereport(ERROR,
804 : : (errcode(ERRCODE_DATETIME_VALUE_OUT_OF_RANGE),
805 : : errmsg("interval out of range for UUID version 7"),
806 : : errdetail("UUID version 7 does not support infinite intervals.")));
807 : :
808 : : /*
809 : : * Shift the current timestamp by the given interval. To calculate time
810 : : * shift correctly, we convert the UNIX epoch to TimestampTz and use
811 : : * timestamptz_pl_interval(). This calculation is done with microsecond
812 : : * precision.
813 : : */
814 : :
815 : 35692 : ts = (TimestampTz) (ns / NS_PER_US) - PG_UNIX_EPOCH_OFFSET_US;
816 : :
817 : : /* Compute time shift */
648 818 : 35692 : ts = DatumGetTimestampTz(DirectFunctionCall2(timestamptz_pl_interval,
819 : : TimestampTzGetDatum(ts),
820 : : IntervalPGetDatum(shift)));
821 : :
822 : : /*
823 : : * Reject timestamps outside the range representable by UUID version 7's
824 : : * 48-bit millisecond field. We compare in PostgreSQL-epoch units so that
825 : : * the subsequent conversion to Unix-epoch microseconds cannot overflow.
826 : : */
66 827 [ + + + + ]: 35692 : if (ts < UUIDV7_MIN_TIMESTAMP || ts > UUIDV7_MAX_TIMESTAMP)
828 [ + - ]: 8 : ereport(ERROR,
829 : : (errcode(ERRCODE_DATETIME_VALUE_OUT_OF_RANGE),
830 : : errmsg("timestamp out of range for UUID version 7"),
831 : : errdetail("UUID version 7 supports timestamps from 1970-01-01 to approximately year 10889.")));
832 : :
833 : : /* Convert the TimestampTz value to a Unix-epoch timestamp in usec */
834 : 35684 : us = ts + PG_UNIX_EPOCH_OFFSET_US;
835 : :
836 : : /* Generate an UUIDv7 */
541 837 : 35684 : uuid = generate_uuidv7(us / US_PER_MS, (us % US_PER_MS) * NS_PER_US + ns % NS_PER_US);
838 : :
648 839 : 35684 : PG_RETURN_UUID_P(uuid);
840 : : }
841 : :
842 : : /*
843 : : * Start of a Gregorian epoch == date2j(1582,10,15)
844 : : * We cast it to 64-bit because it's used in overflow-prone computations
845 : : */
846 : : #define GREGORIAN_EPOCH_JDATE INT64CONST(2299161)
847 : :
848 : : /*
849 : : * Extract timestamp from UUID.
850 : : *
851 : : * Returns null if not RFC 9562 variant or not a version that has a timestamp.
852 : : */
853 : : Datum
915 peter@eisentraut.org 854 : 35704 : uuid_extract_timestamp(PG_FUNCTION_ARGS)
855 : : {
856 : 35704 : pg_uuid_t *uuid = PG_GETARG_UUID_P(0);
857 : : int version;
858 : : uint64 tms;
859 : : TimestampTz ts;
860 : :
861 : : /* check if RFC 9562 variant */
862 [ + + ]: 35704 : if ((uuid->data[8] & 0xc0) != 0x80)
863 : 5 : PG_RETURN_NULL();
864 : :
865 : 35699 : version = uuid->data[6] >> 4;
866 : :
867 [ + + ]: 35699 : if (version == 1)
868 : : {
869 : : /*----------
870 : : * UUIDv1 splits the 60-bit Gregorian timestamp into three fields that
871 : : * are *not* stored most-significant-first (see RFC 9562 Sec. 5.1):
872 : : *
873 : : * time_low (bits 0-31) octets 0-3, the least significant 32 bits
874 : : * time_mid (bits 32-47) octets 4-5, the middle 16 bits
875 : : * time_high (bits 48-59) octet 6 low nibble + octet 7, the most
876 : : * significant 12 bits (octet 6 high nibble
877 : : * holds the version and is masked off)
878 : : *
879 : : * Reassemble the timestamp by shifting each field back to its place.
880 : : *----------
881 : : */
882 : 5 : tms = ((uint64) uuid->data[0] << 24)
883 : 5 : + ((uint64) uuid->data[1] << 16)
884 : 5 : + ((uint64) uuid->data[2] << 8)
885 : 5 : + ((uint64) uuid->data[3])
886 : 5 : + ((uint64) uuid->data[4] << 40)
887 : 5 : + ((uint64) uuid->data[5] << 32)
888 : 5 : + (((uint64) uuid->data[6] & 0xf) << 56)
889 : 5 : + ((uint64) uuid->data[7] << 48);
890 : :
891 : : /* convert 100-ns intervals to us, then adjust */
892 : 5 : ts = (TimestampTz) (tms / 10) -
893 : : ((uint64) POSTGRES_EPOCH_JDATE - GREGORIAN_EPOCH_JDATE) * SECS_PER_DAY * USECS_PER_SEC;
648 msawada@postgresql.o 894 : 5 : PG_RETURN_TIMESTAMPTZ(ts);
895 : : }
896 : :
47 msawada@postgresql.o 897 [ + + ]:GNC 35694 : if (version == 6)
898 : : {
899 : : /*----------
900 : : * UUIDv6 is a field-compatible reordering of UUIDv1 that stores the
901 : : * 60-bit Gregorian timestamp most-significant-first (see RFC 9562
902 : : * Sec. 5.6):
903 : : *
904 : : * time_high (bits 28-59) octets 0-3, the most significant 32 bits
905 : : * time_mid (bits 12-27) octets 4-5, the middle 16 bits
906 : : * time_low (bits 0-11) octet 6 low nibble + octet 7, the least
907 : : * significant 12 bits (octet 6 high nibble
908 : : * holds the version and is masked off)
909 : : *
910 : : * Note that the 12-bit field is the least significant one here,
911 : : * while in UUIDv1 it is the most significant. The version nibble
912 : : * therefore sits below time_high and time_mid rather than above
913 : : * them, and compacting the timestamp squeezes it out: each of
914 : : * octets 0-5 ends up 4 bits lower than a plain big-endian read
915 : : * would put it, hence the 52/44/36/28/20/12 shift counts below.
916 : : *----------
917 : : */
918 : 5 : tms = ((uint64) uuid->data[0] << 52)
919 : 5 : + ((uint64) uuid->data[1] << 44)
920 : 5 : + ((uint64) uuid->data[2] << 36)
921 : 5 : + ((uint64) uuid->data[3] << 28)
922 : 5 : + ((uint64) uuid->data[4] << 20)
923 : 5 : + ((uint64) uuid->data[5] << 12)
924 : 5 : + (((uint64) uuid->data[6] & 0xf) << 8)
925 : 5 : + ((uint64) uuid->data[7]);
926 : :
927 : : /* convert 100-ns intervals to us, then adjust */
928 : 5 : ts = (TimestampTz) (tms / 10) -
929 : : ((uint64) POSTGRES_EPOCH_JDATE - GREGORIAN_EPOCH_JDATE) * SECS_PER_DAY * USECS_PER_SEC;
930 : 5 : PG_RETURN_TIMESTAMPTZ(ts);
931 : : }
932 : :
648 msawada@postgresql.o 933 [ + + ]:CBC 35689 : if (version == 7)
934 : : {
935 : : /*
936 : : * UUIDv7 stores a 48-bit Unix timestamp in milliseconds (unix_ts_ms)
937 : : * most-significant-first in octets 0-5 (see RFC 9562 Sec. 5.7). There
938 : : * is no version nibble inside this field, so the bytes reassemble at
939 : : * clean 8-bit boundaries.
940 : : */
941 : 35685 : tms = (uuid->data[5])
942 : 35685 : + (((uint64) uuid->data[4]) << 8)
943 : 35685 : + (((uint64) uuid->data[3]) << 16)
944 : 35685 : + (((uint64) uuid->data[2]) << 24)
945 : 35685 : + (((uint64) uuid->data[1]) << 32)
946 : 35685 : + (((uint64) uuid->data[0]) << 40);
947 : :
948 : : /* convert ms to us, then adjust */
66 949 : 35685 : ts = (TimestampTz) (tms * US_PER_MS) - PG_UNIX_EPOCH_OFFSET_US;
950 : :
915 peter@eisentraut.org 951 : 35685 : PG_RETURN_TIMESTAMPTZ(ts);
952 : : }
953 : :
954 : : /* not a timestamp-containing UUID version */
955 : 4 : PG_RETURN_NULL();
956 : : }
957 : :
958 : : /*
959 : : * Extract UUID version.
960 : : *
961 : : * Returns null if not RFC 9562 variant.
962 : : */
963 : : Datum
964 : 22 : uuid_extract_version(PG_FUNCTION_ARGS)
965 : : {
966 : 22 : pg_uuid_t *uuid = PG_GETARG_UUID_P(0);
967 : : uint16 version;
968 : :
969 : : /* check if RFC 9562 variant */
970 [ + + ]: 22 : if ((uuid->data[8] & 0xc0) != 0x80)
971 : 5 : PG_RETURN_NULL();
972 : :
973 : 17 : version = uuid->data[6] >> 4;
974 : :
975 : 17 : PG_RETURN_UINT16(version);
976 : : }
|
