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

Question

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

Joe*_*ish 14 performance sql-server query-performance

这有点偏离了真正的问题。如果提供上下文有帮助，则生成此数据对于处理字符串的性能测试方法、生成需要在游标内对其应用某些操作的字符串或为敏感数据生成唯一的匿名名称替换可能很有用。我只是对在 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 中的 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 ?
???????????????????????

Run Code Online (Sandbox Code Playgroud)

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

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

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

Answer 1

Pau*_*ite 8

您的解决方案在我的笔记本电脑上运行了35 秒。以下代码需要26 秒（包括创建和填充临时表）：

临时表

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;

Run Code Online (Sandbox Code Playgroud)

那里的想法是预先填充最多四个字符的有序组合。

主要代码

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

Run Code Online (Sandbox Code Playgroud)

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

执行计划

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

保证是执行计划按规范提供查询语义和顶级顺序。知道合并连接 concat 保留顺序允许查询编写器预测执行计划，但优化器只会在期望有效时交付。

Answer 2

Joe*_*ish 6

我会发布一个答案以开始使用。我的第一个想法是，应该可以利用嵌套循环连接的顺序保留特性以及一些每个字母一行的帮助表。棘手的部分将以这样一种方式循环，即结果按长度排序并避免重复。例如，当交叉连接包含所有 26 个大写字母和 '' 的 CTE 时，您最终可以生成'A' + '' + 'A'并且'' + 'A' + 'A'这当然是相同的字符串。

第一个决定是在哪里存储帮助程序数据。我尝试使用临时表，但这对性能产生了令人惊讶的负面影响，即使数据适合单个页面。临时表包含以下数据：

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

Run Code Online (Sandbox Code Playgroud)

与使用 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)

Run Code Online (Sandbox Code Playgroud)

对查询的添加应该保证结果将以正确的顺序返回。我预计所有这些都会对性能产生很大的负面影响。查询优化器也根据估计的成本预期了这一点：

非常令人惊讶的是，无论是否有显式排序，我都无法观察到 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 六次。假设我们加入 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);

Run Code Online (Sandbox Code Playgroud)

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提示在技术上是不必要的，因为 aCROSS JOIN只能作为 SQL Server 中的循环连接来实现。这NO_PERFORMANCE_SPOOL是为了防止不必要的表假脱机。省略假脱机提示使查询在我的机器上花费了 3 倍的时间。

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

归档时间：	8 年，4 月前
查看次数：	833 次
最近记录：	7 年，11 月前