Date: Sat, 6 Apr 2024 21:59:38 +0000 (UTC)
From: Sergey Prokhorenko <sergeyprokhorenko@yahoo.com.au>
To: Peter Eisentraut <peter@eisentraut.org>, 
	"Andrey M. Borodin" <x4mmm@yandex-team.ru>
Cc: Aleksander Alekseev <aleksander@timescale.com>, 
	pgsql-hackers mailing list <pgsql-hackers@postgresql.org>, 
	Jelte Fennema-Nio <postgres@jeltef.nl>, 
	=?UTF-8?Q?Przemys=C5=82aw_Sztoch?= <przemyslaw@sztoch.pl>, 
	"David G. Johnston" <david.g.johnston@gmail.com>, 
	Mat Arye <mat@timescaledb.com>, 
	Matthias van de Meent <boekewurm+postgres@gmail.com>, 
	Nikolay Samokhvalov <samokhvalov@gmail.com>, 
	Junwang Zhao <zhjwpku@gmail.com>
Message-ID: <305478845.5279532.1712440778735@mail.yahoo.com>
In-Reply-To: <59729066-7C38-40B9-B8BB-3C04E8BB788D@yandex-team.ru>
References: <CAAhFRxitJv=yoGnXUgeLB_O+M7J2BJAmb5jqAT9gZ3bij3uLDA@mail.gmail.com> <1971811009.2132347.1706599708209@mail.yahoo.com> <72C1E7CB-E2EC-46CF-AD2C-B3180CED885B@yandex-team.ru> <CAEG8a3JUgkY3EMp393kJ+bcye8q=VHfQDTQz7Ci-moNVjhPLZA@mail.gmail.com> <0906F8BA-CA52-4956-AA68-E9193E50DFDF@yandex-team.ru> <10553e4c-6b66-44b9-86a7-80bb1958a767@eisentraut.org> <BFDA918D-1CB0-4980-A31F-C1AC95BE68F6@yandex-team.ru> <d59d7cea-fe4a-411d-a63c-2f871cb68a51@eisentraut.org> <DB00ED53-ABD2-4E73-A746-90086964115B@yandex-team.ru> <ea72ac58-a120-4f51-a1b1-c376b96ec2fd@eisentraut.org> <0C26E3AC-983E-43A4-B39E-270FF87A0464@yandex-team.ru> <CAJ7c6TNTwHJR3QJ=wSwJJyBvEX39wh11W6eBQTZv-6apWJqVrg@mail.gmail.com> <C2C7EAD1-4574-45C2-92F2-96C91D4FCABA@yandex-team.ru> <0b1b5e91-177e-4362-8caf-d227d5a1ae3c@eisentraut.org> <FFDEE01F-7E3B-4DCC-8830-F722307C2412@yandex-team.ru> <2cf9eaf5-057f-4dfa-ae4d-9b23c5339abe@eisentraut.org> <234823B2-D723-4302-8D56-BFE2A62221E8@yandex-team.ru> <7dda76c3-4558-4ad0-a934-09d4751adb4e@eisentraut.org> <59729066-7C38-40B9-B8BB-3C04E8BB788D@yandex-team.ru>
Subject: Re: UUID v7
MIME-Version: 1.0
Content-Type: multipart/alternative; 
	boundary="----=_Part_5279531_373688775.1712440778734"
Content-Length: 7253
Archived-At: <https://www.postgresql.org/message-id/305478845.5279532.1712440778735%40mail.yahoo.com>
Precedence: bulk

------=_Part_5279531_373688775.1712440778734
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

For every complex problem there is an answer that is clear, simple, and wro=
ng. Since the RFC allows microsecond timestamp granularity, the first thing=
 that comes to everyone's mind is to insert microsecond granularity into UU=
IDv7. And if the RFC allowed nanosecond timestamp granularity, then they wo=
uld try to insert nanosecond granularity into UUIDv7.
But I am categorically against abandoning the counter under pressure from t=
he unfounded proposal to replace the counter with microsecond granularity.
1) The RFC specifies millisecond timestamp granularity by default.
2) All advanced UUIDv7 implementations include a counter:=E2=80=A2 for Java=
Script https://www.npmjs.com/package/uuidv7=E2=80=A2 for Rust https://crate=
s.io/crates/uuid7=E2=80=A2 for Go (Golang) https://pkg.go.dev/github.com/go=
frs/uuid#NewV7=E2=80=A2 for Python https://github.com/oittaa/uuid6-python
3) The theoretical performance of generating UUIDv7 without loss of monoton=
icity for microsecond granularity is only 1000 UUIDv7 per millisecond. This=
 is very low and insufficient generation performance! But the actual genera=
tion performance is even worse, since the generation demand is unevenly dis=
tributed within a millisecond. Therefore, a UUIDv7 will not be generated ev=
ery microsecond.
For a counter 18 bits long, with the most significant bit initialized to ze=
ro and the remaining bits initialized to a random number, the actual perfor=
mance of generating a UUIDv7 without loss of monotonicity is between 2 to t=
he power of 17 =3D 131072 UUIDv7 per millisecond (if the random number happ=
ens to be all ones) to 2 to the power of 18 =3D 262144 UUIDv7 per milliseco=
nd (if the random number happens to be all zeros). This is more than enough=
.
4) Microsecond timestamp fraction subtracts 10 bits from random data, which=
 increases the risk of collision. In the counter, almost all bits are initi=
