Clasificación natural (humano alfanumérico) en Microsoft SQL 2005

Question

Tenemos una gran base de datos en la que tenemos una paginación de lado de DB. Esto es rápido, devolviendo una página de 50 filas de millones de registros en una pequeña fracción de segundo.

Los usuarios pueden definir su propio tipo, básicamente eligiendo qué columna ordenar. Las columnas son dinámicas, algunas tienen valores numéricos, algunas fechas y texto.

Mientras que la mayoría clasifica como el texto esperado, ordena de una manera tonta. Bueno, digo tonto, tiene sentido para las computadoras, pero frustra a los usuarios.

Por ejemplo, la clasificación por un ID de registro de cadena da algo así como:

rec1 
rec10 
rec14 
rec2 
rec20 
rec3 
rec4 

... y así sucesivamente.

Quiero que esto tiene en cuenta el número, así:

rec1 
rec2 
rec3 
rec4 
rec10 
rec14 
rec20 

no puedo controlar la entrada (de lo contrario estaría solo formato en el que lleva 000s) y no puedo confiar en un solo formato - algunos son cosas como "{código alfa} - {departamento código} - {rec id}".

Conozco algunas formas de hacer esto en C#, pero no puedo seleccionar todos los registros para ordenarlos, ya que eso sería reducir la velocidad.

¿Alguien sabe una forma de aplicar rápidamente una ordenación natural en el servidor Sql?

---

Estamos usando:

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

Y entonces estamos paginación por eso.

Podemos agregar activadores, aunque no lo haríamos. Toda su entrada está parametrizada y similares, pero no puedo cambiar el formato; si ponen "rec2" y "rec10", esperan que se devuelvan así, y en orden natural.

---

Tenemos una entrada de usuario válida que sigue diferentes formatos para diferentes clientes.

Uno podría ir REC1, REC2, REC3, ... rec100, rec101

mientras que otro puede ir: grp1rec1, grp1rec2, ... grp20rec300, grp20rec301

Cuando digo que no podemos controlar la entrada quiero decir que no podemos obligar a los usuarios a cambiar estos estándares; tienen un valor como grp1rec1 y no puedo reformatearlo como grp01rec001, ya que eso estaría cambiando algo usado para búsquedas y enlaces a sistemas externos.

Estos formatos varían mucho, pero a menudo son mezclas de letras y números.

Ordenar estos en C# es fácil - solo divídalo en { "grp", 20, "rec", 301 } y luego compare los valores de secuencia sucesivamente.

Sin embargo, puede haber millones de registros y los datos están paginados, necesito que la clasificación se haga en el servidor SQL.

El servidor SQL ordena por valor, no por comparación: en C# puedo dividir los valores para comparar, pero en SQL necesito un poco de lógica que (muy rápidamente) obtiene un único valor que ordena constantemente.

@moebius - su respuesta podría funcionar, pero se siente como un compromiso feo para agregar una clave de clasificación para todos estos valores de texto.

Answer 1

La mayoría de las soluciones basadas en SQL que he visto se rompen cuando los datos se vuelven lo suficientemente complejos (por ejemplo, más de uno o dos números en él). Inicialmente traté de implementar una función NaturalSort en T-SQL que cumpliera con mis requisitos (entre otras cosas, maneja una cantidad arbitraria de números dentro de la cadena), pero el rendimiento fue manera demasiado lento.

En última instancia, escribí una función escalar CLR en C# para permitir una ordenación natural, e incluso con código no optimizado, el rendimiento que lo llama desde SQL Server es deslumbrantemente rápido. Tiene las siguientes características:

• clasificará los primeros 1.000 caracteres o menos correctamente (fácilmente modificado en clave o convertido en un parámetro)
• ordena adecuadamente decimales, por lo que 123.333 viene antes 123,45
• debido encima , probablemente NO clasifique cosas como direcciones IP correctamente; si se desea un comportamiento diferente, modifique el código
• soportes de clasificación de una cadena con un número arbitrario de números dentro de ella
• va a clasificar correctamente los números hasta 25 dígitos de longitud (fácilmente modificado en clave o convertido en un parámetro)

El código está aquí:

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

public class UDF 
{ 
    [SqlFunction(DataAccess = DataAccessKind.Read)] 
    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'); 
    } 
} 

Para registrar este modo que se le puede llamar desde SQL Server, ejecute los siguientes comandos en el Analizador de consultas:

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 

A continuación, se puede usar como tal:

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

Nota: Si se produce un error en SQL Server en la línea de Ejecución de código de usuario en el .NET Framework está desactivado. Habilite la opción de configuración "clr enabled"., siga las instrucciones here para habilitarlo. Asegúrese de considerar las implicaciones de seguridad antes de hacerlo. Si no es el administrador de db, asegúrese de discutir esto con su administrador antes de realizar cambios en la configuración del servidor.

Nota2: Este código no admite la internacionalización correctamente (por ejemplo, supone que el marcador decimal es ".", No está optimizado para la velocidad, etc. ¡Sugerencias para mejorarlo son bienvenidos!

Editar: cambiado el nombre de la función a Naturalizar en lugar de NaturalSort, ya que no hace ninguna clasificación real.

Answer 2

Todavía no entiendo (probablemente debido a mi pobre inglés).

Usted podría intentar:

ROW_NUMBER() OVER (ORDER BY dbo.human_sort(field_name) ASC) 

pero no va a trabajar para millones de registros.

eso por lo que sugiere el uso de disparador que llena columna separada con valor humano.

Además:

• funciones integradas de T-SQL son realmente lento y Microsoft aconseja la utilización de .NET funciones en su lugar.
• valor humano es constante por lo que no tiene sentido calcularlo cada vez cuando se ejecuta la consulta.

Answer 3

Si tiene problemas para cargar los datos de la base de datos para clasificar C#, entonces estoy seguro de que se sentirá decepcionado con cualquier enfoque para hacerlo programáticamente en la base de datos. Cuando el servidor va a ordenar, tiene que calcular el orden "percibido" tal como lo haría siempre.

Le sugiero que agregue una columna adicional para almacenar la cadena ordenable preprocesada, utilizando algún método C#, cuando se inserten los datos por primera vez. Puede intentar convertir los números en rangos de ancho fijo, por ejemplo, para que "xyz1" se convierta en "xyz00000001". Entonces podría usar la clasificación normal de SQL Server.

A riesgo de tocar mi propio cuerno, escribí un artículo de CodeProject implementando el problema tal como se plantea en el artículo CodingHorror. Siéntase libre de steal from my code.

Answer 4

Sé que esto es un poco viejo en este punto, pero en mi búsqueda de una mejor solución, me encontré con esta pregunta. Actualmente estoy usando una función para ordenar. Funciona bien para mi propósito de la ordenación de registros que se nombra con numérica mixta alfa ('punto 1', 'artículo 10', 'punto 2', etc)

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 

luego llamar a

select item_name from my_table order by fnMixSort(item_name) 

Triplica fácilmente el tiempo de procesamiento para una simple lectura de datos, por lo que puede no ser la solución perfecta.

Answer 5

order by LEN(value), value 

No es perfecto, pero funciona bien en muchos casos.

Answer 6

Usted puede utilizar el código siguiente para resolver el problema:

Select *, 
    substring(Cote,1,len(Cote) - Len(RIGHT(Cote, LEN(Cote) - PATINDEX('%[0-9]%', Cote)+1)))alpha, 
    CAST(RIGHT(Cote, LEN(Cote) - PATINDEX('%[0-9]%', Cote)+1) AS INT)intv 
FROM Documents 
    left outer join Sites ON Sites.IDSite = Documents.IDSite 
Order BY alpha, intv 

cordiales, rabihkahaleh@hotmail.com

Answer 7

acabo de leer un artículo en algún lugar sobre un tema tan. El punto clave es: solo necesita el valor entero para ordenar los datos, mientras que la cadena 'rec' pertenece a la IU. Puede dividir la información en dos campos, por ejemplo, alfa y num, ordenar por alfa y num (por separado) y luego mostrar una cadena compuesta por alfa + num. Puede usar una columna calculada para componer la cadena o una vista. Espero que ayude

Answer 8

Sé que esta es una vieja pregunta, pero acabo de encontrarla y, dado que no tiene una respuesta aceptada.

siempre he utilizado de manera similar a esto:

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

Las únicas veces comunes que esto tiene problemas es si su columna no desechará a un VARCHAR (MAX), o si LEN ([Columna])> 1000 (pero puede cambiar ese 1000 a otra cosa si lo desea), pero puede usar esta idea aproximada para lo que necesita.

También este es un rendimiento mucho peor que el ORDEN normal por [Columna], pero le da el resultado solicitado en el PO.

Editar: Solo para aclarar aún más, esto lo anterior no funcionará si tiene valores decimales, tales como tener 1, 1.15 y 1.5, (que va a clasificar como {1, 1.5, 1.15}) ya que no es lo que se pide en el PO, pero que se puede hacer fácilmente por:

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

Resultado: {1, 1.15, 1.5}

Y todavía toda su totalidad dentro de SQL. Esto no ordenará las direcciones IP porque ahora está ingresando a combinaciones de números muy específicas en lugar de texto simple + número.

Answer 9

Aquí hay una solución escrita para SQL 2000. Probablemente se pueda mejorar para versiones de SQL más nuevas.

/** 
* 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 10

Simplemente ordena por

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

## 

Answer 11

Para el varchar siguientes datos:

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

Esto funcionó mejor para mí:

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

Answer 12

Aquí es una otra solución que Me gusta: http://www.dreamchain.com/sql-and-alpha-numeric-sort-order/

No es Microsoft SQL, pero desde que terminé aquí cuando estaba buscando una solución para Postgres, pensé que agregar esto aquí podría ayudar a otros.

Answer 13

RedFilter's answer es ideal para conjuntos de datos de tamaño razonable donde la indexación no es crítica, sin embargo, si desea un índice, se requieren varios ajustes.

En primer lugar, marcar la función de no hacer ningún acceso a los datos y ser determinista y precisa:

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

A continuación, MSSQL tiene un límite de 900 bytes en el tamaño de la clave de índice, por lo que si el valor naturalizada es el único valor en el índice, debe tener un máximo de 450 caracteres. Si el índice incluye varias columnas, el valor de retorno debe ser aún menor.Dos cambios:

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

y en el código C#:

const int maxLength = 450; 

Por último, se tendrá que añadir una columna calculada a su mesa, y debe ser persistido (porque MSSQL no puede probar que Naturalize es determinista y precisa), lo que significa que el valor naturalizada se almacena realmente en la tabla, pero aún se mantiene de forma automática:

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

ahora puede crear el índice!

CREATE INDEX idx_YourTable_n ON YourTable (nameNaturalized) 

También he hecho un par de cambios en el código de RedFilter: el uso de caracteres para la claridad, la incorporación de eliminación de espacios duplicado en el bucle principal, saliendo una vez que el resultado es mayor que el límite, el establecimiento de longitud máxima, sin subcadena etc. . Aquí está el resultado:

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