Med sql hitta nästa tillgängliga heltal inom intervallet som inte finns i befintliga heltalsdelmängder

I det här fallet behövs ingen rekursion, eftersom vi har LEAD funktion.

Jag kommer att tänka på problemet i termer av "luckor" och "öar".

Jag kommer först att fokusera på IPv4, eftersom det är lättare att göra aritmetik med dem, men idén för IPv6 är densamma och i slutändan ska jag visa en generisk lösning.

Till att börja med har vi ett komplett utbud av möjliga IP-adresser:från 0x00000000 till 0xFFFFFFFF .

Inom detta intervall finns det "öar" definierade av intervallen (inklusive) i dhcp_range :dhcp_range.begin_address, dhcp_range.end_address . Du kan tänka på listan med tilldelade IP-adresser som en annan uppsättning öar, som har ett element vardera:ip_address.address, ip_address.address . Slutligen är själva undernätet två öar:0x00000000, subnet.ipv4_begin och subnet.ipv4_end, 0xFFFFFFFF .

Vi vet att dessa öar inte gör det överlappning, vilket gör vårt liv enklare. Öar kan ligga perfekt intill varandra. Till exempel, när du har få på varandra följande tilldelade IP-adresser, är gapet mellan dem noll. Bland alla dessa öar måste vi hitta det första gapet, som har minst ett element, d.v.s. ett gap som inte är noll, d.v.s. nästa ö börjar kl. en bit efter att den föregående ön tar slut.

Så vi sätter ihop alla öar med UNION (CTE_Islands ) och gå sedan igenom dem alla i ordningen end_address (eller begin_address , använd fältet som har index på det) och använd LEAD att kika fram och få startadressen till nästa ö. Till slut kommer vi att ha en tabell, där varje rad hade end_address av den aktuella ön och begin_address för nästa ö (CTE_Diff ). Om skillnaden mellan dem är mer än en betyder det att "gapet" är tillräckligt stort och vi returnerar end_address av den nuvarande ön plus 1.

Den första tillgängliga IP-adressen för det givna undernätet

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;

Resultatuppsättningen skulle innehålla en rad om det finns minst en IP-adress tillgänglig och skulle inte innehålla rader alls om det inte finns några tillgängliga IP-adresser.

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

Här är en länk till SQLFiddle . Det fungerade inte med parameter, så jag hårdkodade 1 där. Ändra det i UNION till annat subnät-ID (2 eller 3) för att prova andra subnät. Dessutom visade det inte resultat i varbinary korrekt, så jag lämnade det som bigint. Använd till exempel Windows-kalkylatorn för att konvertera den till hex för att verifiera resultatet.

Om du inte begränsar resultaten till den första luckan med TOP(1) , får du en lista över alla tillgängliga IP-intervall (luckor).

Lista över alla intervall av tillgängliga IP-adresser för ett givet undernät

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 enkel bigint, inte i hex, och med hårdkodat 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örsta tillgängliga IP-adressen för varje undernät

Det är lätt att utöka frågan och returnera den första tillgängliga IP-adressen för alla subnät, snarare än att ange ett visst subnät. Använd CROSS APPLY för att få en lista över öar för varje undernät och sedan lägga till PARTITION BY subnet_sk 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

Resultatuppsättning

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

Här är SQLFiddle . Jag var tvungen att ta bort konverteringen till varbinary i SQL Fiddle, eftersom det visade resultatet felaktigt.

Allmän lösning för både IPv4 och IPv6

Alla intervall av tillgängliga IP-adresser för alla undernät

SQL Fiddle med exempel på IPv4- och IPv6-data, funktioner och slutlig fråga

Din exempeldata för IPv6 var inte helt korrekt - slutet av undernätet 0xFC00000000000000FFFFFFFFFFFFFFFF var mindre än dina dhcp-intervall, så jag ändrade det till 0xFC0001066800000000000000FFFFFFFF . Dessutom hade du både IPv4 och IPv6 i samma subnät, vilket är krångligt att hantera. För det här exemplets skull har jag ändrat ditt schema lite - istället för att ha explicit ipv4_begin / end och ipv6_begin / end i subnet Jag gjorde det bara ip_begin / end som varbinary(16) (samma som för dina andra bord). Jag tog också bort address_family , annars var den för stor för SQL Fiddle.

Aritmetiska funktioner

För att få det att fungera för IPv6 måste vi ta reda på hur vi lägger till/subtraherar 1 till/från binary(16) . Jag skulle göra CLR-funktion för det. Om du inte får aktivera CLR så är det möjligt via standard T-SQL. Jag gjorde två funktioner som returnerar en tabell, snarare än skalär, eftersom de på ett sådant sätt kan infogas av optimeraren. Jag ville göra en generisk lösning, så funktionen skulle acceptera varbinary(16) och fungerar för både IPv4 och IPv6.

Här är T-SQL-funktionen för att öka varbinary(16) av en. Om parametern inte är 16 byte lång antar jag att den är IPv4 och konverterar den helt enkelt till bigint för att lägga till 1 och sedan tillbaka till binary . Annars delar jag upp binary(16) i två delar vardera 8 byte långa och gjuta dem till bigint . bigint är undertecknad, men vi behöver osignerade ökningar, så vi måste kontrollera några fall.

else del är vanligast - vi ökar helt enkelt låg del med en och lägger till resultatet till den ursprungliga höga delen.

Om låg del är 0xFFFFFFFFFFFFFFFF , sedan sätter vi låg del till 0x0000000000000000 och bär över flaggan, d.v.s. öka den höga delen med en.

Om den låga delen är 0x7FFFFFFFFFFFFFFF , sedan sätter vi låg del till 0x8000000000000000 uttryckligen, eftersom ett försök att öka denna bigint värde skulle orsaka spill.

Om hela talet är 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF vi ställer in resultatet till 0x00000000000000000000000000000000 .

Funktionen att minska med ett är liknande.

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

Alla intervall av tillgängliga IP-adresser för alla undernät

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;

Resultatuppsättning

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

Utförandeplaner

Jag var nyfiken på att se hur olika lösningar som föreslagits här fungerar, så jag tittade på deras genomförandeplaner. Tänk på att dessa planer är för små exempeluppsättningar av data utan några index.

Min generiska lösning för både IPv4 och IPv6:

Liknande lösning av dnoeth :

Lösning av cha som inte använder LEAD funktion: