Patch for UUID datatype (beta)

Gevik Babakhani wrote:

- new_guid() function is supported. This function is based on V4 random
uuid value. It generated 16 random bytes with uuid 'variant' and
'version'. It is not guaranteed to produce unique values

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

Regards,
Andreas

On Mon, 2006-09-18 at 09:21 +0200, Andreas Pflug wrote:

Gevik Babakhani wrote:

- new_guid() function is supported. This function is based on V4 random
uuid value. It generated 16 random bytes with uuid 'variant' and
'version'. It is not guaranteed to produce unique values

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

uniqueness is never a guaranteed. that is according to the RFC docs.
However the new_guid() generates a random value in the range of 256^256.
The random value is again based on the PG's randomizer which is a very
good one.

uniqueness is never a guaranteed in the sense that there is a tiny
chance someone of the other side of the planet might generate the same
guid. Or if you set your PC's clock back to the past (1981) you have a
tiny chance to generate a same guid twice.

I am running a test that is going on for the past two days, in has
generated over 14 million guids with new_guid() and yet no
duplicates :)

Regards,
Gevik

Gevik,

uniqueness is never a guaranteed. that is according to the RFC docs.

uniqueness is never a guaranteed in the sense that there is a tiny
chance someone of the other side of the planet might generate the same
guid.

As much as I learned, it is recommended to give information about "grade of
uniqueness". I think it would be a valuable information, which information
your UUID-generator takes into account, and what the "grade of uniqueness"
is.

(I know of the Windows UUID, which takes the MAC-Address of the included
Ethernet-Card into it's calculation, which may be guaranteed to be unique)

Some more questions about UUIDs and your patch:

a) compatibility of UUIDs -> I have generated a lot of UUIDs via the WIN32
provided function (for the unix-only-people: Windows uses UUIDs all around
its registry, software IDs and on and on). How unique are those UUIDs when
mixed with "your" UUIDs ?

b) I read some time ago about the problems with UUIDs as primary keys in
contrast to serials: serials get produced in ascending order; and often data
which was produced in one timespan is also connected semantically. "near
serial values" are also local within a btree-index; but UUIDs generated in
"near times" are usually spread around the possible bitranges.
(example for sequence of serials: 1 - 2 - 3 - 4 - 5 - 6
example for sequence of UUIDs : 1 - 999919281921843191 - 782 -
18291831912318971231)
that is supposed to affect the locality of the index, and from that also the
performance of the system.

I do not know how valid this information is; so I am asking you for your
feedback; especially since you put a lot of thoughts into this UUID patch.
Maybe you took allready care of this situation when constructing the index
operators?

Thanks

Harald

--
GHUM Harald Massa
persuadere et programmare
Harald Armin Massa
Reinsburgstraße 202b
70197 Stuttgart
0173/9409607
-
Let's set so double the killer delete select all.

On Mon, 2006-09-18 at 11:11 +0200, Harald Armin Massa wrote:

Gevik,

uniqueness is never a guaranteed. that is according to the RFC docs.

uniqueness is never a guaranteed in the sense that there is a tiny
chance someone of the other side of the planet might generate the

same

guid.

As much as I learned, it is recommended to give information about
"grade of uniqueness". I think it would be a valuable information,
which information your UUID-generator takes into account, and what the
"grade of uniqueness" is.

(I know of the Windows UUID, which takes the MAC-Address of the
included Ethernet-Card into it's calculation, which may be guaranteed
to be unique)

Some more questions about UUIDs and your patch:

a) compatibility of UUIDs -> I have generated a lot of UUIDs via the
WIN32 provided function (for the unix-only-people: Windows uses UUIDs
all around its registry, software IDs and on and on). How unique are
those UUIDs when mixed with "your" UUIDs ?

The new_guid() generates a random guid in the range of 256^256 which is
3.231700607131100730071487668867e+616 (easy to imagine) using PG's
randomizer. I wonder how often someone could actually generate a
duplicate guid in this range. This also goes for the MS version of the
guid. It uses the MAC address and a timespamp but what happens if by
chance your PC's clock is set in the past!

b) I read some time ago about the problems with UUIDs as primary keys
in contrast to serials: serials get produced in ascending order; and
often data which was produced in one timespan is also connected
semantically. "near serial values" are also local within a
btree-index; but UUIDs generated in "near times" are usually spread
around the possible bitranges.
(example for sequence of serials: 1 - 2 - 3 - 4 - 5 - 6
example for sequence of UUIDs : 1 - 999919281921843191 - 782 -
18291831912318971231)
that is supposed to affect the locality of the index, and from that
also the performance of the system.

