Với sql tìm số nguyên có sẵn tiếp theo trong phạm vi không có trong (các) tập hợp con số nguyên hiện có

Trong trường hợp này không cần đệ quy vì chúng ta có LEAD chức năng.

Tôi sẽ suy nghĩ về vấn đề dưới góc độ "khoảng trống" và "đảo".

Lúc đầu, tôi sẽ tập trung vào IPv4, vì nó dễ dàng hơn để làm số học với chúng, nhưng ý tưởng cho IPv6 là giống nhau và cuối cùng tôi sẽ đưa ra một giải pháp chung.

Để bắt đầu, chúng tôi có đầy đủ các IP có thể có:từ 0x00000000 thành 0xFFFFFFFF .

Bên trong phạm vi này có "đảo" được xác định bởi các phạm vi (bao gồm) trong dhcp_range :dhcp_range.begin_address, dhcp_range.end_address . Bạn có thể nghĩ về danh sách các địa chỉ IP được chỉ định như một tập hợp các đảo khác, mỗi đảo có một phần tử:ip_address.address, ip_address.address . Cuối cùng, chính mạng con là hai hòn đảo:0x00000000, subnet.ipv4_begin và subnet.ipv4_end, 0xFFFFFFFF .

Chúng tôi biết rằng những hòn đảo này không trùng lặp, điều này làm cho cuộc sống của chúng tôi dễ dàng hơn. Các quần đảo có thể tiếp giáp với nhau một cách hoàn hảo. Ví dụ:khi bạn có một vài địa chỉ IP được phân bổ liên tục, khoảng cách giữa chúng bằng không. Trong tất cả các đảo này, chúng ta cần tìm khoảng trống đầu tiên, có ít nhất một phần tử, tức là khoảng cách khác 0, tức là đảo tiếp theo bắt đầu tại một số khoảng cách sau khi hòn đảo trước đó kết thúc.

Vì vậy, chúng tôi sẽ gộp tất cả các hòn đảo lại với nhau bằng cách sử dụng UNION (CTE_Islands ) và sau đó xem qua tất cả chúng theo thứ tự end_address (hoặc begin_address , sử dụng trường có chỉ mục trên đó) và sử dụng LEAD để xem trước và lấy địa chỉ xuất phát của hòn đảo tiếp theo. Cuối cùng, chúng ta sẽ có một bảng, trong đó mỗi hàng có end_address của hòn đảo hiện tại và begin_address của hòn đảo tiếp theo (CTE_Diff ). Nếu sự khác biệt giữa chúng nhiều hơn một, điều đó có nghĩa là "khoảng cách" đủ rộng và chúng tôi sẽ trả về end_address của hòn đảo hiện tại cộng với 1.

Địa chỉ IP khả dụng đầu tiên cho mạng con đã cho

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;

Tập hợp kết quả sẽ chứa một hàng nếu có ít nhất một địa chỉ IP và sẽ không chứa hàng nào nếu không có sẵn địa chỉ IP.

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

Đây là liên kết đến SQLFiddle . Nó không hoạt động với tham số, vì vậy tôi đã cố gắng mã hóa 1 ở đó. Thay đổi nó trong UNION thành ID mạng con khác (2 hoặc 3) để thử các mạng con khác. Ngoài ra, nó không hiển thị kết quả trong varbinary chính xác, vì vậy tôi đã để nó là bigint. Giả sử, sử dụng máy tính windows để chuyển nó thành hex để xác minh kết quả.

Nếu bạn không giới hạn kết quả ở khoảng cách đầu tiên bằng TOP(1) , bạn sẽ nhận được danh sách tất cả các dải IP có sẵn (khoảng trống).

Danh sách tất cả các dải địa chỉ IP khả dụng cho một mạng con nhất định

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;

Kết quả. SQL Fiddle với kết quả là bigint đơn giản, không phải ở dạng hex và với ID thông số được mã hóa cứng.

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

Địa chỉ IP khả dụng đầu tiên cho mỗi mạng con

Dễ dàng mở rộng truy vấn và trả về địa chỉ IP sẵn có đầu tiên cho tất cả các mạng con, thay vì chỉ định một mạng con cụ thể. Sử dụng CROSS APPLY để nhận danh sách các đảo cho từng mạng con và sau đó thêm PARTITION BY subnet_sk vào LEAD chức năng.

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

