Com sql, encontre o próximo inteiro disponível dentro do intervalo que não está presente nos subconjuntos de inteiros existentes

Neste caso, nenhuma recursão é necessária, pois temos LEAD função.

Vou pensar no problema em termos de "lacunas" e "ilhas".

Vou focar primeiro no IPv4, porque é mais fácil fazer aritmética com eles, mas a ideia para o IPv6 é a mesma e no final mostrarei uma solução genérica.

Para começar, temos uma gama completa de IPs possíveis:de 0x00000000 para 0xFFFFFFFF .

Dentro deste intervalo existem "ilhas" definidas pelos intervalos (inclusive) em dhcp_range :dhcp_range.begin_address, dhcp_range.end_address . Você pode pensar na lista de endereços IP atribuídos como outro conjunto de ilhas, cada uma com um elemento:ip_address.address, ip_address.address . Finalmente, a própria sub-rede tem duas ilhas:0x00000000, subnet.ipv4_begin e subnet.ipv4_end, 0xFFFFFFFF .

Sabemos que essas ilhas não sobreposição, o que torna nossa vida mais fácil. As ilhas podem ser perfeitamente adjacentes umas às outras. Por exemplo, quando você tem poucos endereços IP alocados consecutivamente, o gap entre eles é zero. alguma distância após o término da ilha anterior.

Então, vamos juntar todas as ilhas usando UNION (CTE_Islands ) e, em seguida, passe por todos eles na ordem de end_address (ou begin_address , use o campo que tem índice nele) e use LEAD para espiar adiante e obter o endereço inicial da próxima ilha. No final teremos uma tabela, onde cada linha possui end_address da ilha atual e begin_address da próxima ilha (CTE_Diff ). Se a diferença entre eles for maior que um, significa que o "gap" é grande o suficiente e retornaremos o end_address da ilha atual mais 1.

O primeiro endereço IP disponível para a sub-rede especificada

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;

O conjunto de resultados conterá uma linha se houver pelo menos um endereço IP disponível e não conterá nenhuma linha se não houver endereços IP disponíveis.

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

Aqui está um link para SQLFiddle . Não funcionou com parâmetro, então codifiquei 1 lá. Altere-o em UNION para outro ID de sub-rede (2 ou 3) para tentar outras sub-redes. Além disso, não exibiu o resultado em varbinary corretamente, então deixei como bigint. Use, digamos, a calculadora do Windows para convertê-lo em hexadecimal para verificar o resultado.

Se você não limitar os resultados à primeira lacuna por TOP(1) , você obterá uma lista de todos os intervalos de IP disponíveis (lacunas).

Lista de todos os intervalos de endereços IP disponíveis para uma determinada sub-rede

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;

Resultado. SQL Fiddle com resultado como bigint simples, não em hexadecimal e com ID de parâmetro codificado.

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

O primeiro endereço IP disponível para cada sub-rede

É fácil estender a consulta e retornar o primeiro endereço IP disponível para todas as sub-redes, em vez de especificar uma sub-rede específica. Use CROSS APPLY para obter a lista de ilhas para cada sub-rede e adicionar PARTITION BY subnet_sk no LEAD função.

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

Conjunto de resultados

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

Aqui está SQLFiddle . Eu tive que remover a conversão para varbinary no SQL Fiddle, porque estava mostrando resultados incorretamente.

Solução genérica para IPv4 e IPv6

Todos os intervalos de endereços IP disponíveis para todas as sub-redes

SQL Fiddle com amostra de dados IPv4 e IPv6, funções e consulta final

Seus dados de amostra para IPv6 não estavam corretos - o fim da sub-rede 0xFC00000000000000FFFFFFFFFFFFFFFF era menor que seus intervalos dhcp, então alterei para 0xFC0001066800000000000000FFFFFFFF . Além disso, você tinha IPv4 e IPv6 na mesma sub-rede, o que é complicado de manusear. Para este exemplo, mudei um pouco seu esquema - em vez de ter ipv4_begin / end explícito e ipv6_begin / end em subnet Eu fiz apenas ip_begin / end como varbinary(16) (o mesmo que para suas outras tabelas). Também removi address_family , caso contrário, seria muito grande para o SQL Fiddle.

Funções aritméticas

Para fazê-lo funcionar para IPv6, precisamos descobrir como adicionar/subtrair 1 de/para binary(16) . Eu faria a função CLR para isso. Se você não tiver permissão para habilitar o CLR, é possível via T-SQL padrão. Fiz duas funções que retornam uma tabela, ao invés de escalar, pois assim podem ser inlineadas pelo otimizador. Eu queria fazer uma solução genérica, para que a função aceitasse varbinary(16) e funciona tanto para IPv4 quanto para IPv6.

Aqui está a função T-SQL para incrementar varbinary(16) por um. Se o parâmetro não tiver 16 bytes, suponho que seja IPv4 e simplesmente o converta para bigint para adicionar 1 e depois de volta para binary . Caso contrário, eu divido binary(16) em duas partes de 8 bytes cada e converta-as em bigint . bigint é assinado, mas precisamos de incremento não assinado, portanto, precisamos verificar alguns casos.

O else parte é mais comum - simplesmente incrementamos a parte baixa em um e acrescentamos o resultado à parte alta original.

Se a parte baixa for 0xFFFFFFFFFFFFFFFF , definimos a parte baixa como 0x0000000000000000 e transportar a bandeira, ou seja, incremente a parte alta em um.

Se a parte baixa for 0x7FFFFFFFFFFFFFFF , definimos a parte baixa como 0x8000000000000000 explicitamente, porque uma tentativa de incrementar este bigint valor causaria estouro.

Se o número inteiro for 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF definimos o resultado como 0x00000000000000000000000000000000 .

A função para decrementar em um é semelhante.

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

Todos os intervalos de endereços IP disponíveis para todas as sub-redes

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;

Conjunto de resultados

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

Planos de execução

Eu estava curioso para ver como as diferentes soluções sugeridas aqui funcionam, então olhei para seus planos de execução. Lembre-se de que esses planos são para o pequeno conjunto de dados de amostra sem índices.

Minha solução genérica para IPv4 e IPv6:

Solução semelhante de dnoeth :

Solução de cha que não usa LEAD função: