Problem statement:
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
I am working with modeling IPv4 and IPv6 subnets in a database. Each subnet is defined by its starting address and ending address (I ensure the integrity of the ranges via business rules). Because IPv6 is too large to store in the bigint datatype we store IP addresses as either binary(4) or binary(16).
The associated data is stored in subnet, dhcp_range and ip_address tables:
- Subnet:
A subnet range is defined by a a beginning and ending IP address and stored in the
subnet table. A subnet range is always of size 2n (as per defintion of CIDR / netmask).
- IP:
A subnet has
0..* IP addresses stored in the ip_address table. An IP address must be between the beginning and ending addresses but not equal to the range as defined by its associated subnet.
- DHCP Range:
A subnet has
0..* DHCP ranges stored in the dhcp_range table. Similar to a subnet each DHCP range defines a beginning and ending address. A DHCP range is bounded by the associated subnet range. DHCP ranges do not overlap each other.
What I want to determine is the next available IP for a subnet:
- that is not already assigned (not in the IP address table)
- not within a DHCP range
- and not equal to the begin or end address of the subnet range.
I am looking for a solution which finds either the minimum available address or all of the available addresses.
My initial thought was to generate the range of possible addresses (numbers) bound by the subnet's range and then remove addresses based on the used sets:
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)
The above query makes use of a recursive CTE and does not work for all data permutations. The recursive CTE is troublesome because it is limited to a max size of 32,767 (much smaller than potential range sizes) and has the very real possibility of being very slow. I could probably get over my issues with the recursive CTE, but the query fails under the following conditions:
- when no IP addresses or DHCP ranges are assigned: it returns nothing
should return all IP addresses as defined by the subnet range
- when multiple DHCP ranges are assigned: returns IPs inside DHCP ranges
To aide in troubleshooting the issue I've created a 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.
I have endeavored to generate the number sequence with recursive and stacked CTEs, but as indicated above am afraid they will be poorly performing and in the case of recursive CTEs artificially limiting. 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). I would prefer to generate the sequence on the fly, but haven't come up with a good way to do so.
Alternatively, I have attempted to seed my query by looking at what I know to be used addresses:
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
Sadly the above query does not work when there is nothing in the ip_address or dhcp_range tables. Worse since it is unaware of the bounds of the subnet range a dhcp_range towards the upper bound of the subnet range will artificially limit what is returned as the query cannot return rows from empty space at the edges. The performance is also not outstanding.
Using SQL or TSQL how do I determine the next minimum available integer value within an arbitrary integer range limited by other ranges?
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;
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;
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;
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;
Result. SQL Fiddle with result as simple bigint, not in hex, and with hardcoded parameter 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
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.
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
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 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
All ranges of available IP addresses for all subnets
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
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:
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_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
This will return all available ranges, for a single subnet simply uncomment the WHERE-condition: fiddle
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://i.stack.imgur.com/yplow.png', '推荐 聊天终结者 的文章《With sql find next available integer within range 》','https://www.manongdao.com/article-2141384.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}