如何有效地搜索IP地址范围？

Question

我有一个表,其中包含IP地址范围(作为整数值)和分配给该范围的相应国家,地区和城市.它看起来如下:

CREATE TABLE [dbo].[IpToRegion]
(
    [BeginRange] [bigint] NOT NULL,
    [EndRange] [bigint] NOT NULL,
    [CountryCode] [varchar](10) NOT NULL,
    [Country] [varchar](50) NOT NULL,
    [Region] [varchar](100) NOT NULL,
    [City] [varchar](100) NOT NULL
) ON [PRIMARY]

CREATE UNIQUE CLUSTERED INDEX [ClusteredIndex-20151031-193911] ON [dbo].[IpToRegion]
(
    [BeginRange] ASC,
    [EndRange] ASC
)
GO

此表中有9.1M行.为了找到单个IP地址的位置,我首先将其转换为大型int,然后执行以下查询:

DECLARE @IPNumber BIGINT
DECLARE @IPAddress varchar(20)

Set @IPNumber = (CONVERT(bigint, PARSENAME(@IPAddress,1)) + CONVERT(bigint, PARSENAME(@IPAddress,2)) * 256 + CONVERT(bigint, PARSENAME(@IPAddress,3)) * 65536 + CONVERT(bigint, PARSENAME(@IPAddress,4)) * 16777216)

Select City + ', ' + Region + ', ' + Country
From IpToRegion 
Where @IPNumber Between BeginRange And EndRange

问题是此查询可能需要5到20秒才能执行.这是查询计划:

当然,我的问题是这个查询如何执行这么长时间？它正在对聚集索引进行搜索并返回单行.我可以尝试一些不同的索引策略.但是,在这一点上,我更好奇为什么这个查询可以表现得如此糟糕.

Answer 1

使用您拥有的索引无法有效地进行此类搜索.

如果您Index Seek在计划中查看运算符的详细信息,您会看到两个谓词.

@IPNumber >= BeginRange 
@IPNumber <= EndRange

索引有助于快速O(log(n))找到范围的开始(或结束),但是它必须检查表中其余行的第二个谓词.

查看计划中读取的实际行数.它会很大.

如果我没有弄错的话,之前有一些类似(更复杂)的问题.虽然有人问过Postgres,但这种方法也适用于SQL Server.在那个问题中,这种搜索不是一次,而是600K次.

"如何提高搜索效率"这一问题的答案取决于一些事情.首先:您能保证表中的IP范围不重叠吗？换句话说,你能保证任何搜索都会返回0或1行吗？

如果是,则向TOP(1)查询添加简单就足够了.