优化 SQL Server 中的数字范围（间隔）搜索

Question

这个问题类似于优化 IP 范围搜索？但那个仅限于 SQL Server 2000。

假设我有 1000 万个范围临时存储在一个表中，结构和填充如下。

CREATE TABLE MyTable
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX IX1 (RangeFrom,RangeTo),
INDEX IX2 (RangeTo,RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO MyTable
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(1)
FROM   RandomNumbers 

我需要知道包含值的所有范围50,000,000。我尝试以下查询

SELECT *
FROM MyTable
WHERE 50000000 BETWEEN RangeFrom AND RangeTo

SQL Server 显示有 10,951 次逻辑读取，读取了近 500 万行以返回 12 个匹配的行。

我可以改进这个性能吗？表的任何重组或附加索引都可以。

Answer 1

与扫描一半表的非聚集索引相比，列存储在这里非常有用。非聚集列存储索引提供了大部分好处，但将有序数据插入聚集列存储索引甚至更好。

DROP TABLE IF EXISTS dbo.MyTableCCI;

CREATE TABLE dbo.MyTableCCI
(
Id        INT PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX CCI CLUSTERED COLUMNSTORE
);

INSERT INTO dbo.MyTableCCI
SELECT TOP (987654321) *
FROM dbo.MyTable
ORDER BY RangeFrom ASC
OPTION (MAXDOP 1);

根据设计，我可以在RangeFrom列上消除行组，这将消除我的行组的一半。但是由于数据的性质，我也在RangeTo列上进行了行组消除：

Table 'MyTableCCI'. Segment reads 1, segment skipped 9.

对于具有更多可变数据的较大表，有不同的方法来加载数据以保证在两列上尽可能最好地消除行组。特别是对于您的数据，查询需要 1 毫秒。

Answer 2

我能够找到一种与 N/CCI 方法相比具有竞争力的行模式方法，但您需要了解一些有关您的数据的信息。假设你有包含的差异列RangeFrom和RangeTo你索引它连同RangeFrom：

ALTER TABLE dbo.MyTableWithDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableWithDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

如果您知道 的所有不同值，DiffOfColumns那么您可以DiffOfColumns使用范围过滤器对 的每个值执行查找RangeTo以获取所有相关数据。例如，如果我们知道DiffOfColumns= 2，那么 的唯一允许值RangeFrom是 49999998、49999999 和 50000000。递归可用于获取 的所有不同值，DiffOfColumns并且它适用于您的数据集，因为它们只有 256 个。下面的查询在我的机器上大约需要 6 毫秒：

WITH RecursiveCTE
AS
(
    -- Anchor
    SELECT TOP (1)
        DiffOfColumns
    FROM dbo.MyTableWithDiff AS T
    ORDER BY
        T.DiffOfColumns

    UNION ALL

    -- Recursive
    SELECT R.DiffOfColumns
    FROM
    (
        -- Number the rows
        SELECT 
            T.DiffOfColumns,
            rn = ROW_NUMBER() OVER (
                ORDER BY T.DiffOfColumns)
        FROM dbo.MyTableWithDiff AS T
        JOIN RecursiveCTE AS R
            ON R.DiffOfColumns < T.DiffOfColumns
    ) AS R
    WHERE
        -- Only the row that sorts lowest
        R.rn = 1
)
SELECT ca.*
FROM RecursiveCTE rcte
CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableWithDiff mt
    WHERE mt.DiffOfColumns = rcte.DiffOfColumns
    AND mt.RangeFrom >= 50000000 - rcte.DiffOfColumns AND mt.RangeFrom <= 50000000
) ca
OPTION (MAXRECURSION 0);

您可以看到通常的递归部分以及每个不同值的索引查找：

这种方法的缺陷是当 的不同值太多时它开始变慢DiffOfColumns。让我们做同样的测试，但使用CRYPT_GEN_RANDOM(2)代替CRYPT_GEN_RANDOM(1)。

DROP TABLE IF EXISTS dbo.MyTableBigDiff;

CREATE TABLE dbo.MyTableBigDiff
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO dbo.MyTableBigDiff
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(2) -- note the 2
FROM   RandomNumbers;


ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableBigDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

相同的查询现在从递归部分找到 65536 行，并在我的机器上占用 823 毫秒的 CPU。有 PAGELATCH_SH 等待和其他不好的事情发生。我可以通过对 diff 值进行分桶以控制唯一值的数量并针对CROSS APPLY. 对于这个数据集，我将尝试 256 个桶：

ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns_bucket256 AS CAST(CEILING((RangeTo-RangeFrom) / 256.) AS INT);

CREATE INDEX [IXDIFF] ON dbo.MyTableBigDiff (DiffOfColumns_bucket256, RangeFrom) INCLUDE (RangeTo);

避免获得额外行的一种方法（现在我正在与舍入值而不是真实值进行比较）是通过过滤RangeTo：

CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableBigDiff mt
    WHERE mt.DiffOfColumns_bucket256 = rcte.DiffOfColumns_bucket256
    AND mt.RangeFrom >= 50000000 - (256 * rcte.DiffOfColumns_bucket256)
    AND mt.RangeFrom <= 50000000
    AND mt.RangeTo >= 50000000
) ca

完整查询现在在我的机器上需要 6 毫秒。

Answer 3

Paul White 指出了一个类似问题的答案，其中包含指向Itzik Ben Gan 的一篇有趣文章的链接。这描述了允许有效完成此操作的“静态关系间隔树”模型。

总之，此方法涉及根据行中的间隔值存储计算（“forknode”）值。在搜索与另一个范围相交的范围时，可以预先计算匹配行必须具有的可能的 forknode 值，并使用它来查找最多 31 次搜索操作的结果（以下支持范围 0 到最大有符号 32 的整数）位整数）

基于此，我重新构造了下表。

CREATE TABLE dbo.MyTable3
(
  Id        INT IDENTITY PRIMARY KEY,
  RangeFrom INT NOT NULL,
  RangeTo   INT NOT NULL,   
  node  AS RangeTo - RangeTo % POWER(2, FLOOR(LOG((RangeFrom - 1) ^ RangeTo, 2))) PERSISTED NOT NULL,
  CHECK (RangeTo > RangeFrom)
);

CREATE INDEX ix1 ON dbo.MyTable3 (node, RangeFrom) INCLUDE (RangeTo);
CREATE INDEX ix2 ON dbo.MyTable3 (node, RangeTo) INCLUDE (RangeFrom);

SET IDENTITY_INSERT MyTable3 ON

INSERT INTO MyTable3
            (Id,
             RangeFrom,
             RangeTo)
SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable

SET IDENTITY_INSERT MyTable3 OFF 

然后使用以下查询（该文章正在寻找相交区间，因此找到包含点的区间是这种情况的退化情况）

DECLARE @value INT = 50000000;

;WITH N AS
(
SELECT 30 AS Level, 
       CASE WHEN @value > POWER(2,30) THEN POWER(2,30) END AS selected_left_node, 
       CASE WHEN @value < POWER(2,30) THEN POWER(2,30) END AS selected_right_node, 
       (SIGN(@value - POWER(2,30)) * POWER(2,29)) + POWER(2,30)  AS node
UNION ALL
SELECT N.Level-1,   
       CASE WHEN @value > node THEN node END AS selected_left_node,  
       CASE WHEN @value < node THEN node END AS selected_right_node,
       (SIGN(@value - node) * POWER(2,N.Level-2)) + node  AS node
FROM N 
WHERE N.Level > 0
)
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS L
    ON I.node = L.selected_left_node
    AND I.RangeTo >= @value
    AND L.selected_left_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS R
    ON I.node = R.selected_right_node
    AND I.RangeFrom <= @value
    AND R.selected_right_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