I do not know how valid this information is; so I am asking you for
your feedback; especially since you put a lot of thoughts into this
UUID patch. Maybe you took allready care of this situation when
constructing the index operators?

I am running many test regarding indexing of the uuid datatype with
large amount of records. But the performance test is still limited to
hardware capacity

Thank you.

Andreas Pflug <pgadmin@pse-consulting.de> writes:

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

Anyone who thinks UUIDs are guaranteed unique has been drinking too much
of the kool-aid. They're at best probably unique. Some generator
algorithms might make it more probable than others, but you simply
cannot "guarantee" it for UUIDs generated on noncommunicating machines.

One of the big reasons that I'm hesitant to put a UUID generation
function into core is the knowledge that none of them are or can be
perfect ... so people might need different ones depending on local
conditions. I'm inclined to think that a reasonable setup would put
the datatype (with input, output, comparison and indexing support)
into core, but provide a generation function as a contrib module,
making it easily replaceable.

regards, tom lane

Am Montag, 18. September 2006 09:21 schrieb Andreas Pflug:

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

There are several such algorithms, which is part of the problem. If someone
could sort that out, we might get somewhere.

--
Peter Eisentraut
http://developer.postgresql.org/~petere/

Completely agreed. I can remove the function from the patch. The
temptation was just too high not to include the new_guid() in the
patch :)

Anyone who thinks UUIDs are guaranteed unique has been drinking too much
of the kool-aid.

Identifier uniqueness considerations:
This document specifies three algorithms to generate UUIDs: the
first leverages the unique values of 802 MAC addresses to
guarantee uniqueness, the second uses pseudo-random number
generators, and the third uses cryptographic hashing and
application-provided text strings. As a result, the UUIDs
generated according to the mechanisms here will be unique from all
other UUIDs that have been or will be assigned.

That is a quote from the ftp://ftp.rfc-editor.org/in-notes/rfc4122.txt

And to quote ITU-T
"""
If generated according to one of the mechanisms defined in ITU-T Rec. X.667
| ISO/IEC 9834-8 <http://fpweb/ITU-T/studygroups/com17/oid.html&gt;, a UUID is
either guaranteed to be different from all other UUIDs generated before 3603
A.D., or is extremely likely to be different (depending on the mechanism
chosen). The UUID generation algorithm specified in this standard supports
very high allocation rates: 10 million per second per machine if necessary,
so UUIDs can also be used as transaction IDs.
"""

They also talk about a "guaranteed differentness" - and as much as I
understand, they are Unique as long as the MAC-Adresses of the Network-Cards
are unique, and fall back to "extremly likely" when there is no network card
present.

I would really like PostgreSQL to include an uuid-generation function
crafted along the recommendations in rfc4122 or ISO/IEC 9834-8; so those
UUIDs have a "ISO/IEC-defined uniqueness" or at least a "ISO/IEC-defined
extreme likelyness to be unique"

As of now there are at least 3 implementations for UUID creation for
PostgreSQL in the wild; as much as I understand is that "UUIDs created by
the same algorithm" are much more likely to be unique to each other then
UUIDs created by different algorithms.

Harald

--
GHUM Harald Massa
persuadere et programmare
Harald Armin Massa
Reinsburgstraße 202b
70197 Stuttgart
0173/9409607
-
Let's set so double the killer delete select all.

On Mon, Sep 18, 2006 at 05:29:34PM +0200, Harald Armin Massa wrote:

I would really like PostgreSQL to include an uuid-generation function
crafted along the recommendations in rfc4122 or ISO/IEC 9834-8; so those
UUIDs have a "ISO/IEC-defined uniqueness" or at least a "ISO/IEC-defined
extreme likelyness to be unique"

The code to get things like the MAC address is going to be a pile of
very OS specific code, which I really don't think is in the realm of
code postgresql wants to maintain. The easier and better solution is to
include a module in contrib (at best) that calls some standard
cross-platform library to do the job.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

"Harald Armin Massa" <haraldarminmassa@gmail.com> writes:

They also talk about a "guaranteed differentness" - and as much as I
understand, they are Unique as long as the MAC-Adresses of the Network-Cards
are unique, and fall back to "extremly likely" when there is no network card
present.

