Естественная (человеческая буквенно-цифровая) сортировка в Microsoft SQL 2005

Question

У нас есть большая база данных, в которой есть пагинация на стороне БД. Это быстро, возвращая страницу из 50 строк из миллионов записей за небольшую долю секунды.

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

В то время как большинство сортирует, как ожидается, текст сортируется тупо. Ну, я говорю глупо, это имеет смысл для компьютеров, но расстраивает пользователей.

Например, сортировка по идентификатору строковой записи дает что-то вроде:

rec1
rec10
rec14
rec2
rec20
rec3
rec4

... и т. Д.

Я хочу, чтобы это учитывало число, поэтому:

rec1
rec2
rec3
rec4
rec10
rec14
rec20

Я не могу контролировать ввод (иначе я бы просто отформатировал первые тысячи), и я не могу полагаться на один формат - некоторые вещи такие, как "{alpha code} - {dept code} - {rec id }».

Я знаю несколько способов сделать это в C #, но не могу вытащить все записи, чтобы отсортировать их, так как это может привести к замедлению.

Кто-нибудь знает способ быстрого применения естественной сортировки на сервере Sql?

---

Мы используем:

ROW_NUMBER() over (order by {field name} asc)

А потом мы этим разбираемся.

Мы можем добавлять триггеры, хотя мы не будем. Все их входные данные параметризованы и тому подобное, но я не могу изменить формат - если они введут «rec2» и «rec10», они ожидают, что они будут возвращены просто так и в естественном порядке.

---

У нас есть действительный пользовательский ввод в разных форматах для разных клиентов.

Можно пойти rec1, rec2, rec3, ... rec100, rec101

В то время как другой может пойти: grp1rec1, grp1rec2, ... grp20rec300, grp20rec301

Когда я говорю, что мы не можем контролировать ввод, я имею в виду, что мы не можем заставить пользователей изменять эти стандарты - они имеют значение, например grp1rec1, и я не могу переформатировать его как grp01rec001, так как это изменило бы что-то используемое для поиска и связи с внешними системами.

Эти форматы сильно различаются, но часто представляют собой смесь букв и цифр.

Сортировать их в C # легко - просто разбейте их на { "grp", 20, "rec", 301 } и затем по очереди сравните значения последовательности.

Несмотря на то, что могут быть миллионы записей и данные разбиты на страницы, мне нужно выполнить сортировку на сервере SQL.

Сервер SQL сортирует по значению, а не по сравнению - в C # я могу разделить значения для сравнения, но в SQL мне нужна логика, которая (очень быстро) получает одно значение, которое последовательно сортирует.

@ moebius - ваш ответ может сработать, но все равно кажется уродливым компромиссом добавить ключ сортировки для всех этих текстовых значений.

Answer 1

order by LEN(value), value

Не идеально, но хорошо работает во многих случаях.

Answer 2

Большинство решений на основе SQL, которые я видел, ломаются, когда данные становятся достаточно сложными (например, более одного или двух чисел в нем). Сначала я пытался реализовать функцию NaturalSort в T-SQL, которая отвечала моим требованиям (помимо прочего, обрабатывает произвольное число чисел в строке), но производительность была way слишком медленной.

В конечном итоге я написал скалярную функцию CLR в C #, чтобы обеспечить естественную сортировку, и даже с неоптимизированным кодом производительность, вызывающая его из SQL Server, невероятно высока. Имеет следующие характеристики:

• отсортирует первые 1000 символов или около того правильно (легко изменяется в коде или превращается в параметр)
• правильно сортирует десятичные дроби, поэтому 123,333 предшествует 123,45
• из-за вышеизложенного, скорее всего, НЕ будет правильно сортировать такие вещи, как IP-адреса; если вы хотите другое поведение, измените код
• поддерживает сортировку строки с произвольным числом чисел в ней
• будет правильно сортировать числа длиной до 25 цифр (легко изменяется в коде или превращается в параметр)

Код здесь:

