为charindex函数拆分/存储长字符串的最快方法

Question

我有一个 1 TB 的数字串。给定一个 12 个字符的数字序列，我想获取该序列在原始字符串（charindex函数）中的起始位置。

我已经使用 SQL Server 使用 1GB 字符串和 9 位子字符串对此进行了测试，并将字符串存储为varchar(max). Charindex需要 10 秒。将 1GB 字符串分解为 900 字节重叠块并创建一个表（StartPositionOfChunk、Chunkofstring），其中包含二进制排序规则的 chunkofstring，索引时间不到 1 秒。10GB,10 位子字符串的后一种方法将 charindex 提高到 1.5 分钟。我想找到一种更快的存储方法。

例子

数字串：0123456789 - 要搜索的子字符串 345
charindex('345','0123456789') 给出 4

方法 1：我现在可以将其存储在包含一列的 SQL Server 表 strtable 中colstr并执行：

select charindex('345',colstr) from strtable

方法2：或者我可以通过拆分原始字符串来组成一个表strtable2（pos，colstr1）：1;012 | 2;123 | 3;234 aso然后我们可以进行查询

select pos from strtable2 where colstr1='345'

方法 3：我可以通过将原始字符串拆分成更大的块来组成一个表strtable2 (pos2,colstr2) 1;01234 | 4;34567 | 7;6789然后

select pos2+charindex('345',colstr2) from strtable2 where colstr2 like '%345%'

第一种方法是最慢的。

第二种方法炸毁数据库存储大小！

方法 3：在二进制排序规则中将 colstr2 长度设置为 900 字节，对于 1GB 字符串和 9 位子字符串搜索，在此列上创建索引需要 1 秒。对于 10GB 字符串和 10 位子字符串，ist 需要 90 秒。

任何其他想法如何使它更快（也许通过使用由数字组成的字符串，长整数，......）？

始终搜索 1TB 数字字符串中的 12 位子字符串 SQL Server 2017 Developer Edition，16 核，16GB RAM。主要目标是搜索速度！10GB 字符串中的 10 位数字（用于性能测试）。

Answer 1

仅用 16GB RAM 存储和处理 1TB 数据可能被证明是一个挑战。每个内核 1GB 是相当不平衡的，尤其是对于这种工作负载。每个核心 8GB 将是一个更好的起点，更可取。

也就是说，我仍然很想尝试方法 2 的变体：

将所有可能的 12 个字符的子字符串存储bigint在聚集列存储表中（如果证明有用，则使用存档压缩）：

CREATE TABLE dbo.Search
(
    pos bigint NOT NULL,
    fragment bigint NOT NULL,

    INDEX CCS CLUSTERED COLUMNSTORE 
        WITH (DATA_COMPRESSION = COLUMNSTORE_ARCHIVE) -- optional
);

您可能必须实现某种方式将源数据增量加载到此表中。确保在完成的列存储结构中得到最大大小的行组（1,048,576 行）。请参阅数据加载指南。

您可以在未索引的行存储表中以 1048576 的倍数暂存行，然后在该表上创建聚集列存储索引，然后将结果直接切换到分区主表中。确切的方法取决于您打算如何加载数据、是否将其添加到以及您对 SQL Server 的总体熟悉程度。

这种方法可以获得非常好的性能，但与列存储一样，您需要实现有效的分区和段消除。对fragment列进行分区并按顺序构建列存储索引，同时替换键控的行存储聚集索引fragment是实现此目的的方法，如上面链接的文档中所述。这也将最大限度地减少存储需求，因为fragment相同范围内的值将存储在同一段中。这允许有效的值变基和位打包。

加载时，尝试将您在 SQL Server 中使用的字符串限制为非 LOB (max) 类型。如果您确实发现使用 LOB 最能提高吞吐量，那么通常会找到数据长度的最佳点，超过该点，性能会显着下降。

根据结构的最终大小和 I/O 子系统的速度，您可能会发现这种方法始终提供足够好的性能。增加可用内存会显着改善情况。

Answer 2

我建议使用方法 2 的风格并将搜索范围拆分为许多目标表。10000 个表是一个很好的第一次尝试。例如，如果您搜索“012345678901”，那么您的查询将查看与以“0123”开头的数据相关联的表。您总共仍会有大约一万亿行，但将数据拆分为多个表具有以下优点：

1. 所有可能的 12 位字符串现在都可以放入 INT。
2. 无论如何，为 1 TB 字符串构建更高效的搜索表示可能会很昂贵。有了许多表，您可以轻松地并行化作业，甚至可以暂时要求将更多 CPU 分配给您的 VM。
3. 您可以构建单个表作为概念证明，以确定完整字符串的查询时间和总空间要求。
4. 如果您需要进行任何类型的数据库维护，您会很高兴没有创建一个巨大的表。

在这一点上，我的主要问题是您使用压缩的行存储还是列存储。下面的代码为“0123”搜索空间创建了一个行存储表，并向其中插入了 1 亿行。如果您的字符串足够随机，那么您还可以期望每个表看到大约 1 亿行。

DROP TABLE IF EXISTS #t;

SELECT TOP (10000) 0 ID INTO #t
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.Q229892_RAW_100M_RANGE;

CREATE TABLE dbo.Q229892_RAW_100M_RANGE (
STRING_PIECE INT NOT NULL,
STR_POS BIGINT NOT NULL
);

INSERT INTO dbo.Q229892_RAW_100M_RANGE WITH (TABLOCK)
SELECT ABS(CHECKSUM(NEWID()) % 100000000),
TRY_CAST(ABS(CHECKSUM(NEWID())) AS BIGINT) * TRY_CAST(ABS(CHECKSUM(NEWID())) AS BIGINT)
FROM #t t1
CROSS JOIN #t t2
OPTION (MAXDOP 4);


DROP TABLE IF EXISTS dbo.T0123_Q229892_PAGE_COMPRESSION;

CREATE TABLE dbo.T0123_Q229892_PAGE_COMPRESSION (
    STRING_PIECE INT NOT NULL,
    STR_POS BIGINT NOT NULL,
    PRIMARY KEY (STRING_PIECE, STR_POS)
) WITH (DATA_COMPRESSION = PAGE);

INSERT INTO dbo.T0123_Q229892_PAGE_COMPRESSION WITH (TABLOCK)
SELECT STRING_PIECE, STR_POS
FROM dbo.Q229892_RAW_100M_RANGE;

坏消息是对于完整的数据集，您可能需要大约 15.4 TB。好消息是，即使缓冲区缓存中没有相关数据，查询对我来说也只需要 1 毫秒，对于与您的数据集一样大的数据集几乎总是如此。

-- 1 ms
CHECKPOINT;
DBCC DROPCLEANBUFFERS;

SELECT MIN(STR_POS)
FROM dbo.T0123_Q229892_PAGE_COMPRESSION
WHERE STRING_PIECE = 45678901; -- searching for '012345678901'

您可能可以将这些数据放在您拥有的最便宜的存储上，并且仍然看到良好的响应时间，因为查询执行的逻辑读取很少。

对于列存储，您无法查找所需的数据，而且您仍然极不可能将所有数据放入内存中，因此在查询中读取尽可能少的压缩数据非常重要。我强烈建议对您的表进行分区。一种行之有效的简单方法是使用搜索字符串的前四位数字来查找表名，然后使用后两位数字作为分区。再次使用“012345678901”，您将转到保存“0123”数据的表的分区 45。100 个分区是一个很好的数字，可以避免由太多分区引起的问题，平均每个分区将有大约 100 万行。可以放入单个行组的最大行数是 1048576，因此使用这种方法，您将执行尽可能少的 IO。

DROP TABLE IF EXISTS dbo.Q229892_RAW_1M_RANGE;

CREATE TABLE dbo.Q229892_RAW_1M_RANGE (
STRING_PIECE INT NOT NULL,
STR_POS BIGINT NOT NULL
);

INSERT INTO dbo.Q229892_RAW_1M_RANGE WITH (TABLOCK)
SELECT TOP (1000000) ABS(CHECKSUM(NEWID()) % 1000000),
TRY_CAST(ABS(CHECKSUM(NEWID())) AS BIGINT) * TRY_CAST(ABS(CHECKSUM(NEWID())) AS BIGINT)
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);



DECLARE @IntegerPartitionFunction nvarchar(max) = 
    N'CREATE PARTITION FUNCTION partition100 (tinyint) 
    AS RANGE LEFT FOR VALUES (';  
DECLARE @i int = 0;  
WHILE @i < 100
BEGIN  
SET @IntegerPartitionFunction += CAST(@i as nvarchar(10)) + N', ';  
SET @i += 1;  
END  
SET @IntegerPartitionFunction += CAST(@i as nvarchar(10)) + N');';  
EXEC sp_executesql @IntegerPartitionFunction;  
GO  

CREATE PARTITION SCHEME partition100_scheme
AS PARTITION partition100  
ALL TO ([DEFAULT]);

DROP TABLE IF EXISTS dbo.T0123_Q229892_COLUMNSTORE;

-- this table must be partitioned by PART_ID!
CREATE TABLE dbo.T0123_Q229892_COLUMNSTORE (
    PART_ID TINYINT NOT NULL,
    STRING_PIECE INT NOT NULL,
    STR_POS BIGINT NOT NULL,
    INDEX CCS CLUSTERED COLUMNSTORE
) ON partition100_scheme (PART_ID);


GO

DECLARE @part_id TINYINT = 0;
SET NOCOUNT ON;
WHILE @part_id < 100
BEGIN
    INSERT INTO dbo.T0123_Q229892_COLUMNSTORE WITH (TABLOCK)
    SELECT @part_id, STRING_PIECE, STR_POS
    FROM dbo.Q229892_RAW_1M_RANGE
    OPTION (MAXDOP 1);

    SET @part_id = @part_id + 1;
END;

GO

使用这种方法，完整的数据集将需要大约 10.9 TB。我不清楚如何使它变小。在这种情况下，搜索查询会慢一些。在我的机器上大约需要 25 毫秒，但这主要取决于 IO：

CHECKPOINT;
DBCC DROPCLEANBUFFERS;

SELECT MIN(STR_POS)
FROM dbo.T0123_Q229892_COLUMNSTORE
WHERE PART_ID = 45
AND STRING_PIECE = 678901; -- searching for '012345678901'

关于列存储方法的一个重要说明是 10.9 TB 数字是针对 100% 压缩数据的。在避免增量存储的同时有效地填充这样的表将具有挑战性。很可能在此过程中的某个时刻，您最终会在增量存储中获得未压缩的数据，这很容易需要超过用于行存储方法的 15.4 TB。