MAC addresses are not guaranteed unique (heck, on Apple machines they're
user-assignable, and I think you can change 'em on Linux too). Another
unrelated-to-reality assumption in the above claim is that the local
system clock is always accurate (is never, say, set backwards).

You can have a reasonably strong probability that UUIDs generated per spec
within a single well-run network are unique, but that's about as far as
I'd care to believe it.

regards, tom lane

On Mon, Sep 18, 2006 at 10:33:22AM -0400, Tom Lane wrote:

Andreas Pflug <pgadmin@pse-consulting.de> writes:

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

Anyone who thinks UUIDs are guaranteed unique has been drinking too much
of the kool-aid. They're at best probably unique. Some generator
algorithms might make it more probable than others, but you simply
cannot "guarantee" it for UUIDs generated on noncommunicating machines.

The versions that include a MAC address, time, and serial number for
the machine come pretty close, presuming that the user has not
overwritten the MAC address with something else. It's unique at
manufacturing time. If the generation is performed from a library
with the same state, on the same machine, on the off chance that you
do request multiple generations at the same exact time (from my
experience, this is already unlikely) the serial number should be
bumped for that time.

So yeah - if you set your MAC address, or if your machine time is ever
set back, or if you assume a serial number of 0 each time (generation
routine isn't shared among processes on the system), you can get overlap.
All of these can be controlled, making it possible to eliminate overlap.

One of the big reasons that I'm hesitant to put a UUID generation
function into core is the knowledge that none of them are or can be
perfect ... so people might need different ones depending on local
conditions. I'm inclined to think that a reasonable setup would put
the datatype (with input, output, comparison and indexing support)
into core, but provide a generation function as a contrib module,
making it easily replaceable.

I have UUID generation in core in my current implementation. In the
last year that I've been using it, I have already chosen twice to
generate UUIDs from my calling program. I find it faster, as it avoids
have to call out to PostgreSQL twice. Once to generate the UUID, and
once to insert the row using it. I have no strong need for UUID
generation to be in core, and believe there does exist strong reasons
not to. Performance is better when not in core. Portability of
PostgreSQL is better when not in core. Ability to control how UUID is
defined is better when not in control.

The only thing an in-core version provides is convenience for those
that do not have easy access to a UUID generation library. I don't
care for that convenience.

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

If you're going to yank it, please at least include a generator in
contrib.

Personally, I'd like to see at least some kind of generator in core,
with appropriate info/disclaimers in the docs. A simple random-number
generator is probably the best way to go in that regard. I think that
most people know that UUID generation isn't 100.00000% perfect.

BTW, at a former company we used SHA1s to identify files that had been
uploaded. We were wondering on the odds of 2 different files hashing to
the same value and found some statistical comparisons of probabilities.
I don't recall the details, but the odds of duplicating a SHA1 (1 in
2^160) are so insanely small that it's hard to find anything in the
physical world that compares. To duplicate random 256^256 numbers you'd
probably have to search until the heat-death of the universe.

On Mon, Sep 18, 2006 at 05:14:22PM +0200, Gevik Babakhani wrote:

Completely agreed. I can remove the function from the patch. The
temptation was just too high not to include the new_guid() in the
patch :)

On Mon, 2006-09-18 at 10:33 -0400, Tom Lane wrote:

Andreas Pflug <pgadmin@pse-consulting.de> writes:

Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
there's a commonly accepted algorithm providing this.

Anyone who thinks UUIDs are guaranteed unique has been drinking too much
of the kool-aid. They're at best probably unique. Some generator
algorithms might make it more probable than others, but you simply
cannot "guarantee" it for UUIDs generated on noncommunicating machines.

One of the big reasons that I'm hesitant to put a UUID generation
function into core is the knowledge that none of them are or can be
perfect ... so people might need different ones depending on local
conditions. I'm inclined to think that a reasonable setup would put
the datatype (with input, output, comparison and indexing support)
into core, but provide a generation function as a contrib module,
making it easily replaceable.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

--
Jim Nasby jimn@enterprisedb.com
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

On Mon, Sep 18, 2006 at 04:00:22PM -0500, Jim C. Nasby wrote:

BTW, at a former company we used SHA1s to identify files that had been
uploaded. We were wondering on the odds of 2 different files hashing to
the same value and found some statistical comparisons of probabilities.
I don't recall the details, but the odds of duplicating a SHA1 (1 in
2^160) are so insanely small that it's hard to find anything in the
physical world that compares. To duplicate random 256^256 numbers you'd
probably have to search until the heat-death of the universe.

The birthday paradox gives you about 2^80 (about 10^24) files before a
SHA1 match, which is huge enough as it is. AIUI a UUID is only 2^128
bits so that would make 2^64 (about 10^19) random strings before you
get a duplicate. Embed the time in there and the chance becomes
*really* small, because then you have to get it in the same second.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

On Mon, Sep 18, 2006 at 12:23:16PM -0400, mark@mark.mielke.cc wrote:

