Как sql-запросом извлечь из базы данных информацию, которой там нет

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


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


    Но отбросим эмоции и применим логику. Ведь, как правило, требуются данные, формирование которых подчиняется некоему правилу — номера квитанций, справок и так далее… И я исхожу из того, что все эти номера и идентификаторы могут быть преобразованы в натуральную последовательность.
    То есть задача будет сформулирована следующим образом: в базе данных хранится последовательность натуральных чисел, в которой есть пропуски, и необходимо вывести пропущенные числа для пользователя.
    В такой формулировке задача уже выглядит достаточно простой. Более того — возникает желание реализовать эту задачу одним единственным 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('')
    )
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 37

      +1
      unnest
        +1
        SELECT '1-2, 4, 6, 10, 13-15, 18...';
        
          +2
          Вот ровно этим самым (получение данных, которых там нет) — игрался в конце 90-х в появившейся тогда базе (ещё на клиппере) городских телефонных номеров (квартирных) — открытие было любопытным — оказалось что в базе отсуствовали все «красивые» номера — типа 2-34-56, 3-00-00, 5-55-55
          Исходником базы был «городской телефонный справочник» — да, были времена когда фамилия-имя-адрес-телефон всех жителей города публиковались. Как оказалось — публиковались не все — позвонив наугад по некоторым — выяснил, что эти телефоны живые, т.е это не горсвязь придерживала их, а как-то кому-то они доставались. (бегло просмотрел потом справочник — телефонов с последними -00-00 в нём действительно не было).
          С тех пор кейс «как оценить объём и состав данных, которые в базе быть должны, но их там нет» попадается достаточно регулярно.
            0
            Сорри, это было лето 93-го, ещё не «конец 90-х».
              0
              Собственно,
              основная цель поста — как раз узнать, насколько это частный случай (или, может, с аналогичными задачами каждый второй сталкивается).
              Про телефонные номера интересно, а можете привести ещё пару примеров, если уж кейсы регулярные?
                0
                Ну это общий кейс, а не sql… Самое простое — найти билет (на поезд), если билетов нет. Особенность РЖД и подобных систем — долго держат бронь с первого к большому городу полустанка, напр для Киева это может быть Дарница, Бровары, Бахмач, Конотоп — и если с самого Киева в Москву билетов наглухо нет — то с указанных пунктов они вполне могут быть, и, что самое удивительное, будут в системе и билеты ДО них — и вполне можно в той же кассе купить на один и тот же поезд-вагон-место — цепочку Киев-Бахмач + Бахмач-Москва. (а если разбивку сделать ещё раз в Белгороде — то выйдет ещё и дешевле).
                Тут главное в голове иметь зарубку, что «если в (какой-либо) системе чего-то нет — это не значит, что этого нет вообще», типа «в каждой пустныне есть оазис… Но не каждый верблюд может его найти»
                А уж как в одной нефтелавке несколько скважин в системе потеряли… (о чём очень долго и не догадывались)…
                Ещё народ регулярно камеры наблюдения теряет — и тоже с обоих концов поиски забавные — что те, у кого камер живых меньше. чем вроде инсталлированных не сразу спохватываются, что наоборот, на местности — висит на верхотуре камера, питается чуть ли не от освещения, поток гонит по вай-фаю, чья, когда, кем поставлена — неведомо, арендаторы открещиваются — не наша мол…
                  0
                  Спасибо, познавательно
                  0
                  На предыдущем месте работы (музей) часто возникала необходимость узнать, какие инвентарные номера (на которых строилась логика всей работы) пропущены. Решение было практически таким же, как вы его представили (единственное различие в том, что номера могли иметь вид [some_letters] 12345 [[start_number][letter]][-][[end_number][letter]], в квадратных скобках — опциональные блоки).
                  К счастью, существовала база, в которой были перечислены промежутки этих номеров (в виде [some_letters] 12345 [start-end]).
                  Запрос, правда, в итоге был сложнее, потому что появилось ещё множество кейсов для проверки (пользователи вводили крайне разнящиеся данные, да и, в конце концов, выяснилось, что релевантнее искать не пропущенные номера, а номера, для которых сделали сразу несколько записей).
                    0
                    Да, я рассматривал простейший случай (-:
                0
                С использованием переменных можно попроще сделать. В принципе, можно и без 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
                
                  0
                  В чем смысл двух знаков подчеркивания в начале переменных?
                  0
                  Спасибо, надо действительно почитать про переменные.

                  Кстати на пустой таблице скрипт неверно отрабатывает.
                    0
                    Да, не подумал. Раз уж тут коллекция вариантов, то вот исправленный и более короткий (для 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
                    
                      0
                      Хороший запрос получился.

                      Переменные — это здорово! Столько возможностей открывается!

                      Чувствую себя диким человеком (-:
                        +1
                        Недавно пришёл к выводу (достаточно дорогой ценой), что лучше user-defined variables MySQL использовать исключительно для эмуляции оконных функций. Чрезмерное их употребление очень снижает переносимость на другие SQL.
                          0
                          Мне кажется, это классическая дилемма производительности и универсальности. (-:
                          Либо пишешь запрос универсальным — и тогда он легко переносим, но не является оптимальным для каждой СУБД, на которую переносится.
                          Либо пишешь под каждую СУБД свою версию запроса, используя те специфические возможности по оптимизации, которые отличают из друг от друга (-:
                          Это, наверно, не касается, только самых простых запросов (-:
                  0
                  Чаще задача попадается получения первого свободного номера, а не всех диапазонов
                    +1
                    Согласен, но про первый свободный номер было неинтересно писать
                    0
                    А что мешает организовать проверку наличия всех необходимых данных при их вводе, чтобы предупредить проблему?
                      0
                      Особенности бумажного документооборота.
                      Если бы номер формировался при вводе в БД, тогда вы правы. Но, увы, это не всегда зависит от вас.
                        0
                        А даже если бы формировался автоматически автоинкрментом, например, то бывают ситуации отмены транзакции. Например с договорами такое бывает часто — в последний момент клиент отказался заключать договор, уже имея на руках распечатаннную копию с присвоенным номером.
                      0
                      Для тех у кого, как и у меня, не получилось с 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


                      Отмазка: способ не работает для сильноразреженных таблиц в которых количество пропусков больше чем количество строк в квадрате. Но в базе ведь всегда найдется таблица в которой много строк, тогда ее можно использовать как 'опорную' во внутреннем запросе. )
                        0
                        В предыдущих версиях Oracle listagg можно реализовать как собственную агрегатную функцию, на сайте Тома Кайта даже была примерная реализация. Для коротких данных, вроде как тут, можно попробовать обойтись генерацией вложенного дерева и sys_connect_by_path.
                          0
                          http://apps-oracle.ru/stragg/
                        +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('')
                        )
                        
                          0
                          Спасибо, добавил скрипт в статью
                          0
                          Более компактный и менее ресурсоёмкий запрос для 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`;
                            0
                            Более лаконичная версия с расширенным функционалом, можно задавать начальный номер
                            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
                            
                              0
                              У меня так получилось:
                                 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
                                0
                                Спасибо, добавил скрипт в статью
                              0
                              Заголовок наше все. Мой любимый заголовок на новостном сайте Американка расчесала голову до мозга
                                0
                                В 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
                                           )
                                )
                                
                                  0
                                  Если так дотошно не показывать-комментировать, то получится очень кратко:
                                  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)
                                  
                                    0
                                    Спасибо за комментарий, добавил ваш скрипт в статью

                                Only users with full accounts can post comments. Log in, please.