Como posso converter os primeiros 100 milhões de inteiros positivos em seqüências de caracteres?

Isso é um pouco de desvio do problema real. Se o fornecimento de contexto ajudar, a geração desses dados poderá ser útil para as formas de teste de desempenho de processamento de strings, para gerar strings que precisam ter alguma operação aplicada a eles dentro de um cursor ou para gerar substituições de nomes anônimos exclusivos para dados confidenciais. Estou interessado apenas em maneiras eficientes de gerar os dados nos SQL Servers. Por favor, não pergunte por que preciso gerar esses dados.

Vou tentar começar com uma definição um pouco formal. Uma sequência será incluída na série se ela consistir apenas de letras maiúsculas de A a Z. O primeiro termo da série é "A". A série consiste em todas as cadeias válidas classificadas por comprimento primeiro e ordem alfabética típica segundo. Se as seqüências estivessem em uma tabela em uma coluna chamada STRING_COL, a ordem poderia ser definida no T-SQL como ORDER BY LEN(STRING_COL) ASC, STRING_COL ASC.

Para dar uma definição menos formal, consulte os cabeçalhos das colunas alfabéticas no excel. A série é o mesmo padrão. Considere como você pode converter um número inteiro em um número base 26:

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

A analogia não é perfeita, porque "A" se comporta de maneira diferente de 0 na base dez. Abaixo está uma tabela de valores selecionados que esperamos tornar mais claro:

╔════════════╦════════╗
║ 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 ║
╚════════════╩════════╝

O objetivo é escrever uma SELECTconsulta que retorne as primeiras 100000000 strings na ordem definida acima. Fiz meus testes executando consultas no SSMS com o conjunto de resultados descartado em vez de salvá-lo em uma tabela:

Idealmente, a consulta será razoavelmente eficiente. Aqui, estou definindo eficiente como tempo da CPU para uma consulta serial e tempo decorrido para uma consulta paralela. Você pode usar os truques não documentados que desejar. Confiar em um comportamento indefinido ou não garantido também é bom, mas seria apreciado se você mencionar isso em sua resposta.

Quais são alguns métodos para gerar eficientemente o conjunto de dados descrito acima? Martin Smith apontou que um procedimento armazenado CLR provavelmente não é uma boa abordagem devido à sobrecarga de processamento de tantas linhas.

Sua solução é executada por 35 segundos no meu laptop. O código a seguir leva 26 segundos (incluindo a criação e o preenchimento de tabelas temporárias):

Tabelas temporárias

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;

A idéia é preencher previamente as combinações ordenadas de até quatro 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);

Essa é uma união simples de preservação de ordem * das quatro tabelas pré-calculadas, com sequências de 5 e 6 caracteres, conforme necessário. A separação do prefixo do sufixo evita a classificação.

Plano de execução

* Não há nada no SQL acima que especifique diretamente uma união de preservação de pedidos . O otimizador escolhe operadores físicos com propriedades que correspondem à especificação de consulta SQL, incluindo a ordem de nível superior por. Aqui, ele escolhe a concatenação implementada pelo operador físico de junção de mesclagem para evitar a classificação.

A garantia é que o plano de execução entregue a consulta semântica e ordem de nível superior por especificação. Saber que a junção de mesclagem concat preserva a ordem permite que o gravador de consultas preveja um plano de execução, mas o otimizador será entregue apenas se a expectativa for válida.

Vou postar uma resposta para começar. Meu primeiro pensamento foi que deveria ser possível tirar proveito da natureza de preservação de ordem de uma junção de loop aninhada, juntamente com algumas tabelas auxiliares que possuem uma linha para cada letra. A parte complicada seria fazer um loop de tal maneira que os resultados fossem ordenados por comprimento, além de evitar duplicatas. Por exemplo, ao ingressar em uma CTE que inclui todas as 26 letras maiúsculas junto com '', você pode acabar gerando 'A' + '' + 'A'e, '' + 'A' + 'A'é claro, a mesma string.

A primeira decisão foi onde armazenar os dados auxiliares. Tentei usar uma tabela temporária, mas isso teve um impacto surpreendentemente negativo no desempenho, mesmo que os dados se encaixem em uma única página. A tabela temporária continha os dados abaixo:

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

Comparada ao uso de um CTE, a consulta demorou 3 vezes mais com uma tabela em cluster e 4X mais com uma pilha. Não acredito que o problema seja que os dados estejam no disco. Ele deve ser lido na memória como uma única página e processado na memória para todo o plano. Talvez o SQL Server possa trabalhar com dados de um operador Constant Scan com mais eficiência do que com dados armazenados em páginas típicas de armazenamento de linhas.

Curiosamente, o SQL Server escolhe colocar os resultados ordenados de uma única tabela tempdb de página com dados ordenados em um spool de tabela:

O SQL Server geralmente coloca os resultados da tabela interna de uma junção cruzada em um spool de tabela, mesmo que pareça absurdo fazê-lo. Eu acho que o otimizador precisa de um pouco de trabalho nessa área. Eu executei a consulta com o NO_PERFORMANCE_SPOOLpara evitar o impacto no desempenho.

Um problema ao usar um CTE para armazenar os dados auxiliares é que não é garantido que os dados sejam solicitados. Não consigo pensar por que o otimizador escolheria não solicitá-lo e, em todos os meus testes, os dados foram processados ​​na ordem em que escrevi o CTE:

No entanto, é melhor não arriscar, especialmente se houver uma maneira de fazê-lo sem uma grande sobrecarga de desempenho. É possível solicitar os dados em uma tabela derivada adicionando um TOPoperador supérfluo . Por exemplo:

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

