Dengan sql temukan integer berikutnya yang tersedia dalam rentang yang tidak ada dalam subset integer yang ada

Dalam hal ini tidak diperlukan rekursi, karena kita memiliki LEAD fungsi.

Saya akan memikirkan masalah dalam istilah "celah" dan "pulau".

Saya akan fokus pada IPv4, karena lebih mudah untuk melakukan aritmatika dengan mereka, tetapi ide untuk IPv6 adalah sama dan pada akhirnya saya akan menunjukkan solusi umum.

Untuk memulainya, kami memiliki berbagai kemungkinan IP:dari 0x00000000 ke 0xFFFFFFFF .

Di dalam rentang ini ada "pulau" yang ditentukan oleh rentang (termasuk) di dhcp_range :dhcp_range.begin_address, dhcp_range.end_address . Anda dapat menganggap daftar alamat IP yang ditetapkan sebagai kumpulan pulau lain, yang masing-masing memiliki satu elemen:ip_address.address, ip_address.address . Akhirnya, subnet itu sendiri adalah dua pulau:0x00000000, subnet.ipv4_begin dan subnet.ipv4_end, 0xFFFFFFFF .

Kami tahu bahwa pulau-pulau ini tidak tumpang tindih, yang membuat hidup kita lebih mudah. Pulau-pulau bisa sangat berdekatan satu sama lain. Misalnya, ketika Anda memiliki beberapa alamat IP yang dialokasikan secara berurutan, jarak di antara mereka adalah nol. Di antara semua pulau ini, kita perlu menemukan celah pertama, yang memiliki setidaknya satu elemen, yaitu celah bukan nol, yaitu pulau berikutnya dimulai pada beberapa jarak setelah pulau sebelumnya berakhir.

Jadi, kita akan menggabungkan semua pulau menggunakan UNION (CTE_Islands ) lalu telusuri semuanya dalam urutan end_address (atau begin_address , gunakan bidang yang memiliki indeks di atasnya) dan gunakan LEAD untuk mengintip ke depan dan mendapatkan alamat awal pulau berikutnya. Pada akhirnya kita akan memiliki sebuah tabel, di mana setiap baris memiliki end_address pulau saat ini dan begin_address dari pulau berikutnya (CTE_Diff ). Jika selisihnya lebih dari satu, berarti "celah" cukup lebar dan kami akan mengembalikan end_address dari pulau saat ini ditambah 1.

Alamat IP pertama yang tersedia untuk subnet yang diberikan

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;

Kumpulan hasil akan berisi satu baris jika setidaknya ada satu alamat IP yang tersedia dan tidak akan berisi baris sama sekali jika tidak ada alamat IP yang tersedia.

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

Berikut ini tautan ke SQLFiddle . Itu tidak berfungsi dengan parameter, jadi saya membuat kode keras 1 di sana. Ubah di UNION ke ID subnet lain (2 atau 3) untuk mencoba subnet lain. Juga, itu tidak menampilkan hasil di varbinary benar, jadi saya meninggalkannya sebagai bigint. Gunakan, katakanlah, kalkulator windows untuk mengubahnya menjadi heksadesimal untuk memverifikasi hasil.

Jika Anda tidak membatasi hasil pada celah pertama dengan TOP(1) , Anda akan mendapatkan daftar semua rentang IP yang tersedia (celah).

Daftar semua rentang alamat IP yang tersedia untuk subnet tertentu

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;

Hasil. SQL Fiddle dengan hasil sebagai bigint sederhana, bukan dalam hex, dan dengan ID parameter hardcoded.

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

Alamat IP pertama yang tersedia untuk setiap subnet

Sangat mudah untuk memperluas kueri dan mengembalikan alamat IP pertama yang tersedia untuk semua subnet, daripada menentukan satu subnet tertentu. Gunakan CROSS APPLY untuk mendapatkan daftar pulau untuk setiap subnet dan kemudian tambahkan PARTITION BY subnet_sk ke dalam LEAD fungsi.

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

Set hasil

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

Ini SQLFiddle . Saya harus menghapus konversi ke varbinary di SQL Fiddle, karena menampilkan hasil yang salah.

Solusi umum untuk IPv4 dan IPv6

Semua rentang alamat IP yang tersedia untuk semua subnet

SQL Fiddle dengan contoh data IPv4 dan IPv6, fungsi, dan kueri terakhir

Data sampel Anda untuk IPv6 salah - akhir subnet 0xFC00000000000000FFFFFFFFFFFFFFFF kurang dari rentang dhcp Anda, jadi saya mengubahnya menjadi 0xFC0001066800000000000000FFFFFFFF . Juga, Anda memiliki IPv4 dan IPv6 di subnet yang sama, yang rumit untuk ditangani. Demi contoh ini, saya telah sedikit mengubah skema Anda - alih-alih memiliki ipv4_begin / end eksplisit dan ipv6_begin / end di subnet Saya membuatnya hanya ip_begin / end sebagai varbinary(16) (sama seperti untuk tabel Anda yang lain). Saya juga menghapus address_family , jika tidak, itu terlalu besar untuk SQL Fiddle.

Fungsi aritmatika

Untuk membuatnya bekerja untuk IPv6 kita perlu mencari cara untuk menambah/mengurangi 1 ke/dari binary(16) . Saya akan membuat fungsi CLR untuk itu. Jika Anda tidak diizinkan untuk mengaktifkan CLR, dimungkinkan melalui T-SQL standar. Saya membuat dua fungsi yang mengembalikan tabel, bukan skalar, karena sedemikian rupa mereka dapat digarisbawahi oleh pengoptimal. Saya ingin membuat solusi umum, sehingga fungsinya akan menerima varbinary(16) dan bekerja untuk IPv4 dan IPv6.

Berikut adalah fungsi T-SQL untuk menambah varbinary(16) dengan satu. Jika parameter tidak panjangnya 16 byte, saya berasumsi bahwa itu adalah IPv4 dan cukup mengubahnya menjadi bigint untuk menambahkan 1 lalu kembali ke binary . Jika tidak, saya membagi binary(16) menjadi dua bagian dengan panjang masing-masing 8 byte dan memasukkannya ke dalam bigint . bigint ditandatangani, tetapi kami membutuhkan kenaikan yang tidak ditandatangani, jadi kami perlu memeriksa beberapa kasus.

else bagian yang paling umum - kami hanya menambah bagian rendah satu per satu dan menambahkan hasil ke bagian tinggi asli.

Jika bagian rendah 0xFFFFFFFFFFFFFFFF , lalu kita set low part ke 0x0000000000000000 dan membawa bendera, yaitu menambah bagian tinggi satu per satu.

Jika bagian rendah 0x7FFFFFFFFFFFFFFF , lalu kita set low part ke 0x8000000000000000 secara eksplisit, karena upaya untuk meningkatkan bigint . ini nilai akan menyebabkan overflow.

Jika bilangan bulat 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF kami menetapkan hasil ke 0x00000000000000000000000000000000 .

Fungsi untuk mengurangi satu sama.

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

Semua rentang alamat IP yang tersedia untuk semua subnet

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;

Set hasil

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

Rencana eksekusi

Saya ingin tahu bagaimana solusi berbeda yang disarankan di sini bekerja, jadi saya melihat rencana eksekusi mereka. Perlu diingat bahwa paket ini adalah untuk kumpulan sampel kecil data tanpa indeks apa pun.

Solusi umum saya untuk IPv4 dan IPv6:

Solusi serupa oleh dnoeth :

Solusi oleh cha yang tidak menggunakan LEAD fungsi: