主页 / dba / 问题 / 173309
Accepted
Joe Obbish
Asked: 2017-05-12 04:22:51 +0800 CST

如何将前 1 亿个正整数转换为字符串？

  • 772

这有点偏离了真正的问题。如果提供上下文有帮助，则生成此数据可能有助于测试字符串处理方式的性能，生成需要在游标中对其应用某些操作的字符串，或生成敏感数据的唯一匿名名称替换。我只是对在 SQL Server 中生成数据的有效方法感兴趣，请不要问我为什么需要生成这些数据。

我将尝试从一个有点正式的定义开始。如果一个字符串仅由 A - Z 的大写字母组成，则该字符串包含在该系列中。该系列的第一项是“A”。该系列由所有有效字符串组成，这些字符串首先按长度排序，然后按典型字母顺序排序。如果字符串位于名为 的列中的表中STRING_COL，则可以在 T-SQL 中将顺序定义为ORDER BY LEN(STRING_COL) ASC, STRING_COL ASC。

要给出不太正式的定义，请查看 excel 中按字母顺序排列的列标题。该系列是相同的模式。考虑如何将整数转换为 26 进制数：

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

这个类比并不十分完美，因为“A”的行为与以十进制表示的 0 不同。下面是一个选定值的表格，希望能使它更清楚：

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

目标是编写一个SELECT查询，按上面定义的顺序返回前 100000000 个字符串。我通过在 SSMS 中运行查询并丢弃结果集而不是将其保存到表中来进行测试：

丢弃结果集

理想情况下，查询将相当有效。在这里，我将高效定义为串行查询的 cpu 时间和并行查询的运行时间。您可以使用您喜欢的任何未记录的技巧。依赖未定义或非保证的行为也可以，但如果您在回答中指出这一点，我们将不胜感激。

有哪些有效生成上述数据集的方法？Martin Smith指出，由于处理这么多行的开销，CLR 存储过程可能不是一个好的方法。

sql-server performance

3 个回答

  1. Best Answer

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

    这是四个预先计算的表的简单保序并集*，根据需要导出 5 个字符和 6 个字符的字符串。将前缀与后缀分开可以避免排序。

    执行计划

    1亿行

    * 上面的 SQL 中没有任何内容直接指定保序联合。优化器选择具有与 SQL 查询规范匹配的属性的物理运算符，包括顶级排序依据。在这里，它选择由 merge join 物理运算符实现的串联以避免排序。

    保证是执行计划按规范传递查询语义和顶级顺序。知道 merge join concat 保留顺序允许查询编写者预测执行计划，但优化器只会在预期有效时交付。

    • 8

  2. 我将发布一个答案以开始。我的第一个想法是，应该可以利用嵌套循环连接的顺序保持特性以及一些每个字母一行的辅助表。棘手的部分将以这样一种方式循环，即结果按长度排序并避免重复。例如，当交叉连接包含所有 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 个字符串的长度为六个字符，因为：

    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。假设我们六次加入​​ CTE，从每个 CTE 中获取一个字母，并将它们连接在一起。假设最左边的字母不是空白。如果任何后续字母为空，则表示该字符串的长度少于六个字符，因此它是重复的。因此，我们可以通过找到第一个非空白字符并要求其后的所有字符也不是空白来防止重复。我选择通过FLAG为其中一个 CTE 分配一列并向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连接到五次，因为它包含一个空白字符行。字符串中的最后一个字符绝不能为空，因此为其定义了一个单独的 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 Server 中只能作为循环连接来实现。这NO_PERFORMANCE_SPOOL是为了防止不必要的表假脱机。省略假脱机提示会使查询在我的机器上花费 3 倍的时间。

    最终查询的 CPU 时间约为 17 秒，总耗时为 18 秒。那是在通过 SSMS 运行查询并丢弃结果集时。我对查看其他生成数据的方法非常感兴趣。

    • 6

  3. 我有一个优化的解决方案，可以获取最多 217,180,147,158（8 个字符）的任何特定数字的字符串代码。但我不能打败你的时间：

    在我的机器上，使用 SQL Server 2014，你的查询需要 18 秒，而我的需要 3m 46s。这两个查询都使用未记录的跟踪标志 8690，因为 2014 不支持该NO_PERFORMANCE_SPOOL提示。

    这是代码：

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

    这里的技巧是预先计算不同排列的开始位置：

    1. 当您必须输出单个字符时，您有 26^1 个从 26^0 开始的排列。
    2. 当您必须输出 2 个字符时，您有 26^2 个从 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.

    • 2

相关问题