Задачка. Количество IP-адресов, соответствующих шаблонам

[SQL*Plus]

Количество IP-адресов, соответствующих шаблонам

Дано

Имеются шаблоны IP-адресов (строк в формате IPv4), используемых для проверки доступа.
Шаблон состоит из цифр, точек и символов '*' (звездочка).
Цифры составляют число от 0 до 255.
Числа разделяются символами ‘.’ (точка).
Символ '* ' (звездочка) означает «любое допустимое в адресе число» (не цифру!).
Шаблон всегда начинается с числа.
Шаблон не может начинаться с символа '*' (звездочка) или ‘.’ (точка).

Допустимые варианты шаблонов:
- NNN.*,
- NNN.NNN.*,
- NNN.NNN.NNN.*,
- NNN.NNN.NNN.NNN,
где NNN – числа от 0 до 255.

Для хранения шаблонов имеется таблица IP_LIST:

Код: Выделить всё

-- Команда для создания для Oracle Database
CREATE TABLE ip_list(
   id NUMBER(9) NOT NULL
 , IP_mask      VARCHAR2(15 CHAR) NOT NULL
 , CONSTRAINT ip_list$P
      PRIMARY KEY(id)
 , CONSTRAINT ip_list$U$ip_mask
      UNIQUE(ip_mask)
 , CONSTRAINT ip_list$C$ip_mask
      CHECK (NVL( LENGTH( LTRIM(ip_mask, '.0123456789*')), 0) = 0)
);

Код: Выделить всё

-- Команда создания для SQLite
CREATE TABLE ip_list(
   id      INTEGER NOT NULL
 , IP_mask TEXT NOT NULL
 , CONSTRAINT ip_list$P
      PRIMARY KEY(id)
 , CONSTRAINT ip_list$U$ip_mask
      UNIQUE(ip_mask)
 , CONSTRAINT ip_list$C$ip_mask
      CHECK (LENGTH( LTRIM(ip_mask, '.0123456789*')) = 0)
) STRICT;

ID – идентификатор строки (первичный ключ),
IP_MASK – шаблон IP-адресов.

Скрипты для создания таблиц и загрузки тестовых данных прилагаются.
После их выполнения в таблице IP_LIST должно быть 24603 строки.

Задание

Одной командой SELECT подсчитать количество IP-адресов (IPv4) устройств, соответствующих шаблонам.

При ответе приведите:
- Название СУБД и её версию
- Команду SELECT
- Полученный результат – одно число.

Примечание: все возможные IP-адреса равноправны – это просто набор из четырёх допустимых чисел (от 0 до 255), разделенных точками.

[SQL*Plus]

Один человек сообщил мне в Телеграме правильный ответ.
Но публиковать здесь SELECT он (пока?) не стал.

[TRust]

Oracle

Код: Выделить всё

Select Sum(NVL2(B, NVL2(B1, NVL2(C, NVL2(C1, NVL2(D, NVL2(D1, 1, 0), 256), 0), 256*256), 0), 256*256*256))
from (Select A,B,C,D
            ,first_value(B) over (partition by A order by B nulls first) B1
            ,first_value(C) over (partition by A, B order by C nulls first) C1
            ,first_value(D) over (partition by A, B, C order by D nulls first) D1
      from (select regexp_substr(ip_mask, '\d+', 1, 1) A
                  ,regexp_substr(ip_mask, '\d+', 1, 2) B
                  ,regexp_substr(ip_mask, '\d+', 1, 3) C
                  ,regexp_substr(ip_mask, '\d+', 1, 4) D
              from ip_list
           )
     )

36536491

[TRust]

Postgresql

Код: Выделить всё

select sum(s)
  from (select case
                 when p[2] is null then 256*256*256 
                 when count(*) filter (where p[2] is null) over (partition by p[1]) = 1 then 0
                 when p[3] is null then 256*256
                 when count(*) filter (where p[3] is null) over (partition by p[1], p[2]) = 1 then 0
                 when p[4] is null then 256
                 when count(*) filter (where p[4] is null) over (partition by p[1], p[2], p[3]) = 1 then 0
                 else 1
               end S 
          from (Select string_to_array(ip_mask, '.', '*') p from ip_list)
        )

36536491

[SQL*Plus]

Oracle

Код: Выделить всё

Select Sum(NVL2(B, NVL2(B1, NVL2(C, NVL2(C1, NVL2(D, NVL2(D1, 1, 0), 256), 0), 256*256), 0), 256*256*256))
from (Select A,B,C,D. . .)
     )

36536491

"Trust Oracle"

ХОРОШО
Результат получился правильный.
SELECT обрабатывает данные за один проход.
Выполняется быстро - 0,5 сек (Oracle 23ai FREE на ноутбуке).

НЕХОРОШО
- Выражение Sum(NVL2(B, NVL2(B1, NVL2(C, NVL2(C1, NVL2(D, NVL2(D1, 1, 0), 256), 0), 256*256), 0), 256*256*256))
тяжело для понимания - это усложняет его сопровождение.
Форматирование средствами Oracle SQL Developer даёт такую невесёлую картину:

Код: Выделить всё

SUM ( nvl2(b,
           nvl2(b1,
                nvl2(c,
                     nvl2(c1,
                          nvl2(d,
                               nvl2(d1, 1, 0),
                               256),
                          0),
                     256 * 256),
                0),
           256 * 256 * 256) )

Предполагаю, что для лучшего понимания этот фрагмент можно переписать с использованием выражений CASE ... WHEN .... THEN ... END.