Tập hợp kết quả

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

Đây là SQLFiddle . Tôi đã phải xóa chuyển đổi thành varbinary trong SQL Fiddle, vì nó hiển thị kết quả không chính xác.

Giải pháp chung cho cả IPv4 và IPv6

Tất cả các dải địa chỉ IP có sẵn cho tất cả các mạng con

SQL Fiddle với dữ liệu, chức năng và dữ liệu IPv4 và IPv6 mẫu và truy vấn cuối cùng

Dữ liệu mẫu của bạn cho IPv6 không chính xác - phần cuối của mạng con 0xFC00000000000000FFFFFFFFFFFFFFFF nhỏ hơn phạm vi dhcp của bạn, vì vậy tôi đã đổi thành 0xFC0001066800000000000000FFFFFFFF . Ngoài ra, bạn có cả IPv4 và IPv6 trong cùng một mạng con, điều này rất phức tạp để xử lý. Vì lợi ích của ví dụ này, tôi đã thay đổi giản đồ của bạn một chút - thay vì có ipv4_begin / end rõ ràng và ipv6_begin / end trong subnet Tôi chỉ làm cho nó ip_begin / end dưới dạng varbinary(16) (giống như đối với các bảng khác của bạn). Tôi cũng đã xóa address_family , nếu không thì nó quá lớn đối với SQL Fiddle.

Hàm số học

Để làm cho nó hoạt động cho IPv6, chúng ta cần tìm ra cách thêm / trừ 1 đến / từ binary(16) . Tôi sẽ thực hiện chức năng CLR cho nó. Nếu bạn không được phép kích hoạt CLR, bạn có thể thực hiện thông qua T-SQL tiêu chuẩn. Tôi đã thực hiện hai hàm trả về một bảng, chứ không phải vô hướng, bởi vì theo cách đó, chúng có thể được trình tối ưu hóa nội tuyến. Tôi muốn tạo một giải pháp chung, vì vậy hàm sẽ chấp nhận varbinary(16) và hoạt động cho cả IPv4 và IPv6.

Đây là hàm T-SQL để tăng varbinary(16) bởi một. Nếu tham số không dài 16 byte, tôi giả sử rằng đó là IPv4 và chỉ cần chuyển đổi nó thành bigint để thêm 1 và sau đó quay lại binary . Nếu không, tôi tách binary(16) thành hai phần, mỗi phần dài 8 byte và chuyển chúng thành bigint . bigint được ký, nhưng chúng tôi cần số tăng chưa ký, vì vậy chúng tôi cần kiểm tra một số trường hợp.

else phần phổ biến nhất - chúng tôi chỉ tăng phần thấp lên một và nối kết quả với phần cao ban đầu.

Nếu phần thấp là 0xFFFFFFFFFFFFFFFF , sau đó chúng tôi đặt phần thấp thành 0x0000000000000000 và chuyển cờ, tức là tăng phần cao lên một.

Nếu phần thấp là 0x7FFFFFFFFFFFFFFF , sau đó chúng tôi đặt phần thấp thành 0x8000000000000000 rõ ràng, bởi vì một nỗ lực để tăng bigint này giá trị sẽ gây tràn.

Nếu toàn bộ số là 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF chúng tôi đặt kết quả thành 0x00000000000000000000000000000000 .

Chức năng giảm dần một cũng tương tự.

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

Tất cả các dải địa chỉ IP có sẵn cho tất cả các mạng con

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;

Tập hợp kết quả

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

Kế hoạch thực thi

Tôi tò mò muốn biết các giải pháp khác nhau được đề xuất ở đây hoạt động như thế nào, vì vậy tôi đã xem xét các kế hoạch thực hiện của chúng. Hãy nhớ rằng những kế hoạch này dành cho tập dữ liệu mẫu nhỏ không có bất kỳ chỉ mục nào.

Giải pháp chung của tôi cho cả IPv4 và IPv6:

Giải pháp tương tự của dnoeth :

Giải pháp của cha không sử dụng LEAD chức năng: