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

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

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

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

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

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

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

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

Ответы

Ответ 1

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

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

Ответ 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);
        }


    }


}

Ответ 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);
};