using System;
using System.Data.SqlTypes;
using System.Text;
using Microsoft.SqlServer.Server;

public class UDF
{
    [SqlFunction(DataAccess = DataAccessKind.None, IsDeterministic=true)]
    public static SqlString Naturalize(string val)
    {
        if (String.IsNullOrEmpty(val))
            return val;

        while(val.Contains("  "))
            val = val.Replace("  ", " ");

        const int maxLength = 1000;
        const int padLength = 25;

        bool inNumber = false;
        bool isDecimal = false;
        int numStart = 0;
        int numLength = 0;
        int length = val.Length < maxLength ? val.Length : maxLength;

        //TODO: optimize this so that we exit for loop once sb.ToString() >= maxLength
        var sb = new StringBuilder();
        for (var i = 0; i < length; i++)
        {
            int charCode = (int)val[i];
            if (charCode >= 48 && charCode <= 57)
            {
                if (!inNumber)
                {
                    numStart = i;
                    numLength = 1;
                    inNumber = true;
                    continue;
                }
                numLength++;
                continue;
            }
            if (inNumber)
            {
                sb.Append(PadNumber(val.Substring(numStart, numLength), isDecimal, padLength));
                inNumber = false;
            }
            isDecimal = (charCode == 46);
            sb.Append(val[i]);
        }
        if (inNumber)
            sb.Append(PadNumber(val.Substring(numStart, numLength), isDecimal, padLength));

        var ret = sb.ToString();
        if (ret.Length > maxLength)
            return ret.Substring(0, maxLength);

        return ret;
    }

    static string PadNumber(string num, bool isDecimal, int padLength)
    {
        return isDecimal ? num.PadRight(padLength, '0') : num.PadLeft(padLength, '0');
    }
}

Чтобы зарегистрировать это, чтобы вы могли вызывать его из SQL Server, выполните следующие команды в Query Analyzer:

CREATE ASSEMBLY SqlServerClr FROM 'SqlServerClr.dll' --put the full path to DLL here
go
CREATE FUNCTION Naturalize(@val as nvarchar(max)) RETURNS nvarchar(1000) 
EXTERNAL NAME SqlServerClr.UDF.Naturalize
go

Затем вы можете использовать его так:

select *
from MyTable
order by dbo.Naturalize(MyTextField)

Примечание : Если в SQL Server появляется ошибка, аналогичная Выполнение кода пользователя в .NET Framework отключено. Включите опцию конфигурации «clr enabled». , следуйте инструкциям здесь , чтобы включить ее. Убедитесь, что вы учитываете последствия для безопасности, прежде чем делать это. Если вы не являетесь администратором db, обязательно обсудите это со своим администратором, прежде чем вносить какие-либо изменения в конфигурацию сервера.

Примечание2 : этот код неправильно поддерживает интернационализацию (например, предполагается, что десятичный маркер равен ".", Не оптимизирован для скорости и т. Д. Приветствуются предложения по его улучшению!

Редактировать: Переименована функция в Натурализовать вместо NaturalSort , поскольку она не выполняет никакой реальной сортировки.

Answer 3

Я знаю, что это старый вопрос, но я только что натолкнулся на него, и так как он не получил принятого ответа.

Я всегда использовал способы, подобные этому:

SELECT [Column] FROM [Table]
ORDER BY RIGHT(REPLICATE('0', 1000) + LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX)))), 1000)

Единственные распространенные случаи, когда возникают проблемы, - это если ваш столбец не будет приведен к VARCHAR (MAX), или если LEN ([Column])> 1000 (но вы можете изменить это значение 1000 на другое, если хотите) , но вы можете использовать эту грубую идею для того, что вам нужно.

Кроме того, это намного хуже производительности, чем обычный ORDER BY [Столбец], но дает результат, запрошенный в OP.

Редактировать: просто для дальнейшего разъяснения, это выше не будет работать, если у вас есть десятичные значения, такие как 1, 1.15 и 1.5, (они будут сортироваться как {1, 1.5, 1.15}), поскольку это не то, что запрашивается в ОП, но это легко сделать:

SELECT [Column] FROM [Table]
ORDER BY REPLACE(RIGHT(REPLICATE('0', 1000) + LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX)))) + REPLICATE('0', 100 - CHARINDEX('.', REVERSE(LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX))))), 1)), 1000), '.', '0')

Результат: {1, 1.15, 1.5}

И все же все целиком в SQL. Это не будет сортировать IP-адреса, потому что теперь вы получаете очень конкретные комбинации цифр, а не просто текст + число.

Answer 4

Ответ RedFilter отлично подходит для наборов данных разумного размера, где индексация не критична, однако, если вы хотите индексировать, требуется несколько настроек.

Во-первых, пометьте функцию как не имеющую доступа к данным, которая будет детерминированной и точной:

[SqlFunction(DataAccess = DataAccessKind.None,
                          SystemDataAccess = SystemDataAccessKind.None,
                          IsDeterministic = true, IsPrecise = true)]

Далее, MSSQL имеет ограничение в 900 байт на размер ключа индекса, поэтому, если натурализованное значение является единственным значением в индексе, оно должно содержать не более 450 символов. Если индекс включает несколько столбцов, возвращаемое значение должно быть еще меньше. Два изменения:

CREATE FUNCTION Naturalize(@str AS nvarchar(max)) RETURNS nvarchar(450)
    EXTERNAL NAME ClrExtensions.Util.Naturalize

и в коде C #:

const int maxLength = 450;

Наконец, вам нужно добавить вычисляемый столбец в вашу таблицу, и он должен быть сохранен (потому что MSSQL не может доказать, что Naturalize является детерминированным и точным), что означает, что натурализованное значение фактически сохраняется в таблице, но по-прежнему поддерживается автоматически:

ALTER TABLE YourTable ADD nameNaturalized AS dbo.Naturalize(name) PERSISTED

Теперь вы можете создать индекс!

CREATE INDEX idx_YourTable_n ON YourTable (nameNaturalized)

Я также внес несколько изменений в код RedFilter: использование символов для ясности, включение удаления дубликата пространства в основной цикл, выход после того, как результат превысил предел, установка максимальной длины без подстроки и т. Д. Вот результат :

using System.Data.SqlTypes;
using System.Text;
using Microsoft.SqlServer.Server;

public static class Util
{
    [SqlFunction(DataAccess = DataAccessKind.None, SystemDataAccess = SystemDataAccessKind.None, IsDeterministic = true, IsPrecise = true)]
    public static SqlString Naturalize(string str)
    {
        if (string.IsNullOrEmpty(str))
            return str;

        const int maxLength = 450;
        const int padLength = 15;

        bool isDecimal = false;
        bool wasSpace = false;
        int numStart = 0;
        int numLength = 0;

        var sb = new StringBuilder();
        for (var i = 0; i < str.Length; i++)
        {
            char c = str[i];
            if (c >= '0' && c <= '9')
            {
                if (numLength == 0)
                    numStart = i;
                numLength++;
            }
            else
            {
                if (numLength > 0)
                {
                    sb.Append(pad(str.Substring(numStart, numLength), isDecimal, padLength));
                    numLength = 0;
                }
                if (c != ' ' || !wasSpace)
                    sb.Append(c);
                isDecimal = c == '.';
                if (sb.Length > maxLength)
                    break;
            }
            wasSpace = c == ' ';
        }
        if (numLength > 0)
            sb.Append(pad(str.Substring(numStart, numLength), isDecimal, padLength));

        if (sb.Length > maxLength)
            sb.Length = maxLength;
        return sb.ToString();
    }

    private static string pad(string num, bool isDecimal, int padLength)
    {
        return isDecimal ? num.PadRight(padLength, '0') : num.PadLeft(padLength, '0');
    }
}

Answer 5

Вот решение, написанное для SQL 2000. Возможно, оно может быть улучшено для более новых версий SQL.

