С помощью sql найдите следующее доступное целое число в пределах диапазона, которого нет в существующих целочисленных подмножествах (-ах)

Описание проблемы:

задан диапазон x -> y целых без знака
   где x и y находятся в диапазоне 0 -> 2 n
   и n - 0 -> 32 (или 64 в альтернативных случаях)
   найти минимальную доступную стоимость
   не равным x или y
   что нет в существующем наборе
   где существующими множествами являются произвольные подмножества x -> y

Я работаю над созданием подсетей IPv4 и IPv6 в базе данных. Каждая подсеть определяется начальным адресом и конечным адресом (я гарантирую целостность диапазонов с помощью бизнес-правил). Поскольку IPv6 слишком велик для хранения в типе bigint, мы храним IP-адреса как binary(4) или binary(16).

Связанные данные хранятся в таблицах subnet, dhcp_range и ip_address:

  • Subnet: Диапазон подсети определяется начальным и конечным IP-адресом и сохраняется в таблице subnet. Диапазон подсети всегда имеет размер 2 n (согласно определению CIDR/netmask).
  • IP: В подсети есть 0..* IP-адреса, сохраненные в таблице ip_address. IP-адрес должен быть между начальным и конечным адресами, но не равным диапазону, как определено его связанной подсетью.
  • Диапазон DHCP: В подсети есть 0..* диапазоны DHCP, хранящиеся в таблице dhcp_range. Подобно подсети, каждый диапазон DHCP определяет начальный и конечный адреса. Диапазон DHCP ограничен связанным диапазоном подсети. Диапазоны DHCP не перекрывают друг друга.

То, что я хочу определить, - это следующий доступный IP для подсети:

  • который еще не назначен (не в таблице IP-адресов)
  • не в диапазоне DHCP
  • и не равен начальному или конечному адресу диапазона подсети.

Я ищу решение, которое найдет либо минимальный доступный адрес, либо все доступные адреса.

Моя первоначальная мысль заключалась в том, чтобы сгенерировать диапазон возможных адресов (чисел), связанных диапазоном подсети, а затем удалить адреса на основе используемых наборов:

declare @subnet_sk int = 42

;with
address_range as (
    select cast(ipv4_begin as bigint) as available_address
          ,cast(ipv4_end as bigint) as end_address, subnet_sk
      from subnet s
     where subnet_sk = @subnet_sk

    union all

    select available_address + 1, end_address, subnet_sk
      from address_range
     where available_address + 1 <= end_address
),
assigned_addresses as (
    select ip.[address]
          ,subnet_sk
      from ip_address ip
     where ip.subnet_sk = @subnet_sk
       and ip.address_family = 'InterNetwork'),
dhcp_ranges as (
    select dhcp.begin_address
          ,dhcp.end_address
          ,subnet_sk
      from dhcp_range dhcp
     where dhcp.subnet_sk = @subnet_sk
       and dhcp.address_family = 'InterNetwork')
select distinct ar.available_address
  from address_range ar
       join dhcp_ranges dhcp
         on ar.available_address
            not between dhcp.begin_address
                    and dhcp.end_address
       left join assigned_addresses aa
         on ar.available_address = aa.[address]
       join subnet s
         on ar.available_address != s.ipv4_begin
        and ar.available_address != s.ipv4_end
 where aa.[address] is null
   and s.subnet_sk = @subnet_sk
order by available_address
option (MAXRECURSION 32767)

В приведенном выше запросе используется рекурсивный CTE и не работает для всех перестановок данных. Рекурсивный КТВ является хлопотным, поскольку он ограничен максимальным размером 32 767 (намного меньше, чем размеры потенциальных диапазонов) и имеет очень реальную возможность быть очень медленным. Вероятно, я мог бы преодолеть свои проблемы с рекурсивным CTE, но запрос не выполняется при следующих условиях:

  • когда не назначены IP-адреса или диапазоны DHCP: он ничего не возвращает
    должен возвращать все IP-адреса, определенные диапазоном подсети
  • при назначении нескольких диапазонов DHCP: возвращает IP-адреса внутри диапазонов DHCP

Помощник в устранении проблемы, я создал SQL Fiddle с тремя подсетей; каждая с другой характеристикой: рубленый, пустой или в основном смежный. Вышеприведенный запрос и настройка в скрипте работают для большей части непрерывной подсети, но не для других. Существует также GitHub Gist схемы и примеры данных.

Я попытался сгенерировать последовательность чисел с рекурсивными и сложными CTE, но, как указано выше, боюсь, что они будут плохо выполняться, а в случае рекурсивных CTE искусственно ограничивают. Аарон Бертран детализирует некоторые альтернативы CTE в своей серии Генерировать набор или последовательность без циклов. К сожалению, набор данных слишком велик для таблицы чисел, так как создание одного только для адресного пространства IPv4 потребует 32 гигабайта дискового пространства (SQL Server сохраняет bigint значения в 8 байт). Я бы предпочел генерировать последовательность "на лету", но придумал хороший способ сделать это.

В качестве альтернативы, я попытался засеять мой запрос, посмотрев, что я знаю, для использования адресов:

declare @subnet_sk int = 1

select unassigned_range.*
  from (select cast(l.address as bigint) + 1 as start
              ,min(cast(fr.address as bigint)) - 1 as stop
          from ip_address as l
               left join ip_address as r on l.address = r.address - 1
               left join ip_address as fr on l.address < fr.address
         where r.address is null and fr.address is not null
           and l.subnet_sk = @subnet_sk
        group by l.address, r.address) as unassigned_range
       join dhcp_range dhcp
         on unassigned_range.start
            not between cast(dhcp.begin_address as bigint)
                and cast(dhcp.end_address as bigint)
        and unassigned_range.stop
            not between cast(dhcp.begin_address as bigint)
                and cast(dhcp.end_address as bigint)
 where dhcp.subnet_sk = @subnet_sk

К сожалению, указанный выше запрос не работает, когда в таблицах ip_address или dhcp_range нет ничего. Хуже того, поскольку он не знает границ диапазона подсети a dhcp_range к верхней границе диапазона подсети, искусственно ограничивает то, что возвращается, поскольку запрос не может возвращать строки из пустого пространства по краям. Производительность также не выдающаяся.

Использование SQL или TSQL, как определить следующее минимальное доступное целочисленное значение в пределах произвольного целочисленного диапазона, ограниченного другими диапазонами?

Ответы

Ответ 1

В этом случае рекурсия не требуется, потому что у нас есть функция LEAD.

Я подумаю о проблеме с точки зрения "пробелов" и "островов".

Сначала я сосредоточусь на IPv4, потому что с ними легче сделать арифметику, но идея для IPv6 такая же, и в конце я покажу общее решение.

Для начала у нас есть полный диапазон возможных IP-адресов: от 0x00000000 до 0xFFFFFFFF.

Внутри этого диапазона есть "острова", определяемые диапазонами (включительно) в dhcp_range: dhcp_range.begin_address, dhcp_range.end_address. Вы можете думать о списке назначенных IP-адресов как о другом наборе островов, каждый из которых имеет по одному элементу: ip_address.address, ip_address.address. Наконец, сама подсеть представляет собой два острова: 0x00000000, subnet.ipv4_begin и subnet.ipv4_end, 0xFFFFFFFF.

Мы знаем, что эти острова не перекрывают не, что облегчает нашу жизнь. Острова могут быть совершенно смежными друг с другом. Например, когда у вас мало последовательных IP-адресов, разрыв между ними равен нулю. Среди всех этих островов нам нужно найти первый зазор, который имеет по меньшей мере один элемент, то есть ненулевой зазор, т.е. Следующий остров начинается на некотором расстоянии после окончания предыдущего острова.

Итак, мы разделим все острова, используя UNION (CTE_Islands), а затем пропустим все их в порядке end_address (или begin_address, используйте поле, на котором есть индекс) и используйте LEAD, чтобы заглянуть вперед и получить начальный адрес следующего острова. В итоге у нас будет таблица, в которой каждая строка имеет end_address текущего острова и begin_address следующего острова (CTE_Diff). Если разница между ними более одного, это означает, что "зазор" достаточно широк, и мы вернем end_address текущего острова плюс 1.

Первый доступный IP-адрес для данной подсети

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;

Набор результатов будет содержать одну строку, если имеется хотя бы один IP-адрес и не будет содержать строк вообще, если нет доступных IP-адресов.

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

Вот ссылка на SQLFiddle. Он не работал с параметром, поэтому я был жестко закодирован 1 там. Измените его в UNION на другой идентификатор подсети (2 или 3), чтобы попробовать другие подсети. Кроме того, он не отображал результат в varbinary правильно, поэтому я оставил его как bigint. Используйте, скажем, калькулятор Windows, чтобы преобразовать его в шестнадцатеричный, чтобы проверить результат.

Если вы не ограничиваете результаты первого разрыва на TOP(1), вы получите список всех доступных диапазонов IP (пробелов).

Список всех диапазонов доступных IP-адресов для данной подсети

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;

Результат. SQL Fiddle с результатом как простой bigint, а не в шестнадцатеричном формате и с жестко запрограммированным идентификатором параметра.

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

Первый доступный IP-адрес для каждой подсети

Легко расширить запрос и вернуть первый доступный IP-адрес для всех подсетей, а не указывать одну конкретную подсеть. Используйте CROSS APPLY, чтобы получить список островов для каждой подсети, а затем добавьте PARTITION BY subnet_sk в функцию LEAD.

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

Набор результатов

subnet_sk    NextAvailableIPAddress
1            0xAC101129
2            0xC0A81B1F
3            0xC0A8160C

Вот SQLFiddle. Мне пришлось удалить преобразование в varbinary в SQL Fiddle, потому что оно показывало результаты неправильно.

Общее решение для IPv4 и IPv6

Все диапазоны доступных IP-адресов для всех подсетей

SQL Fiddle с образцами данных, функций и окончательного запроса IPv4 и IPv6

Ваши образцы данных для IPv6 были не совсем правильными - конец подсети 0xFC00000000000000FFFFFFFFFFFFFFFF был меньше ваших диапазонов dhcp, поэтому я изменил это на 0xFC0001066800000000000000FFFFFFFF. Кроме того, у вас были как IPv4, так и IPv6 в одной подсети, что громоздко для обработки. Для этого примера я немного изменил вашу схему - вместо явного ipv4_begin / end и ipv6_begin / end в subnet я сделал это как раз ip_begin / end как varbinary(16) (так же, как и для ваших других таблиц). Я также удалил address_family, иначе он слишком велик для SQL Fiddle.

Арифметические функции

Чтобы заставить его работать для IPv6, нам нужно выяснить, как добавить/вычесть 1 в/из binary(16). Я бы сделал CLR функцию для него. Если вы не можете разрешить CLR, это возможно с помощью стандартного T-SQL. Я сделал две функции, которые возвращают таблицу, а не скаляр, потому что таким образом они могут быть встроены оптимизатором. Я хотел создать общее решение, поэтому функция примет varbinary(16) и будет работать как для IPv4, так и для IPv6.

Здесь функция T-SQL увеличивает varbinary(16) на единицу. Если значение параметра не равно 16 байтам, я предполагаю, что это IPv4 и просто преобразовать его в bigint, чтобы добавить 1, а затем вернуться к binary. В противном случае я разбил binary(16) на две части по 8 байтов каждый и перевел их в bigint. bigint подписывается, но нам нужно беззнаковое приращение, поэтому нам нужно проверить несколько случаев.

Часть else наиболее распространена - мы просто увеличиваем низкую часть на единицу и добавляем результат к оригинальной высокой части.

Если нижняя часть 0xFFFFFFFFFFFFFFFF, тогда мы устанавливаем нижнюю часть в 0x0000000000000000 и переносим флаг, т.е. увеличиваем верхнюю часть на единицу.

Если нижняя часть 0x7FFFFFFFFFFFFFFF, то мы устанавливаем низкую часть в 0x8000000000000000 явно, потому что попытка увеличить это значение bigint вызовет переполнение.

Если все число 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, мы устанавливаем результат на 0x00000000000000000000000000000000.

Функция для уменьшения на единицу аналогична.

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

Все диапазоны доступных IP-адресов для всех подсетей

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;

Набор результатов

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

Планы выполнения

Мне было любопытно посмотреть, как работают разные решения, поэтому я посмотрел их планы выполнения. Имейте в виду, что эти планы предназначены для небольшого набора данных без каких-либо индексов.

Мое общее решение для IPv4 и IPv6:

yplow.png

Аналогичное решение dnoeth:

PCny6.png

Решение cha, которое не использует функцию LEAD:

fJb2X.png

Ответ 2

После долгих размышлений, я считаю, что запрос такой простой, как это будет делать:

with a as(
  -- next ip address
  select n.next_address, i.subnet_sk
  from ip_address i
  CROSS APPLY (SELECT convert(binary(4), convert(bigint, i.address) + 1) AS next_address) as n
  where n.next_address NOT IN (SELECT address FROM ip_address)
  AND EXISTS (SELECT 1 FROM subnet s WHERE s.subnet_sk = i.subnet_sk and n.next_address > s.ipv4_begin and n.next_address < s.ipv4_end)

  UNION -- use UNION here, not UNION ALL to remove duplicates

  -- first ip address for completely unassigned subnets
  SELECT next_address, subnet_sk
  FROM subnet 
  CROSS APPLY (SELECT convert(binary(4), convert(bigint, ipv4_begin) + 1) AS next_address) n
  where n.next_address NOT IN (SELECT address FROM ip_address)

  UNION -- use UNION here, not UNION ALL to remove duplicates

  -- next ip address from dhcp ranges
  SELECT next_address, subnet_sk
  FROM dhcp_range
  CROSS APPLY (SELECT convert(binary(4), convert(bigint, end_address) + 1) AS next_address) n
  where n.next_address NOT IN (SELECT address FROM ip_address)
)
SELECT min(next_address), subnet_sk
FROM a WHERE NOT exists(SELECT 1 FROM dhcp_range dhcp
         WHERE a.subnet_sk = dhcp.subnet_sk and a.next_address
            between dhcp.begin_address
                and dhcp.end_address)
GROUP BY subnet_sk

Это для IPV4, но может быть легко расширена для IPV6

SQLFiddle

Результаты для каждой подсети:

           subnet_sk
---------- -----------
0xAC101129 1
0xC0A81B1F 2
0xC0A8160C 3

(3 row(s) affected)

По-моему, это должно быть очень быстро. Пожалуйста, проверьте его

Ответ 3

Это вопрос, который я обычно пытаюсь решить с помощью простой суммарной суммы над + 1/-1.

ip_address: ip недоступен для ip_address, но доступен, начиная с ip_address + 1

подсеть: ip недоступен для ipv4_end, но доступен с указанием ipv4_begin + 1

dhcp_range: ip не доступен после begin_address, но доступен, начиная с end_address + 1

Теперь суммируем все + 1/-1, упорядоченные по ip-адресам, всякий раз, когда он больше нуля, это начало ряда бесплатных советов, и теперь следующая строка ip является началом используемого диапазона.

SELECT
   subnet_sk
  ,ip_begin
  ,ip_end
FROM
 (
   SELECT
      subnet_sk
     ,ip AS ip_begin
    -- ,x
     ,LEAD(ip)
      OVER (ORDER BY ip, x) - 1 AS ip_end
     ,SUM(x)
      OVER (ORDER BY ip, x 
            ROWS UNBOUNDED PRECEDING) AS avail
   FROM
   (
      SELECT
         subnet_sk, CAST(ipv4_begin AS BIGINT)+1 AS ip, 1 AS x 
      FROM subnet
   --   WHERE subnet_sk = 1

      UNION ALL

      SELECT
         subnet_sk, CAST(ipv4_end AS BIGINT), -1 
      FROM subnet
   --   WHERE subnet_sk = 1

      UNION ALL

      SELECT
         subnet_sk, CAST(begin_address AS BIGINT), -1
      FROM dhcp_range
   --   WHERE subnet_sk = 1

      UNION ALL

      SELECT
         subnet_sk, CAST(end_address AS BIGINT)+1, 1 
      FROM dhcp_range
   --   WHERE subnet_sk = 1

      UNION ALL

      SELECT
         subnet_sk, CAST(address AS BIGINT), -1 
      FROM ip_address
   --   WHERE subnet_sk = 1

      UNION ALL

      SELECT
         subnet_sk, CAST(address AS BIGINT)+1, 1 
      FROM ip_address
   --   WHERE subnet_sk = 1
   ) AS dt
 ) AS dt
WHERE avail > 0

Это вернет все доступные диапазоны, поскольку одна подсеть просто раскомментирует условие WHERE: fiddle

Ответ 4

Я немного не понимаю, как выглядят ваши данные. Утверждение проблемы, хотя и хорошо сформулированное, похоже, мало связано с запросом.

Позвольте мне предположить, что dhcp_range имеет данные. Запрос, который вы хотите:

SELECT COALESCE(MIN(dr.end_address) + 1, 0)
FROM dhcp_range dr
WHERE NOT EXISTS (SELECT 1
                  FROM dhcp_range dr2
                  WHERE dr.end_address + 1 BETWEEN dr.start_address AND dr.end_address
                 );