6 ms·

How many ways are there to sort GUIDs?

93 points by soheilpro 8y ago

akersten 8y ago
I'm struggling to understand the use case. The article offers "keys in an ordered map" or "binary search" - but the idea of a binary search is that the order of the elements is inherently meaningful, like the floors of a building, weights, rankings, etc. GUIDs are meaningless by design, so there must be some underlying property that you're actually interested in searching. And in that case, why not use that property as the key to the collection? Is there another use case here that I'm missing?
- tracker1 8y ago
  in v1 a portion of the ID is based on a timestamp... this is what SQL server indexes on first for performance reasons IIRC.
- Dylan16807 8y ago
  Sometimes all you need is a dictionary, where you take a key and access a value. Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs. Binary search works just fine for this even when the keys are completely meaningless and random. Databases especially have tons of operations where rows have unique meaningless keys that are used to represent relationships. And at the same time a hash table would mean going offline for hours when it resizes, so they use a tree and apply binary search over it to access rows.
  - twic 8y ago
    > Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs. Isn't a hashtable faster than a binary tree for basically all purposes? The only reason to use a tree is if you want to keep the data in order, but the only reason to do that is if the data has a meaningful order!
    - Dylan16807 8y ago
      A hash table doesn't always have the best constant factors, and often wastes more space. Also when you're in a situation where you need GUIDs to guarantee unique keys, and also you use a GUID variant with timestamps, many access patterns will go sort of in order and be far faster on a tree than a hash table. Even though the GUID itself is meaningless.
    - ben509 8y ago
      > Isn't a hashtable faster than a binary tree for basically all purposes? They're heavily used in query optimization because it's great to build a hash table no one else is using. It all comes down to resizing the underlying buckets. If you're doubling each time, that cost amortizes across updates; hence the claim there's a constant cost per update. But while resizing, you have a choice: make the index inaccessible while it's updating, or fuck it, we'll do it live. To do it live, you need to implement a fallback strategy that tries both copies. If your new buckets fill up before the first one has transferred, okay, we'll set up a third, but now our job has become that much more disk intensive. And that's the real problem: on a server, you already have all kinds of processes and jobs running. Extra processes that can chew up hard-to-predict amounts of disk and CPU are more potential causes of instability. Plus, all these jobs need to be recoverable in case of a crash, etc. Tree structures, OTOH, give you very predictable performance because you're only dealing with log N points on a tree. (B-trees just let you use a very big base for that log.)
- paxys 8y ago
  The elements don't have to themselves be meaningful for their ordering to be meaningful.
  - ehsankia 8y ago
    But also, their ordering doesn't need to be meaningful for data structures to work. It doesn't matter which of the 4-5 ordering showcased there you pick for your GUIDs, the binary search will work more or less the same. None of these orderings really have any meaning either.
- mehrdadn 8y ago
  std::map<GUID, ...> requires an ordering without caring about the meaning (or lack thereof) of said ordering.
- timClicks 8y ago
  GUIDs are not meaningless by design, only v4 is.
- cyphar 8y ago
  Binary search is a cheap way of getting an O(log n) .contains() without the additional logic of proper AVL/RedBlack trees (or hashmaps). If you need to check whether an element is a member of a set many times, the once-off O(n log n) setup cost is no worse than any other trees (it is worse than hashmaps but those have other downsides).
- scott113341 8y ago
  Not strictly related to this article or your question, but generating ordered UUIDs can sometimes bring some performance improvements (at least in Postgres) on index reads/writes [1]. [1] https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/ https://www.2ndquadrant.com/en/blog/sequential-uuid-generato...
  - dspillett 8y ago
    Similarly for SQL Server sequential UUIDs can reduce fragmentation, which can save some IO, storage space, and memory load, particularly if the UUID used a table's clustering key (most cluster by their PKs by default). Unfortunately without a bit of a hack NEWSEQUENTIALID() can only be used in TSQL as a default constraint, which can be an irritation. And you are often better off using something else than a UUID for a table's clustering key, to help common range queries and reduce clustering key size, even if it isn't the PK or otherwise particularly unique.
