Алгоритм сортировки GUID SQL Server.Зачем?

Question

Проблема с уникальными идентификаторами

У нас есть существующая база данных, в которой уникальные идентификаторы широко используются (к сожалению!) Как в качестве первичных ключей, так и в некоторых обнуляемых столбцах некоторых таблиц. Мы столкнулись с ситуацией, когда некоторые отчеты, которые запускаются в этих таблицах, сортируются по этим уникальным идентификаторам, потому что в таблице нет другого столбца, который бы дал бы значимый вид (разве это не ирония!). Намерение состояло в том, чтобы сортировать так, чтобы он отображал элементы в том порядке, в котором они были вставлены, но они не были вставлены с использованием NewSequentialId () - следовательно, это трата времени.

Факт об алгоритме сортировки

В любом случае, учитывая, что SQL Server сортирует уникальные идентификаторы на основе групп байтов, начиная с конечной 5-й группы байтов (6 байтов) и переходя к 1-й группе байтов (4 байта), меняя порядок на 3-й байтовой группе (2 байта) с справа налево налево направо,

Мой вопрос

Мне было любопытно узнать, есть ли какая-то реальная жизненная ситуация, которая вообще помогает этому виду.

Как SQL Server хранит уникальный идентификатор внутри, что может дать представление о почему у него такой дурацкий алгоритм сортировки?

Справка:

Обнаружение Альберто Феррари идентификатора GUID SQL Server

Пример * +1031 *

Уникальные идентификаторы сортируются, как показано ниже, когда вы используете Order By для столбца уникальных идентификаторов, имеющих данные ниже.

Обратите внимание, что приведенные ниже данные отсортированы по возрастанию, и наибольшее предпочтение сортируется от 5-й группы байтов к 1-й группе байтов (в обратном направлении).

-- 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

Код:

Код Альберто расширен для обозначения того, что сортировка выполняется в байтах, а не в отдельных битах.

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

Answer 1

Алгоритм задокументирован ребятами из SQL Server: Как сравниваются GUID в SQL Server 2005?

Кроме того, сортировка следует за порядком байтовых групп (см. Здесь: Глобальный уникальный идентификатор ).Группы 10-15 и 8-9 хранятся с прямым порядком байтов (соответствует Data4 в статье в Википедии), поэтому они сравниваются как с прямым порядком байтов.Другие группы сравниваются с использованием байтов с прямым порядком байтов.

Answer 2

Necromancing.
Специальный сервис для тех, кто считает, что принятые ответы немного расплывчаты.
Кодекс говорит сам за себя, магические части

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;
}

Полный код:

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);
        }


    }


}

Answer 3

Вот другой подход.GUID просто перемешан и готов к обычному сравнению строк, как это происходит в SQL Server.Это Javascript, но его очень легко конвертировать на любой язык.

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);
};