¿Cómo puedo convertir los primeros 100 millones de enteros positivos en cadenas?

Esto es un poco un desvío del problema real. Si proporciona ayuda contextual, la generación de estos datos podría ser útil para probar formas de procesamiento de cadenas, para generar cadenas que necesitan que se les aplique alguna operación dentro de un cursor o para generar reemplazos de nombres únicos y anónimos para datos confidenciales. Solo estoy interesado en formas eficientes de generar los datos dentro de los servidores SQL, por favor no pregunte por qué necesito generar estos datos.

Trataré de comenzar con una definición algo formal. Se incluye una cadena en la serie si solo consta de letras mayúsculas de la A a la Z. El primer término de la serie es "A". La serie consta de todas las cadenas válidas ordenadas por longitud primero y orden alfabético típico segundo. Si las cadenas estuvieran en una tabla en una columna llamada STRING_COL, el orden podría definirse en T-SQL comoORDER BY LEN(STRING_COL) ASC, STRING_COL ASC .

Para dar una definición menos formal, eche un vistazo a los encabezados de columna alfabéticos en Excel. La serie tiene el mismo patrón. Considere cómo podría convertir un número entero en un número base 26:

1 -> A, 2 -> B, 3 -> C, ..., 25 -> Y, 26 -> Z, 27 -> AA, 28 -> AB, ...

La analogía no es perfecta porque "A" se comporta de manera diferente a 0 en base diez. A continuación se muestra una tabla de valores seleccionados que, con suerte, lo aclarará más:

╔════════════╦════════╗
║ ROW_NUMBER ║ STRING ║
╠════════════╬════════╣
║          1 ║ A      ║
║          2 ║ B      ║
║         25 ║ Y      ║
║         26 ║ Z      ║
║         27 ║ AA     ║
║         28 ║ AB     ║
║         51 ║ AY     ║
║         52 ║ AZ     ║
║         53 ║ BA     ║
║         54 ║ BB     ║
║      18278 ║ ZZZ    ║
║      18279 ║ AAAA   ║
║     475253 ║ ZZZY   ║
║     475254 ║ ZZZZ   ║
║     475255 ║ AAAAA  ║
║  100000000 ║ HJUNYV ║
╚════════════╩════════╝

El objetivo es escribir una SELECTconsulta que devuelva las primeras 100000000 cadenas en el orden definido anteriormente. Hice mis pruebas ejecutando consultas en SSMS con el conjunto de resultados descartado en lugar de guardarlo en una tabla:

Idealmente, la consulta será razonablemente eficiente. Aquí estoy definiendo eficiente como tiempo de CPU para una consulta en serie y tiempo transcurrido para una consulta paralela. Puedes usar cualquier truco indocumentado que te guste. Confiar en un comportamiento indefinido o no garantizado también está bien, pero sería apreciado si lo mencionara en su respuesta.

¿Cuáles son algunos métodos para generar eficientemente el conjunto de datos descrito anteriormente? Martin Smith señaló que un procedimiento almacenado CLR probablemente no sea un buen enfoque debido a la sobrecarga de procesar tantas filas.

Su solución se ejecuta durante 35 segundos en mi computadora portátil. El siguiente código tarda 26 segundos (incluida la creación y el llenado de las tablas temporales):

Mesas temporales

DROP TABLE IF EXISTS #T1, #T2, #T3, #T4;

CREATE TABLE #T1 (string varchar(6) NOT NULL PRIMARY KEY);
CREATE TABLE #T2 (string varchar(6) NOT NULL PRIMARY KEY);
CREATE TABLE #T3 (string varchar(6) NOT NULL PRIMARY KEY);
CREATE TABLE #T4 (string varchar(6) NOT NULL PRIMARY KEY);

INSERT #T1 (string)
VALUES
    ('A'), ('B'), ('C'), ('D'), ('E'), ('F'), ('G'),
    ('H'), ('I'), ('J'), ('K'), ('L'), ('M'), ('N'),
    ('O'), ('P'), ('Q'), ('R'), ('S'), ('T'), ('U'),
    ('V'), ('W'), ('X'), ('Y'), ('Z');

INSERT #T2 (string)
SELECT T1a.string + T1b.string
FROM #T1 AS T1a, #T1 AS T1b;

INSERT #T3 (string)
SELECT #T2.string + #T1.string
FROM #T2, #T1;

INSERT #T4 (string)
SELECT #T3.string + #T1.string
FROM #T3, #T1;

La idea es completar previamente las combinaciones ordenadas de hasta cuatro caracteres.

Código principal

SELECT TOP (100000000)
    UA.string + UA.string2
FROM
(
    SELECT U.Size, U.string, string2 = '' FROM 
    (
        SELECT Size = 1, string FROM #T1
        UNION ALL
        SELECT Size = 2, string FROM #T2
        UNION ALL
        SELECT Size = 3, string FROM #T3
        UNION ALL
        SELECT Size = 4, string FROM #T4
    ) AS U
    UNION ALL
    SELECT Size = 5, #T1.string, string2 = #T4.string
    FROM #T1, #T4
    UNION ALL
    SELECT Size = 6, #T2.string, #T4.string
    FROM #T2, #T4
) AS UA
ORDER BY 
    UA.Size, 
    UA.string, 
    UA.string2
OPTION (NO_PERFORMANCE_SPOOL, MAXDOP 1);

Esa es una unión simple para preservar el orden * de las cuatro tablas precalculadas, con cadenas de 5 y 6 caracteres derivadas según sea necesario. Separar el prefijo del sufijo evita la clasificación.

Plan de ejecución

* No hay nada en el SQL anterior que especifique una unión de preservación de orden directamente. El optimizador elige operadores físicos con propiedades que coinciden con la especificación de la consulta SQL, incluido el orden de nivel superior por. Aquí, elige la concatenación implementada por el operador físico de combinación de combinación para evitar la clasificación.

La garantía es que el plan de ejecución entrega la consulta semántica y el orden de nivel superior por especificación. Saber que la combinación unir concat preserva el orden permite al escritor de consultas anticipar un plan de ejecución, pero el optimizador solo se entregará si la expectativa es válida.

Publicaré una respuesta para comenzar. Mi primer pensamiento fue que debería ser posible aprovechar la naturaleza de preservación del orden de una unión de bucle anidado junto con algunas tablas auxiliares que tienen una fila para cada letra. La parte difícil iba a estar en bucle de tal manera que los resultados se ordenaran por longitud, así como para evitar duplicados. Por ejemplo, cuando se une de forma cruzada a un CTE que incluye las 26 letras mayúsculas junto con '', puede terminar generando 'A' + '' + 'A'y'' + 'A' + 'A' que, por supuesto, es la misma cadena.

La primera decisión fue dónde almacenar los datos de ayuda. Intenté usar una tabla temporal, pero esto tuvo un impacto sorprendentemente negativo en el rendimiento, a pesar de que los datos caben en una sola página. La tabla temporal contenía los siguientes datos:

SELECT 'A'
UNION ALL SELECT 'B'
...
UNION ALL SELECT 'Y'
UNION ALL SELECT 'Z'

En comparación con el uso de un CTE, la consulta tardó 3 veces más con una tabla en clúster y 4 veces más con un montón. No creo que el problema sea que los datos están en el disco. Debe leerse en la memoria como una sola página y procesarse en la memoria para todo el plan. Quizás SQL Server pueda trabajar con datos de un operador de exploración constante de manera más eficiente que con los datos almacenados en páginas de almacén de filas típicas.

Curiosamente, SQL Server elige colocar los resultados ordenados de una tabla tempdb de una sola página con datos ordenados en un carrete de tabla:

SQL Server a menudo coloca resultados para la tabla interna de una unión cruzada en un carrete de tabla, incluso si parece absurdo hacerlo. Creo que el optimizador necesita un poco de trabajo en esta área. Ejecuté la consulta con el NO_PERFORMANCE_SPOOLpara evitar el impacto en el rendimiento.

Un problema con el uso de un CTE para almacenar los datos auxiliares es que no se garantiza que los datos se ordenen. No puedo pensar por qué el optimizador elegiría no ordenarlo y en todas mis pruebas los datos se procesaron en el orden en que escribí el CTE:

