With sql find next available integer within range that is not present in existing integer subset(s)

In this case no recursion is needed, because we have LEAD function.

I will think about the problem in terms of "gaps" and "islands".

I will focus at first on IPv4, because it is easier to do arithmetic with them, but idea for IPv6 is the same and in the end I'll show a generic solution.

To start with, we have a full range of possible IPs: from 0x00000000 to 0xFFFFFFFF.

Inside this range there are "islands" defined by the ranges (inclusive) in dhcp_range: dhcp_range.begin_address, dhcp_range.end_address. You can think about the list of assigned IP addresses as another set of islands, which have one element each: ip_address.address, ip_address.address. Finally, the subnet itself is two islands: 0x00000000, subnet.ipv4_begin and subnet.ipv4_end, 0xFFFFFFFF.

We know that these islands do not overlap, which makes our life easier. Islands can be perfectly adjacent to each other. For example, when you have few consecutively allocated IP addresses, the gap between them is zero.Among all these islands we need to find the first gap, which has at least one element, i.e. non-zero gap, i.e. the next island starts at some distance after the previous island ends.

So, we'll put all islands together using UNION (CTE_Islands) and then go through all of them in the order of end_address (or begin_address, use the field that has index on it) and use LEAD to peek ahead and get the starting address of the next island. In the end we'll have a table, where each row had end_address of the current island and begin_address of the next island (CTE_Diff). If difference between them is more than one, it means that the "gap" is wide enough and we'll return the end_address of the current island plus 1.

The first available IP address for the given subnet

DECLARE @ParamSubnet_sk int = 1;WITHCTE_IslandsAS(    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_DiffAS(    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 NextAvailableIPAddressFROM CTE_DiffWHERE Diff > 1ORDER BY end_address;

Result set would contain one row if there is at least one IP address available and would not contain rows at all if there are no IP addresses available.

For parameter 1 result is `0xAC101129`.For parameter 2 result is `0xC0A81B1F`.For parameter 3 result is `0xC0A8160C`.

Here is a link to SQLFiddle. It didn't work with parameter, so I hard coded 1 there. Change it in UNION to other subnet ID (2 or 3) to try other subnets. Also, it didn't display result in varbinary correctly, so I left it as bigint. Use, say, windows calculator to convert it to hex to verify result.

If you don't limit results to the first gap by TOP(1), you'll get a list of all available IP ranges (gaps).

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

DECLARE @ParamSubnet_sk int = 1;WITHCTE_IslandsAS(    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_DiffAS(    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_AvailableIPAddressFROM CTE_DiffWHERE Diff > 1ORDER BY end_address;

Result. SQL Fiddle with result as simple bigint, not in hex, and with hardcoded parameter ID.

Result set for ID = 1begin_range_AvailableIPAddress    end_range_AvailableIPAddress0xAC101129                        0xAC10112EResult set for ID = 2begin_range_AvailableIPAddress    end_range_AvailableIPAddress0xC0A81B1F                        0xC0A81B1F0xC0A81B22                        0xC0A81B280xC0A81BFA                        0xC0A81BFEResult set for ID = 3begin_range_AvailableIPAddress    end_range_AvailableIPAddress0xC0A8160C                        0xC0A8160C0xC0A816FE                        0xC0A816FE

The first available IP address for each subnet

It is easy to extend the query and return first available IP address for all subnets, rather than specifying one particular subnet. Use CROSS APPLY to get list of islands for each subnet and then add PARTITION BY subnet_sk into the LEAD function.

WITHCTE_IslandsAS(    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_DiffAS(    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 NextAvailableIPAddressFROM CTE_DiffWHERE Diff > 1GROUP BY subnet_sk

Result set

subnet_sk    NextAvailableIPAddress1            0xAC1011292            0xC0A81B1F3            0xC0A8160C

Here is SQLFiddle. I had to remove conversion to varbinary in SQL Fiddle, because it was showing results incorrectly.

Generic solution for both IPv4 and IPv6

All ranges of available IP addresses for all subnets

SQL Fiddle with sample IPv4 and IPv6 data, functions and final query

Your sample data for IPv6 wasn't quite correct - the end of the subnet 0xFC00000000000000FFFFFFFFFFFFFFFF was less than your dhcp ranges, so I changed that to 0xFC0001066800000000000000FFFFFFFF. Also, you had both IPv4 and IPv6 in the same subnet, which is cumbersome to handle. For the sake of this example I've changed your schema a little - instead of having explicit ipv4_begin / end and ipv6_begin / end in subnet I made it just ip_begin / end as varbinary(16) (same as for your other tables). I also removed address_family, otherwise it was too big for SQL Fiddle.

Arithmetic functions

To make it work for IPv6 we need to figure out how to add/subtract 1 to/from binary(16). I would make CLR function for it. If you are not allowed to enable CLR, it is possible via standard T-SQL. I made two functions that return a table, rather than scalar, because in such way they can be inlined by the optimizer. I wanted to make a generic solution, so the function would accept varbinary(16) and work for both IPv4 and IPv6.

Here is T-SQL function to increment varbinary(16) by one. If parameter is not 16 bytes long I assume that it is IPv4 and simply convert it to bigint to add 1 and then back to binary. Otherwise, I split binary(16) into two parts 8 bytes long each and cast them into bigint. bigint is signed, but we need unsigned increment, so we need to check few cases.

The else part is most common - we simply increment low part by one and append result to original high part.

If low part is 0xFFFFFFFFFFFFFFFF, then we set low part to 0x0000000000000000 and carry over the flag, i.e. increment the high part by one.

If low part is 0x7FFFFFFFFFFFFFFF, then we set low part to 0x8000000000000000 explicitly, because an attempt to increment this bigint value would cause overflow.

If the whole number is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF we set result to 0x00000000000000000000000000000000.

The function to decrement by one is similar.

CREATE FUNCTION [dbo].[BinaryInc](@src varbinary(16))RETURNS TABLE ASRETURN    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    ;GOCREATE FUNCTION [dbo].[BinaryDec](@src varbinary(16))RETURNS TABLE ASRETURN    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

All ranges of available IP addresses for all subnets

WITHCTE_IslandsAS(    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_GapsAS(    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_GapsIncDecAS(    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_AvailableIPAddressFROM CTE_GapsIncDecWHERE CTE_GapsIncDec.EndThisIslandInc <> BeginNextIslandORDER BY subnet_sk, EndThisIsland;

Result set

subnet_sk    begin_range_AvailableIPAddress        end_range_AvailableIPAddress1            0xAC101129                            0xAC10112E2            0xC0A81B1F                            0xC0A81B1F2            0xC0A81B22                            0xC0A81B282            0xC0A81BFA                            0xC0A81BFE3            0xC0A8160C                            0xC0A8160C3            0xC0A816FE                            0xC0A816FE4            0xFC000000000000000000000000000001    0xFC0000000000000000000000000000FF4            0xFC000000000000000000000000000101    0xFC0000000000000000000000000001FF4            0xFC000000000000000000000000000201    0xFC0000000000000000000000000002FF4            0xFC000000000000000000000000000301    0xFC0000000000000000000000000003FF4            0xFC000000000000000000000000000401    0xFC0000000000000000000000000004FF4            0xFC000000000000000000000000000501    0xFC0000000000000000000000000005FF4            0xFC000000000000000000000000000601    0xFC0000000000000000000000000006FF4            0xFC000000000000000000000000000701    0xFC0000000000000000000000000007FF4            0xFC000000000000000000000000000801    0xFC0000000000000000000000000008FF4            0xFC000000000000000000000000000901    0xFC00000000000000BFFFFFFFFFFFFFFD4            0xFC00000000000000BFFFFFFFFFFFFFFF    0xFC00000000000000CFFFFFFFFFFFFFFD4            0xFC00000000000000CFFFFFFFFFFFFFFF    0xFC00000000000000FBFFFFFFFFFFFFFD4            0xFC00000000000000FBFFFFFFFFFFFFFF    0xFC00000000000000FCFFFFFFFFFFFFFD4            0xFC00000000000000FCFFFFFFFFFFFFFF    0xFC00000000000000FFBFFFFFFFFFFFFD4            0xFC00000000000000FFBFFFFFFFFFFFFF    0xFC00000000000000FFCFFFFFFFFFFFFD4            0xFC00000000000000FFCFFFFFFFFFFFFF    0xFC00000000000000FFFBFFFFFFFFFFFD4            0xFC00000000000000FFFBFFFFFFFFFFFF    0xFC00000000000000FFFCFFFFFFFFFFFD4            0xFC00000000000000FFFCFFFFFFFFFFFF    0xFC00000000000000FFFFBFFFFFFFFFFD4            0xFC00000000000000FFFFBFFFFFFFFFFF    0xFC00000000000000FFFFCFFFFFFFFFFD4            0xFC00000000000000FFFFCFFFFFFFFFFF    0xFC00000000000000FFFFFBFFFFFFFFFD4            0xFC00000000000000FFFFFBFFFFFFFFFF    0xFC00000000000000FFFFFCFFFFFFFFFD4            0xFC00000000000000FFFFFCFFFFFFFFFF    0xFC00000000000000FFFFFFBFFFFFFFFD4            0xFC00000000000000FFFFFFBFFFFFFFFF    0xFC00000000000000FFFFFFCFFFFFFFFD4            0xFC00000000000000FFFFFFCFFFFFFFFF    0xFC00000000000000FFFFFFFBFFFFFFFD4            0xFC00000000000000FFFFFFFBFFFFFFFF    0xFC00000000000000FFFFFFFCFFFFFFFD4            0xFC00000000000000FFFFFFFCFFFFFFFF    0xFC00000000000000FFFFFFFFBFFFFFFD4            0xFC00000000000000FFFFFFFFBFFFFFFF    0xFC00000000000000FFFFFFFFCFFFFFFD4            0xFC00000000000000FFFFFFFFCFFFFFFF    0xFC00000000000000FFFFFFFFFBFFFFFD4            0xFC00000000000000FFFFFFFFFBFFFFFF    0xFC00000000000000FFFFFFFFFCFFFFFD4            0xFC00000000000000FFFFFFFFFCFFFFFF    0xFC00000000000000FFFFFFFFFFBFFFFD4            0xFC00000000000000FFFFFFFFFFBFFFFF    0xFC00000000000000FFFFFFFFFFCFFFFD4            0xFC00000000000000FFFFFFFFFFCFFFFF    0xFC00000000000000FFFFFFFFFFFBFFFD4            0xFC00000000000000FFFFFFFFFFFBFFFF    0xFC00000000000000FFFFFFFFFFFCFFFD4            0xFC00000000000000FFFFFFFFFFFCFFFF    0xFC00000000000000FFFFFFFFFFFFBFFD4            0xFC00000000000000FFFFFFFFFFFFBFFF    0xFC00000000000000FFFFFFFFFFFFCFFD4            0xFC00000000000000FFFFFFFFFFFFCFFF    0xFC00000000000000FFFFFFFFFFFFFBFD4            0xFC00000000000000FFFFFFFFFFFFFBFF    0xFC00000000000000FFFFFFFFFFFFFCFD4            0xFC00000000000000FFFFFFFFFFFFFCFF    0xFC00000000000000FFFFFFFFFFFFFFBD4            0xFC00000000000000FFFFFFFFFFFFFFBF    0xFC00000000000000FFFFFFFFFFFFFFCD4            0xFC00000000000000FFFFFFFFFFFFFFCF    0xFC0001065FFFFFFFFFFFFFFFFFFFFFFF4            0xFC000106600000000000000100000000    0xFC00010666FFFFFFFFFFFFFFFFFFFFFF4            0xFC000106670000000000000100000000    0xFC000106677FFFFFFFFFFFFFFFFFFFFF4            0xFC000106678000000000000100000000    0xFC000106678FFFFFFFFFFFFFFFFFFFFF4            0xFC000106679000000000000100000000    0xFC0001066800000000000000FFFFFFFE

Execution plans

I was curious to see how different solutions suggested here work, so I looked at their execution plans. Keep in mind that these plans are for the small sample set of data without any indexes.

My generic solution for both IPv4 and IPv6:

Similar solution by dnoeth:

Solution by cha that doesn't use LEAD function:

After a lot of thinking, I believe a query as simple as this will do:

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_skFROM 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

It is for IPV4, but can be easily extended for IPV6

SQLFiddle

Results for each subnet:

           subnet_sk---------- -----------0xAC101129 10xC0A81B1F 20xC0A8160C 3(3 row(s) affected)

In my opinion it should be very fast. Please check it

This is a kind of question I usually try to solve with a simple cumulative sum over +1/-1.

ip_address: ip is not available for ip_address, but available starting with ip_address + 1

subnet: ip is not available for ipv4_end, but available stating with ipv4_begin + 1

dhcp_range: ip is not available after begin_address, but available starting with end_address + 1

Now sum all the +1/-1 ordered by ip addresses, whenever it's greater than zero it's the start of a range of free tips and now the next row's ip is the start of a used range.

SELECT   subnet_sk  ,ip_begin  ,ip_endFROM (   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 dtWHERE avail > 0

This will return all available ranges, for a single subnet simply uncomment the WHERE-condition: fiddle