/**
 * Returns a string formatted for natural sorting. This function is very useful when having to sort alpha-numeric strings.
 *
 * @author Alexandre Potvin Latreille (plalx)
 * @param {nvarchar(4000)} string The formatted string.
 * @param {int} numberLength The length each number should have (including padding). This should be the length of the longest number. Defaults to 10.
 * @param {char(50)} sameOrderChars A list of characters that should have the same order. Ex: '.-/'. Defaults to empty string.
 *
 * @return {nvarchar(4000)} A string for natural sorting.
 * Example of use: 
 * 
 *      SELECT Name FROM TableA ORDER BY Name
 *  TableA (unordered)              TableA (ordered)
 *  ------------                    ------------
 *  ID  Name                        ID  Name
 *  1.  A1.                         1.  A1-1.       
 *  2.  A1-1.                       2.  A1.
 *  3.  R1             -->          3.  R1
 *  4.  R11                         4.  R11
 *  5.  R2                          5.  R2
 *
 *  
 *  As we can see, humans would expect A1., A1-1., R1, R2, R11 but that's not how SQL is sorting it.
 *  We can use this function to fix this.
 *
 *      SELECT Name FROM TableA ORDER BY dbo.udf_NaturalSortFormat(Name, default, '.-')
 *  TableA (unordered)              TableA (ordered)
 *  ------------                    ------------
 *  ID  Name                        ID  Name
 *  1.  A1.                         1.  A1.     
 *  2.  A1-1.                       2.  A1-1.
 *  3.  R1              -->         3.  R1
 *  4.  R11                         4.  R2
 *  5.  R2                          5.  R11
 */
ALTER FUNCTION [dbo].[udf_NaturalSortFormat](
    @string nvarchar(4000),
    @numberLength int = 10,
    @sameOrderChars char(50) = ''
)
RETURNS varchar(4000)
AS
BEGIN
    DECLARE @sortString varchar(4000),
        @numStartIndex int,
        @numEndIndex int,
        @padLength int,
        @totalPadLength int,
        @i int,
        @sameOrderCharsLen int;

    SELECT 
        @totalPadLength = 0,
        @string = RTRIM(LTRIM(@string)),
        @sortString = @string,
        @numStartIndex = PATINDEX('%[0-9]%', @string),
        @numEndIndex = 0,
        @i = 1,
        @sameOrderCharsLen = LEN(@sameOrderChars);

    -- Replace all char that have the same order by a space.
    WHILE (@i <= @sameOrderCharsLen)
    BEGIN
        SET @sortString = REPLACE(@sortString, SUBSTRING(@sameOrderChars, @i, 1), ' ');
        SET @i = @i + 1;
    END

    -- Pad numbers with zeros.
    WHILE (@numStartIndex <> 0)
    BEGIN
        SET @numStartIndex = @numStartIndex + @numEndIndex;
        SET @numEndIndex = @numStartIndex;

        WHILE(PATINDEX('[0-9]', SUBSTRING(@string, @numEndIndex, 1)) = 1)
        BEGIN
            SET @numEndIndex = @numEndIndex + 1;
        END

        SET @numEndIndex = @numEndIndex - 1;

        SET @padLength = @numberLength - (@numEndIndex + 1 - @numStartIndex);

        IF @padLength < 0
        BEGIN
            SET @padLength = 0;
        END

        SET @sortString = STUFF(
            @sortString,
            @numStartIndex + @totalPadLength,
            0,
            REPLICATE('0', @padLength)
        );

        SET @totalPadLength = @totalPadLength + @padLength;
        SET @numStartIndex = PATINDEX('%[0-9]%', RIGHT(@string, LEN(@string) - @numEndIndex));
    END

    RETURN @sortString;
END

Answer 6

Я знаю, что это немного устарело, но в поисках лучшего решения я наткнулся на этот вопрос. В настоящее время я использую функцию для заказа. Он отлично работает для моей цели сортировки записей, имена которых имеют смешанные буквенно-цифровые символы («элемент 1», «элемент 10», «элемент 2» и т. Д.)

