Como posso converter os primeiros 100 milhões de inteiros positivos em strings?

Your solution runs for 35 seconds on my laptop. The following code takes 26 seconds (including creating and populating the temporary tables):

Temporary tables

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;

The idea there is to pre-populate ordered combinations of up to four characters.

Main code

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 strings de 5 e 6 caracteres derivadas conforme necessário. Separar o prefixo do sufixo evita a classificação.

Plano de execução

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

A garantia é que o plano de execução entrega a semântica da consulta e a ordem de nível superior por especificação. Saber que merge join concat preserva a ordem permite que o escritor de consultas antecipe um plano de execução, mas o otimizador só entregará 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 junto com algumas tabelas auxiliares que têm uma linha para cada letra. A parte complicada seria fazer um loop de tal forma que os resultados fossem ordenados por comprimento, além de evitar duplicatas. Por exemplo, ao fazer uma junção cruzada de um CTE que inclui todas as 26 letras maiúsculas junto com '', você pode acabar gerando 'A' + '' + 'A'e '' + 'A' + 'A'que obviamente é 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 caibam 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'

Comparado ao uso de um CTE, a consulta demorou 3 vezes mais com uma tabela em cluster e 4 vezes mais com um heap. Eu não acredito que o problema é que os dados estão 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 de rowstore típicas.

Curiosamente, o SQL Server opta por colocar os resultados ordenados de uma tabela tempdb de página única 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. Acho que o otimizador precisa de um pouco de trabalho nessa área. Executei a consulta com o NO_PERFORMANCE_SPOOLpara evitar o impacto no desempenho.

Um problema com o uso de um CTE para armazenar os dados auxiliares é que não há garantia de que os dados sejam ordenados. Não consigo pensar por que o otimizador optaria por não ordená-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 fazer isso sem uma grande sobrecarga de desempenho. É possível ordenar 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 também esperava isso com base nos custos estimados:

Surpreendentemente, não pude observar nenhuma diferença estatisticamente significativa no tempo de CPU ou tempo de execução 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 era descobrir como inserir caracteres em branco nos lugares certos. Como mencionado anteriormente, um simples CROSS JOINresultaria em dados duplicados. Sabemos que a 100000000ª string 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 juntar a letra CTE seis vezes. Suponha que nos juntemos ao CTE seis vezes, pegue uma letra de cada CTE e concatene-os todos juntos. Suponha que a letra mais à esquerda não esteja em branco. Se alguma das letras subsequentes estiver em branco, isso significa que a string tem menos de seis caracteres, portanto, é uma duplicata. Portanto, podemos evitar duplicatas encontrando o primeiro caractere não em branco e exigindo que todos os caracteres depois dele também não estejam em branco. Escolhi rastrear 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 os descritos acima. ALL_CHARé unido a cinco vezes porque inclui uma linha para um caractere em branco. O caractere final na string nunca deve ficar em branco, portanto, um CTE separado é definido para ele, FIRST_CHAR. A coluna de sinalização extra em 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 fazê-lo. Uma tentativa minha LEN()e POWER()fez com que a consulta fosse seis vezes mais lenta que a versão atual.

As dicas MAXDOP 1e FORCE ORDERsão essenciais para garantir que a ordem seja preservada 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 varredura constante. À medida que você se move da esquerda para a direita, espero que menos linhas sejam solicitadas de 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 junçã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 strings) que não passam do 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 é evitar o spool de tabela desnecessário. Omitir a dica de spool fez a consulta demorar 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 por meio 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 da string para qualquer número específico até 217.180.147.158 (8 caracteres). Mas eu não posso bater o seu tempo:

Na minha máquina, com 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 dá suporte à 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é-computar onde as diferentes permutações começam:

1. Quando você tem que produzir um único caractere, você tem 26^1 permutações que começam em 26^0.
2. Quando você tem que produzir 2 caracteres, você tem 26^2 permutações que começam em 26^0 + 26^1
3. When you have to output 3 chars you have 26^3 permutations that start at 26^0 + 26^1 + 26^2
4. repeat for n chars

The other trick used is to simply use sum to get to the right value instead of trying to concat. To achieve this I simply offset the digits from base 26 to base 256 and add the ascii value of 'A' for each digit. So we obtain the binary representation of the string we're looking for. After that some string manipulations complete the process.