I have UUID generation in core in my current implementation. In the
last year that I've been using it, I have already chosen twice to
generate UUIDs from my calling program. I find it faster, as it avoids
have to call out to PostgreSQL twice. Once to generate the UUID, and
once to insert the row using it. I have no strong need for UUID
generation to be in core, and believe there does exist strong reasons
not to. Performance is better when not in core. Portability of
PostgreSQL is better when not in core. Ability to control how UUID is
defined is better when not in control.

That's kinda short-sighted. You're assuming that the only place you'll
want to generate UUIDs is outside the database. What about a stored
procedure that's adding data to the database? How about populating a
table via a SELECT INTO? There's any number of cases where you'd want to
generate a UUID inside the database.

The only thing an in-core version provides is convenience for those
that do not have easy access to a UUID generation library. I don't
care for that convenience.

It's not about access to a library, it's about how do you get to that
library from inside the database, which may not be very easy.

You may not care for that convenience, but I certainly would.
--
Jim Nasby jimn@enterprisedb.com
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

On Mon, 2006-09-18 at 16:00 -0500, Jim C. Nasby wrote:

BTW, at a former company we used SHA1s to identify files that had been
uploaded. We were wondering on the odds of 2 different files hashing to
the same value and found some statistical comparisons of probabilities.
I don't recall the details, but the odds of duplicating a SHA1 (1 in
2^160) are so insanely small that it's hard to find anything in the
physical world that compares. To duplicate random 256^256 numbers you'd
probably have to search until the heat-death of the universe.

That assumes you have good random data. Usually there is some kind of
tradeoff between the randomness and the performance. If you
read /dev/random each time, that eliminates some applications that need
to generate UUIDs very quickly. If you use pseudorandom data, you are
vulnerable in the case a clock is set back or the data repeats.

Regards,
Jeff Davis

If you have trouble with duplicate OIDs
Please use patch-0.2 for testing. I have changed the OIDs to 5000 range.

You can download it from:
http://www.truesoftware.net/pgsql/uuid/patch-0.2/

On Mon, Sep 18, 2006 at 04:17:50PM -0500, Jim C. Nasby wrote:

On Mon, Sep 18, 2006 at 12:23:16PM -0400, mark@mark.mielke.cc wrote:

I have UUID generation in core in my current implementation. In the
last year that I've been using it, I have already chosen twice to
generate UUIDs from my calling program. I find it faster, as it avoids
have to call out to PostgreSQL twice. Once to generate the UUID, and
once to insert the row using it. I have no strong need for UUID
generation to be in core, and believe there does exist strong reasons
not to. Performance is better when not in core. Portability of
PostgreSQL is better when not in core. Ability to control how UUID is
defined is better when not in control.

That's kinda short-sighted. You're assuming that the only place you'll
want to generate UUIDs is outside the database. What about a stored
procedure that's adding data to the database? How about populating a
table via a SELECT INTO? There's any number of cases where you'd want to
generate a UUID inside the database.

contrib module.

The only thing an in-core version provides is convenience for those
that do not have easy access to a UUID generation library. I don't
care for that convenience.

It's not about access to a library, it's about how do you get to that
library from inside the database, which may not be very easy.
You may not care for that convenience, but I certainly would.

Then load the contrib module. I do both. I'd happily reduce my contrib
module to be based upon a built-in UUID type within PostgreSQL, providing
the necessary UUID generation routines.

I would not use a 100% random number generator for a UUID value as was
suggested. I prefer inserting the MAC address and the time, to at
least allow me to control if a collision is possible. This is not easy
to do using a few lines of C code. I'd rather have a UUID type in core
with no generation routine, than no UUID type in core because the code
is too complicated to maintain, or not portable enough.

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:

I would not use a 100% random number generator for a UUID value as was
suggested. I prefer inserting the MAC address and the time, to at
least allow me to control if a collision is possible. This is not easy
to do using a few lines of C code. I'd rather have a UUID type in core
with no generation routine, than no UUID type in core because the code
is too complicated to maintain, or not portable enough.

As others have mentioned, using MAC address doesn't remove the
possibility of a collision.

Maybe a good compromise that would allow a generator function to go into
the backend would be to combine the current time with a random number.
That will ensure that you won't get a dupe, so long as your clock never
runs backwards.
--
Jim Nasby jimn@enterprisedb.com
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

As others have mentioned, using MAC address doesn't remove the
possibility of a collision.

Maybe a good compromise that would allow a generator function to go into
the backend would be to combine the current time with a random number.
That will ensure that you won't get a dupe, so long as your clock never
runs backwards.

I think that is a reasonable solution. I just wonder if there is a cross
platform way to get the MAC address for all OS we support.