Essa adição à consulta deve garantir que os resultados sejam retornados na ordem correta. Eu esperava que todos os tipos tivessem um grande impacto negativo no desempenho. O otimizador de consultas esperava isso também com base nos custos estimados:

Surpreendentemente, não pude observar nenhuma diferença estatisticamente significante no tempo ou no tempo de execução da CPU, com ou sem ordenação explícita. Se alguma coisa, a consulta parecia correr mais rápido com o ORDER BY! Não tenho explicação para esse comportamento.

A parte complicada do problema foi descobrir como inserir caracteres em branco nos lugares certos. Como mencionado anteriormente, um simples CROSS JOINresultaria em dados duplicados. Sabemos que a sequência 100000000 terá um comprimento de seis caracteres porque:

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

mas

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

Portanto, só precisamos aderir à carta CTE seis vezes. Suponha que nos juntemos ao CTE seis vezes, pegue uma letra de cada CTE e concatene-as todas juntas. Suponha que a letra mais à esquerda não esteja em branco. Se alguma das letras subseqüentes estiver em branco, isso significa que a cadeia tem menos de seis caracteres e, portanto, é uma duplicata. Portanto, podemos evitar duplicatas localizando o primeiro caractere que não está em branco e exigindo todos os caracteres depois que ele também não estiver em branco. Eu escolhi acompanhar isso atribuindo uma FLAGcoluna a um dos CTEs e adicionando uma verificação à WHEREcláusula. Isso deve ficar mais claro depois de analisar a consulta. A consulta final é a seguinte:

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

Os CTEs são como descritos acima. ALL_CHARé associado a cinco vezes porque inclui uma linha para um caractere em branco. O caractere final da string nunca deve ficar em branco, para que um CTE separado seja definido para ele FIRST_CHAR. A coluna de sinalizador extra ALL_CHARé usada para evitar duplicatas, conforme descrito acima. Pode haver uma maneira mais eficiente de fazer essa verificação, mas definitivamente existem maneiras mais ineficientes de fazer isso. Uma tentativa minha feita LEN()e POWER()executada a consulta seis vezes mais lenta que a versão atual.

As dicas MAXDOP 1e FORCE ORDERsão essenciais para garantir que o pedido seja preservado na consulta. Um plano estimado anotado pode ser útil para ver por que as junções estão na ordem atual:

Os planos de consulta geralmente são lidos da direita para a esquerda, mas as solicitações de linha acontecem da esquerda para a direita. Idealmente, o SQL Server solicitará exatamente 100 milhões de linhas do d1operador de verificação constante. Conforme você se move da esquerda para a direita, espero que menos linhas sejam solicitadas a cada operador. Podemos ver isso no plano de execução real . Além disso, abaixo está uma captura de tela do SQL Sentry Plan Explorer:

Temos exatamente 100 milhões de linhas de d1, o que é uma coisa boa. Observe que a proporção de linhas entre d2 e d3 é quase exatamente 27: 1 (165336 * 27 = 4464072), o que faz sentido se você pensar em como a união cruzada funcionará. A proporção de linhas entre d1 e d2 é 22,4, o que representa algum trabalho desperdiçado. Eu acredito que as linhas extras são de duplicatas (devido aos caracteres em branco no meio das cadeias) que não passam pelo operador de junção de loop aninhado que faz a filtragem.

A LOOP JOINdica é tecnicamente desnecessária porque a CROSS JOINsó pode ser implementada como uma junção de loop no SQL Server. O NO_PERFORMANCE_SPOOLobjetivo é impedir o spool desnecessário da tabela. Omitir a dica do spool fez com que a consulta demorasse 3 vezes mais na minha máquina.

A consulta final tem um tempo de CPU de cerca de 17 segundos e um tempo total decorrido de 18 segundos. Isso foi ao executar a consulta através do SSMS e descartar o conjunto de resultados. Estou muito interessado em ver outros métodos de geração de dados.

Eu tenho uma solução otimizada para obter o código de seqüência de caracteres para qualquer número específico até 217.180.147.158 (8 caracteres). Mas não posso vencer o seu tempo:

Na minha máquina, com o SQL Server 2014, sua consulta leva 18 segundos, enquanto a minha leva 3m 46s. Ambas as consultas usam o sinalizador de rastreamento não documentado 8690 porque 2014 não suporta a NO_PERFORMANCE_SPOOLdica.

Aqui está o 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);

O truque aqui é pré-calcular onde começam as diferentes permutações:

1. Quando você precisa gerar um único caractere, possui 26 ^ 1 permutações que começam em 26 ^ 0.
2. Quando você precisa gerar 2 caracteres, possui 26 ^ 2 permutações que começam em 26 ^ 0 + 26 ^ 1
3. Quando você precisa gerar 3 caracteres, possui 26 ^ 3 permutações que começam em 26 ^ 0 + 26 ^ 1 + 26 ^ 2
4. repita para n caracteres

O outro truque usado é simplesmente usar soma para obter o valor certo em vez de tentar concat. Para conseguir isso, basta deslocar os dígitos da base 26 para a base 256 e adicionar o valor ASCII de 'A' para cada dígito. Então, obtemos a representação binária da string que estamos procurando. Depois disso, algumas manipulações de strings concluem o processo.

ok, aqui vai meu último script.

Sem loop, sem recursividade.

Funciona apenas para 6 caracteres

Maior desvantagem é levar cerca de 22 min para 1,00,00,000

Desta vez, meu script é muito curto.

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