How to maintain insertion order using UUID

Question

On a pet project I started to work with UUIDs. The application is fairly simple, it adds data in a MySQL database with binary(16) primary keys.

To generate PK's I'm using JUG this way :

UUID uuid = Generators.timeBasedGenerator().generate();

Then I convert it to a byte array :

byte[] b = UUIDUtil.asByteArray(uuid);

The problem now is that I have no idea on the insertion order of my rows. If I sort my rows by the ID some recent rows comes before older rows (according to a DATETIME field)

What should I do to be able to keep the insertion order of my rows (for sorting purpose) ?

Illustration of the problem, UUIDs are sorted ASC, I'm expecting created_at being in the same order.

select hex(id), created_at from myTable order by id

+----------------------------------+---------------------+
| hex(id)                          | created_at          |
+----------------------------------+---------------------+
| 0913FF1FC53911E39D8D6F7C246EE143 | 2014-04-16 09:30:50 |
| 09378CB1C53911E39D8DD94CAEA8D23F | 2014-04-16 09:30:50 |
| 094A9F83C53911E39D8DDF087D0ED31A | 2014-04-16 09:30:51 |
| 0CBE40D5C0B711E38172B9CB0C485EE3 | 2014-04-10 15:50:17 |
| 0CBF5247C0B711E3817277CAF5E1D5B5 | 2014-04-10 15:50:17 |
| 0CC03CA9C0B711E381721BA12057F9E2 | 2014-04-10 15:50:17 |
| 0CC14E1BC0B711E381720505D5FFDCD3 | 2014-04-10 15:50:17 |
| 0CC2387DC0B711E38172F9A6B29EB613 | 2014-04-10 15:50:17 |
| 0CC349EFC0B711E381723D1DB8515E3F | 2014-04-10 15:50:17 |
| 0CC43451C0B711E3817257D8AFFD09B8 | 2014-04-10 15:50:17 |
| 0CC545C3C0B711E381729B3CB87CD707 | 2014-04-10 15:50:17 |
| 0CC8C835C0B711E38172CDA11992F9BC | 2014-04-10 15:50:17 |
| 0E33A6B5C08B11E396829782BD5365D2 | 2014-04-10 10:35:22 |
| 0E368CE7C08B11E39682A9F63D5EF0E6 | 2014-04-10 10:35:22 |
| 0E383A99C08B11E396825D6048BFC696 | 2014-04-10 10:35:22 |
| 128DD6C5C53911E39D8D7577DB523A2C | 2014-04-16 09:31:06 |
+----------------------------------+---------------------+

EDIT

Just to clarify, I of course know and am used to auto_increment PK's, I just wanted to see how it was achievable to work without them. (In case it is !)

Pneumoencephalogram

Why not just have integer auto_increment field and use it for default sorting? – Competency

For research purpose I'd like to be completely free from database generated values (so no auto_increment) – Pneumoencephalogram

Can't you just sort by created_at? – Bus

UUIDs aren't designed to be ordered. If you want to select based on insertion order you need to order based on created_by. – Araminta

Why not working with my created_at column but in it's current form it isn't precise enough (there are duplicates) how could I deal with it ? – Pneumoencephalogram

@AlexandreJacob why would you need to have ordered inserts? – Gershon

Ah good question, I want to fetch X rows that come before row id Y ordered by id desc. Now I'm starting to think that I can do otherwise ... – Pneumoencephalogram

@Araminta Update: Fortunately that is no longer true. Versions 6 & 7 were invented to address the need for ordering. See Answer by fabiolimace. – Airla

Answer 1

Today there's a standard, RFC 9562, which describes two new time-based UUID types:

• UUIDv6
• UUIDv7

If you want to create a UUIDv6 by yourself, first generate a UUIDv1 (time-based) and change the byte order this way:

From: aaaaaaaa-bbbb-1ccc-dddd-eeeeeeeeeeee (time-based, v1)
To:   cccbbbba-aaaa-6aaa-dddd-eeeeeeeeeeee (reordered time-based, v6)

a: time lower bits
b: time middle bits
c: time higher bits
d: "clock sequence" (usually random bits)
e: "node ID" (usually the MAC address)

If you want to create a UUIDv7 yourself, first generate a UUIDv4 (fully random) and replace the first 6 bytes with the Unix timestamp in milliseconds, this way:

From: rrrrrrrr-rrrr-4rrr-rrrr-rrrrrrrrrrrr (random-based, v4)
To:   uuuuuuuu-uuuu-7rrr-rrrr-rrrrrrrrrrrr (Unix time-based, v7)

r: random bytes
u: Unix timestamp in milliseconds

If you want a library that already does it, you may use uuid-creator, assuming you are coding in Java. Example:

// Generate a UUIDv6
UUID uuid = UuidCreator.getTimeOrdered();

// Generate a UUIDv7
UUID uuid = UuidCreator.getTimeOrderedEpoch();

If you want a more mature Java library, just update java-uuid-generator and continue using it, as it now implements UUIDv6 and UUIDv7.

If you are coding in PHP, you can use a library from Ben Ramsey. I think it was the first project to implement UUIDv6:

Project on github: https://github.com/ramsey/uuid

---

Disclosure: I'm the main contributor of uuid-creator.

Electrosurgery

Answer 2

Please see this link https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/

Here the author rearranged the UUID to make it sequential, for this he created one MySQL user defined function.

Vilayet

Answer 3

UUIDs that sort nicely

Sorting didn't work in your case, because your call generated a UUIDv1, which has the timestamp in wrong byte order for sorting.

This month, the standard for UUID formats received an update via RFC 9562. It now defines UUID version 7 (specification), which is time ordered, based on Unix Epoch timestamp in millisecond resolution - in a byte order corresponding to string representation. So, UUIDv7 values are sortable by creation date. If you don’t need backward compatibility, this is the recommended version to use.

While standard Java SDK class java.util.UUID does support holding V7 UUIDS, it (currently) does not support generation of such UUIDs.

Using the Java Uuid Generator (JUG) library, you can generate a v7 UUID:

Generators.timeBasedEpochGenerator().generate()

Fantail