Hacker News Reader

Comment by mvitorino | Hacker News Reader

The problem is that most uuids are generated in a way that, when sorted alphabetically as strings, would have a random order.

Example: t0: 7458e3a9-716b-4352-b2e4-b5b67d0c089b t1: 4d8d753c-1777-439d-8725-b093b1bd8430

Using this as a PK in any relational database will mean the rows are stored in the clustered index order, which causes extreme fragmentation because the db engine constantly has to find "holes" in the data pages to insert more recent records instead of adding those at the bottom of the table as would happen with any continuously increasing key.

View on HN

This is a non-issue. Most db engines just append new data rows at the end of the data table and assign an internal row ID for it. The keys (UUID in this case) are stored in the separate index pages using B+ tree, which searches random key (UUID) or sequentially incremented key equally well.

UUID key is a problem only if your main query is a range query on the PK of a clustered indexed table. If your main query is a range query, you should pick something that can be sorted in the range anyway.

Not the case with MS SQL Server for example (and there are probably several others). Physical row ordering (at least up to 2008 edition as far as I can recall) coincides with clustered index.

A lot of times when a UUID is used, it's not generated in the db, such as when you need to generate guaranteed unique IDs client side. Also 4 bytes vs 16 is not "equally well" in terms of performance. Note that the the diagram linked at the root of this thread is encoding uuids as strings which means 32-36 bytes instead of 16.

Actually only postgresql does it this way (by storing data in the heap and not in the primary index). Mysql(innodb),mssql,oracle uses the store the row in the primary-key.

Edit: I'm ~wrong, see below.

Only Innodb does it by default. The others use heap table by default.

MSSQL allows clustered indexed table as an option to order the physical storage of rows. Oracle has index-organized table as an option.

Edit: They don't use clustered indexed table by default because record insertion is very expensive since clustered index forces the table to store the records contiguously in the index's order. Also Innodb is not truely clustered indexed. It only stores records contiguously for one page at the B+ Tree leaf level. Records in different pages are scattered all over even if the index values are sequential.

It's pretty variable, but Postgres definitely is not the only one that does it that way (or even close).

I don't believe that the Primary Key affects the physical ordering of records in PostgreSQL.

Primary Key is implemented as a unique index coupled with a not null constraint. It's essentially syntactic sugar.

To elaborate, even if you do call CLUSTER[1] to enforce a physical ordering, the primary key is not the default (there is no default).

1. http://www.postgresql.org/docs/9.5/static/sql-cluster.html

That would be true except for that fact that database designers know this, and offer a way to generate sequential GUID's; so it's actually not a problem for that reason. The only real downside is performance, an int key performs better.

Every sequential GUID generation feature provides guarantees only per session. In other words, when you bring your database down to upgrade or patch it and then bring it back up, your GUID sequence starts over again at some arbitrary value which is likely to overlap with your existing GUIDs.

> your GUID sequence starts over again at some arbitrary value which is likely to overlap with your existing GUIDs.

I don't believe that's true. You're right that they start the session over, but it'll still be a fresh sequence that doesn't overlap anything generated in the past.

> an int key performs better.

A UUID is a 128-bit integer. That people do not store, generate, or interact with them that way is the bug.

I'd kill for a 128-bit architecture so a UUID compare would be a single instruction, and it's too bad consensus is that we don't really need it.

An int is either 4 or 8 bytes, it's still going to perform better no matter how you treat the GUID.

edit: bytes

I hope you mean bytes. On a 128bit architecture that would be a single instruction compare, just like a 32 or 64 bit compare. Performance would be roughly the same (minus maybe a cache miss because you blew it out with your fat ints).

> An int is either 4 or 8 bits

This perfectly summarizes the bitwise-innumeracy of the argument against UUIDs. Even without 128 bit word sizes, most UUIDs are going to be non-matches in their lower bits, assuming a random distribution. There's no computational efficiency gained in the vastly wide critical path here.

> most UUIDs are going to be non-matches in their lower bits, assuming a random distribution

But you can't assume a random distribution because anyone using UUID's for database keys isn't using random UUID's, they're using sequential ones.

Which would still make the low-order quadword not match.

It's a database though, you don't get to control how comparisons are done. Guid's are larger than ints, so using them as keys or joining on them is going to be slightly slower (not that it makes them bad, I'm not against GUID's). Just as using a bigint will be slower than an int.

If I were implementing the uuid type in Postgres and did anything other than `if(unlikely(LO(uuid1) == LO(uuid2)) && unlikely(HI(uuid1) == HI(uuid2)))` I'd consider myself doing the wrong thing, personally. Two 64-bit compares, two flag checks, and a branch, which is about as fast as it's going to get in the absence of a 128-bit architecture.

You could actually vectorize the compares in SSE, I believe (but I stopped writing assembly before SSE existed and don't know much about it at a low level). This is why it's so critical to treat a UUID as an integer instead of a string, and I see a lot of code that does the latter.

While all of that is true, it's really not relevant to a programmer deciding on which to use as a key; he has no control over any of those things.

> I'd kill for a 128-bit architecture so a UUID compare would be a single instruction

Well, there's PCMPESTRI on Intel.

http://www.felixcloutier.com/x86/PCMPESTRI.html

Yeah, I just said this in another comment, but SSE is my weak point; I stopped writing assembly and dealing with this stuff before SSE was even introduced.

That looks basically like what you need, though, yeah. Cool.

A number of scenarios that require UUIDs as keys, involve generation client side where such guarantees may not be available. In my view, UUIDs should not be used unless there is a strong reason for it (such as making keys not guessable). Most people will implement them incorrectly/inefficiently.

So you're saying it's specifically less efficient for a write-heavy tables, correct?

I generally prefer auto-incremented integers, but UUIDs are very useful for client-generated records (like for an app/website that's built for offline usage).

It's also bigger than necessary when a sequence will do. Large PKs mean larger indexes. For very large databases or very high volume every little inefficiency adds up.

As I always say, if we don't split hairs now, we'll be splitting heads later.

I don't understand this... How does the sort order in the index have anything to do with the arrangement of the table? If you build an index over the UUIDs, it's just going to refer to rows in the table by their internal offsets.

Having a sort order is immensely preferable when you're joining multiple sequential rows at once. The optimiser can create a pseudo-partition for your join, and constrain its reads to that. Especially on spinning rust (or I/O constrained systems), you're also reading multiple sequential pages in a stream off disk, which gives a big speed boost compared to random reads.

Without that ordering, the index is 'dumb', and has to find all your rows one by one in its structure. Admittedly it's not as much of an issue for SSDs, but it does still impact performance.

>How does the sort order in the index have anything to do with the arrangement of the table?

If you have a clustered index based upon that column (and in systems that support this it is common for the primary key to be the clustered index for the table) then the physical layout of the data will follow this column.

See http://use-the-index-luke.com/blog/2014-01/unreasonable-defa... as a good run down of the whys and wherefores of clustered indexes.

Reply on news.ycombinator.com