CREATE FUNCTION [dbo].[fnMixSort]
(
    @ColValue NVARCHAR(255)
)
RETURNS NVARCHAR(1000)
AS

BEGIN
    DECLARE @p1 NVARCHAR(255),
        @p2 NVARCHAR(255),
        @p3 NVARCHAR(255),
        @p4 NVARCHAR(255),
        @Index TINYINT

    IF @ColValue LIKE '[a-z]%'
        SELECT  @Index = PATINDEX('%[0-9]%', @ColValue),
            @p1 = LEFT(CASE WHEN @Index = 0 THEN @ColValue ELSE LEFT(@ColValue, @Index - 1) END + REPLICATE(' ', 255), 255),
            @ColValue = CASE WHEN @Index = 0 THEN '' ELSE SUBSTRING(@ColValue, @Index, 255) END
    ELSE
        SELECT  @p1 = REPLICATE(' ', 255)

    SELECT  @Index = PATINDEX('%[^0-9]%', @ColValue)

    IF @Index = 0
        SELECT  @p2 = RIGHT(REPLICATE(' ', 255) + @ColValue, 255),
            @ColValue = ''
    ELSE
        SELECT  @p2 = RIGHT(REPLICATE(' ', 255) + LEFT(@ColValue, @Index - 1), 255),
            @ColValue = SUBSTRING(@ColValue, @Index, 255)

    SELECT  @Index = PATINDEX('%[0-9,a-z]%', @ColValue)

    IF @Index = 0
        SELECT  @p3 = REPLICATE(' ', 255)
    ELSE
        SELECT  @p3 = LEFT(REPLICATE(' ', 255) + LEFT(@ColValue, @Index - 1), 255),
            @ColValue = SUBSTRING(@ColValue, @Index, 255)

    IF PATINDEX('%[^0-9]%', @ColValue) = 0
        SELECT  @p4 = RIGHT(REPLICATE(' ', 255) + @ColValue, 255)
    ELSE
        SELECT  @p4 = LEFT(@ColValue + REPLICATE(' ', 255), 255)

    RETURN  @p1 + @p2 + @p3 + @p4

END

Тогда звоните

select item_name from my_table order by fnMixSort(item_name)

Он легко утраивает время обработки при простом считывании данных, поэтому может оказаться не идеальным решением.

Answer 7

Вот еще одно решение, которое мне нравится: http://www.dreamchain.com/sql-and-alpha-numeric-sort-order/

Это не Microsoft SQL, но, поскольку я оказался здесь, когда искал решение для Postgres, я подумал, что добавление этого здесь поможет другим.

Answer 8

Для следующих varchar данных:

BR1
BR2
External Location
IR1
IR2
IR3
IR4
IR5
IR6
IR7
IR8
IR9
IR10
IR11
IR12
IR13
IR14
IR16
IR17
IR15
VCR

Это лучше всего сработало для меня:

ORDER BY substring(fieldName, 1, 1), LEN(fieldName)

Answer 9

Если у вас возникли проблемы с загрузкой данных из БД для сортировки в C #, то я уверен, что вы будете разочарованы любым подходом к программному выполнению этого в БД. Когда сервер собирается сортировать, он должен каждый раз вычислять «воспринимаемый» порядок, как вы бы это делали.

Я бы предложил добавить дополнительный столбец для хранения предварительно обработанной сортируемой строки, используя некоторый метод C #, когда данные впервые вставляются. Например, вы можете попытаться преобразовать числа в диапазоны фиксированной ширины, чтобы «xyz1» превратился в «xyz00000001». Тогда вы можете использовать обычную сортировку SQL Server.

Рискуя своим собственным рогом, я написал статью CodeProject, в которой реализована проблема, изложенная в статье CodingHorror. Не стесняйтесь украсть из моего кода .

Answer 10

Просто вы сортируете по

ORDER BY 
cast (substring(name,(PATINDEX('%[0-9]%',name)),len(name))as int)

 ##