시작하기 위해 답변을 게시하겠습니다. 내 첫 번째 생각은 각 문자에 대해 하나의 행이있는 몇 개의 도우미 테이블과 함께 중첩 루프 조인의 순서 유지 특성을 활용할 수 있어야한다는 것입니다. 까다로운 부분은 결과를 길이별로 정렬하고 중복을 피하는 방식으로 반복됩니다. ”와 함께 모두 26 대문자를 포함하는 CTE에 가입 할 때 크로스 예를 들어, 생성을 끝낼 수 'A' + '' + 'A'와 '' + 'A' + 'A'물론 같은 문자열이다.

첫 번째 결정은 도우미 데이터를 저장할 위치입니다. 임시 테이블을 사용해 보았지만 데이터가 단일 페이지에 적합하더라도 성능에 놀라 울 정도로 부정적인 영향을 미쳤습니다. 임시 테이블에는 다음 데이터가 포함되어 있습니다.

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

CTE를 사용하는 것에 비해 쿼리는 클러스터 된 테이블의 경우 3 배, 힙의 경우 4 배 더 오래 걸렸습니다. 문제는 데이터가 디스크에 있다고 생각하지 않습니다. 단일 페이지로 메모리에 읽고 전체 계획에 대해 메모리에서 처리해야합니다. SQL Server는 일반적인 행 저장소 페이지에 저장된 데이터보다 Constant Scan 연산자의 데이터를 더 효율적으로 사용할 수 있습니다.

흥미롭게도 SQL Server는 정렬 된 데이터가있는 단일 페이지 tempdb 테이블의 정렬 된 결과를 테이블 스풀에 넣도록 선택합니다.

SQL Server는 교차 조인의 내부 테이블에 대한 결과를 의미가없는 것처럼 보이더라도 테이블 스풀에 넣는 경우가 많습니다. 옵티마이 저는이 분야에서 약간의 작업이 필요하다고 생각합니다. NO_PERFORMANCE_SPOOL성능 저하를 피하기 위해 쿼리를 실행했습니다 .

CTE를 사용하여 헬퍼 데이터를 저장하는 데있어 한 가지 문제점은 데이터의 순서가 보장되지 않는다는 것입니다. 옵티마이 저가 왜 주문하지 않기로 결정했는지는 알 수 없으며 모든 테스트에서 CTE를 작성한 순서대로 데이터가 처리되었습니다.

그러나 특히 성능 오버 헤드가 크지 않은 경우에는 수행 할 수있는 기회가없는 것이 좋습니다. 불필요한 TOP연산자 를 추가하여 파생 테이블에서 데이터를 정렬 할 수 있습니다. 예를 들면 다음과 같습니다.

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

쿼리에 추가하면 결과가 올바른 순서로 반환됩니다. 모든 종류의 성능에 부정적인 영향을 미칠 것으로 예상했습니다. 쿼리 최적화 프로그램은 예상 비용을 기반으로이를 예측했습니다.

놀랍게도, 명시 적 순서의 유무에 관계없이 CPU 시간 또는 런타임에서 통계적으로 유의 한 차이를 관찰 할 수 없었습니다. 무엇이든, 쿼리는 ORDER BY! 이 동작에 대한 설명이 없습니다.

문제의 까다로운 부분은 올바른 위치에 공백 문자를 삽입하는 방법을 알아내는 것이 었습니다. 앞에서 언급했듯이 간단한 CROSS JOIN데이터는 중복됩니다. 우리는 다음과 같은 이유로 100000000 번째 문자열의 길이가 6 자라는 것을 알고 있습니다.

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

그러나

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

따라서 CTE에 6 번만 가입하면됩니다. CTE에 6 번 가입하고 각 CTE에서 한 글자를 가져 와서 모두 연결한다고 가정합니다. 가장 왼쪽의 문자가 공백이 아니라고 가정하십시오. 후속 문자가 비어 있으면 문자열의 길이가 6 자 미만이므로 중복됩니다. 따라서 공백이 아닌 첫 번째 문자를 찾아 공백이 아닌 모든 문자를 요구하여 중복을 방지 할 수 있습니다. FLAGCTE 중 하나에 열을 할당 하고 WHERE절에 검사를 추가하여 이를 추적하기로 선택했습니다 . 쿼리를 확인한 후에 더 명확해야합니다. 최종 쿼리는 다음과 같습니다.

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

CTE는 전술 한 바와 같다. ALL_CHAR빈 문자에 대한 행이 포함되어 있기 때문에 5 번 연결됩니다. 문자열의 마지막 문자는 비워 둘 수 없으므로 별도의 CTE가 정의됩니다 FIRST_CHAR. 추가 플래그 열 ALL_CHAR은 위에서 설명한대로 중복을 방지하는 데 사용됩니다. 이 검사를 수행하는 데 더 효율적인 방법이있을 수 있지만 더 비효율적 인 방법이 있습니다. 하나 개 나에 의하여 시도 LEN()하고 POWER()현재 버전보다 여섯 배 느린 쿼리 실행을했다.

MAXDOP 1와 FORCE ORDER힌트는 확인 주문이 쿼리에 보존되어 있는지 확인하는 것이 필수적이다. 주석이 달린 추정 계획은 조인이 현재 순서 인 이유를 확인하는 데 도움이 될 수 있습니다.

쿼리 계획은 종종 오른쪽에서 왼쪽으로 읽지 만 행 요청은 왼쪽에서 오른쪽으로 발생합니다. 이상적으로 SQL Server는 d1상수 스캔 연산자에게 정확히 1 억 개의 행을 요청합니다 . 왼쪽에서 오른쪽으로 이동할 때 각 연산자에서 더 적은 수의 행을 요청할 것으로 예상합니다. 우리는 이것을 실제 실행 계획 에서 볼 수 있습니다 . 또한 아래는 SQL Sentry Plan Explorer의 스크린 샷입니다.

우리는 d1에서 정확히 1 억 개의 행을 얻었습니다. d2와 d3 사이의 행 비율은 거의 정확히 27 : 1 (165336 * 27 = 4464072)이므로 크로스 조인의 작동 방식에 대해 생각하는 것이 좋습니다. d1과 d2 사이의 행 비율은 22.4이며 일부 낭비 된 작업을 나타냅니다. 여분의 행은 중복 된 것 (문자열 중간의 빈 문자로 인해)에서 나온 것으로 필터링을 수행하는 중첩 루프 조인 연산자를 지나치지 않습니다.

LOOP JOIN때문에 힌트는 기술적으로 필요하지 않습니다 CROSS JOIN만 루프로 구현 될 수는 SQL 서버에 가입 할 수 있습니다. 는 NO_PERFORMANCE_SPOOL불필요한 테이블 스풀링을 방지하는 것입니다. 스풀 힌트를 생략하면 쿼리가 컴퓨터에서 3 배 더 오래 걸렸습니다.

최종 쿼리의 CPU 시간은 약 17 초이고 총 경과 시간은 18 초입니다. SSMS를 통해 쿼리를 실행하고 결과 집합을 버릴 ​​때였습니다. 데이터를 생성하는 다른 방법을 보는 데 관심이 있습니다.

답변

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

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