- Сопровождающий персонал должен иметь квалификацию по работе с оконными функциями и регулярными выражениями.
Это некритично, но всё же.

* * *
В целом решение мне понравилось.

[SQL*Plus]

Postgresql

Код: Выделить всё

select sum(s)
  from (select case
                 when p[2] is null then 256*256*256 
. . .
          from (Select string_to_array(ip_mask, '.', '*') p from ip_list) )

36536491

Trust PostgreSQL

ХОРОШО
- Результат получился правильный.
- SELECT обрабатывает данные за один проход.
- Предполагаю, что выполняется быстро.
(У кого есть возможность проверить, напишите сколько времени занимает выполнение запроса)
- Думаю, что использованием массивов будет приятно и понятно Python'истам...


НЕХОРОШО
Используются новые возможности стандарта SQL - (работа с массивами, filter),
которые пока не поддерживаются многими другими производителями СУБД.
Это делает очень короткий изящный код непереносимым на другие СУБД.

* * *
Понравилась лаконичность и использование новых возможностей.

[SQL*Plus]

Моё решение:

Код: Выделить всё

SELECT 
   SUM(CASE WHEN ip_mask LIKE '%.%.%.*' THEN 256
            WHEN ip_mask LIKE '%.%.*' THEN 256*256
            WHEN ip_mask LIKE '%.*' THEN 256*256*256
            ELSE 1
       END) AS cnt
FROM ip_list
WHERE id NOT IN (
   SELECT A.id
   FROM ip_list A JOIN ip_list B 
           ON A.ip_mask LIKE Replace(B.ip_mask, '*', '%')
              AND A.id <> B.id);

Результат = 36 536 491

Выполнено на ноутбуке в Oracle 23ai FREE и SQLite 3.49.1.

ХОРОШО
- Результат получился правильный.
- Код прост и понятен - это хорошо для сопровождения.
Oracle - отрабатывает мгновенно (менее 0,1 сек), поскольку использует индекс при соединении по LIKE.

НЕХОРОШО
Выполняется за несколько проходов: сначала отбираются строки, которые нужно исключить из расчета,
затем выполняется агрегация данных из оставшихся строк.
SQLite - отрабатывает катастрофически долго (202 сек = 3 мин 22 сек), поскольку НЕ использует индекс при соединении по LIKE.

Код: Выделить всё

+----------+
|   cnt    |
+----------+
| 36536491 |
+----------+
Run Time: real 201.549 user 193.828125 sys 0.640625

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

Код: Выделить всё

QUERY PLAN
|--SCAN ip_list
`--LIST SUBQUERY 1
   |--SCAN A
   |--SCAN B
   `--CREATE BLOOM FILTER

[Unanonimized]

Oracle

Код: Выделить всё

select sum(sub_pow) ans
  from ip_list
  match_recognize(
  order by IP_mask
  measures decode(translate(trim(m.ip_mask),'.*0123456789','.*') 
                 , '...*', 256
                 , '..*', 256*256
                 , '.*', 256*256*256
                 , '*', 256*256*256*256
                 , 1
                 ) as sub_pow
  pattern(m x*)
  define x as (x.ip_mask like replace(m.ip_mask,'*','%'))
)

36536491

[Unanonimized]

Postgresql

Я Вашу полечку на родной язык перевёл (с)
Oracle

Код: Выделить всё

select sum(s)
  from ( select case
                 when p2 is null then 256*256*256 
                 when count(nvl2(p2,null,1)) over (partition by p1) = 1 then 0
                 when p3 is null then 256*256
                 when count(nvl2(p3,null,1)) over (partition by p1, p2) = 1 then 0
                 when p4 is null then 256
                 when count(nvl2(p4,null,1)) over (partition by p1, p2, p3) = 1 then 0
                 else 1
               end S 
          from (  select regexp_substr(ip_mask,'\d+',1,1) p1
                       , regexp_substr(ip_mask,'\d+',1,2) p2
                       , regexp_substr(ip_mask,'\d+',1,3) p3
                       , regexp_substr(ip_mask,'\d+',1,4) p4
                    from ip_list
               )
        )

[Unanonimized]

Oracle
Причесывать не буду, просто как альтернатива

Код: Выделить всё

with t as (
        select ip_mask
             , regexp_substr(ip_mask,'\d+',1,1) p1
             , regexp_substr(ip_mask,'\d+',1,2) p2
             , regexp_substr(ip_mask,'\d+',1,3) p3
             , regexp_substr(ip_mask,'\d+',1,4) p4     
             , decode(translate(trim(ip_mask),'.*0123456789','.*') 
                     , '...*', 256
                     , '..*', 256*256
                     , '.*', 256*256*256
                     , '*', 256*256*256*256
                     , 1) as sub_pow
  from ip_list
), t2 as(
select sum(sub_pow) s
     ,   case grouping_id(p1,p2,p3,p4)
         when 15 then 0
         when 7 then case max(sub_pow) when 256*256*256 then sum(case when p2 is not null and p3 is null then -sub_pow end) end
         when 3 then case max(sub_pow) when 256*256 then sum(case when p3 is not null and p4 is null then -sub_pow end) end
         when 1 then case max(sub_pow) when 256 then sum(case when p4 is not null then -sub_pow end) end
       end adj
  from t
group by rollup(p1,p2,p3,p4)
)
select max(s) + sum(adj) ans 
  from t2
;

36536491