Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qQ3MB-00Cnsc-7C for pgsql-hackers@arkaria.postgresql.org; Sun, 30 Jul 2023 10:08:59 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qQ3M7-008mbZ-AY for pgsql-hackers@arkaria.postgresql.org; Sun, 30 Jul 2023 10:08:55 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qQ3M6-008mbR-Up for pgsql-hackers@lists.postgresql.org; Sun, 30 Jul 2023 10:08:55 +0000 Received: from forwardcorp1b.mail.yandex.net ([178.154.239.136]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qQ3M0-001Fyo-6n for pgsql-hackers@postgresql.org; Sun, 30 Jul 2023 10:08:54 +0000 Received: from mail-nwsmtp-smtp-corp-main-44.iva.yp-c.yandex.net (mail-nwsmtp-smtp-corp-main-44.iva.yp-c.yandex.net [IPv6:2a02:6b8:c0c:9a90:0:640:d8ed:0]) by forwardcorp1b.mail.yandex.net (Yandex) with ESMTP id 67A66602C8; Sun, 30 Jul 2023 13:08:45 +0300 (MSK) Received: from smtpclient.apple (unknown [2a02:6b8:b081:b5a8::1:c]) by mail-nwsmtp-smtp-corp-main-44.iva.yp-c.yandex.net (smtpcorp/Yandex) with ESMTPSA id g8MRZN0OcGk0-LVnBv7vp; Sun, 30 Jul 2023 13:08:44 +0300 X-Yandex-Fwd: 1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex-team.ru; s=default; t=1690711724; bh=FEt5AzuVJ8YPnHBrPrcGw7CIgTtZ9v6Hu4GXtnV5pTM=; h=References:To:Cc:In-Reply-To:Date:From:Message-Id:Subject; b=fiUSF7gHgcPKv/jl8GvF3Gvh8oUy4mQLSc8JIIDl1RBxcWP7LTBvCIH8bBegAOcUr 8jnS99yOlodblzjag6cPawwzcPbTsJGeQl6TfeZormWGRRNJu0y5S4+NsfP+LMg8By 9SAPGsP0CjYQGM/mxaFcny6B9/br5dXF67CHd9Fc= Authentication-Results: mail-nwsmtp-smtp-corp-main-44.iva.yp-c.yandex.net; dkim=pass header.i=@yandex-team.ru From: "Andrey M. Borodin" Message-Id: <84D20D0F-B5FF-41CD-9F48-E282CE9FEC1D@yandex-team.ru> Content-Type: multipart/alternative; boundary="Apple-Mail=_8F964B80-60D5-46C0-BE70-8BB7CCA356D1" Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.120.41.1.2\)) Subject: Re: UUID v7 Date: Sun, 30 Jul 2023 15:08:41 +0500 In-Reply-To: <5dc6fdaa-5896-ebc4-7094-eac45a818846@enterprisedb.com> Cc: Tom Lane , Daniel Gustafsson , Matthias van de Meent , Nikolay Samokhvalov , "Kyzer Davis (kydavis)" , Andres Freund , Andrey Borodin , PostgreSQL Hackers , "brad@peabody.io" , "wolakk@gmail.com" , sergeyprokhorenko@yahoo.com.au To: Peter Eisentraut References: <20230211011453.uq2yopunpbovcbnn@awork3.anarazel.de> <5ceb7394-7488-d438-0951-fcc940feb539@enterprisedb.com> <5176A0E4-CA75-47D0-A1F3-FBC9B6116595@yesql.se> <7AC9F1D2-A02B-4FF6-A331-C686C7EA244B@yesql.se> <1204013.1688652164@sss.pgh.pa.us> <457ba532-ea71-dc13-6d60-2b79bb32eeeb@enterprisedb.com> <5dc6fdaa-5896-ebc4-7094-eac45a818846@enterprisedb.com> X-Mailer: Apple Mail (2.3696.120.41.1.2) List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --Apple-Mail=_8F964B80-60D5-46C0-BE70-8BB7CCA356D1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii > On 10 Jul 2023, at 21:50, Peter Eisentraut = wrote: >=20 > I suggest we keep this thread to v7, which has pretty straightforward = semantics for PostgreSQL. v8 by definition has many possible = implementations, so you're going to have to make pretty strong arguments = that yours is the best and only one, if you are going to claim the = gen_uuid_v8 function name. Thanks Peter, I'll follow this course of action. After discussion on GitHub with Sergey Prokhorenko [0] I understood that = counter is optional, but useful part of UUID v7. It actually promotes = sortability of data generated at high speed. The standard does not specify how big counter should be. PFA patch with = 16 bit counter. Maybe it worth doing 18bit counter - it will save us one = byte of PRNG data. Currently we only take 2 bits out of the whole random = byte. Best regards, Andrey Borodin. [0] https://github.com/x4m/pg_uuid_next/issues/1#issuecomment-1657074776 = --Apple-Mail=_8F964B80-60D5-46C0-BE70-8BB7CCA356D1 Content-Type: multipart/mixed; boundary="Apple-Mail=_D1CA7478-ADD7-4B8F-AC6C-29793D49C02F" --Apple-Mail=_D1CA7478-ADD7-4B8F-AC6C-29793D49C02F Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii

