How many ways are there to sort GUIDs? How much time do you have?

13 comments

Comments are closed. Login to edit/delete your existing comments

• 

  Henrik Arlinghaus April 26, 2019 7:37 am 0

  collapse this comment copy link to this comment

  I wonder if Platform::Guid is implemented branchless using SSE. So far I always used memcmp, but may try to code a faster SSE implementation.

• 

  Peter Cooper Jr. April 26, 2019 7:47 am 0

  collapse this comment copy link to this comment

  For SQL GUIDs and Footnote 2, I think that sorting it that way means that new sequential Type-1 GUIDs generated by the same server usually (or always?) ends up at the end of the sort? If so, that would mean that if uniqueIdentifier is used as a key, and insertions usually happen on one database server, you usually end up with new inserted records being added to the end of the data structure. I can imagine that would lead to enough improved performance to be worth doing that way. Just a wild guess, though.

  • 

    Dave Bacher April 26, 2019 1:27 pm 0

    collapse this comment copy link to this comment

    I can tell you what they were thinking, but I can’t tell you if the type-1 is coinidental or intentional.
    Pretend that I buy four servers from the same batch, an stage them.  If I do a left to right sort – my index is going to start with the MAC address (which is almost identical) followed by the most constant portion of the clock.  Followed by the most constant part of my counter, followed by the least constant portion of my counter.
    And so once I get to the MAC address bucket, I’ve only discarded 3/4 of the data.
    If I start from the right instead, each digit eliminates 15/16 of the data – and I’ve likely completed by the time I get to the clock value.  I’m sorting the most dynamic part of the time first, so again – I’m eliminating 15/16 at a time there, until I get to the constant part.  I’m then sorting the most dynamic part of the MAC adress first – and so I most likely never make it to the vendor prefix.
    So its about the indexing speed – if I’m pulling sorted records, I want to use the index for an in-order traversal – and so my sort order needs to match the index order, and the index order is selected for speed.

    • 

      David Walker April 29, 2019 10:57 am 0

      collapse this comment copy link to this comment

      MAC addresses are not used any more in generating GUIDs.  That is, type 4 GUIDS (which are returned by SQL and .NET funcitons) don’t use the computer’s MAC address at all.

  • 

    Kalle Niemitalo April 28, 2019 11:33 pm 0

    collapse this comment copy link to this comment

    Newsequentialid (Histrory/Benefits and Implementation) says SQL Server already had its UNIQUEIDENTIFER comparison scheme before they added NEWSEQUENTIALID() in SQL Server 2005 to improve INSERT performance.
    However, MSDN Library for Visual Studio 2008 says that on Windows NT 4.0, UuidCreate used the MAC address (so it presumably generated Type-1 GUIDs) and UuidCreateSequential did not exist. I suspect that the SQL Server function NEWID() may have generated Type-1 GUIDs on NT4 and earlier. In which case it is strange that SQL Server’s UNIQUEIDENTIFER comparison scheme did not already sort time stamps optimally and Microsoft had to implement “some byte scrambling” in NEWSEQUENTIALID().

  • 

    David Walker April 29, 2019 10:55 am 0

    collapse this comment copy link to this comment

    Microsoft SQL has a Newid() function, plus a Newsequentialid() function that definitely will end up sorting “higher” than any other sequential ID that has been generated by the same server since its last reboot.  If you use SQL’s standard sorting, that is.  So yes, you are basically correct, except that newid() is easier to use than newsequentialid() — the latter can only be used in a Default expression for a column type.  It can’t be used anywhere you want (which I thin kis unfortunate).   Guids returned by Newid() will sort randomly.
    (Edited to make a correction at “since its last reboot”.)

    • 

      Michael Ryan April 29, 2019 8:43 pm 0

      collapse this comment copy link to this comment

      You can use a COMB GUID library to generate sequencial Ids in your application…  The sequence may be slightly out of order at the database level, which is the main reason, but much better performing in an index than UUIDv4 spec alone.

• 

  Dave Steckler April 26, 2019 8:07 am 0

  collapse this comment copy link to this comment

  As the dev who wrote the first implemention of UuidCreate for what eventually became Win32, I can add we were indeed incredibly concerned with using the mac address portion of the uuid (guid) for, well, everything. Grouping/sorting on individual network servers was a significant consideration as we pondered whether to adhere the UUID standard of the time, or break it and invent our own. For example, we had all sorts of problems preserving this consistency on machines with other-than-1 network cards. I recall extravagant XOR schemes tossed about conference rooms, and eventually discarded.Side note: Frankly, I hope my original slm(?) checkin is 100% lost to time. It was the first job I was given after switching from SDE-T to SDE. I can only imagine what the code looks like. Egad. Can you imagine giving such a critical task to a brand new, young dev straight out of test? Lol.

  • 

    Wil Wilder Apaza Bustamante April 29, 2019 12:36 am 0

    collapse this comment copy link to this comment

    This comment has been deleted.

• 

  Matthew van Eerde (^_^) April 26, 2019 8:50 am 0

  collapse this comment copy link to this comment

  If you make a bunch of files with GUIDs as their names, File Explorer will sort them using StrCmpLogicalW. This is designed to make “track 9.mp3” < “track 10.mp3” which makes perfect sense, but unfortunately when you apply it to GUIDs you get weird behavior like “{AA4982AA-…” < “{AA26724A-“.

• 

  yuri.v.khan@gmail.com April 26, 2019 12:14 pm 0

  collapse this comment copy link to this comment

  From the title alone (with the “how much time”), I was expecting the answer to be (2^128)!. That’s the total number of ways the set of all GUIDs can be ordered, and if we agree to enumerate them with a constant speed of several billions per second, still takes lots of time.

• 

  Nico Sap April 26, 2019 12:37 pm 0

  collapse this comment copy link to this comment

  I thought a Guid had ( in some cases) a datetime variable to be unique. I was actually hoping in how to use this to my advantage. I noticed sometimes the data is already ordered and I was thinking it could have been by the Guid ( just now).  I found a site that can extract it ( https://www.famkruithof.net/uuid/uuidgen?typeReq=-1 ), they do mention that v4 makes it impossible though. Any input on this?

  Ps. Some algorithms are also described in the UUID standard: https://www.ietf.org/rfc/rfc4122.txt

• 

  Michael Ryan April 29, 2019 8:41 pm 0

  collapse this comment copy link to this comment

  The sorting for SQL Server coincides with the UUID v1 variant.  The default sorting is on the timestamp portion for performance reasons.  The “NEWSEQUENTIALID” is part UUIDv1 (sequential) and part UUIDv4 (random) … The reason is that index performance out of the box works better this way.  Prior to the addition, there was an article and library for a COMB guid generator that was effectively this format.  It has been repeated.The SQL Server variant and sorting probably makes the most sense overall.  As to serialization, there’s a few variants.  MongoDB’s JS library supports like 3-4 serialization options mostly because of the incompatible serializations that are in differing languages/platforms.

  https://codingsight.com/combguid-generation-of-sql-server-friendly-guid-values-in-net-applications/