使用 sql 在现有整数子集中不存在的范围内查找下一个可用整数
With sql find next available integer within range that is not present in existing integer subset(s)
问题陈述：
given a range x -> y of unsigned integers
where x and y are both in the range 0 -> 2n
and n is 0 -> 32 (or 64 in alternate cases)
find the minimum available value
not equal to x or y
that is not in an existing set
where existing sets are arbitrary subsets of x -> y
我正在为数据库中的 IPv4 和 IPv6 子网建模。每个子网都由其起始地址和结束地址定义（我通过业务规则确保范围的完整性）。因为 IPv6 太大而无法存储在 bigint 数据类型中，我们将 IP 地址存储为 binary(4) 或 binary(16).
关联数据存储在subnet、dhcp_range和ip_address tables:
- 子网：
子网范围由开始和结束 IP 地址定义，并存储在
subnet table 中。子网范围的大小始终为 2n（根据 CIDR / 网络掩码的定义）。
- IP:
一个子网有
0..* 个 IP 地址存储在 ip_address table 中。 IP 地址必须介于起始地址和结束地址之间，但不等于其关联子网定义的范围。
- DHCP 范围:
一个子网有
0..* 个 DHCP 范围存储在 dhcp_range table 中。与子网类似，每个 DHCP 范围都定义了一个开始地址和结束地址。 DHCP 范围受关联子网范围的限制。 DHCP 范围彼此不重叠。
我要确定的是子网的下一个可用 IP：
- 即未已分配（不在IP地址table中）
- 不在 DHCP 范围内
- 和不等于子网范围的开始或结束地址。
我正在寻找找到最小可用地址或所有可用地址的解决方案。
我最初的想法是生成受子网范围限制的可能地址（数字）范围，然后根据使用的集合删除地址：
declare @subnet_sk int = 42
;with
address_range as (
select cast(ipv4_begin as bigint) as available_address
,cast(ipv4_end as bigint) as end_address, subnet_sk
from subnet s
where subnet_sk = @subnet_sk
union all
select available_address + 1, end_address, subnet_sk
from address_range
where available_address + 1 <= end_address
),
assigned_addresses as (
select ip.[address]
,subnet_sk
from ip_address ip
where ip.subnet_sk = @subnet_sk
and ip.address_family = 'InterNetwork'),
dhcp_ranges as (
select dhcp.begin_address
,dhcp.end_address
,subnet_sk
from dhcp_range dhcp
where dhcp.subnet_sk = @subnet_sk
and dhcp.address_family = 'InterNetwork')
select distinct ar.available_address
from address_range ar
join dhcp_ranges dhcp
on ar.available_address
not between dhcp.begin_address
and dhcp.end_address
left join assigned_addresses aa
on ar.available_address = aa.[address]
join subnet s
on ar.available_address != s.ipv4_begin
and ar.available_address != s.ipv4_end
where aa.[address] is null
and s.subnet_sk = @subnet_sk
order by available_address
option (MAXRECURSION 32767)
上述查询使用了递归 CTE，并不适用于所有数据排列。递归 CTE 很麻烦，因为它的最大大小被限制为 32,767（比潜在的范围大小小得多）并且非常有可能变得非常慢。我可能可以解决递归 CTE 的问题，但查询在以下情况下失败：
- 当没有分配 IP 地址或 DHCP 范围时：它return什么都没有
应该 return 子网范围 定义的所有 IP 地址
- 当分配了多个 DHCP 范围时：returns IPs inside DHCP ranges
为了帮助解决问题，我创建了一个 SQL Fiddle with three subnets; each with a different characteristic: chopped up, empty, or mostly contiguous. The above query and the setup in the fiddle both work for the mostly contiguous subnet, but fails for the others. There is also a GitHub Gist of the schema and example data。
我已经努力生成具有递归和堆叠 CTE 的数字序列，但如上所述，恐怕它们的性能会很差，并且在人为限制递归 CTE 的情况下。 Aaron Bertrand details some alternatives to CTEs in his series Generate a set or sequence without loops. Sadly the dataset is too large for a numbers table as creating one just for the IPv4 address space would require 32 gigabytes of disk space (SQL Server stores bigint values in 8 bytes)。我更喜欢动态生成序列，但还没有想出一个好的方法。
或者，我试图通过查看我知道要使用的地址来为我的查询设置种子：
declare @subnet_sk int = 1
select unassigned_range.*
from (select cast(l.address as bigint) + 1 as start
,min(cast(fr.address as bigint)) - 1 as stop
from ip_address as l
left join ip_address as r on l.address = r.address - 1
left join ip_address as fr on l.address < fr.address
where r.address is null and fr.address is not null
and l.subnet_sk = @subnet_sk
group by l.address, r.address) as unassigned_range
join dhcp_range dhcp
on unassigned_range.start
not between cast(dhcp.begin_address as bigint)
and cast(dhcp.end_address as bigint)
and unassigned_range.stop
not between cast(dhcp.begin_address as bigint)
and cast(dhcp.end_address as bigint)
where dhcp.subnet_sk = @subnet_sk
遗憾的是，当 ip_address 或 dhcp_range table 中没有任何内容时，上述查询不起作用。更糟糕的是，由于它不知道子网范围的边界，因此 dhcp_range 朝向子网范围的上限将人为地限制 returned 的内容，因为查询不能 return 行来自空 space 在边缘。表现也不突出。
使用 SQL 或 TSQL 如何确定受其他范围限制的任意整数范围内的下一个最小可用整数值？
经过深思熟虑，我相信像这样简单的查询就可以了：
with a as(
-- next ip address
select n.next_address, i.subnet_sk
from ip_address i
CROSS APPLY (SELECT convert(binary(4), convert(bigint, i.address) + 1) AS next_address) as n
where n.next_address NOT IN (SELECT address FROM ip_address)
AND EXISTS (SELECT 1 FROM subnet s WHERE s.subnet_sk = i.subnet_sk and n.next_address > s.ipv4_begin and n.next_address < s.ipv4_end)
UNION -- use UNION here, not UNION ALL to remove duplicates
-- first ip address for completely unassigned subnets
SELECT next_address, subnet_sk
FROM subnet
CROSS APPLY (SELECT convert(binary(4), convert(bigint, ipv4_begin) + 1) AS next_address) n
where n.next_address NOT IN (SELECT address FROM ip_address)
UNION -- use UNION here, not UNION ALL to remove duplicates
-- next ip address from dhcp ranges
SELECT next_address, subnet_sk
FROM dhcp_range
CROSS APPLY (SELECT convert(binary(4), convert(bigint, end_address) + 1) AS next_address) n
where n.next_address NOT IN (SELECT address FROM ip_address)
)
SELECT min(next_address), subnet_sk
FROM a WHERE NOT exists(SELECT 1 FROM dhcp_range dhcp
WHERE a.subnet_sk = dhcp.subnet_sk and a.next_address
between dhcp.begin_address
and dhcp.end_address)
GROUP BY subnet_sk
它适用于 IPV4，但可以轻松扩展到 IPV6
每个子网的结果：
subnet_sk
---------- -----------
0xAC101129 1
0xC0A81B1F 2
0xC0A8160C 3
(3 row(s) affected)
我觉得应该很快。请查收
我不太清楚你的数据到底是什么样的。问题陈述虽然表述得很好，但似乎与查询关系不大。
让我假设 dhcp_range 有数据。您想要的查询是：
SELECT COALESCE(MIN(dr.end_address) + 1, 0)
FROM dhcp_range dr
WHERE NOT EXISTS (SELECT 1
FROM dhcp_range dr2
WHERE dr.end_address + 1 BETWEEN dr.start_address AND dr.end_address
);
在这种情况下不需要递归，因为我们有 LEAD 函数。
我会从"gaps"和"islands"的角度思考问题。
我会首先关注 IPv4，因为用它们做算术更容易，但 IPv6 的想法是一样的，最后我会展示一个通用的解决方案。
首先，我们有所有可能的 IP：从 0x00000000 到 0xFFFFFFFF。
在此范围内有 "islands" 由 dhcp_range 中的范围（含）定义：dhcp_range.begin_address, dhcp_range.end_address。您可以将分配的 IP 地址列表视为另一组岛屿，每个岛屿都有一个元素：ip_address.address, ip_address.address。最后，子网本身是两个孤岛：0x00000000, subnet.ipv4_begin 和 subnet.ipv4_end, 0xFFFFFFFF。
我们知道这些岛屿 不 重叠，这让我们的生活更轻松。岛屿可以彼此完美相邻。例如，当您连续分配的 IP 地址很少时，它们之间的差距为零。
在所有这些岛中，我们需要找到第一个间隙，它至少有一个元素，即非零间隙，即下一个岛在前一个岛结束后的某个距离处开始。
因此，我们将使用 UNION（CTE_Islands）将所有岛屿放在一起，然后按照 end_address（或 begin_address）的顺序遍历所有岛屿，使用上面有索引的字段）并使用 LEAD 向前看并获取下一个岛屿的起始地址。最后我们将有一个 table，其中每一行都有当前岛屿的 end_address 和下一个岛屿的 begin_address (CTE_Diff)。如果它们之间的差异大于一，则意味着 "gap" 足够宽，我们将 return 当前岛屿的 end_address 加 1。
给定子网的第一个可用 IP 地址
DECLARE @ParamSubnet_sk int = 1;
WITH
CTE_Islands
AS
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
)
,CTE_Diff
AS
(
SELECT
begin_address
, end_address
--, LEAD(begin_address) OVER(ORDER BY end_address) AS BeginNextIsland
, LEAD(begin_address) OVER(ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT TOP(1)
CAST(end_address + 1 AS varbinary(4)) AS NextAvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
ORDER BY end_address;
如果至少有一个可用的 IP 地址，结果集将包含一行，如果没有可用的 IP 地址，则结果集将完全不包含行。
For parameter 1 result is `0xAC101129`.
For parameter 2 result is `0xC0A81B1F`.
For parameter 3 result is `0xC0A8160C`.
这里是link到SQLFiddle。它不适用于参数，所以我在那里硬编码 1 。在 UNION 中将其更改为其他子网 ID（2 或 3）以尝试其他子网。此外，它没有在 varbinary 中正确显示结果，所以我将其保留为 bigint。例如，使用 windows 计算器将其转换为十六进制以验证结果。
如果您不通过 TOP(1) 将结果限制为第一个间隙，您将获得所有可用 IP 范围（间隙）的列表。
给定子网的所有可用 IP 地址范围列表
DECLARE @ParamSubnet_sk int = 1;
WITH
CTE_Islands
AS
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
)
,CTE_Diff
AS
(
SELECT
begin_address
, end_address
, LEAD(begin_address) OVER(ORDER BY end_address) AS BeginNextIsland
, LEAD(begin_address) OVER(ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT
CAST(end_address + 1 AS varbinary(4)) AS begin_range_AvailableIPAddress
,CAST(BeginNextIsland - 1 AS varbinary(4)) AS end_range_AvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
ORDER BY end_address;
结果。 SQL Fiddle 结果为简单的 bigint，不是十六进制，并且参数 ID 是硬编码的。
Result set for ID = 1
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xAC101129 0xAC10112E
Result set for ID = 2
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xC0A81B1F 0xC0A81B1F
0xC0A81B22 0xC0A81B28
0xC0A81BFA 0xC0A81BFE
Result set for ID = 3
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xC0A8160C 0xC0A8160C
0xC0A816FE 0xC0A816FE
每个子网的第一个可用IP地址
扩展查询和 return 所有子网的第一个可用 IP 地址很容易，而不是指定一个特定的子网。使用 CROSS APPLY 获取每个子网的岛屿列表，然后将 PARTITION BY subnet_sk 添加到 LEAD 函数中。
WITH
CTE_Islands
AS
(
SELECT
subnet_sk
, begin_address
, end_address
FROM
subnet AS Main
CROSS APPLY
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE dhcp_range.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE ip_address.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet.subnet_sk = Main.subnet_sk
) AS CA
)
,CTE_Diff
AS
(
SELECT
subnet_sk
, begin_address
, end_address
, LEAD(begin_address) OVER(PARTITION BY subnet_sk ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT
subnet_sk
, CAST(MIN(end_address) + 1 as varbinary(4)) AS NextAvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
GROUP BY subnet_sk
结果集
subnet_sk NextAvailableIPAddress
1 0xAC101129
2 0xC0A81B1F
3 0xC0A8160C
这里是SQLFiddle。我不得不在 SQL Fiddle 中删除对 varbinary 的转换，因为它显示的结果不正确。
IPv4 和 IPv6 通用解决方案
所有子网的所有可用 IP 地址范围
SQL Fiddle with sample IPv4 and IPv6 data, functions and final query
您的 IPv6 示例数据不太正确 - 子网的末尾 0xFC00000000000000FFFFFFFFFFFFFFFF 小于您的 dhcp 范围，因此我将其更改为 0xFC0001066800000000000000FFFFFFFF。此外，您在同一子网中同时拥有 IPv4 和 IPv6，处理起来很麻烦。为了这个例子，我稍微改变了你的模式 - 而不是在 subnet 中有明确的 ipv4_begin / end 和 ipv6_begin / end 我只是 ip_begin / end as varbinary(16)（与您的其他 table 相同）。我也删除了 address_family，否则它对于 SQL Fiddle.
来说太大了
算术函数
为了使其适用于 IPv6，我们需要弄清楚如何 add/subtract 1 to/from binary(16)。我会为它制作 CLR 函数。如果您不允许启用 CLR，则可以通过标准 T-SQL。我创建了两个 return 和 table 的函数，而不是标量，因为这样它们可以被优化器内联。我想做一个通用的解决方案，所以该函数将接受 varbinary(16) 并适用于 IPv4 和 IPv6。
这里是 T-SQL 函数，将 varbinary(16) 递增 1。如果参数不是 16 字节长，我假设它是 IPv4，只需将其转换为 bigint 以添加 1，然后返回 binary。否则，我将 binary(16) 分成两部分，每部分长 8 个字节，然后将它们转换为 bigint。 bigint 是有符号的，但我们需要无符号增量，所以我们需要检查一些情况。
else 部分是最常见的 - 我们只需将低部分加一并将结果附加到原始高部分。
如果低位部分是0xFFFFFFFFFFFFFFFF，那么我们将低位部分设置为0x0000000000000000并保留标志位，即高位部分加1。
如果低部分是 0x7FFFFFFFFFFFFFFF，那么我们将低部分显式设置为 0x8000000000000000，因为尝试增加此 bigint 值会导致溢出。
如果整数是 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 我们将结果设置为 0x00000000000000000000000000000000.
减一函数类似
CREATE FUNCTION [dbo].[BinaryInc](@src varbinary(16))
RETURNS TABLE AS
RETURN
SELECT
CASE WHEN DATALENGTH(@src) = 16
THEN
-- Increment IPv6 by splitting it into two bigints 8 bytes each and then concatenating them
CASE
WHEN @src = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
THEN 0x00000000000000000000000000000000
WHEN SUBSTRING(@src, 9, 8) = 0x7FFFFFFFFFFFFFFF
THEN SUBSTRING(@src, 1, 8) + 0x8000000000000000
WHEN SUBSTRING(@src, 9, 8) = 0xFFFFFFFFFFFFFFFF
THEN CAST(CAST(SUBSTRING(@src, 1, 8) AS bigint) + 1 AS binary(8)) + 0x0000000000000000
ELSE SUBSTRING(@src, 1, 8) + CAST(CAST(SUBSTRING(@src, 9, 8) AS bigint) + 1 AS binary(8))
END
ELSE
-- Increment IPv4 by converting it into 8 byte bigint and then back into 4 bytes binary
CAST(CAST(CAST(@src AS bigint) + 1 AS binary(4)) AS varbinary(16))
END AS Result
;
GO
CREATE FUNCTION [dbo].[BinaryDec](@src varbinary(16))
RETURNS TABLE AS
RETURN
SELECT
CASE WHEN DATALENGTH(@src) = 16
THEN
-- Decrement IPv6 by splitting it into two bigints 8 bytes each and then concatenating them
CASE
WHEN @src = 0x00000000000000000000000000000000
THEN 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
WHEN SUBSTRING(@src, 9, 8) = 0x8000000000000000
THEN SUBSTRING(@src, 1, 8) + 0x7FFFFFFFFFFFFFFF
WHEN SUBSTRING(@src, 9, 8) = 0x0000000000000000
THEN CAST(CAST(SUBSTRING(@src, 1, 8) AS bigint) - 1 AS binary(8)) + 0xFFFFFFFFFFFFFFFF
ELSE SUBSTRING(@src, 1, 8) + CAST(CAST(SUBSTRING(@src, 9, 8) AS bigint) - 1 AS binary(8))
END
ELSE
-- Decrement IPv4 by converting it into 8 byte bigint and then back into 4 bytes binary
CAST(CAST(CAST(@src AS bigint) - 1 AS binary(4)) AS varbinary(16))
END AS Result
;
GO
所有子网的所有可用 IP 地址范围
WITH
CTE_Islands
AS
(
SELECT subnet_sk, begin_address, end_address
FROM dhcp_range
UNION ALL
SELECT subnet_sk, address AS begin_address, address AS end_address
FROM ip_address
UNION ALL
SELECT subnet_sk, SUBSTRING(0x00000000000000000000000000000000, 1, DATALENGTH(ip_begin)) AS begin_address, ip_begin AS end_address
FROM subnet
UNION ALL
SELECT subnet_sk, ip_end AS begin_address, SUBSTRING(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, 1, DATALENGTH(ip_end)) AS end_address
FROM subnet
)
,CTE_Gaps
AS
(
SELECT
subnet_sk
,end_address AS EndThisIsland
,LEAD(begin_address) OVER(PARTITION BY subnet_sk ORDER BY end_address) AS BeginNextIsland
FROM CTE_Islands
)
,CTE_GapsIncDec
AS
(
SELECT
subnet_sk
,EndThisIsland
,EndThisIslandInc
,BeginNextIslandDec
,BeginNextIsland
FROM CTE_Gaps
CROSS APPLY
(
SELECT bi.Result AS EndThisIslandInc
FROM dbo.BinaryInc(EndThisIsland) AS bi
) AS CA_Inc
CROSS APPLY
(
SELECT bd.Result AS BeginNextIslandDec
FROM dbo.BinaryDec(BeginNextIsland) AS bd
) AS CA_Dec
)
SELECT
subnet_sk
,EndThisIslandInc AS begin_range_AvailableIPAddress
,BeginNextIslandDec AS end_range_AvailableIPAddress
FROM CTE_GapsIncDec
WHERE CTE_GapsIncDec.EndThisIslandInc <> BeginNextIsland
ORDER BY subnet_sk, EndThisIsland;
结果集
subnet_sk begin_range_AvailableIPAddress end_range_AvailableIPAddress
1 0xAC101129 0xAC10112E
2 0xC0A81B1F 0xC0A81B1F
2 0xC0A81B22 0xC0A81B28
2 0xC0A81BFA 0xC0A81BFE
3 0xC0A8160C 0xC0A8160C
3 0xC0A816FE 0xC0A816FE
4 0xFC000000000000000000000000000001 0xFC0000000000000000000000000000FF
4 0xFC000000000000000000000000000101 0xFC0000000000000000000000000001FF
4 0xFC000000000000000000000000000201 0xFC0000000000000000000000000002FF
4 0xFC000000000000000000000000000301 0xFC0000000000000000000000000003FF
4 0xFC000000000000000000000000000401 0xFC0000000000000000000000000004FF
4 0xFC000000000000000000000000000501 0xFC0000000000000000000000000005FF
4 0xFC000000000000000000000000000601 0xFC0000000000000000000000000006FF
4 0xFC000000000000000000000000000701 0xFC0000000000000000000000000007FF
4 0xFC000000000000000000000000000801 0xFC0000000000000000000000000008FF
4 0xFC000000000000000000000000000901 0xFC00000000000000BFFFFFFFFFFFFFFD
4 0xFC00000000000000BFFFFFFFFFFFFFFF 0xFC00000000000000CFFFFFFFFFFFFFFD
4 0xFC00000000000000CFFFFFFFFFFFFFFF 0xFC00000000000000FBFFFFFFFFFFFFFD
4 0xFC00000000000000FBFFFFFFFFFFFFFF 0xFC00000000000000FCFFFFFFFFFFFFFD
4 0xFC00000000000000FCFFFFFFFFFFFFFF 0xFC00000000000000FFBFFFFFFFFFFFFD
4 0xFC00000000000000FFBFFFFFFFFFFFFF 0xFC00000000000000FFCFFFFFFFFFFFFD
4 0xFC00000000000000FFCFFFFFFFFFFFFF 0xFC00000000000000FFFBFFFFFFFFFFFD
4 0xFC00000000000000FFFBFFFFFFFFFFFF 0xFC00000000000000FFFCFFFFFFFFFFFD
4 0xFC00000000000000FFFCFFFFFFFFFFFF 0xFC00000000000000FFFFBFFFFFFFFFFD
4 0xFC00000000000000FFFFBFFFFFFFFFFF 0xFC00000000000000FFFFCFFFFFFFFFFD
4 0xFC00000000000000FFFFCFFFFFFFFFFF 0xFC00000000000000FFFFFBFFFFFFFFFD
4 0xFC00000000000000FFFFFBFFFFFFFFFF 0xFC00000000000000FFFFFCFFFFFFFFFD
4 0xFC00000000000000FFFFFCFFFFFFFFFF 0xFC00000000000000FFFFFFBFFFFFFFFD
4 0xFC00000000000000FFFFFFBFFFFFFFFF 0xFC00000000000000FFFFFFCFFFFFFFFD
4 0xFC00000000000000FFFFFFCFFFFFFFFF 0xFC00000000000000FFFFFFFBFFFFFFFD
4 0xFC00000000000000FFFFFFFBFFFFFFFF 0xFC00000000000000FFFFFFFCFFFFFFFD
4 0xFC00000000000000FFFFFFFCFFFFFFFF 0xFC00000000000000FFFFFFFFBFFFFFFD
4 0xFC00000000000000FFFFFFFFBFFFFFFF 0xFC00000000000000FFFFFFFFCFFFFFFD
4 0xFC00000000000000FFFFFFFFCFFFFFFF 0xFC00000000000000FFFFFFFFFBFFFFFD
4 0xFC00000000000000FFFFFFFFFBFFFFFF 0xFC00000000000000FFFFFFFFFCFFFFFD
4 0xFC00000000000000FFFFFFFFFCFFFFFF 0xFC00000000000000FFFFFFFFFFBFFFFD
4 0xFC00000000000000FFFFFFFFFFBFFFFF 0xFC00000000000000FFFFFFFFFFCFFFFD
4 0xFC00000000000000FFFFFFFFFFCFFFFF 0xFC00000000000000FFFFFFFFFFFBFFFD
4 0xFC00000000000000FFFFFFFFFFFBFFFF 0xFC00000000000000FFFFFFFFFFFCFFFD
4 0xFC00000000000000FFFFFFFFFFFCFFFF 0xFC00000000000000FFFFFFFFFFFFBFFD
4 0xFC00000000000000FFFFFFFFFFFFBFFF 0xFC00000000000000FFFFFFFFFFFFCFFD
4 0xFC00000000000000FFFFFFFFFFFFCFFF 0xFC00000000000000FFFFFFFFFFFFFBFD
4 0xFC00000000000000FFFFFFFFFFFFFBFF 0xFC00000000000000FFFFFFFFFFFFFCFD
4 0xFC00000000000000FFFFFFFFFFFFFCFF 0xFC00000000000000FFFFFFFFFFFFFFBD
4 0xFC00000000000000FFFFFFFFFFFFFFBF 0xFC00000000000000FFFFFFFFFFFFFFCD
4 0xFC00000000000000FFFFFFFFFFFFFFCF 0xFC0001065FFFFFFFFFFFFFFFFFFFFFFF
4 0xFC000106600000000000000100000000 0xFC00010666FFFFFFFFFFFFFFFFFFFFFF
4 0xFC000106670000000000000100000000 0xFC000106677FFFFFFFFFFFFFFFFFFFFF
4 0xFC000106678000000000000100000000 0xFC000106678FFFFFFFFFFFFFFFFFFFFF
4 0xFC000106679000000000000100000000 0xFC0001066800000000000000FFFFFFFE
执行计划
我很好奇这里建议的不同解决方案是如何工作的，所以我查看了它们的执行计划。请记住，这些计划适用于没有任何索引的小样本数据集。
我的 IPv4 和 IPv6 通用解决方案：
dnoeth的类似解决方案：
cha 不使用 LEAD 函数的解决方案：
这是一类我通常尝试用超过 +1/-1 的简单累积和来解决的问题。
ip_address: ip_address不可用ip，但ip_address + 1
开头可用
子网：ip 不适用于 ipv4_end，但可用 ipv4_begin + 1
dhcp_range：begin_address之后ip不可用，end_address+1
开始可用
现在对所有按 ip 地址排序的 +1/-1 求和，只要它大于零，它就是免费提示范围的开始，现在下一行的 ip 是已用范围的开始。
SELECT
subnet_sk
,ip_begin
,ip_end
FROM
(
SELECT
subnet_sk
,ip AS ip_begin
-- ,x
,LEAD(ip)
OVER (ORDER BY ip, x) - 1 AS ip_end
,SUM(x)
OVER (ORDER BY ip, x
ROWS UNBOUNDED PRECEDING) AS avail
FROM
(
SELECT
subnet_sk, CAST(ipv4_begin AS BIGINT)+1 AS ip, 1 AS x
FROM subnet
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(ipv4_end AS BIGINT), -1
FROM subnet
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(begin_address AS BIGINT), -1
FROM dhcp_range
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(end_address AS BIGINT)+1, 1
FROM dhcp_range
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(address AS BIGINT), -1
FROM ip_address
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(address AS BIGINT)+1, 1
FROM ip_address
-- WHERE subnet_sk = 1
) AS dt
) AS dt
WHERE avail > 0
这将 return 所有可用范围，对于单个子网，只需取消注释 WHERE 条件：fiddle
问题陈述：
given a range
x -> yof unsigned integers
wherexandyare both in the range0 -> 2n
andnis0 -> 32(or 64 in alternate cases)
find the minimum available value
not equal toxory
that is not in an existing set
where existing sets are arbitrary subsets ofx -> y
我正在为数据库中的 IPv4 和 IPv6 子网建模。每个子网都由其起始地址和结束地址定义（我通过业务规则确保范围的完整性）。因为 IPv6 太大而无法存储在 bigint 数据类型中，我们将 IP 地址存储为 binary(4) 或 binary(16).
关联数据存储在subnet、dhcp_range和ip_address tables:
- 子网：
子网范围由开始和结束 IP 地址定义，并存储在
subnettable 中。子网范围的大小始终为 2n（根据 CIDR / 网络掩码的定义）。 - IP:
一个子网有
0..*个 IP 地址存储在ip_addresstable 中。 IP 地址必须介于起始地址和结束地址之间，但不等于其关联子网定义的范围。 - DHCP 范围:
一个子网有
0..*个 DHCP 范围存储在dhcp_rangetable 中。与子网类似，每个 DHCP 范围都定义了一个开始地址和结束地址。 DHCP 范围受关联子网范围的限制。 DHCP 范围彼此不重叠。
我要确定的是子网的下一个可用 IP：
- 即未已分配（不在IP地址table中）
- 不在 DHCP 范围内
- 和不等于子网范围的开始或结束地址。
我正在寻找找到最小可用地址或所有可用地址的解决方案。
我最初的想法是生成受子网范围限制的可能地址（数字）范围，然后根据使用的集合删除地址：
declare @subnet_sk int = 42
;with
address_range as (
select cast(ipv4_begin as bigint) as available_address
,cast(ipv4_end as bigint) as end_address, subnet_sk
from subnet s
where subnet_sk = @subnet_sk
union all
select available_address + 1, end_address, subnet_sk
from address_range
where available_address + 1 <= end_address
),
assigned_addresses as (
select ip.[address]
,subnet_sk
from ip_address ip
where ip.subnet_sk = @subnet_sk
and ip.address_family = 'InterNetwork'),
dhcp_ranges as (
select dhcp.begin_address
,dhcp.end_address
,subnet_sk
from dhcp_range dhcp
where dhcp.subnet_sk = @subnet_sk
and dhcp.address_family = 'InterNetwork')
select distinct ar.available_address
from address_range ar
join dhcp_ranges dhcp
on ar.available_address
not between dhcp.begin_address
and dhcp.end_address
left join assigned_addresses aa
on ar.available_address = aa.[address]
join subnet s
on ar.available_address != s.ipv4_begin
and ar.available_address != s.ipv4_end
where aa.[address] is null
and s.subnet_sk = @subnet_sk
order by available_address
option (MAXRECURSION 32767)
上述查询使用了递归 CTE，并不适用于所有数据排列。递归 CTE 很麻烦，因为它的最大大小被限制为 32,767（比潜在的范围大小小得多）并且非常有可能变得非常慢。我可能可以解决递归 CTE 的问题，但查询在以下情况下失败：
- 当没有分配 IP 地址或 DHCP 范围时：它return什么都没有
应该 return 子网范围 定义的所有 IP 地址
- 当分配了多个 DHCP 范围时：returns IPs inside DHCP ranges
为了帮助解决问题，我创建了一个 SQL Fiddle with three subnets; each with a different characteristic: chopped up, empty, or mostly contiguous. The above query and the setup in the fiddle both work for the mostly contiguous subnet, but fails for the others. There is also a GitHub Gist of the schema and example data。
我已经努力生成具有递归和堆叠 CTE 的数字序列，但如上所述，恐怕它们的性能会很差，并且在人为限制递归 CTE 的情况下。 Aaron Bertrand details some alternatives to CTEs in his series Generate a set or sequence without loops. Sadly the dataset is too large for a numbers table as creating one just for the IPv4 address space would require 32 gigabytes of disk space (SQL Server stores bigint values in 8 bytes)。我更喜欢动态生成序列，但还没有想出一个好的方法。
或者，我试图通过查看我知道要使用的地址来为我的查询设置种子：
declare @subnet_sk int = 1
select unassigned_range.*
from (select cast(l.address as bigint) + 1 as start
,min(cast(fr.address as bigint)) - 1 as stop
from ip_address as l
left join ip_address as r on l.address = r.address - 1
left join ip_address as fr on l.address < fr.address
where r.address is null and fr.address is not null
and l.subnet_sk = @subnet_sk
group by l.address, r.address) as unassigned_range
join dhcp_range dhcp
on unassigned_range.start
not between cast(dhcp.begin_address as bigint)
and cast(dhcp.end_address as bigint)
and unassigned_range.stop
not between cast(dhcp.begin_address as bigint)
and cast(dhcp.end_address as bigint)
where dhcp.subnet_sk = @subnet_sk
遗憾的是，当 ip_address 或 dhcp_range table 中没有任何内容时，上述查询不起作用。更糟糕的是，由于它不知道子网范围的边界，因此 dhcp_range 朝向子网范围的上限将人为地限制 returned 的内容，因为查询不能 return 行来自空 space 在边缘。表现也不突出。
使用 SQL 或 TSQL 如何确定受其他范围限制的任意整数范围内的下一个最小可用整数值？
经过深思熟虑，我相信像这样简单的查询就可以了：
with a as(
-- next ip address
select n.next_address, i.subnet_sk
from ip_address i
CROSS APPLY (SELECT convert(binary(4), convert(bigint, i.address) + 1) AS next_address) as n
where n.next_address NOT IN (SELECT address FROM ip_address)
AND EXISTS (SELECT 1 FROM subnet s WHERE s.subnet_sk = i.subnet_sk and n.next_address > s.ipv4_begin and n.next_address < s.ipv4_end)
UNION -- use UNION here, not UNION ALL to remove duplicates
-- first ip address for completely unassigned subnets
SELECT next_address, subnet_sk
FROM subnet
CROSS APPLY (SELECT convert(binary(4), convert(bigint, ipv4_begin) + 1) AS next_address) n
where n.next_address NOT IN (SELECT address FROM ip_address)
UNION -- use UNION here, not UNION ALL to remove duplicates
-- next ip address from dhcp ranges
SELECT next_address, subnet_sk
FROM dhcp_range
CROSS APPLY (SELECT convert(binary(4), convert(bigint, end_address) + 1) AS next_address) n
where n.next_address NOT IN (SELECT address FROM ip_address)
)
SELECT min(next_address), subnet_sk
FROM a WHERE NOT exists(SELECT 1 FROM dhcp_range dhcp
WHERE a.subnet_sk = dhcp.subnet_sk and a.next_address
between dhcp.begin_address
and dhcp.end_address)
GROUP BY subnet_sk
它适用于 IPV4，但可以轻松扩展到 IPV6
每个子网的结果：
subnet_sk
---------- -----------
0xAC101129 1
0xC0A81B1F 2
0xC0A8160C 3
(3 row(s) affected)
我觉得应该很快。请查收
我不太清楚你的数据到底是什么样的。问题陈述虽然表述得很好，但似乎与查询关系不大。
让我假设 dhcp_range 有数据。您想要的查询是：
SELECT COALESCE(MIN(dr.end_address) + 1, 0)
FROM dhcp_range dr
WHERE NOT EXISTS (SELECT 1
FROM dhcp_range dr2
WHERE dr.end_address + 1 BETWEEN dr.start_address AND dr.end_address
);
在这种情况下不需要递归，因为我们有 LEAD 函数。
我会从"gaps"和"islands"的角度思考问题。
我会首先关注 IPv4，因为用它们做算术更容易，但 IPv6 的想法是一样的，最后我会展示一个通用的解决方案。
首先，我们有所有可能的 IP：从 0x00000000 到 0xFFFFFFFF。
在此范围内有 "islands" 由 dhcp_range 中的范围（含）定义：dhcp_range.begin_address, dhcp_range.end_address。您可以将分配的 IP 地址列表视为另一组岛屿，每个岛屿都有一个元素：ip_address.address, ip_address.address。最后，子网本身是两个孤岛：0x00000000, subnet.ipv4_begin 和 subnet.ipv4_end, 0xFFFFFFFF。
我们知道这些岛屿 不 重叠，这让我们的生活更轻松。岛屿可以彼此完美相邻。例如，当您连续分配的 IP 地址很少时，它们之间的差距为零。 在所有这些岛中，我们需要找到第一个间隙，它至少有一个元素，即非零间隙，即下一个岛在前一个岛结束后的某个距离处开始。
因此，我们将使用 UNION（CTE_Islands）将所有岛屿放在一起，然后按照 end_address（或 begin_address）的顺序遍历所有岛屿，使用上面有索引的字段）并使用 LEAD 向前看并获取下一个岛屿的起始地址。最后我们将有一个 table，其中每一行都有当前岛屿的 end_address 和下一个岛屿的 begin_address (CTE_Diff)。如果它们之间的差异大于一，则意味着 "gap" 足够宽，我们将 return 当前岛屿的 end_address 加 1。
给定子网的第一个可用 IP 地址
DECLARE @ParamSubnet_sk int = 1;
WITH
CTE_Islands
AS
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
)
,CTE_Diff
AS
(
SELECT
begin_address
, end_address
--, LEAD(begin_address) OVER(ORDER BY end_address) AS BeginNextIsland
, LEAD(begin_address) OVER(ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT TOP(1)
CAST(end_address + 1 AS varbinary(4)) AS NextAvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
ORDER BY end_address;
如果至少有一个可用的 IP 地址，结果集将包含一行，如果没有可用的 IP 地址，则结果集将完全不包含行。
For parameter 1 result is `0xAC101129`.
For parameter 2 result is `0xC0A81B1F`.
For parameter 3 result is `0xC0A8160C`.
这里是link到SQLFiddle。它不适用于参数，所以我在那里硬编码 1 。在 UNION 中将其更改为其他子网 ID（2 或 3）以尝试其他子网。此外，它没有在 varbinary 中正确显示结果，所以我将其保留为 bigint。例如，使用 windows 计算器将其转换为十六进制以验证结果。
如果您不通过 TOP(1) 将结果限制为第一个间隙，您将获得所有可用 IP 范围（间隙）的列表。
给定子网的所有可用 IP 地址范围列表
DECLARE @ParamSubnet_sk int = 1;
WITH
CTE_Islands
AS
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet_sk = @ParamSubnet_sk
)
,CTE_Diff
AS
(
SELECT
begin_address
, end_address
, LEAD(begin_address) OVER(ORDER BY end_address) AS BeginNextIsland
, LEAD(begin_address) OVER(ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT
CAST(end_address + 1 AS varbinary(4)) AS begin_range_AvailableIPAddress
,CAST(BeginNextIsland - 1 AS varbinary(4)) AS end_range_AvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
ORDER BY end_address;
结果。 SQL Fiddle 结果为简单的 bigint，不是十六进制，并且参数 ID 是硬编码的。
Result set for ID = 1
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xAC101129 0xAC10112E
Result set for ID = 2
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xC0A81B1F 0xC0A81B1F
0xC0A81B22 0xC0A81B28
0xC0A81BFA 0xC0A81BFE
Result set for ID = 3
begin_range_AvailableIPAddress end_range_AvailableIPAddress
0xC0A8160C 0xC0A8160C
0xC0A816FE 0xC0A816FE
每个子网的第一个可用IP地址
扩展查询和 return 所有子网的第一个可用 IP 地址很容易，而不是指定一个特定的子网。使用 CROSS APPLY 获取每个子网的岛屿列表，然后将 PARTITION BY subnet_sk 添加到 LEAD 函数中。
WITH
CTE_Islands
AS
(
SELECT
subnet_sk
, begin_address
, end_address
FROM
subnet AS Main
CROSS APPLY
(
SELECT CAST(begin_address AS bigint) AS begin_address, CAST(end_address AS bigint) AS end_address
FROM dhcp_range
WHERE dhcp_range.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(address AS bigint) AS begin_address, CAST(address AS bigint) AS end_address
FROM ip_address
WHERE ip_address.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(0x00000000 AS bigint) AS begin_address, CAST(ipv4_begin AS bigint) AS end_address
FROM subnet
WHERE subnet.subnet_sk = Main.subnet_sk
UNION ALL
SELECT CAST(ipv4_end AS bigint) AS begin_address, CAST(0xFFFFFFFF AS bigint) AS end_address
FROM subnet
WHERE subnet.subnet_sk = Main.subnet_sk
) AS CA
)
,CTE_Diff
AS
(
SELECT
subnet_sk
, begin_address
, end_address
, LEAD(begin_address) OVER(PARTITION BY subnet_sk ORDER BY end_address) - end_address AS Diff
FROM CTE_Islands
)
SELECT
subnet_sk
, CAST(MIN(end_address) + 1 as varbinary(4)) AS NextAvailableIPAddress
FROM CTE_Diff
WHERE Diff > 1
GROUP BY subnet_sk
结果集
subnet_sk NextAvailableIPAddress
1 0xAC101129
2 0xC0A81B1F
3 0xC0A8160C
这里是SQLFiddle。我不得不在 SQL Fiddle 中删除对 varbinary 的转换，因为它显示的结果不正确。
IPv4 和 IPv6 通用解决方案
所有子网的所有可用 IP 地址范围
SQL Fiddle with sample IPv4 and IPv6 data, functions and final query
您的 IPv6 示例数据不太正确 - 子网的末尾 0xFC00000000000000FFFFFFFFFFFFFFFF 小于您的 dhcp 范围，因此我将其更改为 0xFC0001066800000000000000FFFFFFFF。此外，您在同一子网中同时拥有 IPv4 和 IPv6，处理起来很麻烦。为了这个例子，我稍微改变了你的模式 - 而不是在 subnet 中有明确的 ipv4_begin / end 和 ipv6_begin / end 我只是 ip_begin / end as varbinary(16)（与您的其他 table 相同）。我也删除了 address_family，否则它对于 SQL Fiddle.
算术函数
为了使其适用于 IPv6，我们需要弄清楚如何 add/subtract 1 to/from binary(16)。我会为它制作 CLR 函数。如果您不允许启用 CLR，则可以通过标准 T-SQL。我创建了两个 return 和 table 的函数，而不是标量，因为这样它们可以被优化器内联。我想做一个通用的解决方案，所以该函数将接受 varbinary(16) 并适用于 IPv4 和 IPv6。
这里是 T-SQL 函数，将 varbinary(16) 递增 1。如果参数不是 16 字节长，我假设它是 IPv4，只需将其转换为 bigint 以添加 1，然后返回 binary。否则，我将 binary(16) 分成两部分，每部分长 8 个字节，然后将它们转换为 bigint。 bigint 是有符号的，但我们需要无符号增量，所以我们需要检查一些情况。
else 部分是最常见的 - 我们只需将低部分加一并将结果附加到原始高部分。
如果低位部分是0xFFFFFFFFFFFFFFFF，那么我们将低位部分设置为0x0000000000000000并保留标志位，即高位部分加1。
如果低部分是 0x7FFFFFFFFFFFFFFF，那么我们将低部分显式设置为 0x8000000000000000，因为尝试增加此 bigint 值会导致溢出。
如果整数是 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 我们将结果设置为 0x00000000000000000000000000000000.
减一函数类似
CREATE FUNCTION [dbo].[BinaryInc](@src varbinary(16))
RETURNS TABLE AS
RETURN
SELECT
CASE WHEN DATALENGTH(@src) = 16
THEN
-- Increment IPv6 by splitting it into two bigints 8 bytes each and then concatenating them
CASE
WHEN @src = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
THEN 0x00000000000000000000000000000000
WHEN SUBSTRING(@src, 9, 8) = 0x7FFFFFFFFFFFFFFF
THEN SUBSTRING(@src, 1, 8) + 0x8000000000000000
WHEN SUBSTRING(@src, 9, 8) = 0xFFFFFFFFFFFFFFFF
THEN CAST(CAST(SUBSTRING(@src, 1, 8) AS bigint) + 1 AS binary(8)) + 0x0000000000000000
ELSE SUBSTRING(@src, 1, 8) + CAST(CAST(SUBSTRING(@src, 9, 8) AS bigint) + 1 AS binary(8))
END
ELSE
-- Increment IPv4 by converting it into 8 byte bigint and then back into 4 bytes binary
CAST(CAST(CAST(@src AS bigint) + 1 AS binary(4)) AS varbinary(16))
END AS Result
;
GO
CREATE FUNCTION [dbo].[BinaryDec](@src varbinary(16))
RETURNS TABLE AS
RETURN
SELECT
CASE WHEN DATALENGTH(@src) = 16
THEN
-- Decrement IPv6 by splitting it into two bigints 8 bytes each and then concatenating them
CASE
WHEN @src = 0x00000000000000000000000000000000
THEN 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
WHEN SUBSTRING(@src, 9, 8) = 0x8000000000000000
THEN SUBSTRING(@src, 1, 8) + 0x7FFFFFFFFFFFFFFF
WHEN SUBSTRING(@src, 9, 8) = 0x0000000000000000
THEN CAST(CAST(SUBSTRING(@src, 1, 8) AS bigint) - 1 AS binary(8)) + 0xFFFFFFFFFFFFFFFF
ELSE SUBSTRING(@src, 1, 8) + CAST(CAST(SUBSTRING(@src, 9, 8) AS bigint) - 1 AS binary(8))
END
ELSE
-- Decrement IPv4 by converting it into 8 byte bigint and then back into 4 bytes binary
CAST(CAST(CAST(@src AS bigint) - 1 AS binary(4)) AS varbinary(16))
END AS Result
;
GO
所有子网的所有可用 IP 地址范围
WITH
CTE_Islands
AS
(
SELECT subnet_sk, begin_address, end_address
FROM dhcp_range
UNION ALL
SELECT subnet_sk, address AS begin_address, address AS end_address
FROM ip_address
UNION ALL
SELECT subnet_sk, SUBSTRING(0x00000000000000000000000000000000, 1, DATALENGTH(ip_begin)) AS begin_address, ip_begin AS end_address
FROM subnet
UNION ALL
SELECT subnet_sk, ip_end AS begin_address, SUBSTRING(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, 1, DATALENGTH(ip_end)) AS end_address
FROM subnet
)
,CTE_Gaps
AS
(
SELECT
subnet_sk
,end_address AS EndThisIsland
,LEAD(begin_address) OVER(PARTITION BY subnet_sk ORDER BY end_address) AS BeginNextIsland
FROM CTE_Islands
)
,CTE_GapsIncDec
AS
(
SELECT
subnet_sk
,EndThisIsland
,EndThisIslandInc
,BeginNextIslandDec
,BeginNextIsland
FROM CTE_Gaps
CROSS APPLY
(
SELECT bi.Result AS EndThisIslandInc
FROM dbo.BinaryInc(EndThisIsland) AS bi
) AS CA_Inc
CROSS APPLY
(
SELECT bd.Result AS BeginNextIslandDec
FROM dbo.BinaryDec(BeginNextIsland) AS bd
) AS CA_Dec
)
SELECT
subnet_sk
,EndThisIslandInc AS begin_range_AvailableIPAddress
,BeginNextIslandDec AS end_range_AvailableIPAddress
FROM CTE_GapsIncDec
WHERE CTE_GapsIncDec.EndThisIslandInc <> BeginNextIsland
ORDER BY subnet_sk, EndThisIsland;
结果集
subnet_sk begin_range_AvailableIPAddress end_range_AvailableIPAddress
1 0xAC101129 0xAC10112E
2 0xC0A81B1F 0xC0A81B1F
2 0xC0A81B22 0xC0A81B28
2 0xC0A81BFA 0xC0A81BFE
3 0xC0A8160C 0xC0A8160C
3 0xC0A816FE 0xC0A816FE
4 0xFC000000000000000000000000000001 0xFC0000000000000000000000000000FF
4 0xFC000000000000000000000000000101 0xFC0000000000000000000000000001FF
4 0xFC000000000000000000000000000201 0xFC0000000000000000000000000002FF
4 0xFC000000000000000000000000000301 0xFC0000000000000000000000000003FF
4 0xFC000000000000000000000000000401 0xFC0000000000000000000000000004FF
4 0xFC000000000000000000000000000501 0xFC0000000000000000000000000005FF
4 0xFC000000000000000000000000000601 0xFC0000000000000000000000000006FF
4 0xFC000000000000000000000000000701 0xFC0000000000000000000000000007FF
4 0xFC000000000000000000000000000801 0xFC0000000000000000000000000008FF
4 0xFC000000000000000000000000000901 0xFC00000000000000BFFFFFFFFFFFFFFD
4 0xFC00000000000000BFFFFFFFFFFFFFFF 0xFC00000000000000CFFFFFFFFFFFFFFD
4 0xFC00000000000000CFFFFFFFFFFFFFFF 0xFC00000000000000FBFFFFFFFFFFFFFD
4 0xFC00000000000000FBFFFFFFFFFFFFFF 0xFC00000000000000FCFFFFFFFFFFFFFD
4 0xFC00000000000000FCFFFFFFFFFFFFFF 0xFC00000000000000FFBFFFFFFFFFFFFD
4 0xFC00000000000000FFBFFFFFFFFFFFFF 0xFC00000000000000FFCFFFFFFFFFFFFD
4 0xFC00000000000000FFCFFFFFFFFFFFFF 0xFC00000000000000FFFBFFFFFFFFFFFD
4 0xFC00000000000000FFFBFFFFFFFFFFFF 0xFC00000000000000FFFCFFFFFFFFFFFD
4 0xFC00000000000000FFFCFFFFFFFFFFFF 0xFC00000000000000FFFFBFFFFFFFFFFD
4 0xFC00000000000000FFFFBFFFFFFFFFFF 0xFC00000000000000FFFFCFFFFFFFFFFD
4 0xFC00000000000000FFFFCFFFFFFFFFFF 0xFC00000000000000FFFFFBFFFFFFFFFD
4 0xFC00000000000000FFFFFBFFFFFFFFFF 0xFC00000000000000FFFFFCFFFFFFFFFD
4 0xFC00000000000000FFFFFCFFFFFFFFFF 0xFC00000000000000FFFFFFBFFFFFFFFD
4 0xFC00000000000000FFFFFFBFFFFFFFFF 0xFC00000000000000FFFFFFCFFFFFFFFD
4 0xFC00000000000000FFFFFFCFFFFFFFFF 0xFC00000000000000FFFFFFFBFFFFFFFD
4 0xFC00000000000000FFFFFFFBFFFFFFFF 0xFC00000000000000FFFFFFFCFFFFFFFD
4 0xFC00000000000000FFFFFFFCFFFFFFFF 0xFC00000000000000FFFFFFFFBFFFFFFD
4 0xFC00000000000000FFFFFFFFBFFFFFFF 0xFC00000000000000FFFFFFFFCFFFFFFD
4 0xFC00000000000000FFFFFFFFCFFFFFFF 0xFC00000000000000FFFFFFFFFBFFFFFD
4 0xFC00000000000000FFFFFFFFFBFFFFFF 0xFC00000000000000FFFFFFFFFCFFFFFD
4 0xFC00000000000000FFFFFFFFFCFFFFFF 0xFC00000000000000FFFFFFFFFFBFFFFD
4 0xFC00000000000000FFFFFFFFFFBFFFFF 0xFC00000000000000FFFFFFFFFFCFFFFD
4 0xFC00000000000000FFFFFFFFFFCFFFFF 0xFC00000000000000FFFFFFFFFFFBFFFD
4 0xFC00000000000000FFFFFFFFFFFBFFFF 0xFC00000000000000FFFFFFFFFFFCFFFD
4 0xFC00000000000000FFFFFFFFFFFCFFFF 0xFC00000000000000FFFFFFFFFFFFBFFD
4 0xFC00000000000000FFFFFFFFFFFFBFFF 0xFC00000000000000FFFFFFFFFFFFCFFD
4 0xFC00000000000000FFFFFFFFFFFFCFFF 0xFC00000000000000FFFFFFFFFFFFFBFD
4 0xFC00000000000000FFFFFFFFFFFFFBFF 0xFC00000000000000FFFFFFFFFFFFFCFD
4 0xFC00000000000000FFFFFFFFFFFFFCFF 0xFC00000000000000FFFFFFFFFFFFFFBD
4 0xFC00000000000000FFFFFFFFFFFFFFBF 0xFC00000000000000FFFFFFFFFFFFFFCD
4 0xFC00000000000000FFFFFFFFFFFFFFCF 0xFC0001065FFFFFFFFFFFFFFFFFFFFFFF
4 0xFC000106600000000000000100000000 0xFC00010666FFFFFFFFFFFFFFFFFFFFFF
4 0xFC000106670000000000000100000000 0xFC000106677FFFFFFFFFFFFFFFFFFFFF
4 0xFC000106678000000000000100000000 0xFC000106678FFFFFFFFFFFFFFFFFFFFF
4 0xFC000106679000000000000100000000 0xFC0001066800000000000000FFFFFFFE
执行计划
我很好奇这里建议的不同解决方案是如何工作的，所以我查看了它们的执行计划。请记住，这些计划适用于没有任何索引的小样本数据集。
我的 IPv4 和 IPv6 通用解决方案：
dnoeth的类似解决方案：
cha 不使用 LEAD 函数的解决方案：
这是一类我通常尝试用超过 +1/-1 的简单累积和来解决的问题。
ip_address: ip_address不可用ip，但ip_address + 1
开头可用子网：ip 不适用于 ipv4_end，但可用 ipv4_begin + 1
dhcp_range：begin_address之后ip不可用，end_address+1
开始可用现在对所有按 ip 地址排序的 +1/-1 求和，只要它大于零，它就是免费提示范围的开始，现在下一行的 ip 是已用范围的开始。
SELECT
subnet_sk
,ip_begin
,ip_end
FROM
(
SELECT
subnet_sk
,ip AS ip_begin
-- ,x
,LEAD(ip)
OVER (ORDER BY ip, x) - 1 AS ip_end
,SUM(x)
OVER (ORDER BY ip, x
ROWS UNBOUNDED PRECEDING) AS avail
FROM
(
SELECT
subnet_sk, CAST(ipv4_begin AS BIGINT)+1 AS ip, 1 AS x
FROM subnet
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(ipv4_end AS BIGINT), -1
FROM subnet
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(begin_address AS BIGINT), -1
FROM dhcp_range
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(end_address AS BIGINT)+1, 1
FROM dhcp_range
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(address AS BIGINT), -1
FROM ip_address
-- WHERE subnet_sk = 1
UNION ALL
SELECT
subnet_sk, CAST(address AS BIGINT)+1, 1
FROM ip_address
-- WHERE subnet_sk = 1
) AS dt
) AS dt
WHERE avail > 0
这将 return 所有可用范围，对于单个子网，只需取消注释 WHERE 条件：fiddle