I dette tilfælde behøves ingen rekursion, fordi vi har LEAD funktion.
Jeg vil tænke over problemet i form af "huller" og "øer".
Jeg vil først fokusere på IPv4, fordi det er lettere at regne med dem, men idéen til IPv6 er den samme, og til sidst vil jeg vise en generisk løsning.
Til at starte med har vi et komplet udvalg af mulige IP'er:fra 0x00000000 til 0xFFFFFFFF .
Inden for dette område er der "øer" defineret af områderne (inklusive) i dhcp_range :dhcp_range.begin_address, dhcp_range.end_address . Du kan tænke på listen over tildelte IP-adresser som et andet sæt øer, som hver har et element:ip_address.address, ip_address.address . Endelig er selve undernettet to øer:0x00000000, subnet.ipv4_begin og subnet.ipv4_end, 0xFFFFFFFF .
Vi ved, at disse øer ikke gør det overlap, hvilket gør vores liv lettere. Øer kan være perfekt støder op til hinanden. For eksempel, når du har få fortløbende tildelte IP-adresser, er afstanden mellem dem nul. Blandt alle disse øer skal vi finde det første hul, som har mindst ét element, dvs. ikke-nul hul, dvs. den næste ø starter kl. et stykke efter den forrige ø slutter.
Så vi samler alle øer ved hjælp af UNION (CTE_Islands ) og gå derefter igennem dem alle i rækkefølgen end_address (eller begin_address , brug det felt, der har indeks på) og brug LEAD at kigge frem og få startadressen på den næste ø. Til sidst får vi en tabel, hvor hver række havde end_address af den aktuelle ø og begin_address af den næste ø (CTE_Diff ). Hvis forskellen mellem dem er mere end én, betyder det, at "mellemrummet" er stort nok, og vi returnerer end_address af den nuværende ø plus 1.
Den første tilgængelige IP-adresse for det givne undernet
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;
Resultatsættet ville indeholde én række, hvis der er mindst én tilgængelig IP-adresse, og ville slet ikke indeholde rækker, hvis der ikke er tilgængelige IP-adresser.
For parameter 1 result is `0xAC101129`.
For parameter 2 result is `0xC0A81B1F`.
For parameter 3 result is `0xC0A8160C`.
Her er et link til SQLFiddle
. Det virkede ikke med parameter, så jeg hårdkodede 1 der. Skift det i UNION til andet undernet-id (2 eller 3) for at prøve andre undernet. Det viste heller ikke resultatet i varbinary korrekt, så jeg forlod det som bigint. Brug f.eks. Windows-beregneren til at konvertere den til hex for at bekræfte resultatet.
Hvis du ikke begrænser resultaterne til det første hul med TOP(1) , får du en liste over alle tilgængelige IP-intervaller (gaps).
Liste over alle rækker af tilgængelige IP-adresser for et givet undernet
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;
Resultat. SQL Fiddle med resultatet som simpel bigint, ikke i hex, og med hårdkodet 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
Den første tilgængelige IP-adresse for hvert undernet
Det er nemt at udvide forespørgslen og returnere den første tilgængelige IP-adresse for alle undernet, i stedet for at angive et bestemt undernet. Brug CROSS APPLY for at få en liste over øer for hvert undernet og derefter tilføje PARTITION BY subnet_sk ind i LEAD funktion.
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
Resultatsæt
subnet_sk NextAvailableIPAddress
1 0xAC101129
2 0xC0A81B1F
3 0xC0A8160C
Her er SQLFiddle
. Jeg var nødt til at fjerne konvertering til varbinary i SQL Fiddle, fordi den viste resultater forkert.
Generisk løsning til både IPv4 og IPv6
Alle rækker af tilgængelige IP-adresser for alle undernet
SQL Fiddle med eksempler på IPv4- og IPv6-data, funktioner og endelig forespørgsel
Dine eksempeldata for IPv6 var ikke helt korrekte - slutningen af undernettet 0xFC00000000000000FFFFFFFFFFFFFFFF var mindre end dine dhcp-intervaller, så jeg ændrede det til 0xFC0001066800000000000000FFFFFFFF . Desuden havde du både IPv4 og IPv6 i det samme undernet, hvilket er besværligt at håndtere. Af hensyn til dette eksempel har jeg ændret dit skema lidt - i stedet for at have eksplicit ipv4_begin / end og ipv6_begin / end i subnet Jeg lavede det bare ip_begin / end som varbinary(16) (samme som for dine andre borde). Jeg fjernede også address_family , ellers var den for stor til SQL Fiddle.
Aritmetiske funktioner
For at få det til at fungere for IPv6 skal vi finde ud af, hvordan vi tilføjer/fratrækker 1 til/fra binary(16) . Jeg ville lave CLR-funktion til det. Hvis du ikke må aktivere CLR, er det muligt via standard T-SQL. Jeg lavede to funktioner, der returnerer en tabel i stedet for skalar, fordi de på en sådan måde kan indlejres af optimizeren. Jeg ville lave en generisk løsning, så funktionen ville acceptere varbinary(16) og fungerer til både IPv4 og IPv6.
Her er T-SQL-funktion til at øge varbinary(16) af én. Hvis parameteren ikke er 16 bytes lang, antager jeg, at den er IPv4 og konverterer den blot til bigint for at tilføje 1 og derefter tilbage til binary . Ellers opdeler jeg binary(16) i to dele 8 bytes lange hver og cast dem til bigint . bigint er underskrevet, men vi har brug for usignerede stigninger, så vi skal tjekke nogle få tilfælde.
else del er mest almindelig - vi øger simpelthen lav del med én og tilføjer resultatet til original høj del.
Hvis lav del er 0xFFFFFFFFFFFFFFFF , så sætter vi lav del til 0x0000000000000000 og overfør flaget, dvs. forøg den høje del med én.
Hvis den lave del er 0x7FFFFFFFFFFFFFFF , så sætter vi lav del til 0x8000000000000000 eksplicit, fordi et forsøg på at øge denne bigint værdi ville forårsage overløb.
Hvis hele tallet er 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF vi indstiller resultatet til 0x00000000000000000000000000000000 .
Funktionen til at formindske med én er den samme.
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
Alle rækker af tilgængelige IP-adresser for alle undernet
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;
Resultatsæt
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
Udførelsesplaner
Jeg var nysgerrig efter at se, hvordan forskellige løsninger, der er foreslået her, virker, så jeg kiggede på deres udførelsesplaner. Husk, at disse planer er for det lille eksempelsæt af data uden nogen indekser.
Min generiske løsning til både IPv4 og IPv6:
Lignende løsning af dnoeth :
Løsning af cha der ikke bruger LEAD funktion:
