15.06.2016 13:25
avshukan 34 9300 Источник

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


Приходят пользователи и просят: «Вот мы внесли данные в базу, а скажите нам, чего не хватает? Какие данные мы ещё не внесли в базу и их не хватает для полного счастья?»
Первая (и скажем честно, весьма глупая) реакция: «Как же я вам найду то, чего нет в базе данных?».


Но отбросим эмоции и применим логику. Ведь, как правило, требуются данные, формирование которых подчиняется некоему правилу — номера квитанций, справок и так далее… И я исхожу из того, что все эти номера и идентификаторы могут быть преобразованы в натуральную последовательность.
То есть задача будет сформулирована следующим образом: в базе данных хранится последовательность натуральных чисел, в которой есть пропуски, и необходимо вывести пропущенные числа для пользователя.
В такой формулировке задача уже выглядит достаточно простой. Более того — возникает желание реализовать эту задачу одним единственным sql-запросом.


Давайте создадим таблицу и заполним какими-нибудь данными.


CREATE TABLE IF NOT EXISTS `Test` (`id` int(6) NOT NULL);
INSERT INTO `Test` (`id`) VALUES (3), (5), (7), (8) , (9) , (11) , (12), (16) , (17) ;

Основная идея следующая: сравнить таблицу с самой собой же и для каждого значения ИКС найти минимальное ИГРЕК (которое всё же больше ИКСа), где (ИКС + 1) и (ИГРЕК — 1) будут нашими границами пропущенных диапазонов чисел. Добавив логичное условие, что, (ИКС + 1) должен быть не меньше (ИГРЕК — 1) получим следующие диапазоны: от 4 до 4, от 6 до 6, от 10 до 10 и от 13 до 15.
Какие есть нюансы:
1) Может быть пропущен первый элемент последовательности (в нашем случае это 1)
2) Неизвестен последний элемент последовательности (а вдруг это 22). Можно, конечно, запрашивать эту информацию у пользователя, но опыт подсказывает, что лучше этого избегать.
3) Диапазон «от 4 до 4» выглядит глючно, надо заменить просто на одно число
4) Результат всё-таки желательно получить значением одной строки, а не набором строк


Учитываем замечания и получаем вариант скрипта под MySQL:


SELECT GROUP_CONCAT( ranges )
FROM (
     SELECT
     CASE
          WHEN id2 IS NULL
          THEN CONCAT( id1, '...' )
          WHEN id1 = id2
          THEN id1
          ELSE CONCAT( id1, '-', id2 )
     END ranges
     FROM (
          SELECT id +1 id1, (
               SELECT MIN( id ) -1
               FROM `Test` t2
               WHERE t2.id > t1.id
               )id2
          FROM `Test` t1
          UNION
          SELECT 1 , MIN( id ) -1
          FROM `Test` t3
     )t
     WHERE id1 <= id2
     OR id2 IS NULL
     ORDER BY id1
)tt

и вариант под Oracle:


SELECT LISTAGG (ranges, ', ')
FROM (
     SELECT CASE
          WHEN id2 IS NULL THEN TO_CHAR (id1) || '...'
          WHEN id1 = id2 THEN TO_CHAR (id1)
          ELSE TO_CHAR (id1) || '-' || TO_CHAR (id2)
     END  ranges
     FROM (
          SELECT id + 1 id1,
               (SELECT MIN (id) - 1
               FROM TEST t2
               WHERE t2.id < t1.id)  id2
          FROM TEST t1
          UNION
          SELECT 1, MIN (id) - 1
          FROM TEST t3) t
     WHERE id1 <= id2 OR id2 IS NULL
     ORDER BY id1
) tt

Результатом их выполнения является строка '1-2, 4, 6, 10, 13-15, 18...'
Во-первых, эта строка содержит то, что хотели пользователи.
Во-вторых, результат выглядит понятно для любого пользователя.
И в-главных, запрос выводит данные, которые действительно в базе данных не хранятся!


UPD1:


Большое спасибо всем, кто предложил варианты по улучшению скриптов, да и просто высказал интерес к этому вопросу.
Как это часто бывает, комментарии оказались интереснее и полезнее первоначальной статьи.
Действительно, стоило отметить, что нюанс номер 4 не реализуется стандартным синтаксисом SQL и для этой задачи необходимо привлекать дополнительный функционал, реализуемый на каждой отдельной СУБД по своему.
Ниже привожу скрипты, вытянутые мной из комментариев к статье.


Вариант для MySQL от asmm 


SELECT CONCAT(IFNULL(CONCAT(GROUP_CONCAT(miss_num), ','), '')
        , IFNULL(MAX(id) + 1, @start_num)
        , '...'
    ) miss_num
FROM (
    SELECT @prev_id prev_id
        , CASE
            WHEN @prev_id + 1 = id THEN NULL
            WHEN @prev_id + 2 = id THEN @prev_id + 1
            ELSE CONCAT(@prev_id + 1, '-', id - 1)
        END miss_num
        , @prev_id := id id
    FROM (SELECT @start_num := 1 start_num, @prev_id := @start_num - 1 prev_id) p
        , `Test` t
    WHERE t.id >= p.start_num
    ORDER BY t.id
) t

Вариант для Oracle от xtender


select listagg(id1||decode(id2
                            ,id1 ,null
                            ,null,'...'
                            ,'-'||id2)
              ,',') 
         within group(order by id1)s
from (select max(id)+1                            id1
            ,lead(min(id)) over(order by min(id)) id2
      from (select 0 id, 0 rn from dual
            union all
            select id,row_number()over(order by id) rn from test)
      group by id - rn)

Вариант для MSSQL от yizraor


select rlist =
(
    select "text()" =
        iif(id1 < id2, convert(varchar(15), id1) +
        iif(id1 < (id2 - 1), '-' + convert(varchar(15), id2 - 1), ''), '') +
        iif(id3 is null, iif(id1 < id2, ', ', '') + convert(varchar(15), id2 + 1) + '...', ', ')
    from
    (
        select
            id1 = isnull(lag(id) over (order by id), 0) + 1,
            id2 = id,
            id3 = lead(id) over (order by id)
        from test
    ) t
    where ( id1 < id2 ) or ( id3 is null )
    order by id2
    for xml path('')
)
Поделиться с друзьями
-->

Комментарии (34)


  1. maxru
    15.06.2016 16:51
    #9657364
    +1

    unnest


  1. Igogo2012
    15.06.2016 16:52
    #9657368
    +1

    SELECT '1-2, 4, 6, 10, 13-15, 18...';


  1. impetus
    15.06.2016 16:57
    #9657382
    +2

    Вот ровно этим самым (получение данных, которых там нет) — игрался в конце 90-х в появившейся тогда базе (ещё на клиппере) городских телефонных номеров (квартирных) — открытие было любопытным — оказалось что в базе отсуствовали все «красивые» номера — типа 2-34-56, 3-00-00, 5-55-55
    Исходником базы был «городской телефонный справочник» — да, были времена когда фамилия-имя-адрес-телефон всех жителей города публиковались. Как оказалось — публиковались не все — позвонив наугад по некоторым — выяснил, что эти телефоны живые, т.е это не горсвязь придерживала их, а как-то кому-то они доставались. (бегло просмотрел потом справочник — телефонов с последними -00-00 в нём действительно не было).
    С тех пор кейс «как оценить объём и состав данных, которые в базе быть должны, но их там нет» попадается достаточно регулярно.


    1. impetus
      15.06.2016 17:06
      #9657396

      Сорри, это было лето 93-го, ещё не «конец 90-х».


    1. avshukan
      15.06.2016 17:44
      #9657444

      Собственно,
      основная цель поста — как раз узнать, насколько это частный случай (или, может, с аналогичными задачами каждый второй сталкивается).
      Про телефонные номера интересно, а можете привести ещё пару примеров, если уж кейсы регулярные?


      1. impetus
        15.06.2016 22:17
        #9657868

        Ну это общий кейс, а не sql… Самое простое — найти билет (на поезд), если билетов нет. Особенность РЖД и подобных систем — долго держат бронь с первого к большому городу полустанка, напр для Киева это может быть Дарница, Бровары, Бахмач, Конотоп — и если с самого Киева в Москву билетов наглухо нет — то с указанных пунктов они вполне могут быть, и, что самое удивительное, будут в системе и билеты ДО них — и вполне можно в той же кассе купить на один и тот же поезд-вагон-место — цепочку Киев-Бахмач + Бахмач-Москва. (а если разбивку сделать ещё раз в Белгороде — то выйдет ещё и дешевле).
        Тут главное в голове иметь зарубку, что «если в (какой-либо) системе чего-то нет — это не значит, что этого нет вообще», типа «в каждой пустныне есть оазис… Но не каждый верблюд может его найти»
        А уж как в одной нефтелавке несколько скважин в системе потеряли… (о чём очень долго и не догадывались)…
        Ещё народ регулярно камеры наблюдения теряет — и тоже с обоих концов поиски забавные — что те, у кого камер живых меньше. чем вроде инсталлированных не сразу спохватываются, что наоборот, на местности — висит на верхотуре камера, питается чуть ли не от освещения, поток гонит по вай-фаю, чья, когда, кем поставлена — неведомо, арендаторы открещиваются — не наша мол…


        1. avshukan
          16.06.2016 12:18
          #9658722

          Спасибо, познавательно


      1. ySky
        15.06.2016 22:39
        #9657952

        На предыдущем месте работы (музей) часто возникала необходимость узнать, какие инвентарные номера (на которых строилась логика всей работы) пропущены. Решение было практически таким же, как вы его представили (единственное различие в том, что номера могли иметь вид [some_letters] 12345 [[start_number][letter]][-][[end_number][letter]], в квадратных скобках — опциональные блоки).
        К счастью, существовала база, в которой были перечислены промежутки этих номеров (в виде [some_letters] 12345 [start-end]).
        Запрос, правда, в итоге был сложнее, потому что появилось ещё множество кейсов для проверки (пользователи вводили крайне разнящиеся данные, да и, в конце концов, выяснилось, что релевантнее искать не пропущенные номера, а номера, для которых сделали сразу несколько записей).


        1. avshukan
          19.06.2016 15:58
          #9663384

          Да, я рассматривал простейший случай (-:


  1. michael_vostrikov
    15.06.2016 20:06
    #9657662

    С использованием переменных можно попроще сделать. В принципе, можно и без 3-го уровня вложенности обойтись, но так понятнее выглядит.

    SELECT GROUP_CONCAT(__range)
FROM (
    SELECT IF(__from = __to, __from, CONCAT(__from, '-', __to)) AS __range
    FROM (
        SELECT  (@n + 1) AS __from,  (id - 1) AS __to,  @n := id AS __change
        FROM (
            SELECT id, @n := 0 FROM test ORDER BY id
        ) t
    ) t2
    WHERE __to >= __from
    
    UNION
    
    SELECT CONCAT((@n + 1), '...') AS __range
) t3


    1. m8rge
      16.06.2016 21:04
      #9659906

      В чем смысл двух знаков подчеркивания в начале переменных?


      1. michael_vostrikov
        16.06.2016 21:10
        #9659926

        'from' и 'to' — ключевые слова


        1. m8rge
          17.06.2016 07:05
          #9660310

          А __range, __change?


          1. michael_vostrikov
            17.06.2016 07:17
            #9660318
            +1

            И они тоже)


    1. avshukan
      22.06.2016 15:17
      #9669326

      Спасибо, надо действительно почитать про переменные.

      Кстати на пустой таблице скрипт неверно отрабатывает.


      1. michael_vostrikov
        22.06.2016 18:25
        #9669872

        Да, не подумал. Раз уж тут коллекция вариантов, то вот исправленный и более короткий (для MySQL):

        SELECT CONCAT_WS(',',
    GROUP_CONCAT( IF(f = t, f, CONCAT(f, '-', t)) ),
    CONCAT((@n + 1), '...')
) AS result
FROM (
    SELECT  (@n + 1) AS f,  (id - 1) AS t,  @n := id AS c
    FROM (SELECT @n := 0) t, test
    ORDER BY id
) t2
WHERE t >= f


  1. VolCh
    15.06.2016 20:10
    #9657664

    Чаще задача попадается получения первого свободного номера, а не всех диапазонов


    1. avshukan
      16.06.2016 12:21
      #9658730
      +1

      Согласен, но про первый свободный номер было неинтересно писать


  1. burrdarr
    16.06.2016 12:15
    #9658706

    А что мешает организовать проверку наличия всех необходимых данных при их вводе, чтобы предупредить проблему?


    1. avshukan
      16.06.2016 12:23
      #9658736

      Особенности бумажного документооборота.
      Если бы номер формировался при вводе в БД, тогда вы правы. Но, увы, это не всегда зависит от вас.


      1. VolCh
        16.06.2016 19:08
        #9659730

        А даже если бы формировался автоматически автоинкрментом, например, то бывают ситуации отмены транзакции. Например с договорами такое бывает часто — в последний момент клиент отказался заключать договор, уже имея на руках распечатаннную копию с присвоенным номером.


  1. KonstantinSoloviov
    16.06.2016 18:04
    #9659602

    Для тех у кого, как и у меня, не получилось с Oracle:

    Функцию LISTAGG можно использовать в следующих версиях Oracle / PLSQL:
    Oracle 12c, Oracle 11g Release 2

    Насколько я знаю задача объединения полей выборки в одну строку не может быть решена в стандартном SQL без привлечения специальных функций агрегирования типа LISTAGG.

    «В столбик» же задачу можно решить как-то так:

    DROP TABLE TEST;
CREATE TABLE Test ( Id NUMBER NOT NULL );

INSERT INTO Test(id) VALUES (3);
INSERT INTO Test(id) VALUES (5);
INSERT INTO Test(id) VALUES (7);
INSERT INTO Test(id) VALUES (8);
INSERT INTO Test(id) VALUES (9);
INSERT INTO Test(id) VALUES (11);
INSERT INTO Test(id) VALUES (12);
INSERT INTO Test(id) VALUES (16);
INSERT INTO Test(id) VALUES (17);

select nid from
(select ROWNUM nid from Test, Test where ROWNUM <= (select max(id) from Test)+1)
left join Test T on T.id = nid
where T.id is null
order by nid

    NID
    ----------
    1
    2
    4
    6
    10
    13
    14
    15
    18


    Отмазка: способ не работает для сильноразреженных таблиц в которых количество пропусков больше чем количество строк в квадрате. Но в базе ведь всегда найдется таблица в которой много строк, тогда ее можно использовать как 'опорную' во внутреннем запросе. )


    1. Vapaamies
      17.06.2016 00:59
      #9660144

      В предыдущих версиях Oracle listagg можно реализовать как собственную агрегатную функцию, на сайте Тома Кайта даже была примерная реализация. Для коротких данных, вроде как тут, можно попробовать обойтись генерацией вложенного дерева и sys_connect_by_path.


      1. avshukan
        17.06.2016 11:55
        #9660720

        http://apps-oracle.ru/stragg/


  1. yizraor
    16.06.2016 23:55
    #9660104
    +1

    заголовок громкий :)
    но задача (нахождение пропусков в нумерации) не такая уж и малоизвестная.

    кстати, насчет MySQL не знаю, а в ORACLE есть функции LAG() и LEAD(), с которыми можно бы избавиться от лишних подзапросов.

    под рукой сейчас только MSSQL, так что на нём набросал вот такой вариант, который идет в одно чтение таблицы (и вообще без сортировки, если поле «id» — первичный ключ):

    select rlist =
(
	select "text()" =
		iif(id1 < id2, convert(varchar(15), id1) +
		iif(id1 < (id2 - 1), '-' + convert(varchar(15), id2 - 1), ''), '') +
		iif(id3 is null, iif(id1 < id2, ', ', '') + convert(varchar(15), id2 + 1) + '...', ', ')
	from
	(
		select
			id1 = isnull(lag(id) over (order by id), 0) + 1,
			id2 = id,
			id3 = lead(id) over (order by id)
		from test
	) t
	where ( id1 < id2 ) or ( id3 is null )
	order by id2
	for xml path('')
)


    1. avshukan
      22.06.2016 15:19
      #9669340

      Спасибо, добавил скрипт в статью


  1. asmm
    17.06.2016 11:41
    #9660696

    Более компактный и менее ресурсоёмкий запрос для MySQL:
    DROP TABLE IF EXISTS `Test`;
    CREATE TABLE IF NOT EXISTS `Test` (`id` int(6) NOT NULL/* PRIMARY KEY*/);
    INSERT INTO `Test` (`id`) VALUES (3), (5), (7), (8), (9), (11), (17), (12), (16);

    SET @prev_id := 0;
    SELECT CONCAT(GROUP_CONCAT(miss_num), ',', MAX(id) + 1, '...') miss_num
    FROM (
    SELECT t.*
    , CASE
    WHEN prev_id_plan = prev_id_fact THEN NULL
    WHEN prev_id_plan = prev_id_fact + 1 THEN prev_id_plan
    ELSE CONCAT(prev_id_fact + 1, '-', prev_id_plan)
    END miss_num
    FROM (
    SELECT id — 1 prev_id_plan, @prev_id prev_id_fact, @prev_id := id id
    FROM `Test` t
    ORDER BY t.id
    ) t
    ) t
    ;

    DROP TABLE `Test`;


    1. asmm
      17.06.2016 12:23
      #9660802

      Более лаконичная версия с расширенным функционалом, можно задавать начальный номер

      SELECT CONCAT(IFNULL(CONCAT(GROUP_CONCAT(miss_num), ','), '')
, IFNULL(MAX(id) + 1, @start_num)
, '...'
) miss_num
FROM (
SELECT @prev_id prev_id
, CASE
    WHEN @prev_id + 1 = id THEN NULL
    WHEN @prev_id + 2 = id THEN @prev_id + 1
    ELSE CONCAT(@prev_id + 1, '-', id - 1)
  END miss_num
, @prev_id := id id
FROM (SELECT @start_num := 1 start_num, @prev_id := @start_num - 1 prev_id) p
, `Test` t
WHERE t.id >= p.start_num
ORDER BY t.id
) t


      1. xtender
        19.06.2016 01:04
        #9662890

        У меня так получилось:

           select
      concat(
         ifnull(group_concat(if(id-p=1,'',concat(p+1,if(id-p=2,'',concat('-',id-1)),',')) separator ''),'')
        ,max(id)+1,'...')
      s
   from (
         select @p p
               ,@p := id id
         from (
               select 0 id, @rn:=0 rn from dual
               union all
               select id, @rn:=@rn+1  from test
              ) v1
         ) v2

        но я не спец по mysql


      1. avshukan
        22.06.2016 15:19
        #9669344

        Спасибо, добавил скрипт в статью


  1. sergeypid
    17.06.2016 12:11
    #9660760

    Заголовок наше все. Мой любимый заголовок на новостном сайте Американка расчесала голову до мозга


  1. xtender
    18.06.2016 02:25
    #9662332

    В Oracle все это можно сделать за один скан.
    Объединение диапазонов вообще древняя и широкоизвестная задача и делается кучей разных способов, например так:

    select
   listagg(decode(id1,id2,to_char(id1),to_char(id1)||'-'||to_char(id2)),',') 
      within group(order by id1)s -- просто форматирование
from (
     select min(id) id1,max(id) id2  -- это у нас и есть схлопнутые диапазоны, т.е. типа (1,3); (4,4); (7,10)
     from (select id,row_number()over(order by id) rn
           from test)
     group by id - rn -- группируем по дельте от ряда
     )

    Соответственно, чтобы найти пропущенные/недостающие, достаточно внести небольшое изменение — после «схлопывания» диапазонов группировкой, вывести диапазоны между ними, используя lead или lag и +-1:
    select
   listagg(decode(id2
                 ,id1 ,to_char(id1)
                 ,null,to_char(id1)||'...'
                 ,to_char(id1)||'-'||to_char(id2)
                 )
           ,',') 
      within group(order by id1)s -- просто требуемое форматирование
from (
      select
         id2+1 id1 -- конец предыдущего + 1
        ,lead(id1) over(order by id1)-1 id2 --начало следующего - 1
      from (
           select min(id) id1,max(id) id2 -- это у нас и есть схлопнутые диапазоны, т.е. типа (1,3); (4,4); (7,10)
           from (select 0 id, 0 rn from dual -- добавляем "начало"
                 union all
                 select id,row_number()over(order by id) rn
                 from test)
           group by id - rn
           )
)


    1. xtender
      18.06.2016 02:36
      #9662338

      Если так дотошно не показывать-комментировать, то получится очень кратко:

      select listagg(id1||decode(id2
                            ,id1 ,null
                            ,null,'...'
                            ,'-'||id2)
              ,',') 
         within group(order by id1)s
from (select max(id)+1                            id1
            ,lead(min(id)) over(order by min(id)) id2
      from (select 0 id, 0 rn from dual
            union all
            select id,row_number()over(order by id) rn from test)
      group by id - rn)


      1. avshukan
        22.06.2016 15:20
        #9669350

        Спасибо за комментарий, добавил ваш скрипт в статью