Найдите самый маленький недостающий элемент на основе определенной формулы

Мне нужно иметь возможность найти отсутствующий элемент из таблицы с десятками миллионов строк и иметь первичный ключ BINARY(64)столбца (который является входным значением для вычисления). Эти значения в основном вставляются по порядку, но иногда я хочу использовать предыдущее значение, которое было удалено. Невозможно изменить удаленные записи IsDeletedстолбцом, поскольку иногда вставляется строка, которая на много миллионов значений опережает существующие в настоящее время строки. Это означает, что пример данных будет выглядеть примерно так:

KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF

Таким образом, вставка всех пропущенных значений между 0x000000000002и 0xFFFFFFFFFFFFневозможна, использованное количество времени и пространства было бы нежелательным. По сути, когда я запускаю алгоритм, я ожидаю, что он вернется 0x000000000003, что является первым открытием.

Я придумал алгоритм бинарного поиска в C #, который будет запрашивать базу данных для каждого значения в позиции iи проверять, ожидалось ли это значение. Для контекста, мой ужасный алгоритм: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Этот алгоритм будет выполнять, например, 26-27 SQL-запросов к таблице с 100 000 000 элементов. (Это не так много, но это будет происходить очень часто.) В настоящее время эта таблица содержит приблизительно 50 000 000 строк, и производительность становится заметной .

Моя первая альтернативная мысль - перевести это на хранимую процедуру, но у нее есть свои препятствия. (Я должен написать BINARY(64) + BINARY(64)алгоритм, а также множество других вещей.) Это было бы больно, но не невозможно. Я также рассмотрел реализацию алгоритма перевода на основе ROW_NUMBER, но у меня действительно плохое предчувствие по этому поводу. (A BIGINTне достаточно большой для этих значений.)

Я готов к другим предложениям, поскольку мне действительно нужно, чтобы это было как можно быстрее. Для чего стоит единственный столбец, выбранный запросом C # KeyCol, остальные не имеют значения для этой части.

Кроме того, что бы ни стоило, текущий запрос, который выбирает соответствующую запись, выглядит следующим образом:

SELECT [KeyCol]
  FROM [Table]
  ORDER BY [KeyCol] ASC
  OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY

Где <VALUE>индекс, предоставляемый алгоритмом. У меня также не было BIGINTпроблемы с OFFSET, но я буду. (Только наличие 50 000 000 строк прямо сейчас означает, что он никогда не запрашивает индекс выше этого значения, но в какой-то момент он окажется выше BIGINTдиапазона.)

Некоторые дополнительные данные:

• Из удалений gap:sequentialсоотношение составляет около 1:20;
• Последние 35 000 строк в таблице имеют значения> BIGINTмаксимум;

Джо уже набрал большинство пунктов, которые я только что провел, набирая час:

• Весьма сомнительно, что каждый из вас исчерпает KeyColзначения < bigintmax (9.2e18), поэтому преобразование (при необходимости) в / из bigintне должно быть проблемой, если вы ограничиваете поискиKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• Я не могу думать о запросе, который будет «эффективно» постоянно находить пробел; вам может повезти, и вы найдете пробел в начале вашего поиска, или вы можете дорого заплатить, чтобы найти пробел в ваших поисках
• хотя я кратко подумал о том, как распараллелить запрос, я быстро отказался от этой идеи (как администратор БД, я не хотел бы выяснять, что ваш процесс постоянно перегружает мой сервер данных со 100% использованием ЦП ... особенно, если вы можете использовать несколько копии этого работали одновременно); Нееееет ... о параллелизации не может быть и речи

Так что делать?

Давайте на минуту остановим (повторяющийся, интенсивно использующий процессор, перебор) идею поиска и посмотрим на картину в целом.

• в среднем одному экземпляру этого поиска потребуется отсканировать миллионы ключей индекса (и потребовать немало ресурсов процессора, перебора кэша БД и пользователя, наблюдающего за вращающимися часами), чтобы найти единственное значение
• умножьте использование процессора / кэш-тайширование / вращение часов на ... сколько поисков вы ожидаете в день?
• имейте в виду, что, вообще говоря, каждый экземпляр этого поиска должен сканировать один и тот же набор (миллионов) индексных ключей; это ЛОТ неоднократного деятельности такого минимального пособия

Я хотел бы предложить несколько дополнений к модели данных ...

• новая таблица, которая отслеживает набор значений «доступны для использования» KeyCol, например:available_for_use(KeyCol binary(64) not null primary key)
• сколько записей вы храните в этой таблице, решать вам, например, может быть, достаточно для месячной активности?
• таблицу можно периодически (еженедельно?) KeyColдополнять новой партией значений (возможно, создать хранимый процесс «top top»?) [например, обновить select/top/row_number()запрос Джо, чтобы сделать top 100000]
• Вы можете настроить процесс мониторинга, чтобы отслеживать количество доступных записей на available_for_use тот случай, если у вас начнут заканчиваться значения
• новый (или измененный) триггер DELETE на> main_table <, который помещает удаленные KeyColзначения в нашу новую таблицу available_for_useвсякий раз, когда строка удаляется из основной таблицы
• если вы разрешите обновления KeyColстолбца, то новый / измененный триггер UPDATE на> main_table <также сохранит нашу новую таблицу available_for_useобновленной
• когда приходит время «искать» новое KeyColзначение, которое вам select min(KeyCol) from available_for_use(очевидно, есть кое-что еще, поскольку а) вам нужно будет кодировать проблемы параллелизма - не нужно, чтобы 2 копии вашего процесса захватывали одно min(KeyCol)и то же, и б) вы нужно будет удалить min(KeyCol)из таблицы; это должно быть относительно легко закодировано, возможно, как хранимый процесс, и может быть обращено в другой Q & A при необходимости)
• в худшем случае, если ваш select min(KeyCol)процесс не найдет доступных строк, вы можете запустить процедуру «top top» для генерации нового пакета строк

С этими предлагаемыми изменениями в модель данных:

• Вы устраняете ОЧЕНЬ большое количество циклов ЦП
• вы устраняете ВСЕ эти повторяющиеся сканирования индекса и перебивание кэша [ваш администратор базы данных поблагодарит вас]
• вашим пользователям больше не нужно смотреть на вращающиеся песочные часы (хотя им может не понравиться потеря повода отойти от своего стола)
• Есть много способов контролировать размер available_for_useтаблицы, чтобы убедиться, что вы никогда не исчерпаете новые значения

Да, предлагаемая available_for_useтаблица - это просто таблица предварительно сгенерированных значений «следующего ключа»; и да, существует вероятность некоторой конкуренции при получении значения «next», но любая конкуренция a) легко решается с помощью надлежащей структуры таблицы / индекса / запроса и b) будет незначительной / недолгой по сравнению с издержками / задерживается с текущей идеей повторных, грубых действий, поисков по индексу.

Есть несколько проблем с этим вопросом. Индексы в SQL Server могут очень эффективно выполнять следующие действия с помощью нескольких логических операций чтения:

• проверьте, что строка существует
• проверьте, что строки не существует
• найти следующую строку, начиная с некоторой точки
• найти предыдущую строку, начиная с некоторой точки

Однако их нельзя использовать для поиска N-й строки в индексе. Для этого необходимо свернуть собственный индекс, сохраненный в виде таблицы, или отсканировать первые N строк в индексе. Ваш код C # в значительной степени основан на том факте, что вы можете эффективно найти N-й элемент массива, но вы не можете сделать это здесь. Я думаю, что алгоритм не может использоваться для T-SQL без изменения модели данных.

Вторая проблема связана с ограничениями на BINARYтипы данных. Насколько я могу сказать, вы не можете выполнять сложение, вычитание или деление обычными способами. Вы можете преобразовать ваше BINARY(64)в a, BIGINTи оно не будет выдавать ошибки преобразования, но поведение не определено :

Преобразования между любыми типами данных и двоичными типами данных не гарантируются одинаковыми между версиями SQL Server.

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

Это правда, что сейчас у вас есть значения, которые больше, чем 9223372036854775807. Однако, если вы всегда начинаете с 1 и ищете наименьшее минимальное значение, эти большие значения не могут быть релевантными, если в вашей таблице не более 9223372036854775807 строк. Это кажется маловероятным, поскольку ваша таблица в этот момент будет иметь размер около 2000 эксабайт, поэтому для ответа на ваш вопрос я собираюсь предположить, что не нужно искать очень большие значения. Я также собираюсь сделать преобразование типов данных, потому что они кажутся неизбежными.

Для тестовых данных я вставил в таблицу эквивалент 50 миллионов последовательных целых чисел, а также еще 50 миллионов целых чисел с одним пропуском значений примерно на каждые 20 значений. Я также вставил одно значение, которое не помещается в подписи BIGINT:

CREATE TABLE dbo.BINARY_PROBLEMS (
    KeyCol BINARY(64) NOT NULL
);