WHERE node = @value;

1ms当所有页面都在缓存中时，这通常在我的机器上执行- 带有 IO 统计信息。

Table 'MyTable3'. Scan count 24, logical reads 72, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 4, logical reads 374, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

和计划

注意：源使用多语句 TVF 而不是递归 CTE 来让节点加入，但为了让我的答案自包含，我选择了后者。对于生产用途，我可能会使用 TVF。

Answer 4

表示范围的另一种方法是作为线上的点。

下面将所有数据迁移到一个新表中，其范围表示为geometry数据类型。

CREATE TABLE MyTable2
(
Id INT IDENTITY PRIMARY KEY,
Range GEOMETRY NOT NULL,
RangeFrom AS Range.STPointN(1).STX,
RangeTo   AS Range.STPointN(2).STX,
CHECK (Range.STNumPoints() = 2 AND Range.STPointN(1).STY = 0 AND Range.STPointN(2).STY = 0)
);

SET IDENTITY_INSERT MyTable2 ON

INSERT INTO MyTable2
            (Id,
             Range)
SELECT ID,
       geometry::STLineFromText(CONCAT('LINESTRING(', RangeFrom, ' 0, ', RangeTo, ' 0)'), 0)
FROM   MyTable

SET IDENTITY_INSERT MyTable2 OFF 


CREATE SPATIAL INDEX index_name   
ON MyTable2 ( Range )  
USING GEOMETRY_GRID  
WITH (  
BOUNDING_BOX = ( xmin=0, ymin=0, xmax=110000000, ymax=1 ),  
GRIDS = (HIGH, HIGH, HIGH, HIGH),  
CELLS_PER_OBJECT = 16); 

查找包含该值的范围的等效查询50,000,000如下。

SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable2
WHERE  Range.STContains(geometry::STPointFromText ('POINT (50000000 0)', 0)) = 1 

对此的读取显示了对10,951原始查询的改进。

Table 'MyTable2'. Scan count 0, logical reads 505, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'extended_index_1797581442_384000'. Scan count 4, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

然而，就时间流逝而言，与原版相比并没有显着的改进。典型的执行结果是 250 ms vs 252 ms。

执行计划比较复杂，如下

重写对我来说性能更好的唯一情况是使用冷缓存。

在这种情况下令人失望，很难推荐这种重写，但发布负面结果也很有用。

Answer 5

为了向我们的新机器人霸主致敬，我决定看看是否有任何新的 R 和 Python 功能可以帮助我们解决这个问题。答案是否定的，至少对于我可以工作并返回正确结果的脚本而言。如果有人有更好的知识出现，那么，请随时打我。我的价格是合理的。

为此，我设置了一个具有 4 个内核和 16 GB RAM 的 VM，认为这足以处理约 200MB 的数据集。

让我们从波士顿不存在的语言开始吧！

电阻

EXEC sp_execute_external_script 
@language = N'R', 
@script = N'
tweener = 50000000
MO = data.frame(MartinIn)
MartinOut <- subset(MO, RangeFrom <= tweener & RangeTo >= tweener, select = c("Id","RangeFrom","RangeTo"))
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

这是一个糟糕的时期。

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3219 ms,  elapsed time = 5349 ms.

该执行计划是相当无趣，虽然我不知道为什么中间操作员给我们打电话的名字。

接下来，用蜡笔编码！

Python

EXEC sp_execute_external_script 
@language = N'Python', 
@script = N'
import pandas as pd
MO = pd.DataFrame(MartinIn)
tweener = 50000000
MartinOut = MO[(MO.RangeFrom <= tweener) & (MO.RangeTo >= tweener)]
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

就在您认为它不会比 R 更糟的时候：

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3797 ms,  elapsed time = 10146 ms.

另一个满嘴脏话的执行计划：

嗯嗯嗯

到目前为止，我没有留下深刻的印象。我等不及要删除这个虚拟机了。