Tri naturel (alpha-numérique humain) dans Microsoft SQL 2005

Question

Nous avons une grande base de données sur laquelle nous avons une pagination côté DB. Celle-ci est rapide, renvoyant une page de 50 lignes à partir de millions d'enregistrements en une petite fraction de seconde.

Les utilisateurs peuvent définir leur propre tri, en choisissant essentiellement la colonne par laquelle ils souhaitent trier. Les colonnes sont dynamiques - certaines ont des valeurs numériques, d'autres des dates et d'autres encore du texte.

Alors que la plupart trient comme prévu, les textes trient d'une manière stupide. Eh bien, je dis stupide, cela a du sens pour les ordinateurs, mais frustre les utilisateurs.

Par exemple, le tri par une chaîne d'identifiant d'enregistrement donne quelque chose comme.. :

rec1
rec10
rec14
rec2
rec20
rec3
rec4

...et ainsi de suite.

Je veux que cela prenne en compte le nombre, donc :

rec1
rec2
rec3
rec4
rec10
rec14
rec20

Je ne peux pas contrôler l'entrée (sinon, je me contenterais de formater en milliers) et je ne peux pas me fier à un format unique - certains sont des choses comme "{code alpha}-{code de département}-{identification du dossier}".

Je connais quelques moyens de le faire en C#, mais je ne peux pas faire descendre tous les enregistrements pour les trier, car cela serait trop lent.

Quelqu'un connaît-il un moyen d'appliquer rapidement un tri naturel dans Sql server ?

---

Nous utilisons :

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

Et ensuite on pagine par là.

Nous pouvons ajouter des déclencheurs, mais nous ne le ferions pas. Toutes les entrées sont paramétrées et autres, mais je ne peux pas changer le format - s'ils entrent "rec2" et "rec10", ils s'attendent à ce qu'ils soient renvoyés comme ça, et dans l'ordre naturel.

---

Nous avons des entrées utilisateur valides qui suivent différents formats pour différents clients.

On pourrait dire rec1, rec2, rec3, ... rec100, rec101

Alors qu'un autre pourrait aller : grp1rec1, grp1rec2, ... grp20rec300, grp20rec301

Lorsque je dis que nous ne pouvons pas contrôler l'entrée, je veux dire que nous ne pouvons pas forcer les utilisateurs à modifier ces normes - elles ont une valeur comme grp1rec1 et je ne peux pas la reformater en grp01rec001, car cela reviendrait à modifier un élément utilisé pour les recherches et les liens vers des systèmes externes.

Ces formats varient beaucoup, mais sont souvent des mélanges de lettres et de chiffres.

Le tri en C# est facile - il suffit de le décomposer en { "grp", 20, "rec", 301 } puis comparer les valeurs des séquences à tour de rôle.

Cependant, il peut y avoir des millions d'enregistrements et les données sont paginées, j'ai besoin que le tri soit effectué sur le serveur SQL.

Le serveur SQL trie par valeur, pas par comparaison. En C#, je peux séparer les valeurs pour les comparer, mais en SQL, j'ai besoin d'une logique qui permette d'obtenir (très rapidement) une valeur unique qui trie de manière cohérente.

@moebius - votre réponse pourrait fonctionner, mais il semble que ce soit un vilain compromis d'ajouter une clé de tri pour toutes ces valeurs de texte.

Answer 1

order by LEN(value), value

Il n'est pas parfait, mais il fonctionne bien dans de nombreux cas.

Answer 2

La plupart des solutions basées sur SQL que j'ai vues se cassent lorsque les données deviennent suffisamment complexes (par exemple, lorsqu'elles contiennent plus d'un ou deux chiffres). Au départ, j'ai essayé d'implémenter une fonction NaturalSort en T-SQL qui répondait à mes exigences (entre autres, elle gère un nombre arbitraire de chiffres dans la chaîne), mais les performances étaient les suivantes chemin trop lent.

En fin de compte, j'ai écrit une fonction CLR scalaire en C# pour permettre un tri naturel, et même avec un code non optimisé, la performance en l'appelant à partir de SQL Server est incroyablement rapide. Elle présente les caractéristiques suivantes :