alized with a random number, which reduces the risk of collision.


The only reasonable use of microsecond granularity is when writing to a dat=
abase table in parallel. However, monotonicity in this case can be ensured =
in another way, namely a single UUIDv7 generator per database table, simila=
r to SERIAL (https://postgrespro.com/docs/postgresql/16/datatype-numeric#DA=
TATYPE-SERIAL) in PostgreSQL.
Best regards,
Sergey Prokhorenkosergeyprokhorenko@yahoo.com.au=20

    On Thursday, 4 April 2024 at 09:12:17 pm GMT+3, Andrey M. Borodin <x4mm=
m@yandex-team.ru> wrote: =20
=20
=20
...

At this point we can skip the counter\microseconds entirely, just fill ever=
ything after unix_ts_ms with randomness. It's still a valid UUIDv7, exhibit=
ing much more data locality than UUIDv4. We can adjust this sortability mea=
sures later.


Best regards, Andrey Borodin. =20
------=_Part_5279531_373688775.1712440778734
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<html><head></head><body><div class=3D"ydpad97d2f6yahoo-style-wrap" style=
=3D"font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:16px=
;"><div><div dir=3D"ltr" data-setdir=3D"false"><div><div>For every complex =
problem there is an answer that is clear, simple, and wrong. Since the RFC =
allows microsecond timestamp granularity, the first thing that comes to eve=
ryone's mind is to insert microsecond granularity into UUIDv7. And if the R=
FC allowed nanosecond timestamp granularity, then they would try to insert =
nanosecond granularity into UUIDv7.</div><div><br></div><div>But I am categ=
orically against abandoning the counter under pressure from the unfounded p=
roposal to replace the counter with microsecond granularity.</div><div><br>=
</div><div>1) The RFC specifies millisecond timestamp granularity by defaul=
t.</div><div><br></div><div>2) All advanced UUIDv7 implementations include =
a counter:</div><div>=E2=80=A2 for JavaScript https://www.npmjs.com/package=
/uuidv7</div><div>=E2=80=A2 for Rust https://crates.io/crates/uuid7</div><d=
iv>=E2=80=A2 for Go (Golang) https://pkg.go.dev/github.com/gofrs/uuid#NewV7=
</div><div>=E2=80=A2 for Python https://github.com/oittaa/uuid6-python</div=
><div><br></div><div>3) The theoretical performance of generating UUIDv7 wi=
thout loss of monotonicity for microsecond granularity is only 1000 UUIDv7 =
per millisecond. This is very low and insufficient generation performance! =
But the actual generation performance is even worse, since the generation d=
emand is unevenly distributed within a millisecond. Therefore, a UUIDv7 wil=
l not be generated every microsecond.</div><div><br></div><div>For a counte=
r 18 bits long, with the most significant bit initialized to zero and the r=
emaining bits initialized to a random number, the actual performance of gen=
erating a UUIDv7 without loss of monotonicity is between 2 to the power of =
17 =3D 131072 UUIDv7 per millisecond (if the random number happens to be al=
l ones) to 2 to the power of 18 =3D 262144 UUIDv7 per millisecond (if the r=
andom number happens to be all zeros). This is more than enough.</div><div>=
<br></div><div>4) Microsecond timestamp fraction subtracts 10 bits from ran=
dom data, which increases the risk of collision. In the counter, almost all=
 bits are initialized with a random number, which reduces the risk of colli=
sion.</div><div><br></div><div><br></div><div><br></div><div>The only reaso=
nable use of microsecond granularity is when writing to a database table in=
 parallel. However, monotonicity in this case can be ensured in another way=
, namely a single UUIDv7 generator per database table, similar to SERIAL (h=
ttps://postgrespro.com/docs/postgresql/16/datatype-numeric#DATATYPE-SERIAL)=
 in PostgreSQL.</div></div><br></div><div dir=3D"ltr" data-setdir=3D"false"=
><span>Best regards,</span><br></div><div class=3D"ydpad97d2f6signature">Se=
rgey Prokhorenko</div><div class=3D"ydpad97d2f6signature">sergeyprokhorenko=
@yahoo.com.au</div></div>
        <div><br></div><div><br></div>
       =20
        </div><div id=3D"ydp7dfd7f7byahoo_quoted_2974299074" class=3D"ydp7d=
fd7f7byahoo_quoted">
            <div style=3D"font-family:'Helvetica Neue', Helvetica, Arial, s=
ans-serif;font-size:13px;color:#26282a;">
               =20
                <div>
                        On Thursday, 4 April 2024 at 09:12:17 pm GMT+3, And=
rey M. Borodin &lt;x4mmm@yandex-team.ru&gt; wrote:
                    </div>
                    <div><br></div>
                    <div><br></div>
               =20
               =20
                <div><div dir=3D"ltr"><br clear=3D"none"><div class=3D"ydp7=
dfd7f7byqt2992890460" id=3D"ydp7dfd7f7byqtfd25560">...</div><br clear=3D"no=
ne"><br clear=3D"none">At this point we can skip the counter\microseconds e=
ntirely, just fill everything after unix_ts_ms with randomness. It's still =
a valid UUIDv7, exhibiting much more data locality than UUIDv4. We can adju=
st this sortability measures later.<br clear=3D"none"><br clear=3D"none"><b=
r clear=3D"none">Best regards, Andrey Borodin.</div></div>
            </div>
        </div></body></html>
------=_Part_5279531_373688775.1712440778734--