Интересная задачка. Поиск отсутствующего уникального значения.

[RXL]

Задачка больше академическая, т.к. можно обойтись без нее, воспользовавшись автоматической генерацией нового номера и взяв целый тип с достаточным запасом. По этому вопрос как решить эту задачу, а не о том, как сделать иначе.

Такую задачку с тем же академическим интересом я решил в далеком 2002-м и записал на бумагу, а тут мне эта задача попалась и я обнаружил в ней ошибку. Стал разбираться детальнее и оказалось, что не все так просто...

Данную задачку я решаю в MySQL, но думаю, что она примерно одинаково выглядит в любой другой СУБД.


Предположим, что есть некая таблица и в ней столбец, содержащий уникальные целые числа.

Код: (SQL)

CREATE TABLE test (id TINYINT UNSIGNED NOT NULL PRIMARY KEY); -- беззнаковое целое размеров один байт

Таблица может иметь три ключевых состояния:
1. пустая;
2. полная (значения id покрывают весь диапазон типа);
3. промежуточное состояние (в нее еще что-то можно вставить без ошибки).

Нужно сделать такой запрос (можно и не один запрос, а целый SQL-блок), который даст на выходе либо одно из свободных чисел, либо как-то сигнализирует об ошибке.


Это был первый вариант решения.

Код: (SQL)

SELECT (t1.id + 1) res
INTO id
FROM test t1
        LEFT JOIN test t2 ON (t2.id = t1.id + 1)
WHERE t2.id IS NULL
HAVING res BETWEEN 0 AND 255
LIMIT 1;

Если убрать "LIMIT 1", то запрос вернет начальные значения в пустующих окнах диапазона.
Особенности запроса:
1. таблица пуста - запрос ничего не вернет;
2. таблица не пуста, но других окон, кроме начинающегося с ноля, нет - вернет 256, которое отвергнет условие в HAVING, и в итоге - ничего.
3. таблица полная - аналогично п.2.

Попробуем в другую сторону...

Код: (SQL)

SELECT (t1.id - 1) res
INTO id
FROM test t1
        LEFT JOIN test t2 ON (t2.id = t1.id - 1)
WHERE t2.id IS NULL
HAVING res BETWEEN 0 AND 255
LIMIT 1;

Теперь болезнь немного изменилась: таже трабла с диапазоном - кончающимся значением 255.

Логично было бы состыковать оба запроса по UNION. Это решает проблему п.2., но не помогает различить ситуации, когда таблица пустая или полная. Решаю усложнением кода - переходом от одиночного оператора к блоку.

Код: (SQL)

DECLARE id INT;

SELECT COUNT(*)
INTO id
FROM test;

IF id = 0 THEN
        SET id = 1;
ELSEIF id = 256 THEN
        SET id = NULL;
ELSE
        SELECT (t1.id - 1) res
        INTO id
        FROM test t1
                LEFT JOIN test t2 ON (t2.id = t1.id - 1)
        WHERE t2.id IS NULL
        HAVING res BETWEEN 0 AND 255
        LIMIT 1;

        IF id IS NULL THEN
                SELECT (t1.id + 1) res
                INTO id
                FROM test t1
                        LEFT JOIN test t2 ON (t2.id = t1.id + 1)
                WHERE t2.id IS NULL
                HAVING res BETWEEN 0 AND 255
                LIMIT 1;
        END IF;
END IF;

А может можно как-нибудь проще решить задачу?

[PooH]

Для оракла пишу наугад, днем проверю, если не забуду.
Select min(t.id+1) from test t where not exists (Select 1 from test tt where tt.id=t.id+1) and t.id<254

[RXL]

PooH, у тебя точно тот же алгоритм, только через подзапрос (MySQL до 4.1 не поддерживала подзапросов и надо было извращаться с LEFT JOIN). Траблы остаются теже: пустая таблица и окно с началом в ноле.

t.id<254

Наверно все таки - 255...

[PooH]

... ну ё моё =) список ограничений в студию! =)

[RXL]

Никаких ограничений - просто хотелось бы узнать о других алгоритмах. И твой, и мой запросы приведутся оптимизатором к одному виду.
Кстати, у него есть серьезный недостаток - одна "таблица" пойдет в full scan. Для примера я выбрал очень маленький тип, ну, а если будет что-то по больше, то скорость по мере заполнения таблицы будет быстро падать.


Смысл в этой задаче все же есть - использование малых типов дает выйгрыш, если его потом надо использовать в нескольких индексах в нескольких таблицах: индекс меньше, скорость поиска выше. Только вот выделение id какое-то гиморное получается...

[PooH]

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

можно еще придумать вариант с аналитическим функциями - просмотр вперед/назад

[Dimka]

Академические задачки и full-scan - вещи несовместимые Индекса таблицы как математического понятия нет.

А вообще разрывы в упорядоченной последовательности целых чисел можно определять через разность соседних номеров. Где она больше 1, там разрыв. И на сколько она больше 1, столько там свободных мест. Но конец таблицы это не обрабатывает, всегда придётся задавать максимум.

[PooH]

Если диапазон чисел 0-255 (если диапазон больше, то кол-во единиц в CUBE д.б. равно спепени 2), то в оракле можно сделать "финт ушами" =)

Код:

SELECT MIN(s.cnt)
  FROM x_test t,
       (SELECT 1, (row_number() over(ORDER BY 1)) - 1 cnt
          FROM dual
         GROUP BY CUBE(1, 1, 1, 1, 1, 1, 1, 1)) s
 WHERE t.id(+) = s.cnt
 AND t.ID IS NULL

ну или

Код:

SELECT MIN(s.cnt)
  FROM x_test t,
       (SELECT xcnt - 1 cnt
          FROM (SELECT LEVEL xcnt FROM dual CONNECT BY LEVEL < 256)) s
 WHERE t.id(+) = s.cnt
       AND t.id IS NULL

[RXL]

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

Как ты видишь подобное в SQL? Есть идеи?

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

[PooH]

RXL, там явный косяк был... =)
а про последнее... там генерится ряд натуральных цисел и к нему приклеиваются существующие... ну и соответственно находится наименьшее натуральное для которого нет пары.

[Dimka]

Как ты видишь подобное в SQL? Есть идеи?

Я эту или очень близкую к ней задачу решал в 2003-м году именно через разности. Увы, сейчас не могу выделить пару часиков, чтобы восстановить. Но сразу предупреждаю, что запрос там был далёк от оптимальности и избегания full scan.

Можно посчитать разности между номером текущей строки и ID (считая, что номера строк и ID - целые числа от 1 до N). Для монотонно возрастающих номеров разность будет фиксированной (сначала 0). В месте первого разрыва она возрастает и потом опять сохраняет своё значение до следующего разрыва.

Код:

ID RowNumber Diff
1  1         0
2  2         0
4  3         1
5  4         1
6  5         1
9  6         3
10 7         3

Это была центральная идея решения. Затем группировки по разностям и определение диапазонов, заполненных номерами, через min и max для группы... Потом не помню...

Идея была почерпнута из курса "Вычислительной математики", когда там аналитические производные заменялись на численные разности, и на этом основании что-то там искалось. Положительное или отрицательное постоянное значение первой производной означает равномерное возрастание или убывание значения функции ID(RowNumber).

На код сейчас нет времени.

[RXL]

PooH, очень интересно.

Упростил выражение:

Код: (SQL)

SELECT LEVEL - 1 cnt FROM dual CONNECT BY LEVEL < 257

Одним подзапросом меньше.

Вариант с CUBE работает медленнее. Для генерации 256 значений потрачено 450мс, а на 65536 - более двух минут (не стал ждать).

Переписал немного в привычную форму с LEFT JOIN. Знаю, что функционал у нее в Oracle меньше, чем у конструкции "(+)", но это зато переносимо и логически понятнее.

