使用sql查找范围内的下一个可用整数，该整数在现有整数子集中不存在-Java 学习之路

问题陈述：

给定范围x - > y的无符号整数，其中x和y都在0 - > 2n的范围内，n是0 - > 32（或者在交替的情况下是64）找到不等于x或y的最小可用值不在现有集合中，其中现有集合是x - > y的任意子集

我正在使用数据库中的IPv4和IPv6子网建模 . 每个子网由其起始地址和结束地址定义（我通过业务规则确保范围的完整性） . 由于IPv6太大而无法存储在 bigint 数据类型中，因此我们将IP地址存储为 binary(4) 或 binary(16) .

关联数据存储在 subnet ， dhcp_range 和 ip_address 表中：

Subnet ：子网范围由起始和结束IP地址定义，并存储在 subnet 表中 . 子网范围始终为2n（根据CIDR / netmask的定义） .
IP ：子网具有 ip_address 表中存储的 0..* IP地址 . IP地址必须位于起始地址和结束地址之间，但不等于其关联子网定义的范围 .
DHCP Range ：子网在 dhcp_range 表中存储了 0..* DHCP范围 . 与子网类似，每个DHCP范围定义开始和结束地址 . DHCP范围受相关子网范围的限制 . DHCP范围不会相互重叠 .

我想要确定的是子网的下一个可用IP：

尚未分配（不在IP地址表中）
不在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范围时：它不返回任何内容
应返回子网范围定义的所有IP地址
分配多个DHCP范围时：返回DHCP范围内的IP

为了帮助解决问题，我创建了一个包含三个子网的SQL Fiddle;每个都有不同的特征：切碎，空，或大多是连续的 . 上述查询和小提琴中的设置都适用于大多数连续的子网，但对其他子网无效 . 还有GitHub Gist of the schema and example data .

我已经努力用递归和堆叠CTE生成数字序列，但如上所述，我担心它们会表现不佳，并且在递归CTE的情况下会人为地限制 . Aaron Bertrand在他的系列文章_2541594中详细介绍了CTE的一些替代方案 . 遗憾的是，数据集对于数字表来说太大了，因为仅为IPv4地址空间创建一个数据集需要32千兆字节的磁盘空间（SQL Server存储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 表中没有任何内容时，上述查询不起作用 . 更糟糕的是，因为它不知道子网范围的边界，所以朝向子网范围的上限将人为地限制返回的内容，因为查询不能从边缘的空白空间返回行 . 表现也不出众 .

使用SQL或TSQL如何确定受其他范围限制的任意整数范围内的下一个最小可用整数值？

4 回答

在这种情况下，不需要递归，因为我们有 LEAD 函数 .

我将从“差距”和“孤岛”的角度思考问题 .

我将首先关注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 ） . 如果它们之间的差异大于1，则意味着"gap"足够宽，我们将返回当前岛的 end_address 加1 .

The first available IP address for the given subnet

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`.

这是SQLFiddle的链接 . 它不适用于参数，所以我在那里硬编码 1 . 将其在UNION中更改为其他子网ID（2或3）以尝试其他子网 . 此外，它没有正确显示 varbinary 中的结果，因此我将其保留为bigint . 比如使用Windows计算器将其转换为十六进制以验证结果 .

如果您没有通过 TOP(1) 将结果限制在第一个间隙，您将获得所有可用IP范围（间隙）的列表 .

List of all ranges of available IP addresses for a given subnet

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

The first available IP address for each subnet

很容易扩展查询并返回所有子网的第一个可用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

Result set

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

这是SQLFiddle . 我不得不在SQL Fiddle中删除转换为 varbinary ，因为它显示的结果不正确 .

IPv4和IPv6的通用解决方案

All ranges of available IP addresses for all subnets

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 设为 varbinary(16) （与其他表相同） . 我也删除了 address_family ，否则它对于SQL Fiddle来说太大了 .

算术函数

为了使其适用于IPv6，我们需要弄清楚如何在 binary(16) 中添加/减去 1 . 我会为它做CLR功能 . 如果不允许启用CLR，则可以通过标准T-SQL实现 . 我创建了两个返回表而不是标量的函数，因为这样它们可以由优化器内联 . 我想制作一个通用解决方案，因此该函数将接受 varbinary(16) 并适用于IPv4和IPv6 .

这是T-SQL函数，将 varbinary(16) 递增一 . 如果参数不是16字节长，我假设它是IPv4并简单地将其转换为 bigint 以添加 1 然后再返回 binary . 否则，我将 binary(16) 分成两个部分，每个部分长8个字节，并将它们转换为 bigint . bigint 已签名，但我们需要无符号增量，因此我们需要检查几个案例 .

else 部分是最常见的 - 我们只是将低部分逐渐递增并将结果附加到原始高部分 .

如果低部分是 0xFFFFFFFFFFFFFFFF ，那么我们将低部分设置为 0x0000000000000000 并继承该标志，即将高部分递增1 .

如果低部分是 0x7FFFFFFFFFFFFFFF ，那么我们将低部分显式设置为 0x8000000000000000 ，因为尝试递增此 bigint 值会导致溢出 .

如果整数是 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF ，我们将结果设置为 0x00000000000000000000000000000000 .

递减1的功能是相似的 .

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;

Result set

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 函数：

回复于 2024-04-29T06:46:57+08:00

经过深思熟虑后，我相信一个简单的查询就可以了：

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

SQLFiddle

每个子网的结果：

subnet_sk
---------- -----------
0xAC101129 1
0xC0A81B1F 2
0xC0A8160C 3

(3 row(s) affected)

在我看来，它应该非常快 . 请检查一下

回复于 2024-04-29T06:46:57+08:00

这是一个我通常试图用1 / -1的简单累积和求解的问题 .

ip_address：ip不适用于ip_address，但可以从ip_address 1开始使用

subnet：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

这将返回所有可用范围，对于单个子网，只需取消注释WHERE条件：fiddle

回复于 2024-04-29T06:46:57+08:00

我对你的数据真实情况有点不清楚 . 问题陈述虽然制定得很好，但似乎与查询关系不大 .

我假设 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
                 );

回复于 2024-04-29T06:46:57+08:00

使用sql查找范围内的下一个可用整数，该整数在现有整数子集中不存在

4 回答

IPv4和IPv6的通用解决方案

执行计划

相关问题