• triera correctement les quelque 1000 premiers caractères (facilement modifiable en code ou en paramètre).
• trie correctement les décimales, ainsi 123.333 vient avant 123.45
• en raison de ce qui précède, ne triera probablement PAS correctement les éléments tels que les adresses IP ; si vous souhaitez un comportement différent, modifiez le code
• permet de trier une chaîne de caractères contenant un nombre arbitraire de chiffres.
• triera correctement les nombres jusqu'à 25 chiffres (facilement modifiable en code ou en paramètre).

Le code est ici :

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

Pour l'enregistrer afin de pouvoir l'appeler depuis le serveur SQL, exécutez les commandes suivantes dans 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

Ensuite, vous pouvez l'utiliser comme suit :

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

Nota : Si vous obtenez une erreur dans SQL Server du type L'exécution du code utilisateur dans le .NET Framework est désactivée. Activez l'option de configuration "clr enabled". Suivez les instructions. aquí pour l'activer. Veillez à prendre en compte les implications en matière de sécurité avant de le faire. Si vous n'êtes pas l'administrateur de la base de données, assurez-vous d'en discuter avec votre administrateur avant d'apporter des modifications à la configuration du serveur.

Note2 : Ce code ne prend pas correctement en charge l'internationalisation (par exemple, il suppose que le marqueur décimal est ".", n'est pas optimisé pour la vitesse, etc. Les suggestions pour l'améliorer sont les bienvenues !

Editar: J'ai renommé la fonction en Naturaliser au lieu de NaturalSort puisqu'il n'effectue pas de tri réel.

Answer 3

Je sais que c'est une vieille question mais je viens de tomber dessus et comme il n'y a pas de réponse acceptée, j'ai décidé de la poser.

J'ai toujours utilisé des méthodes similaires à celle-ci :

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

Les seules fois où cela pose problème sont si votre colonne ne peut pas être convertie en VARCHAR(MAX), ou si LEN([Column]) > 1000 (mais vous pouvez changer ce 1000 en quelque chose d'autre si vous voulez), mais vous pouvez utiliser cette idée approximative pour ce dont vous avez besoin.

Les performances sont également bien pires que celles d'un ORDER BY [Column] normal, mais cela vous donne le résultat demandé dans l'OP.

Edit : Juste pour clarifier, ce qui précède ne fonctionnera pas si vous avez des valeurs décimales, comme avoir 1 , 1.15 y 1.5 (ils seront triés comme {1, 1.5, 1.15} ) car ce n'est pas ce qui est demandé dans l'OP, mais cela peut facilement être fait par :

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

Résultat : {1, 1.15, 1.5}

Et toujours entièrement dans SQL. Cette méthode ne permet pas de trier les adresses IP, car il s'agit alors de combinaisons de chiffres très spécifiques, par opposition à un simple texte + chiffre.

Answer 4

Voici une solution écrite pour SQL 2000. Elle peut probablement être améliorée pour les nouvelles versions de 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 5

La réponse de RedFilter est idéal pour les ensembles de données de taille raisonnable où l'indexation n'est pas essentielle, mais si vous voulez un index, plusieurs modifications sont nécessaires.

Tout d'abord, marquez la fonction comme ne faisant aucun accès aux données et étant déterministe et précise :

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

Ensuite, MSSQL a une limite de 900 octets pour la taille de la clé d'index, donc si la valeur naturalisée est la seule valeur de l'index, elle doit faire au maximum 450 caractères. Si l'index comprend plusieurs colonnes, la valeur de retour doit être encore plus petite. Deux changements :

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

et dans le code C# :

const int maxLength = 450;

Enfin, vous devrez ajouter une colonne calculée à votre table, et celle-ci doit être persistée (parce que MSSQL ne peut pas prouver que Naturalize est déterministe et précise), ce qui signifie que la valeur naturalisée est effectivement stockée dans la table mais qu'elle est toujours gérée automatiquement :

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

Vous pouvez maintenant créer l'index !

CREATE INDEX idx_YourTable_n ON YourTable (nameNaturalized)

J'ai également apporté quelques modifications au code de RedFilter : utilisation des chars pour plus de clarté, intégration de la suppression des espaces en double dans la boucle principale, sortie dès que le résultat est plus long que la limite, définition de la longueur maximale sans sous-chaîne, etc. Voici le résultat :

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