- willvarfar 8y ago
  Often UUIDs are used as keys to things... And these things are often stored in databases... And usually the database puts them into a btree internally, because that's how tables are stored. The moment you have any kind of load on such a table, your performance goes to hell. This is because the inserts are going to happen all over the place, and the way tables are stored definitely prefers appends. So a common word of wisdom is to have an auto-increment primary key, and the uuid indexed! Ugh what a work around. A better way is to discover ULIDs, which are like UUIDs but with the high-bits including a timestamp. This turns inserts into, approximately, appends. Much nicer! https://github.com/ulid/spec https://github.com/ulid/spec is fairly recent, but the 'trick' has been used for years. I've build gazillion-row databases where all the data sources have, independently, used this same high-bits-are-timestamp trick. So even though I didn't see it discussed and called ULID until fairly recently, its a very old and well-known trick in some circles. Once you have ULIDs and you know you have UILDs, a lot of database type tasks become easier because the ID encodes a creation date. I've found myself adding AND id BETWEEN to queries, and using them as a partition key, and using them to DELETE old data etc, and various other admin stuff that the original creators of the table never thought about.
  - marcus_holmes 8y ago
    thank you. That's the first decent rational explanation I've heard for why anyone would sort anything by UUID. I use UUID's for keys, and always sort my results by another field (any other field). If necessary, I add an index for that other field. I guess I'll have to change this strategy if I get to the kind of scale where the append time matters. I hope I get to that scale, it seems like a good problem to have :) I also have another metric asstonne of problems I'll need to solve at that scale. But then, premature optimisation is the devil, so I'm happy I'm not dealing with any of that until I need to :)
    - tempguy9999 8y ago
      Please see my reply above where I disagree, and please watch for willvarfar's response where he's likely to point out that for his case I'm probably wrong. I've got experience with 'large' datasets (it's very relative! Mine have been tiddlers in industry terms!) and I'm happy to pass on anything that may help. Even if you don't scale up, smaller data is likely to improve response times, all else being equal. Anyway, feel free to ask.
tracker1 8y ago
The portions of a UUID/GUID have meaning, there isn't just one version, though the display as a string is relatively consistent. The sorting often will sort on the timestamp portion of UUID v1, there are variants of a GUID (COMB or Combined Guid or Sequencial UUID, etc) that are meant where a portion of the values are sequencial like v1, and the rest is mostly random like v4. SQL is optimized for the portion that is timestamp based when using v1 algorithms, because it results in better indexing performance. It's also why there's a sequencial id option with SQL server. Other systems/databases will sort the raw bytes differently, other languages/platforms will use different arrangements. IIRC MongoDB's JS API actually has like 3-4 different serialization options because of these inconsistencies between languages/platforms. Edit: https://codingsight.com/combguid-generation-of-sql-server-friendly-guid-values-in-net-applications/ https://codingsight.com/combguid-generation-of-sql-server-fr... NOTE: sequencial id's are not quite the same, they're part of the auto insert so that they are ensured sequencial... this is the best indexing option for SQL Server, though a COMB is probably easiest for applications. Other dbms will structure them differently, so best do figure out your serialization strategy based on your db.
- Tornhoof 8y ago
  Here is a more recent post with benchmarks of different GUID algorithms in SQL Server, the author has a different outcome. In his benchmarks about index fragmentation, COMBGuid is not really much better than normal GUIDs. http://microsoftprogrammers.jebarson.com/benchmarking-index-fragmentation-with-popular-sequential-guid-algorithms/ http://microsoftprogrammers.jebarson.com/benchmarking-index-...
  - tracker1 8y ago
    It does look like the sequencial ids (not the combs) does about 50% better overall, and the comb from nhibernate does about 10% better than just random uuids .. this is in terms of paging and indexes.. total time to run the test isn't bad, but that's just the insert time. If you're generating from your application layer and storing in SQL Server, looks like the best option is UuidCreateSequential.
edoceo 8y ago
Check out ULID, lex-sort by time built in. It's super cool
- 4e1a 8y ago
  Or try KSUID [0]. K-Sortable Unique IDs. I'm not affiliated, just easy to code from scratch and sortable. [0] - https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid
amluto 8y ago
I’m not sure whose fault it is that GUID string representations depend on endianness, but I blame Microsoft. I’ve never seen a little endian string GUID anywhere that wasn’t either Windows or a standard that had heavy MS involvement. Hey, MS, the string “0001” is the number one, or the bytes 0,1 in that order. It is not the number two hundred and fifty six!
- Sahhaese 8y ago
  Or even 128 or 8
pdw 8y ago
I never understood why GUIDs were defined as typedef struct _GUID { DWORD Data1; WORD Data2; WORD Data3; BYTE Data4[8]; } GUID; rather than simply typedef struct _GUID { BYTE Data[16]; } GUID; I get that traditional GUIDs have an internal structure, but it's entirely different than the struct (60-bit timestamp, 4-bit version, 16-bit sequence number, 48-bit MAC address).
- aljarry 8y ago
  It's divided exactly as it is in string representation: 4 bytes time_low, 2 bytes time_mid, 2 bytes time_hi_and_version and then: other stuff - 8 bytes.
  - Sharlin 8y ago
    That seems like begging the question. Why it is divided like that in the string representation?
  - pdw 8y ago
    But the string representation has five fields, not four. There might be an interesting story in tracing the history of GUIDs through the ages... I found some 1987 code dealing with UUIDs here: https://stuff.mit.edu/afs/athena/astaff/project/opssrc/quotasrc/src/ncs/nck https://stuff.mit.edu/afs/athena/astaff/project/opssrc/quota... They seem to have originated as a 64-bit "uid"s: struct uid_t { u_long clockh; u_int clockl: 4; u_char extra: 8; u_long node: 20; }; Then the 1987 version seems to have been something like this (with the reserved field ignored in the string representation!) struct uuid_$t { u32 time_high; u16 time_low; u16 reserved; u8 family; u8 host[7]; } And I guess that's pretty close to the current struct...
    - pdw 8y ago
      And to complete the story, I'm guessing that that old struct likely got serialized in the DCE protocol as dword/word/word/bytes, so the struct layout remained unchanged to maintain compatibility, even as the definition of an UUID evolved...
afpx 8y ago
So, a GUID is not actually a UUID? The article refers to endians, but I don't see endian referenced in the UUID spec (rfc4122).
qwerty456127 8y ago
Here is a great related article I can recommend: https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/ https://www.percona.com/blog/2014/12/19/store-uuid-optimized...
deleted 8y ago
[deleted]

93 points by soheilpro 8y ago

I'm struggling to understand the use case. The article offers "keys in an ordered map" or "binary search" - but the idea of a binary search is that the order of the elements is inherently meaningful, like the floors of a building, weights, rankings, etc. GUIDs are meaningless by design, so there must be some underlying property that you're actually interested in searching. And in that case, why not use that property as the key to the collection? Is there another use case here that I'm missing?

tracker1 8y ago
in v1 a portion of the ID is based on a timestamp... this is what SQL server indexes on first for performance reasons IIRC.
Dylan16807 8y ago
Sometimes all you need is a dictionary, where you take a key and access a value. Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs. Binary search works just fine for this even when the keys are completely meaningless and random. Databases especially have tons of operations where rows have unique meaningless keys that are used to represent relationships. And at the same time a hash table would mean going offline for hours when it resizes, so they use a tree and apply binary search over it to access rows.
- twic 8y ago
  > Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs. Isn't a hashtable faster than a binary tree for basically all purposes? The only reason to use a tree is if you want to keep the data in order, but the only reason to do that is if the data has a meaningful order!
  - Dylan16807 8y ago
    A hash table doesn't always have the best constant factors, and often wastes more space. Also when you're in a situation where you need GUIDs to guarantee unique keys, and also you use a GUID variant with timestamps, many access patterns will go sort of in order and be far faster on a tree than a hash table. Even though the GUID itself is meaningless.
  - ben509 8y ago
    > Isn't a hashtable faster than a binary tree for basically all purposes? They're heavily used in query optimization because it's great to build a hash table no one else is using. It all comes down to resizing the underlying buckets. If you're doubling each time, that cost amortizes across updates; hence the claim there's a constant cost per update. But while resizing, you have a choice: make the index inaccessible while it's updating, or fuck it, we'll do it live. To do it live, you need to implement a fallback strategy that tries both copies. If your new buckets fill up before the first one has transferred, okay, we'll set up a third, but now our job has become that much more disk intensive. And that's the real problem: on a server, you already have all kinds of processes and jobs running. Extra processes that can chew up hard-to-predict amounts of disk and CPU are more potential causes of instability. Plus, all these jobs need to be recoverable in case of a crash, etc. Tree structures, OTOH, give you very predictable performance because you're only dealing with log N points on a tree. (B-trees just let you use a very big base for that log.)
paxys 8y ago
The elements don't have to themselves be meaningful for their ordering to be meaningful.
- ehsankia 8y ago
  But also, their ordering doesn't need to be meaningful for data structures to work. It doesn't matter which of the 4-5 ordering showcased there you pick for your GUIDs, the binary search will work more or less the same. None of these orderings really have any meaning either.
mehrdadn 8y ago
std::map<GUID, ...> requires an ordering without caring about the meaning (or lack thereof) of said ordering.
timClicks 8y ago
GUIDs are not meaningless by design, only v4 is.
cyphar 8y ago
Binary search is a cheap way of getting an O(log n) .contains() without the additional logic of proper AVL/RedBlack trees (or hashmaps). If you need to check whether an element is a member of a set many times, the once-off O(n log n) setup cost is no worse than any other trees (it is worse than hashmaps but those have other downsides).
scott113341 8y ago
Not strictly related to this article or your question, but generating ordered UUIDs can sometimes bring some performance improvements (at least in Postgres) on index reads/writes [1]. [1] https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/ https://www.2ndquadrant.com/en/blog/sequential-uuid-generato...
- dspillett 8y ago
  Similarly for SQL Server sequential UUIDs can reduce fragmentation, which can save some IO, storage space, and memory load, particularly if the UUID used a table's clustering key (most cluster by their PKs by default). Unfortunately without a bit of a hack NEWSEQUENTIALID() can only be used in TSQL as a default constraint, which can be an irritation. And you are often better off using something else than a UUID for a table's clustering key, to help common range queries and reduce clustering key size, even if it isn't the PK or otherwise particularly unique.
willvarfar 8y ago
Often UUIDs are used as keys to things... And these things are often stored in databases... And usually the database puts them into a btree internally, because that's how tables are stored. The moment you have any kind of load on such a table, your performance goes to hell. This is because the inserts are going to happen all over the place, and the way tables are stored definitely prefers appends. So a common word of wisdom is to have an auto-increment primary key, and the uuid indexed! Ugh what a work around. A better way is to discover ULIDs, which are like UUIDs but with the high-bits including a timestamp. This turns inserts into, approximately, appends. Much nicer! https://github.com/ulid/spec https://github.com/ulid/spec is fairly recent, but the 'trick' has been used for years. I've build gazillion-row databases where all the data sources have, independently, used this same high-bits-are-timestamp trick. So even though I didn't see it discussed and called ULID until fairly recently, its a very old and well-known trick in some circles. Once you have ULIDs and you know you have UILDs, a lot of database type tasks become easier because the ID encodes a creation date. I've found myself adding AND id BETWEEN to queries, and using them as a partition key, and using them to DELETE old data etc, and various other admin stuff that the original creators of the table never thought about.
- marcus_holmes 8y ago
  thank you. That's the first decent rational explanation I've heard for why anyone would sort anything by UUID. I use UUID's for keys, and always sort my results by another field (any other field). If necessary, I add an index for that other field. I guess I'll have to change this strategy if I get to the kind of scale where the append time matters. I hope I get to that scale, it seems like a good problem to have :) I also have another metric asstonne of problems I'll need to solve at that scale. But then, premature optimisation is the devil, so I'm happy I'm not dealing with any of that until I need to :)
  - tempguy9999 8y ago
    Please see my reply above where I disagree, and please watch for willvarfar's response where he's likely to point out that for his case I'm probably wrong. I've got experience with 'large' datasets (it's very relative! Mine have been tiddlers in industry terms!) and I'm happy to pass on anything that may help. Even if you don't scale up, smaller data is likely to improve response times, all else being equal. Anyway, feel free to ask.

tracker1 8y ago

The portions of a UUID/GUID have meaning, there isn't just one version, though the display as a string is relatively consistent. The sorting often will sort on the timestamp portion of UUID v1, there are variants of a GUID (COMB or Combined Guid or Sequencial UUID, etc) that are meant where a portion of the values are sequencial like v1, and the rest is mostly random like v4. SQL is optimized for the portion that is timestamp based when using v1 algorithms, because it results in better indexing performance. It's also why there's a sequencial id option with SQL server. Other systems/databases will sort the raw bytes differently, other languages/platforms will use different arrangements. IIRC MongoDB's JS API actually has like 3-4 different serialization options because of these inconsistencies between languages/platforms. Edit: https://codingsight.com/combguid-generation-of-sql-server-friendly-guid-values-in-net-applications/ https://codingsight.com/combguid-generation-of-sql-server-fr... NOTE: sequencial id's are not quite the same, they're part of the auto insert so that they are ensured sequencial... this is the best indexing option for SQL Server, though a COMB is probably easiest for applications. Other dbms will structure them differently, so best do figure out your serialization strategy based on your db.

Tornhoof 8y ago
Here is a more recent post with benchmarks of different GUID algorithms in SQL Server, the author has a different outcome. In his benchmarks about index fragmentation, COMBGuid is not really much better than normal GUIDs. http://microsoftprogrammers.jebarson.com/benchmarking-index-fragmentation-with-popular-sequential-guid-algorithms/ http://microsoftprogrammers.jebarson.com/benchmarking-index-...
- tracker1 8y ago
  It does look like the sequencial ids (not the combs) does about 50% better overall, and the comb from nhibernate does about 10% better than just random uuids .. this is in terms of paging and indexes.. total time to run the test isn't bad, but that's just the insert time. If you're generating from your application layer and storing in SQL Server, looks like the best option is UuidCreateSequential.

edoceo 8y ago

Check out ULID, lex-sort by time built in. It's super cool

4e1a 8y ago
Or try KSUID [0]. K-Sortable Unique IDs. I'm not affiliated, just easy to code from scratch and sortable. [0] - https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid

amluto 8y ago

I’m not sure whose fault it is that GUID string representations depend on endianness, but I blame Microsoft. I’ve never seen a little endian string GUID anywhere that wasn’t either Windows or a standard that had heavy MS involvement. Hey, MS, the string “0001” is the number one, or the bytes 0,1 in that order. It is not the number two hundred and fifty six!

Sahhaese 8y ago
Or even 128 or 8

pdw 8y ago

I never understood why GUIDs were defined as typedef struct _GUID { DWORD Data1; WORD Data2; WORD Data3; BYTE Data4[8]; } GUID; rather than simply typedef struct _GUID { BYTE Data[16]; } GUID; I get that traditional GUIDs have an internal structure, but it's entirely different than the struct (60-bit timestamp, 4-bit version, 16-bit sequence number, 48-bit MAC address).

aljarry 8y ago
It's divided exactly as it is in string representation: 4 bytes time_low, 2 bytes time_mid, 2 bytes time_hi_and_version and then: other stuff - 8 bytes.
- Sharlin 8y ago
  That seems like begging the question. Why it is divided like that in the string representation?
- pdw 8y ago
  But the string representation has five fields, not four. There might be an interesting story in tracing the history of GUIDs through the ages... I found some 1987 code dealing with UUIDs here: https://stuff.mit.edu/afs/athena/astaff/project/opssrc/quotasrc/src/ncs/nck https://stuff.mit.edu/afs/athena/astaff/project/opssrc/quota... They seem to have originated as a 64-bit "uid"s: struct uid_t { u_long clockh; u_int clockl: 4; u_char extra: 8; u_long node: 20; }; Then the 1987 version seems to have been something like this (with the reserved field ignored in the string representation!) struct uuid_$t { u32 time_high; u16 time_low; u16 reserved; u8 family; u8 host[7]; } And I guess that's pretty close to the current struct...
  - pdw 8y ago
    And to complete the story, I'm guessing that that old struct likely got serialized in the DCE protocol as dword/word/word/bytes, so the struct layout remained unchanged to maintain compatibility, even as the definition of an UUID evolved...

afpx 8y ago

So, a GUID is not actually a UUID? The article refers to endians, but I don't see endian referenced in the UUID spec (rfc4122).

qwerty456127 8y ago

Here is a great related article I can recommend: https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/ https://www.percona.com/blog/2014/12/19/store-uuid-optimized...

deleted 8y ago

[deleted]