On 10 Jul 2023, at 21:50, Peter Eisentraut <peter.eisentraut@enterprisedb.com> wrote:

I suggest we keep this thread = to v7, which has pretty straightforward semantics for PostgreSQL. =  v8 by definition has many possible implementations, so you're = going to have to make pretty strong arguments that yours is the best and = only one, if you are going to claim the gen_uuid_v8 function name.

Thanks = Peter, I'll follow this course of action.

After discussion on GitHub with Sergey Prokhorenko = [0] I understood that counter is optional, but useful part of UUID v7. = It actually promotes sortability of data generated at high = speed.
The standard does not specify how big counter should = be. PFA patch with 16 bit counter. Maybe it worth doing 18bit counter - = it will save us one byte of PRNG data. Currently we only take 2 bits out = of the whole random byte.


Best regards, Andrey Borodin.


[0] https://github.com/x4m/pg_uuid_next/issues/1#issuecomment-16570= 74776
= --Apple-Mail=_D1CA7478-ADD7-4B8F-AC6C-29793D49C02F Content-Disposition: attachment; filename=v3-0001-Implement-UUID-v7-as-per-IETF-draft.patch Content-Type: application/octet-stream; x-unix-mode=0644; name="v3-0001-Implement-UUID-v7-as-per-IETF-draft.patch" Content-Transfer-Encoding: quoted-printable =46rom=2067f4202555d1c8cf3230235e134d070ddb82173c=20Mon=20Sep=2017=20= 00:00:00=202001=0AFrom:=20Andrey=20Borodin=20=0A= Date:=20Fri,=2010=20Feb=202023=2015:38:40=20-0800=0ASubject:=20[PATCH=20= v3]=20Implement=20UUID=20v7=20as=20per=20IETF=20draft=0A=0AAuthors:=20= Andrey=20Borodin,=20Sergey=20Prokhorenko=0A---=0A=20= doc/src/sgml/func.sgml=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20|=2010=20++++-=0A=20src/backend/utils/adt/uuid.c=20=20=20=20=20=20=20= =20=20=20=20=20=20|=2050=20++++++++++++++++++++++++=0A=20= src/include/catalog/pg_proc.dat=20=20=20=20=20=20=20=20=20=20|=20=203=20= ++=0A=20src/test/regress/expected/opr_sanity.out=20|=20=201=20+=0A=20= src/test/regress/expected/uuid.out=20=20=20=20=20=20=20|=2010=20+++++=0A=20= src/test/regress/sql/uuid.sql=20=20=20=20=20=20=20=20=20=20=20=20|=20=20= 6=20+++=0A=206=20files=20changed,=2079=20insertions(+),=201=20= deletion(-)=0A=0Adiff=20--git=20a/doc/src/sgml/func.sgml=20= b/doc/src/sgml/func.sgml=0Aindex=20be2f54c914..b2d89cf415=20100644=0A---=20= a/doc/src/sgml/func.sgml=0A+++=20b/doc/src/sgml/func.sgml=0A@@=20= -13947,13=20+13947,21=20@@=20CREATE=20TYPE=20rainbow=20AS=20ENUM=20= ('red',=20'orange',=20'yellow',=20'green',=20'blue',=20'purple=0A=20=20=20= =20gen_random_uuid=0A=20=20=20=0A=20=0A+=20= =20=0A+=20=20=20gen_uuid_v7=0A+=20=20= =0A+=0A=20=20=20=0A-=20=20=20= PostgreSQL=20includes=20one=20function=20to=20= generate=20a=20UUID:=0A+=20=20=20PostgreSQL=20= includes=20three=20functions=20to=20generate=20a=20UUID:=0A=20=0A= =20gen_random_uuid=20()=20= uuid=0A=20=0A=20=20=20=20This=20= function=20returns=20a=20version=204=20(random)=20UUID.=20=20This=20is=20= the=20most=20commonly=0A=20=20=20=20used=20type=20of=20UUID=20and=20is=20= appropriate=20for=20most=20applications.=0A+=0A= +gen_uuid_v7=20()=20uuid=0A= +=0A+=20=20=20This=20function=20returns=20a=20version=207=20= (time-ordered=20+=20random)=20UUID.=0A=20=20=20=0A=20=0A=20=20=20= =0Adiff=20--git=20a/src/backend/utils/adt/uuid.c=20= b/src/backend/utils/adt/uuid.c=0Aindex=204f7aa768fd..49f9c03995=20100644=0A= ---=20a/src/backend/utils/adt/uuid.c=0A+++=20= b/src/backend/utils/adt/uuid.c=0A@@=20-13,6=20+13,9=20@@=0A=20=0A=20= #include=20"postgres.h"=0A=20=0A+#include=20=0A+=0A+#include=20= "access/xlog.h"=0A=20#include=20"common/hashfn.h"=0A=20#include=20= "lib/hyperloglog.h"=0A=20#include=20"libpq/pqformat.h"=0A@@=20-421,3=20= +424,50=20@@=20gen_random_uuid(PG_FUNCTION_ARGS)=0A=20=0A=20=09= PG_RETURN_UUID_P(uuid);=0A=20}=0A+=0A+static=20uint16_t=20= sequence_counter;=0A+=0A+Datum=0A+gen_uuid_v7(PG_FUNCTION_ARGS)=0A+{=0A+=09= pg_uuid_t=20=20*uuid=20=3D=20palloc(UUID_LEN);=0A+=09struct=20timeval=20= tp;=0A+=09uint64_t=20tms;=0A+=09uint16_t=20local_counter=20=3D=20= sequence_counter++;=0A+=0A+=09gettimeofday(&tp,=20NULL);=0A+=0A+=09tms=20= =3D=20((uint64_t)tp.tv_sec)=20*=201000;=0A+=09tms=20+=3D=20= ((uint64_t)tp.tv_usec)=20/=201000;=0A+=0A+=09tms=20=3D=20= pg_hton64(tms<<16);=0A+=0A+=09/*=20Fill=20in=20time=20part=20*/=0A+=09= memcpy(&uuid->data[0],=20&tms,=206);=0A+=0A+=0A+=09/*=20fill=20= everything=20after=20the=20timestamp=20and=20counter=20with=20random=20= bytes=20*/=0A+=09if=20(!pg_strong_random(&uuid->data[8],=20UUID_LEN=20-=20= 8))=0A+=09=09ereport(ERROR,=0A+=09=09=09=09= (errcode(ERRCODE_INTERNAL_ERROR),=0A+=09=09=09=09=20errmsg("could=20not=20= generate=20random=20values")));=0A+=0A+=09/*=20most=20significant=204=20= bits=20of=20counter=20*/=0A+=09uuid->data[6]=20=3D=20(unsigned=20= char)(local_counter>>12);=0A+=09/*=20next=208=20bits=20*/=0A+=09= uuid->data[7]=20=3D=20(unsigned=20char)(local_counter>>4);=0A+=09/*=20= least=20significant=204=20bits=20in=20a=20middle=20of=20a=20byte,=20= leaving=202=20bits=20of=20entropy=20*/=0A+=09uuid->data[8]=20=3D=20= (unsigned=20char)(local_counter<<2);=0A+=0A+=09/*=0A+=09=20*=20Set=20= magic=20numbers=20for=20a=20"version=207"=20(pseudorandom)=20UUID,=20see=0A= +=09=20*=20http://tools.ietf.org/html/rfc=20???=0A+=09=20*=20= https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-form= at#name-creating-a-uuidv7-value=0A+=09=20*/=0A+=09/*=20set=20version=20= field,=20top=20four=20bits=20are=200,=201,=201,=201=20*/=0A+=09= uuid->data[6]=20=3D=20(uuid->data[6]=20&=200x0f)=20|=200x70;=0A+=09/*=20= set=20variant=20field,=20top=20two=20bits=20are=201,=200=20*/=0A+=09= uuid->data[8]=20=3D=20(uuid->data[8]=20&=200x3f)=20|=200x80;=0A+=0A+=09= PG_RETURN_UUID_P(uuid);=0A+}=0Adiff=20--git=20= a/src/include/catalog/pg_proc.dat=20b/src/include/catalog/pg_proc.dat=0A= index=206996073989..b11e0382c0=20100644=0A---=20= a/src/include/catalog/pg_proc.dat=0A+++=20= b/src/include/catalog/pg_proc.dat=0A@@=20-9119,6=20+9119,9=20@@=0A=20{=20= oid=20=3D>=20'3432',=20descr=20=3D>=20'generate=20random=20UUID',=0A=20=20= =20proname=20=3D>=20'gen_random_uuid',=20proleakproof=20=3D>=20't',=20= provolatile=20=3D>=20'v',=0A=20=20=20prorettype=20=3D>=20'uuid',=20= proargtypes=20=3D>=20'',=20prosrc=20=3D>=20'gen_random_uuid'=20},=0A+{=20= oid=20=3D>=20'3813',=20descr=20=3D>=20'generate=20UUID=20version=207',=0A= +=20=20proname=20=3D>=20'gen_uuid_v7',=20proleakproof=20=3D>=20't',=20= provolatile=20=3D>=20'v',=0A+=20=20prorettype=20=3D>=20'uuid',=20= proargtypes=20=3D>=20'',=20prosrc=20=3D>=20'gen_uuid_v7'=20},=0A=20=0A=20= #=20pg_lsn=0A=20{=20oid=20=3D>=20'3229',=20descr=20=3D>=20'I/O',=0Adiff=20= --git=20a/src/test/regress/expected/opr_sanity.out=20= b/src/test/regress/expected/opr_sanity.out=0Aindex=20= a1bdf2c0b5..3141183b01=20100644=0A---=20= a/src/test/regress/expected/opr_sanity.out=0A+++=20= b/src/test/regress/expected/opr_sanity.out=0A@@=20-857,6=20+857,7=20@@=20= sha384(bytea)=0A=20sha512(bytea)=0A=20gen_random_uuid()=0A=20= starts_with(text,text)=0A+gen_uuid_v7()=0A=20= macaddr8_eq(macaddr8,macaddr8)=0A=20macaddr8_lt(macaddr8,macaddr8)=0A=20= macaddr8_le(macaddr8,macaddr8)=0Adiff=20--git=20= a/src/test/regress/expected/uuid.out=20= b/src/test/regress/expected/uuid.out=0Aindex=208e7f21910d..fc9f50e69e=20= 100644=0A---=20a/src/test/regress/expected/uuid.out=0A+++=20= b/src/test/regress/expected/uuid.out=0A@@=20-168,5=20+168,15=20@@=20= SELECT=20count(DISTINCT=20guid_field)=20FROM=20guid1;=0A=20=20=20=20=20=20= 2=0A=20(1=20row)=0A=20=0A+--=20generation=20test=20for=20v7=0A+TRUNCATE=20= guid1;=0A+INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20= (gen_uuid_v7());=0A+INSERT=20INTO=20guid1=20(guid_field)=20VALUES=20= (gen_uuid_v7());=0A+SELECT=20count(DISTINCT=20guid_field)=20FROM=20= guid1;=0A+=20count=20=0A+-------=0A+=20=20=20=20=202=0A+(1=20row)=0A+=0A=20= --=20clean=20up=0A=20DROP=20TABLE=20guid1,=20guid2=20CASCADE;=0Adiff=20= --git=20a/src/test/regress/sql/uuid.sql=20= b/src/test/regress/sql/uuid.sql=0Aindex=209a8f437c7d..02b8e7f10c=20= 100644=0A---=20a/src/test/regress/sql/uuid.sql=0A+++=20= b/src/test/regress/sql/uuid.sql=0A@@=20-85,5=20+85,11=20@@=20INSERT=20= INTO=20guid1=20(guid_field)=20VALUES=20(gen_random_uuid());=0A=20INSERT=20= INTO=20guid1=20(guid_field)=20VALUES=20(gen_random_uuid());=0A=20SELECT=20= count(DISTINCT=20guid_field)=20FROM=20guid1;=0A=20=0A+--=20generation=20= test=20for=20v7=0A+TRUNCATE=20guid1;=0A+INSERT=20INTO=20guid1=20= (guid_field)=20VALUES=20(gen_uuid_v7());=0A+INSERT=20INTO=20guid1=20= (guid_field)=20VALUES=20(gen_uuid_v7());=0A+SELECT=20count(DISTINCT=20= guid_field)=20FROM=20guid1;=0A+=0A=20--=20clean=20up=0A=20DROP=20TABLE=20= guid1,=20guid2=20CASCADE;=0A--=20=0A2.37.1=20(Apple=20Git-137.1)=0A=0A= --Apple-Mail=_D1CA7478-ADD7-4B8F-AC6C-29793D49C02F Content-Transfer-Encoding: 7bit Content-Type: text/html; charset=us-ascii
--Apple-Mail=_D1CA7478-ADD7-4B8F-AC6C-29793D49C02F-- --Apple-Mail=_8F964B80-60D5-46C0-BE70-8BB7CCA356D1--