Is there a mechanism inside of database engines to avoid collisions of non-sequential keys? If so, how does it work?

Question

Say that I create a table that that has a random uuid for a primary key. Is there typically a mechanism inside of the database to gracefully deal with collisions? How does it work?

My mind is picturing something simple like "generate a key and check if it exists, and generate another one if it does exist." But if you have a simple non-sequential key, you could end up in this collision loop for quite some time.

Answer 1

The answer is "no". It's the application responsibility to generate unique IDs using a method appropriate for its requirements and handle duplicate keys as it sees fit. The database cannot decide for you whether you want to generate a new ID or update an existing records (or do something entirely different, like raise an alert).

Even things like IDENTITY and AUTO_INCREMENT are simply shortcuts to sequences, which are subject to wraparounds and subsequent collisions.

Answer 2

Well here I am busting the party....

Your question:

Is there typically a mechanism inside of the database to gracefully deal with collisions? How does it work?

Yes and no (but not in that order).

Let Me Explain

Let's generate a table on SQL Server 2019:

CREATE TABLE [dbo].[Generated_Data_GUID]
(
    [ID]            [int] IDENTITY(1, 1) NOT NULL,
    [GUID]          [uniqueidentifier] NOT NULL,
    [SEQGUID]       [uniqueidentifier] NOT NULL,
    [Data1]         [char](4000) NULL,
    [Data2]         [char](4000) NULL,
    [Data3]         [char](9) NULL,
    [EntryDate]     [datetime2](7) NULL
) ON [PRIMARY]

We'll add some constraints/default values for some of the columns:

ALTER TABLE [dbo].[Generated_Data_GUID] ADD  CONSTRAINT [DF_Generated_Data_GUID_GUID]  DEFAULT(NEWID()) FOR [GUID]
GO
ALTER TABLE [dbo].[Generated_Data_GUID] ADD  CONSTRAINT [DF_Generated_Data_GUID_SEQGUID]  DEFAULT(NEWSEQUENTIALID()) FOR 
[SEQGUID]
GO
ALTER TABLE [dbo].[Generated_Data_GUID] ADD  CONSTRAINT [DF_Generated_Data_GUID_EntryDate]  DEFAULT(GETDATE()) FOR 
[EntryDate]
GO

And then we'll pop some data into the table:

DECLARE @iValue INT

SET @iValue = 1

WHILE @iValue <= 20
BEGIN
    INSERT INTO [dbo].[Generated_Data_GUID]
      (
        [Data1],
        [Data2],
        [Data3]
      )
    VALUES
      (
        CAST(@iValue AS CHAR(5)) + ' ' + REPLICATE('M', 1990) + ' ' + CAST(@iValue AS CHAR(5)),
        CAST(@iValue AS CHAR(5)) + ' ' + REPLICATE('M', 1990) + ' ' + CAST(@iValue AS CHAR(5)),
        CAST(@iValue AS CHAR(5)) + ' ' + REPLICATE('M', 3)
      )
    SET @iValue = @iValue + 1
END

A running version of the above can be found on this db<>fiddle link.

Selecting Some Data

select * from [Generated_Data_GUID];
GO

ID | GUID                                 | SEQGUID                              | Data1                                                                                                | Data2                                                                                                | Data3     | EntryDate                  
-: | :----------------------------------- | :----------------------------------- | :--------------------------------------------------------------------------------------------------- | :--------------------------------------------------------------------------------------------------- | :-------- | :--------------------------
 1 | dc79149e-af08-4647-90cc-61dfbaf04746 | d8446817-b422-ec11-ba42-00163ef319ff | 1     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 1     | 1     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 1     | 1     MMM | 2021-10-01 13:35:43.3800000
 2 | bb80d88d-fbfd-4279-a2a4-6ff000c75d92 | d9446817-b422-ec11-ba42-00163ef319ff | 2     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 2     | 2     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 2     | 2     MMM | 2021-10-01 13:35:43.3800000
 3 | dbe57a01-cb3b-4d62-a110-547c6cc6d900 | da446817-b422-ec11-ba42-00163ef319ff | 3     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 3     | 3     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 3     | 3     MMM | 2021-10-01 13:35:43.3800000
 4 | 106959e5-7195-498e-b83e-e736e5215746 | db446817-b422-ec11-ba42-00163ef319ff | 4     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 4     | 4     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 4     | 4     MMM | 2021-10-01 13:35:43.3800000
 5 | e533ddf4-5ba7-4202-9668-467a767d85f2 | dc446817-b422-ec11-ba42-00163ef319ff | 5     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 5     | 5     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 5     | 5     MMM | 2021-10-01 13:35:43.3800000
 6 | 047a1fff-000f-44cf-9f90-0467decb1603 | dd446817-b422-ec11-ba42-00163ef319ff | 6     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 6     | 6     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 6     | 6     MMM | 2021-10-01 13:35:43.3800000
 7 | 672be672-dbf1-48b3-866f-f220a46580d4 | de446817-b422-ec11-ba42-00163ef319ff | 7     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 7     | 7     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 7     | 7     MMM | 2021-10-01 13:35:43.3800000
 8 | 3397de10-fb4d-457c-86c1-b54ec61725f4 | df446817-b422-ec11-ba42-00163ef319ff | 8     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 8     | 8     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 8     | 8     MMM | 2021-10-01 13:35:43.3800000
 9 | 83e9287c-589d-48a0-a611-22eb8cc33a59 | e0446817-b422-ec11-ba42-00163ef319ff | 9     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 9     | 9     MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 9     | 9     MMM | 2021-10-01 13:35:43.3800000
10 | c3787718-8e5b-433d-b357-ab9cf51e807f | e1446817-b422-ec11-ba42-00163ef319ff | 10    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 10    | 10    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 10    | 10    MMM | 2021-10-01 13:35:43.3800000
11 | c193d49b-9cc4-4f15-9673-563be384a22e | e2446817-b422-ec11-ba42-00163ef319ff | 11    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 11    | 11    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 11    | 11    MMM | 2021-10-01 13:35:43.3800000
12 | f11f8f9f-f586-413e-a969-c0afc63361f7 | e3446817-b422-ec11-ba42-00163ef319ff | 12    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 12    | 12    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 12    | 12    MMM | 2021-10-01 13:35:43.3800000
13 | fc44827a-3b26-452a-ac37-c44526632ffe | e4446817-b422-ec11-ba42-00163ef319ff | 13    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 13    | 13    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 13    | 13    MMM | 2021-10-01 13:35:43.3800000
14 | 45f4c4e2-2186-4743-b9db-69c4b7451e4f | e5446817-b422-ec11-ba42-00163ef319ff | 14    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 14    | 14    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 14    | 14    MMM | 2021-10-01 13:35:43.3800000
15 | 2b611af9-27c4-467c-b28b-2c39039f651b | e6446817-b422-ec11-ba42-00163ef319ff | 15    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 15    | 15    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 15    | 15    MMM | 2021-10-01 13:35:43.3800000
16 | 6b068942-a27e-4d90-95dc-a4aeced6d8ea | e7446817-b422-ec11-ba42-00163ef319ff | 16    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 16    | 16    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 16    | 16    MMM | 2021-10-01 13:35:43.3800000
17 | a82dee5e-3b71-45da-a9fb-48e7c069161a | e8446817-b422-ec11-ba42-00163ef319ff | 17    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 17    | 17    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 17    | 17    MMM | 2021-10-01 13:35:43.3800000
18 | afc2d730-367d-457f-aae6-b7b6626f1ef6 | e9446817-b422-ec11-ba42-00163ef319ff | 18    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 18    | 18    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 18    | 18    MMM | 2021-10-01 13:35:43.3800000
19 | ded29375-bc95-4a16-986d-4fd5c9691973 | ea446817-b422-ec11-ba42-00163ef319ff | 19    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 19    | 19    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 19    | 19    MMM | 2021-10-01 13:35:43.3800000
20 | 0295c91a-8351-4c4e-9c8f-0091872b2814 | eb446817-b422-ec11-ba42-00163ef319ff | 20    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 20    | 20    MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM 20    | 20    MMM | 2021-10-01 13:35:43.3800000

As you can see in the small sample, both random UUIDs and sequential UUIDs didn't collide. You can tell db<>fiddle to generate millions of records, or you can take the example and run on a SQL Server Express edition and see what happens.

You shouldn't observe any collisions.

Explaining Stuff

The first part of your question:

Is there typically a mechanism inside of the database to gracefully deal with collisions?

...is no. There are built-in functions to create sequential UUIDs, but there is no function that gracefully deals with collisions.

However, the second part of your question:

How does it work?

... can be answered via the Wikipedia article on UUIDs: Universally unique identifier.

The implementation of the UUID generation (especially version 4) reduces the need for such a collision detector with probabilities. The probability that the same UUID will be generated is very low. It's actually so low that it can be deemed negligible.

In contrast to version-1 and version-2 UUID's generated using MAC addresses, with version-1 and -2 UUIDs which use randomly generated node ids, hash-based version-3 and version-5 UUIDs, and random version-4 UUIDs, collisions can occur even without implementation problems, albeit with a probability so small that it can normally be ignored

^{Taken from Wikipedia link}

...and...

This number is equivalent to generating 1 billion UUIDs per second for about 85 years. A file containing this many UUIDs, at 16 bytes per UUID, would be about 45 exabytes.

So the solution to generating random, non-collisionable UUIDs is the probability, that this will (nearly) never occur if the correct UUID generator is used.

Answer 3

I think you might be confusing a few different concepts which makes it a little difficult to provide a satisfactory answer, but I'll try my best. Additionally, your mileage may vary on what options are available, or what the "usual case" is, depending on which specific database system you're talking about. My answer is based on my general database knowledge and specific knowledge of Microsoft SQL Server.

A Primary Key constraint defined on a column does not mean it automatically generates a value for that column. Rather, an Identity specification is what is typically used to define when a column is auto-incrementing and resultantly auto-generating. A Primary Key just enforces uniqueness on the column(s) it's defined on.

An Identity specification is generally a numeric data type such that it can be an incremental (or decremental - depending on how you define it) series of values. Note that it doesn't necessarily need to be defined as a contiguous series, as the "increment" value can be a value that generates gaps in the series. E.g. if the increment value is specified as 5, then every new value will be 5 greater than the previous value, and your series of Identities could look something like (5, 10, 15, 20, 25...).

Because an Identity column typically has to be numerical, as mustaccio mentioned, most relational database systems don't offer a way to auto-generate a UUID value, as a column specification. Furthermore, there typically is no mechanism for regenerating one when a collision occurs. Rather the onus of responding to a collision should be handled at the application layer, or at least the responding behavior needs to be defined by the developer somehow.

Going back to my first paragraph about Primary Keys, again their function is to enforce uniqueness. So while a UUID column can have a Primary Key defined on it. All that'll do is prevent a duplicateUUID value from being inserted into such column, typically by throwing an error back to the caller. And again, then it's up to the caller to handle how to respond to this error, which could be by regenerating a new UUID if the developer chooses to.

Finally, to hopefully clarify your comment on mustaccio's answer, most relational database systems do provide functions for manually generating a UUID (sequential and not) and they do leverage an algorithm in the database system's engine to handle collisions when generating a new value. But again, those are functions, and can't be used as auto-generating specifications on a column level. In some database systems, you may be able to hack something together with a user-defined function or leveraging the existing functions, inside of a computed column perhaps. But there is typically not something out-of-the-box, and hacking your own version is likely at risk for edge cases and / or errors.