INSERT INTO dbo.BINARY_PROBLEMS WITH (TABLOCK)
SELECT CAST(SUM(OFFSET) OVER (ORDER BY (SELECT NULL) ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS BINARY(64))
FROM
(
    SELECT 1 + CASE WHEN t.RN > 50000000 THEN
        CASE WHEN ABS(CHECKSUM(NewId()) % 20)  = 10 THEN 1 ELSE 0 END
    ELSE 0 END OFFSET
    FROM
    (
        SELECT TOP (100000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
        CROSS JOIN master..spt_values t3
    ) t
) tt
OPTION (MAXDOP 1);

CREATE UNIQUE CLUSTERED INDEX CI_BINARY_PROBLEMS ON dbo.BINARY_PROBLEMS (KeyCol);

-- add a value too large for BIGINT
INSERT INTO dbo.BINARY_PROBLEMS
SELECT CAST(0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000 AS BINARY(64));

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

SELECT TOP (2) KeyColBigInt
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    FROM dbo.BINARY_PROBLEMS
) t
ORDER By KeyCol DESC;

Результаты показывают, что максимальное значение, которое мы конвертируем, BIGINTравно 102500672:

╔══════════════════════╗
║     KeyColBigInt     ║
╠══════════════════════╣
║ -9223372036854775808 ║
║            102500672 ║
╚══════════════════════╝

Есть 100 миллионов строк со значениями, которые вписываются в BIGINT, как и ожидалось:

SELECT COUNT(*) 
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF;

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

SELECT TOP (1) KeyCol
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    , ROW_NUMBER() OVER (ORDER BY KeyCol) RN
    FROM dbo.BINARY_PROBLEMS
    WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt <> RN
ORDER BY KeyCol;

По причинам, которые не вписываются в этот ответ, этот запрос часто запускается последовательно SQL Server, а SQL Server часто недооценивает количество строк, которые необходимо отсканировать, прежде чем будет найдено первое совпадение. На моем компьютере SQL Server сканирует 50000022 строк из индекса, прежде чем находит первое совпадение. Выполнение запроса занимает 11 секунд. Обратите внимание, что это возвращает первое значение после пробела. Непонятно, какую именно строку вы хотите получить, но вы сможете изменить запрос в соответствии со своими потребностями без особых проблем. Вот как выглядит план :

Моя единственная другая идея заключалась в том, чтобы заставить SQL Server использовать параллелизм для запроса. У меня четыре процессора, поэтому я собираюсь разбить данные на четыре диапазона и выполнить поиск по этим диапазонам. Каждому ЦПУ будет присвоен диапазон. Чтобы вычислить диапазоны, я просто взял максимальное значение и предположил, что данные были распределены равномерно. Если вы хотите быть более умным в этом, вы можете посмотреть на выборочную гистограмму статистики для значений столбцов и построить свои диапазоны таким образом. Приведенный ниже код опирается на множество недокументированных приемов, которые небезопасны для работы, включая флаг трассировки 8649 :

SELECT TOP 1 ca.KeyCol
FROM (
    SELECT 1 bucket_min_value, 25625168 bucket_max_value
    UNION ALL
    SELECT 25625169, 51250336
    UNION ALL
    SELECT 51250337, 76875504
    UNION ALL
    SELECT 76875505, 102500672
) buckets
CROSS APPLY (
    SELECT TOP 1 t.KeyCol
    FROM
    (
        SELECT KeyCol
        , CAST(KeyCol AS BIGINT) KeyColBigInt
        , buckets.bucket_min_value - 1 + ROW_NUMBER() OVER (ORDER BY KeyCol) RN
        FROM dbo.BINARY_PROBLEMS
        WHERE KeyCol >= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol <=  CAST(buckets.bucket_max_value AS BINARY(64))
    ) t
    WHERE t.KeyColBigInt <> t.RN
    ORDER BY t.KeyCol
) ca
ORDER BY ca.KeyCol
OPTION (QUERYTRACEON 8649);

Вот как выглядит шаблон параллельного вложенного цикла:

В целом, запрос выполняет больше работы, чем раньше, поскольку он будет сканировать больше строк в таблице. Тем не менее, теперь он запускается за 7 секунд на моем рабочем столе. Это может лучше распараллелить на реальном сервере. Вот ссылка на фактический план .

Я действительно не могу придумать хороший способ решить эту проблему. Выполнение расчетов за пределами SQL или изменение модели данных может быть вашим лучшим выбором.

Вот ответ, который, вероятно, не сработает для вас, но я все равно добавлю его.

Несмотря на то, что BINARY (64) перечислим, существует слабая поддержка для определения преемника элемента. Поскольку BIGINT кажется слишком маленьким для вашего домена, вы можете рассмотреть возможность использования DECIMAL (38,0), который представляется самым большим типом NUMBER в SQL-сервере.

CREATE TABLE SearchTestTableProper
( keycol decimal(38,0) not null primary key );

INSERT INTO SearchTestTableProper (keycol)
VALUES (1),(2),(3),(12);

Найти первый пробел легко, так как мы можем построить искомое число:

select top 1 t1.keycol+1 
from SearchTestTableProper t1 
where not exists (
    select 1 
    from SearchTestTableProper t2 
    where t2.keycol = t1.keycol + 1
)
order by t1.keycol;

Соединение с вложенным циклом по индексу pk должно быть достаточным для поиска первого доступного элемента.