SQL Server GUID sort algorithm. Why?

Question

Problem with UniqueIdentifiers

We have an existing database which uses uniqueidentifiers extensively (unfortunately!) both as primary keys and some nullable columns of some tables. We came across a situation where some reports that run on these tables sort on these uniqueidentifiers because there is no other column in the table that would give a meaningful sort (isn't that ironic!). The intent was to sort so that it shows the items in the order they were inserted but they were not inserted using NewSequentialId() - hence a waste of time.

Fact about the Sort Algorithm

Anyway, considering SQL Server sorts uniqueidentifiers based on byte groups starting from the ending 5th byte group (6 bytes) and moving towards the 1st byte group (4 bytes) reversing the order on the 3rd byte-group (2 bytes) from right-left to left-right,

My Question

I was curious to know if there is any real life situation that this kind of sort helps at all.

How does SQL Server store the uniqueidentifier internally which might provide insight on why it has this whacky sort algorithm?

Reference:

Alberto Ferrari's discovery of the SQL Server GUID sort

Example

Uniqueidentifiers are sorted as shown below when you use a Order By on a uniqueidentifier column having the below data.

Please note that the below data is sorted ascendingly and highest sort preference is from the 5th byte group towards the 1st byte group (backwards).

-- 1st byte group of 4 bytes sorted in the reverse (left-to-right) order below -- 

01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000

-- 2nd byte group of 2 bytes sorted in the reverse (left-to-right) order below -- 

00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000

-- 3rd byte group of 2 bytes sorted in the reverse (left-to-right) order below -- 

00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000

-- 4th byte group of 2 bytes sorted in the straight (right-to-left) order below -- 

00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000

-- 5th byte group of 6 bytes sorted in the straight (right-to-left) order below -- 

00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000

Code:

Alberto's code extended to denote that sorting is on the bytes and not on the individual bits.

With Test_UIDs As (--                     0 1 2 3  4 5  6 7  8 9  A B C D E F
            Select ID =  1, UID = cast ('00000000-0000-0000-0000-100000000000' as uniqueidentifier)
    Union   Select ID =  2, UID = cast ('00000000-0000-0000-0000-010000000000' as uniqueidentifier)
    Union   Select ID =  3, UID = cast ('00000000-0000-0000-0000-001000000000' as uniqueidentifier)
    Union   Select ID =  4, UID = cast ('00000000-0000-0000-0000-000100000000' as uniqueidentifier)
    Union   Select ID =  5, UID = cast ('00000000-0000-0000-0000-000010000000' as uniqueidentifier)
    Union   Select ID =  6, UID = cast ('00000000-0000-0000-0000-000001000000' as uniqueidentifier)
    Union   Select ID =  7, UID = cast ('00000000-0000-0000-0000-000000100000' as uniqueidentifier)
    Union   Select ID =  8, UID = cast ('00000000-0000-0000-0000-000000010000' as uniqueidentifier)
    Union   Select ID =  9, UID = cast ('00000000-0000-0000-0000-000000001000' as uniqueidentifier)
    Union   Select ID = 10, UID = cast ('00000000-0000-0000-0000-000000000100' as uniqueidentifier)
    Union   Select ID = 11, UID = cast ('00000000-0000-0000-0000-000000000010' as uniqueidentifier)
    Union   Select ID = 12, UID = cast ('00000000-0000-0000-0000-000000000001' as uniqueidentifier)
    Union   Select ID = 13, UID = cast ('00000000-0000-0000-0001-000000000000' as uniqueidentifier)
    Union   Select ID = 14, UID = cast ('00000000-0000-0000-0010-000000000000' as uniqueidentifier)
    Union   Select ID = 15, UID = cast ('00000000-0000-0000-0100-000000000000' as uniqueidentifier)
    Union   Select ID = 16, UID = cast ('00000000-0000-0000-1000-000000000000' as uniqueidentifier)
    Union   Select ID = 17, UID = cast ('00000000-0000-0001-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 18, UID = cast ('00000000-0000-0010-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 19, UID = cast ('00000000-0000-0100-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 20, UID = cast ('00000000-0000-1000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 21, UID = cast ('00000000-0001-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 22, UID = cast ('00000000-0010-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 23, UID = cast ('00000000-0100-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 24, UID = cast ('00000000-1000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 25, UID = cast ('00000001-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 26, UID = cast ('00000010-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 27, UID = cast ('00000100-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 28, UID = cast ('00001000-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 29, UID = cast ('00010000-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 30, UID = cast ('00100000-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 31, UID = cast ('01000000-0000-0000-0000-000000000000' as uniqueidentifier)
    Union   Select ID = 32, UID = cast ('10000000-0000-0000-0000-000000000000' as uniqueidentifier)
)
Select * From Test_UIDs Order By UID, ID

Bondholder

Here's an updated link to the blog referenced in the question: sqlbi.com/blog/alberto/2007/08/31/… – Skillern

Part of your confusion might be that you think that a UUID is a 16-byte blob. In fact it is: 63-bit timestamp, UInt16 sequence, and a 6-byte NodeID (i.e. MAC address). First it sorts by the NodeID, then the clock sequence, and then the timestamp. Gotchas are it also sorts the UInt32 and 2 of the UInt16s as big-endian. Which is why we shift bits around so that it sorts by timestamp first, then clock, then node. – Miguelmiguela

Answer 1

The algorithm is documented by the SQL Server guys here: How are GUIDs compared in SQL Server 2005? I am quoting it here (since it's an old article that may be gone forever in a few years)

In general, equality comparisons make a lot of sense with uniqueidentifier values. However, if you find yourself needing general ordering, then you might be looking at the wrong data type and should consider various integer types instead.

If, after careful thought, you decide to order on a uniqueidentifier column, you might be surprised by what you get back.

Given these two uniqueidentifier values:

@g1= '55666BEE-B3A0-4BF5-81A7-86FF976E763F' @g2 = '8DD5BCA5-6ABE-4F73-B4B7-393AE6BBB849'

Many people think that @g1 is less than @g2, since '55666BEE' is certainly smaller than '8DD5BCA5'. However, this is not how SQL Server 2005 compares uniqueidentifier values.

The comparison is made by looking at byte "groups" right-to-left, and left-to-right within a byte "group". A byte group is what is delimited by the '-' character. More technically, we look at bytes {10 to 15} first, then {8-9}, then {6-7}, then {4-5}, and lastly {0 to 3}.

In this specific example, we would start by comparing '86FF976E763F' with '393AE6BBB849'. Immediately we see that @g2 is indeed greater than @g1.

Note that in .NET languages, Guid values have a different default sort order than in SQL Server. If you find the need to order an array or list of Guid using SQL Server comparison semantics, you can use an array or list of SqlGuid instead, which implements IComparable in a way which is consistent with SQL Server semantics.

Plus, the sort follows byte groups endianness (see here: Globally unique identifier). The groups 10-15 and 8-9 are stored as big endian (corresponding to the Data4 in the wikipedia article), so they are compared as big endian. Other groups are compared using little endian.

Schizoid

Just a note: g1 is bigger! select case when cast('55666BEE-B3A0-4BF5-81A7-86FF976E763F' as uniqueidentifier) > cast('8DD5BCA5-6ABE-4F73-B4B7-393AE6BBB849' as uniqueidentifier) then 1 else 0 end – Hogwash

Answer 2

A special service for those that find that the accepted answer a bit vague. The code speaks for itself; the magical parts are:

System.Guid g
g.ToByteArray();
int[] m_byteOrder = new int[16] // 16 Bytes = 128 Bit 
    {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};


public int Compare(Guid x, Guid y)
{
    byte byte1, byte2;

    //Swap to the correct order to be compared
    for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
    {
        byte1 = x.ToByteArray()[m_byteOrder[i]];
        byte2 = y.ToByteArray()[m_byteOrder[i]];
        if (byte1 != byte2)
            return (byte1 < byte2) ? (int)EComparison.LT : (int)EComparison.GT;
    } // Next i 

    return (int)EComparison.EQ;
}

Full code:

namespace BlueMine.Data
{


    public class SqlGuid
        : System.IComparable
        , System.IComparable<SqlGuid>
        , System.Collections.Generic.IComparer<SqlGuid>
        , System.IEquatable<SqlGuid>
    {
        private const int NUM_BYTES_IN_GUID = 16;

        // Comparison orders.
        private static readonly int[] m_byteOrder = new int[16] // 16 Bytes = 128 Bit 
        {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

        private byte[] m_bytes; // the SqlGuid is null if m_value is null


        public SqlGuid(byte[] guidBytes)
        {
            if (guidBytes == null || guidBytes.Length != NUM_BYTES_IN_GUID)
                throw new System.ArgumentException("Invalid array size");

            m_bytes = new byte[NUM_BYTES_IN_GUID];
            guidBytes.CopyTo(m_bytes, 0);
        }


        public SqlGuid(System.Guid g)
        {
            m_bytes = g.ToByteArray();
        }


        public byte[] ToByteArray()
        {
            byte[] ret = new byte[NUM_BYTES_IN_GUID];
            m_bytes.CopyTo(ret, 0);
            return ret;
        }

        int CompareTo(object obj)
        {
            if (obj == null)
                return 1; // https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx

            System.Type t = obj.GetType();

            if (object.ReferenceEquals(t, typeof(System.DBNull)))
                return 1;

            if (object.ReferenceEquals(t, typeof(SqlGuid)))
            {
                SqlGuid ui = (SqlGuid)obj;
                return this.Compare(this, ui);
            } // End if (object.ReferenceEquals(t, typeof(UInt128)))

            return 1;
        } // End Function CompareTo(object obj)


        int System.IComparable.CompareTo(object obj)
        {
            return this.CompareTo(obj);
        }


        int CompareTo(SqlGuid other)
        {
            return this.Compare(this, other);
        }


        int System.IComparable<SqlGuid>.CompareTo(SqlGuid other)
        {
            return this.Compare(this, other);
        }


        enum EComparison : int
        {
            LT = -1, // itemA precedes itemB in the sort order.
            EQ = 0, // itemA occurs in the same position as itemB in the sort order.
            GT = 1 // itemA follows itemB in the sort order.
        }


        public int Compare(SqlGuid x, SqlGuid y)
        {
            byte byte1, byte2;

            //Swap to the correct order to be compared
            for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
            {
                byte1 = x.m_bytes[m_byteOrder[i]];
                byte2 = y.m_bytes[m_byteOrder[i]];
                if (byte1 != byte2)
                    return (byte1 < byte2) ? (int)EComparison.LT : (int)EComparison.GT;
            } // Next i 

            return (int)EComparison.EQ;
        }


        int System.Collections.Generic.IComparer<SqlGuid>.Compare(SqlGuid x, SqlGuid y)
        {
            return this.Compare(x, y);
        }


        public bool Equals(SqlGuid other)
        {
            return Compare(this, other) == 0;
        }


        bool System.IEquatable<SqlGuid>.Equals(SqlGuid other)
        {
            return this.Equals(other);
        }


    }


}

Countenance

Answer 3

Here's a different approach. The GUID is simply shuffled around ready for a normal string comparison like it occurs in SQL Server. This is Javascript but it is very easy to convert to any language.

function guidForComparison(guid) {
  /*
  character positions:  
            11111111112222222222333333
  012345678901234567890123456789012345

  00000000-0000-0000-0000-000000000000

  byte positions:  
                          111111111111
  00112233 4455 6677 8899 001122334455
  */
  return guid.substr(24, 12) + 
         guid.substr(19, 4) + 
         guid.substr(16, 2) + 
         guid.substr(14, 2) + 
         guid.substr(11, 2) + 
         guid.substr(9, 2) + 
         guid.substr(6, 2) +
         guid.substr(4, 2) +
         guid.substr(2, 2) +
         guid.substr(0, 2);
};

Spenserian

doesnt it sort some of them in reverse? – Afrikaans