6 ms·

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

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

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.