Sin embargo, es mejor no correr riesgos, especialmente si hay una manera de hacerlo sin una gran sobrecarga de rendimiento. Es posible ordenar los datos en una tabla derivada agregando un TOPoperador superfluo . Por ejemplo:

(SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR)

Esa adición a la consulta debería garantizar que los resultados se devolverán en el orden correcto. Esperaba que todo este tipo tuviera un gran impacto negativo en el rendimiento. El optimizador de consultas también esperaba esto en función de los costos estimados:

Sorprendentemente, no pude observar ninguna diferencia estadísticamente significativa en el tiempo de CPU o el tiempo de ejecución con o sin un pedido explícito. En todo caso, la consulta parecía correr más rápido con el ORDER BY! No tengo explicación para este comportamiento.

La parte difícil del problema fue descubrir cómo insertar caracteres en blanco en los lugares correctos. Como se mencionó anteriormente, un simple CROSS JOINdaría como resultado datos duplicados. Sabemos que la cadena 100000000 tendrá una longitud de seis caracteres porque:

26 + 26 ^ 2 + 26 ^ 3 + 26 ^ 4 + 26 ^ 5 = 914654 <100000000

pero

26 + 26 ^ 2 + 26 ^ 3 + 26 ^ 4 + 26 ^ 5 + 26 ^ 6 = 321272406> 100000000

Por lo tanto, solo necesitamos unirnos a la letra CTE seis veces. Supongamos que nos unimos al CTE seis veces, tomamos una letra de cada CTE y las concatenamos todas juntas. Supongamos que la letra de la izquierda no está en blanco. Si alguna de las letras posteriores está en blanco, significa que la cadena tiene menos de seis caracteres, por lo que es un duplicado. Por lo tanto, podemos evitar duplicados al encontrar el primer carácter que no esté en blanco y requerir que todos los caracteres después de él tampoco estén en blanco. Elegí rastrear esto asignando una FLAGcolumna a uno de los CTE y agregando un cheque a la WHEREcláusula. Esto debería quedar más claro después de mirar la consulta. La consulta final es la siguiente:

WITH FIRST_CHAR (CHR) AS
(
    SELECT 'A'
    UNION ALL SELECT 'B'
    UNION ALL SELECT 'C'
    UNION ALL SELECT 'D'
    UNION ALL SELECT 'E'
    UNION ALL SELECT 'F'
    UNION ALL SELECT 'G'
    UNION ALL SELECT 'H'
    UNION ALL SELECT 'I'
    UNION ALL SELECT 'J'
    UNION ALL SELECT 'K'
    UNION ALL SELECT 'L'
    UNION ALL SELECT 'M'
    UNION ALL SELECT 'N'
    UNION ALL SELECT 'O'
    UNION ALL SELECT 'P'
    UNION ALL SELECT 'Q'
    UNION ALL SELECT 'R'
    UNION ALL SELECT 'S'
    UNION ALL SELECT 'T'
    UNION ALL SELECT 'U'
    UNION ALL SELECT 'V'
    UNION ALL SELECT 'W'
    UNION ALL SELECT 'X'
    UNION ALL SELECT 'Y'
    UNION ALL SELECT 'Z'
)
, ALL_CHAR (CHR, FLAG) AS
(
    SELECT '', 0 CHR
    UNION ALL SELECT 'A', 1
    UNION ALL SELECT 'B', 1
    UNION ALL SELECT 'C', 1
    UNION ALL SELECT 'D', 1
    UNION ALL SELECT 'E', 1
    UNION ALL SELECT 'F', 1
    UNION ALL SELECT 'G', 1
    UNION ALL SELECT 'H', 1
    UNION ALL SELECT 'I', 1
    UNION ALL SELECT 'J', 1
    UNION ALL SELECT 'K', 1
    UNION ALL SELECT 'L', 1
    UNION ALL SELECT 'M', 1
    UNION ALL SELECT 'N', 1
    UNION ALL SELECT 'O', 1
    UNION ALL SELECT 'P', 1
    UNION ALL SELECT 'Q', 1
    UNION ALL SELECT 'R', 1
    UNION ALL SELECT 'S', 1
    UNION ALL SELECT 'T', 1
    UNION ALL SELECT 'U', 1
    UNION ALL SELECT 'V', 1
    UNION ALL SELECT 'W', 1
    UNION ALL SELECT 'X', 1
    UNION ALL SELECT 'Y', 1
    UNION ALL SELECT 'Z', 1
)
SELECT TOP (100000000)
d6.CHR + d5.CHR + d4.CHR + d3.CHR + d2.CHR + d1.CHR
FROM (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d6
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d5
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d4
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d3
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d2
CROSS JOIN (SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR) d1
WHERE (d2.FLAG + d3.FLAG + d4.FLAG + d5.FLAG + d6.FLAG) =
    CASE 
    WHEN d6.FLAG = 1 THEN 5
    WHEN d5.FLAG = 1 THEN 4
    WHEN d4.FLAG = 1 THEN 3
    WHEN d3.FLAG = 1 THEN 2
    WHEN d2.FLAG = 1 THEN 1
    ELSE 0 END
OPTION (MAXDOP 1, FORCE ORDER, LOOP JOIN, NO_PERFORMANCE_SPOOL);

Los CTE son como se describieron anteriormente. ALL_CHARse une a cinco veces porque incluye una fila para un carácter en blanco. El carácter final de la cadena no debe estar en blanco de manera separada un CTE se define por ella, FIRST_CHAR. La columna de bandera adicional en ALL_CHARse usa para evitar duplicados como se describió anteriormente. Puede haber una forma más eficiente de hacer esta verificación, pero definitivamente hay formas más ineficientes de hacerlo. Un intento por mi parte LEN()e POWER()hizo que la consulta se ejecutara seis veces más lento que la versión actual.

Las sugerencias MAXDOP 1y FORCE ORDERson esenciales para asegurarse de que el orden se conserva en la consulta. Un plan estimado anotado podría ser útil para ver por qué las uniones están en su orden actual:

Los planes de consulta a menudo se leen de derecha a izquierda, pero las solicitudes de fila ocurren de izquierda a derecha. Idealmente, SQL Server solicitará exactamente 100 millones de filas del d1operador de exploración constante. A medida que se mueve de izquierda a derecha, espero que se soliciten menos filas de cada operador. Podemos ver esto en el plan de ejecución real . Además, a continuación se muestra una captura de pantalla de SQL Sentry Plan Explorer:

Obtuvimos exactamente 100 millones de filas de d1, lo cual es algo bueno. Tenga en cuenta que la proporción de filas entre d2 y d3 es casi exactamente 27: 1 (165336 * 27 = 4464072), lo que tiene sentido si piensa en cómo funcionará la unión cruzada. La relación de filas entre d1 y d2 es 22.4, lo que representa algo de trabajo desperdiciado. Creo que las filas adicionales provienen de duplicados (debido a los caracteres en blanco en el medio de las cadenas) que no pasan del operador de unión de bucle anidado que hace el filtrado.

La LOOP JOINsugerencia es técnicamente innecesaria porque a CROSS JOINsolo se puede implementar como una unión de bucle en SQL Server. El NO_PERFORMANCE_SPOOLes para evitar el carrete innecesario de la mesa. Omitir la sugerencia del carrete hizo que la consulta tardara 3 veces más en mi máquina.

La consulta final tiene un tiempo de CPU de alrededor de 17 segundos y un tiempo total transcurrido de 18 segundos. Eso fue al ejecutar la consulta a través de SSMS y descartar el conjunto de resultados. Estoy muy interesado en ver otros métodos para generar los datos.

Tengo una solución optimizada para obtener el código de cadena para cualquier número específico hasta 217,180,147,158 (8 caracteres). Pero no puedo vencer tu tiempo:

En mi máquina, con SQL Server 2014, su consulta tarda 18 segundos, mientras que la mía tarda 3m 46s. Ambas consultas utilizan el indicador de seguimiento no documentado 8690 porque 2014 no admite la NO_PERFORMANCE_SPOOLsugerencia.

Aquí está el código:

/* precompute offsets and powers to simplify final query */
CREATE TABLE #ExponentsLookup (
    offset          BIGINT NOT NULL,
    offset_end      BIGINT NOT NULL,
    position        INTEGER NOT NULL,
    divisor         BIGINT NOT NULL,
    shifts          BIGINT NOT NULL,
    chars           INTEGER NOT NULL,
    PRIMARY KEY(offset, offset_end, position)
);

WITH base_26_multiples AS ( 
    SELECT  number  AS exponent,
            CAST(POWER(26.0, number) AS BIGINT) AS multiple
    FROM    master.dbo.spt_values
    WHERE   [type] = 'P'
            AND number < 8
),
num_offsets AS (
    SELECT  *,
            -- The maximum posible value is 217180147159 - 1
            LEAD(offset, 1, 217180147159) OVER(
                ORDER BY exponent
            ) AS offset_end
    FROM    (
                SELECT  exponent,
                        SUM(multiple) OVER(
                            ORDER BY exponent
                        ) AS offset
                FROM    base_26_multiples
            ) x
)
INSERT INTO #ExponentsLookup(offset, offset_end, position, divisor, shifts, chars)
SELECT  ofst.offset, ofst.offset_end,
        dgt.number AS position,
        CAST(POWER(26.0, dgt.number) AS BIGINT)     AS divisor,
        CAST(POWER(256.0, dgt.number) AS BIGINT)    AS shifts,
        ofst.exponent + 1                           AS chars
FROM    num_offsets ofst
        LEFT JOIN master.dbo.spt_values dgt --> as many rows as resulting chars in string
            ON [type] = 'P'
            AND dgt.number <= ofst.exponent;

/*  Test the cases in table example */
SELECT  /*  1.- Get the base 26 digit and then shift it to align it to 8 bit boundaries
            2.- Sum the resulting values
            3.- Bias the value with a reference that represent the string 'AAAAAAAA'
            4.- Take the required chars */
        ref.[row_number],
        REVERSE(SUBSTRING(REVERSE(CAST(SUM((((ref.[row_number] - ofst.offset) / ofst.divisor) % 26) * ofst.shifts) +
            CAST(CAST('AAAAAAAA' AS BINARY(8)) AS BIGINT) AS BINARY(8))),
            1, MAX(ofst.chars))) AS string
FROM    (
            VALUES(1),(2),(25),(26),(27),(28),(51),(52),(53),(54),
            (18278),(18279),(475253),(475254),(475255),
            (100000000), (CAST(217180147158 AS BIGINT))
        ) ref([row_number])
        LEFT JOIN #ExponentsLookup ofst
            ON ofst.offset <= ref.[row_number]
            AND ofst.offset_end > ref.[row_number]
GROUP BY
        ref.[row_number]
ORDER BY
        ref.[row_number];

/*  Test with huge set  */
WITH numbers AS (
    SELECT  TOP(100000000)
            ROW_NUMBER() OVER(
                ORDER BY x1.number
            ) AS [row_number]
    FROM    master.dbo.spt_values x1
            CROSS JOIN (SELECT number FROM master.dbo.spt_values WHERE [type] = 'P' AND number < 676) x2
            CROSS JOIN (SELECT number FROM master.dbo.spt_values WHERE [type] = 'P' AND number < 676) x3
    WHERE   x1.number < 219
)
SELECT  /*  1.- Get the base 26 digit and then shift it to align it to 8 bit boundaries
            2.- Sum the resulting values
            3.- Bias the value with a reference that represent the string 'AAAAAAAA'
            4.- Take the required chars */
        ref.[row_number],
        REVERSE(SUBSTRING(REVERSE(CAST(SUM((((ref.[row_number] - ofst.offset) / ofst.divisor) % 26) * ofst.shifts) +
            CAST(CAST('AAAAAAAA' AS BINARY(8)) AS BIGINT) AS BINARY(8))),
            1, MAX(ofst.chars))) AS string
FROM    numbers ref
        LEFT JOIN #ExponentsLookup ofst
            ON ofst.offset <= ref.[row_number]
            AND ofst.offset_end > ref.[row_number]
GROUP BY
        ref.[row_number]
ORDER BY
        ref.[row_number]
OPTION (QUERYTRACEON 8690);

El truco aquí es calcular previamente dónde comienzan las diferentes permutaciones:

1. Cuando tiene que generar un único carácter, tiene 26 ^ 1 permutaciones que comienzan en 26 ^ 0.
2. Cuando tiene que generar 2 caracteres, tiene 26 ^ 2 permutaciones que comienzan en 26 ^ 0 + 26 ^ 1
3. Cuando tiene que generar 3 caracteres, tiene 26 ^ 3 permutaciones que comienzan en 26 ^ 0 + 26 ^ 1 + 26 ^ 2
4. repetir para n caracteres

El otro truco utilizado es simplemente usar la suma para llegar al valor correcto en lugar de intentar concat. Para lograr esto, simplemente desplazo los dígitos de la base 26 a la base 256 y agrego el valor ascii de 'A' para cada dígito. Entonces obtenemos la representación binaria de la cadena que estamos buscando. Después de eso, algunas manipulaciones de cadenas completan el proceso.

ok, aquí va mi último guión.

Sin bucle, sin recursividad.

Solo funciona para 6 char

El mayor inconveniente es que toma alrededor de 22 minutos por 1,00,00,000

Esta vez mi guión es muy corto.

SET NoCount on

declare @z int=26
declare @start int=@z+1 
declare @MaxLimit int=10000000

SELECT TOP (@MaxLimit) IDENTITY(int,1,1) AS N
    INTO NumbersTest1
    FROM     master.dbo.spt_values x1   
   CROSS JOIN (SELECT number FROM master.dbo.spt_values WHERE [type] = 'P' AND number < 500) x2
            CROSS JOIN (SELECT number FROM master.dbo.spt_values WHERE [type] = 'P' AND number < 500) x3
    WHERE   x1.number < 219
ALTER TABLE NumbersTest1 ADD CONSTRAINT PK_NumbersTest1 PRIMARY KEY CLUSTERED (N)


select N, strCol from NumbersTest1
cross apply
(
select 
case when IntCol6>0 then  char((IntCol6%@z)+64) else '' end 
+case when IntCol5=0 then 'Z' else isnull(char(IntCol5+64),'') end 
+case when IntCol4=0 then 'Z' else isnull(char(IntCol4+64),'') end 
+case when IntCol3=0 then 'Z' else isnull(char(IntCol3+64),'') end 
+case when IntCol2=0 then 'Z' else isnull(char(IntCol2+64),'') end 
+case when IntCol1=0 then 'Z' else isnull(char(IntCol1+64),'') end strCol
from
(
select  IntCol1,IntCol2,IntCol3,IntCol4
,case when IntCol5>0 then  IntCol5%@z else null end IntCol5

,case when IntCol5/@z>0 and  IntCol5%@z=0 then  IntCol5/@z-1 
when IntCol5/@z>0 then IntCol5/@z
else null end IntCol6
from
(
select IntCol1,IntCol2,IntCol3
,case when IntCol4>0 then  IntCol4%@z else null end IntCol4

,case when IntCol4/@z>0 and  IntCol4%@z=0 then  IntCol4/@z-1 
when IntCol4/@z>0 then IntCol4/@z
else null end IntCol5
from
(
select IntCol1,IntCol2
,case when IntCol3>0 then  IntCol3%@z else null end IntCol3
,case when IntCol3/@z>0 and  IntCol3%@z=0 then  IntCol3/@z-1 
when IntCol3/@z>0 then IntCol3/@z
else null end IntCol4

from
(
select IntCol1
,case when IntCol2>0 then  IntCol2%@z else null end IntCol2
,case when IntCol2/@z>0 and  IntCol2%@z=0 then  IntCol2/@z-1 
when IntCol2/@z>0 then IntCol2/@z
else null end IntCol3

from
(
select case when N>0 then N%@z else null end IntCol1
,case when N%@z=0 and  (N/@z)>1 then (N/@z)-1 else  (N/@z) end IntCol2 

)Lv2
)Lv3
)Lv4
)Lv5
)LV6

)ca

DROP TABLE NumbersTest1