Код: (SQL)

SELECT MIN(s.cnt)
FROM (SELECT LEVEL - 1 cnt FROM DUAL CONNECT BY LEVEL < 257) s
        LEFT JOIN test t ON (t.id = s.cnt)
WHERE t.id IS NULL

-- или

SELECT MIN(s.cnt)
FROM test t, (SELECT LEVEL - 1 cnt FROM DUAL CONNECT BY LEVEL < 257) s
WHERE t.id (+) = s.cnt
        AND t.id IS NULL

Запрос сильно зависим по скорости от предела диапазона: для 0..255 - мгновенно, для 0..65535 - 0.4-0.6 с, на больший диапазон задумывается надолго. Видимо, первый запрос выполняется полностью, прежде чем начнутся поиски строк в таблице test.
Очень интересный вариант. Осталось найти ему аналог в MySQL...

dimka, пока читаю...

[RXL]

dimka, вот реализация твоей идеи. Нужно найти только одно любое значение, не присутствующее в таблице.

Код: (SQL)

SELECT s.rn
FROM (
        SELECT t.id, ROWNUM - 1 rn
        FROM test t
        ORDER BY t.id
) s
WHERE s.id != s.rn
        AND ROWNUM = 1

Работает Но не обрабатывает диапазон (MAX(t.ID) + 1)...255 и пустую таблицу. Значит, требуется дополнительный запрос и условие. При попытке объединить запросы по UNION Oracle мне заявил, что типы столбцов в таблицах не совпадают (NULL и NUMBER).
Кроме того, есть затраты на full scan и сортировку. На таблице из 4 значений это не заметно совсем.

Надо подумать еще...

[RXL]

Самым тупым и скоростным способом стало создание таблицы из одного столбца, содержащей все значения ID, с последующим LEFT JOIN с таблицей test. Для 2^8 значений - пустяк, для 2^16 - 128кБ минимум. Тут тоже возможны вариации: сортировать или нет перед объединением (соотв. - нужен или нет первичный ключ).

[PooH]

Тут фишки есть - сам по себе запрос с connect by level возвращает не более 100 значений, чтобы вернулись все нужен внешний запрос. Ты правильно изменил - я его оставил чтоб по в глаза бросился . Для генерации ряда есть менее надежный способ - выборка из большой системной таблицы, например, all_objects.

Чтобы совпадали типы нужно явное преобразование to_number(null)

[PooH]

Можно сделать функцию для генерации таблицы в памяти.

Вот тема на sql.ru  про генерацию ряда чисел: http://www.sql.ru/forum/actualthread.aspx?bid=3&tid=34821&pg=1

[Антон (LogRus)]

А может следует делать всё наоборот?
Заполнить таблицу свободными номерами и по мере использования их удалять? Дёшево и сердито. просто берёшь любой ну или минимальный.

[PooH]

вот еще вариант решения (вроде работает)

Код:

SELECT nvl(MIN(tt.id) + 1, 0) res
  FROM x_test t,
       (SELECT -1 id
          FROM dual
        UNION
        SELECT id
          FROM x_test
        UNION
        SELECT 255 FROM dual) tt
 WHERE t.id(+) = tt.id + 1
       AND t.id IS NULL

[Sla]

в продолжение идеи PooH

Код:

SELECT t.id res
  FROM        (SELECT id
          FROM xtest
        UNION
        SELECT max(id)+1
          FROM x_test
       ) t,
       (SELECT min(id)-1 id
          FROM xtest
        UNION
        SELECT id
          FROM x_test
       ) tt
 WHERE (t.id- tt.id)>2

[PooH]

Sla, если в таблице только 1,2 то возвращается 3, а должно 0
Если в таблице только одно значение, то запрос ничего не возвращает.

[Sla]

PooH, я не проверял, но чуть попозже проверю

[Dimka]

Мне кажется, что поиск отсутствующих значений всегда означает перебор всех имеющихся. Каким образом можно избежать full scan (исключая случай обработки самого большого или самого маленького значения)?

[Sla]

 а идея была следующая
создать две псевдотаблицы, а потом их связать
в Oracle их можно связать по rownum
усложнив запрос

Код:

SELECT t.id res
  FROM  ( select rownum r, id
      from     (SELECT id
          FROM xtest
        UNION
        SELECT max(id)+1
          FROM x_test
       ) ) t,
       (select rownum r, id 
         from (SELECT min(id)-1 id
          FROM xtest
        UNION
        SELECT id
          FROM x_test
       )) tt
 WHERE t.r=tt.r and (t.id- tt.id)>2

если не запутался в скобках

[PooH]

Sla, когда в таблице только одно значение у тебя (t.id- tt.id)>2 не выполнится... также использую min и max у тебя не обозначен диапазон, то есть, если в таблице минимальное значение например 10, у тебя 0 не вернется в запросе.

[Sla]

согласен, не дочитал условия
Поиск отсутствующего уникального значения.

нету оракла под рукой, есть mssql
а тем более 10-ки
как я понял
SELECT LEVEL xcnt FROM dual ...
генерит порядковые номера

ушел мысль думать

[PooH]

Sla, хм... ну по поставленным условиям 0 и не обязан возвращаться, если минимальное в таблице 10... а вот если в таблице только одно значение (причем есть разница 0 это или не 0, я об это споткнулся), то Min-1 и Max+1 не пройдут по условиям

[Sla]

Код:

select tt.id from
  test2 tt
  left join test1 t on (tt.id=t.id)
where t.id is null

test2 - сгенерированная таблица от необходимого минимального значения до максимального значения в test1

[RXL]

Можно сделать функцию для генерации таблицы в памяти.

Вот тема на sql.ru  про генерацию ряда чисел: http://www.sql.ru/forum/actualthread.aspx?bid=3&tid=34821&pg=1

Интересная тема. Жаль, что ссылки на oracle magazine и т.п. говорят not found...

Вот еще одна загадочная штука Oracle из той темы:

Код: (SQL)

SELECT Y FROM DUAL
MODEL
        DIMENSION BY (0 AS X) MEASURES (0 AS Y)
        RULES ITERATE (65535)
        (Y[ITERATION_NUMBER + 1] = ITERATION_NUMBER + 1);

Выдает последовательность 0..65535 за 1 с.
Скорость MODEL не линейная: 100к значений выдает за 2-3 секунды, 200к - почти минуту.


LogRus, можно, но тогда идут расходы на содержание таблицы. Когда база промышленного масштаба, то лишний "метр" не жалко, а вообще - жалко. Ну, и просто не кошерный способ - слишком легко


PooH, запрос работает

Код:

SELECT nvl(MIN(tt.id) + 1, 0) res
  FROM x_test t,
       (SELECT -1 id
          FROM dual
        UNION
        SELECT id
          FROM x_test
        UNION
        SELECT 255 FROM dual) tt
 WHERE t.id(+) = tt.id + 1
       AND t.id IS NULL

На таблице, где первое значение - 1 (377 разрозненных значений), потрачено 16 мс.
На таблице, где первое - 20000 (332865 значений), потрачено 2 с.
На пустой странице сработало за 16 мс.
На почти полной (0..65534) - 125 мс, на полностью полной - 216 мс.

Это оказался самый скоростной запрос для умеренных по размеру таблиц (~100000 строк).

Одна странность: таблицы с PK для id обрабатываются в 2-2.5 раза медленнее, чем таблицы без индекса.

[PooH]

Думаю время тратится на чтение индекса, надо план смотреть. Думаю на такой таблице индекс только мешает. Ещё не помешало бы статистику по таблице собрать.

[RXL]

По плану индексы посмотреть забыл, но по другим вариантам смотрел. Статистика вдвое снижает стоимость (COST) full scan.