Быстрый поиск без индекса

Проблема

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

Конечно, они также хотели получить данные быстро. Я, как обычно, сказал: «Я посмотрю, что я могу сделать» и пошел поближе взглянуть на обсуждаемую таблицу. Удача никогда не покинет нас, индекс действительно не существовал, и таблица была огромной. Не проблема, мы можем просканировать таблицу, правильно? Неправильно. Если я чему-то научился за годы работы с базами данных, то это тому, что размер имеет значение. Таблица с сотнями миллионов записей, состоящая из нескольких целочисленных столбцов, была бы достаточно грозной. Затем добавьте различные столбцы varchar и datetime. Теперь это настоящий вызов, не так ли?

Таблица, на которую я смотрел, имела миллиард записей, буквально. Простое сканирование таблицы могло легко занять больше суток, и мне нужно было также обработать извлеченные данные. Кроме того, сканирование таблицы такого размера может оказаться не таким уж благоприятным для общего состояния системы, как кажется на первый взгляд. Все отсканированные страницы должны быть извлечены с дисков в память sql сервера, заполнив её. Это, в свою очередь, выгрузит из кеша страницы данных, которые могут быть использованы для текущих оперативных задач. Запросы ваших текущих пользователей могут ждать дольше, пока сервер перечитывает данные с дисков, вместо того, чтобы быстро повторно использовать страницы данных из памяти. Производительность может снизиться, и в худшем случае сервер может быть полностью поставлен на колени. Таким образом, при сканировании таблицы следует использовать особую технику — запускать ее небольшими партиями, сохраняя где-то текущую позицию и промежуточные результаты. Такой подход позволяет серверу перенастраиваться и иметь передышку, не допуская большой просадки производительности.

И вот я, обдумывал сценарий работы и оценивал время, которое потребуется для запуска и выполнения скрипта, когда мне пришло в голову, что значения datetime времени создания были связаны с идентификатором таблицы. Идентификатор (ID) представлял собой столбец с постоянно растущими значениями и основанным на нем первичным ключом. При выборке по идентификатору значения даты и времени создания, естественно, были предварительно отсортированы так же, как и значения идентификатора. Подожди, подумал я, я могу реализовать что-то чрезвычайно быстрое, чем сканирование таблицы, что-то, что в худшем случае потребовало бы всего 30 шагов вместо 500 000 000! Бинарный поиск!

Поиск

Для всех кто, как и я, закончил обучение довольно давно, переподготовка по теории должна быть в порядке вещей. Бинарный поиск — это простой, но чрезвычайно эффективный способ поиска значения в отсортированном массиве (в нашем случае в столбце таблицы). Массив должен быть предварительно отсортирован и конечен. Поиск осуществляется путем сравнения среднего элемента вашего массива с целью. Если они равны, то поиск окончен. Если нет, вы удаляете половину, в которой искомый элемент заведомо отсутствует, и повторяете предыдущий шаг пока не останется один. Найдите середину, сравните цель с ней, если они не равны, снова уберите половину и так далее. Общее количество шагов, необходимых для нахождения цели в худшем случае, когда вы найдете ее к самому последнему шагу, будет log(N), где N — число элементов. Сравните это с N / 2, когда вы просто перебираете массив. Вообще говоря, это было бы N, но, если бы мы могли догадаться, ближе ли цель к концу, мы могли бы вернуться назад, таким образом уменьшая общее количество необходимых шагов.

В моем случае, N=1,000,000,000 и вот как я пришел к двум числам выше: 30 и 500,000,000. Идентификатор (ID) играл бы роль перечислителя массива, а datetime создания был бы значением элемента массива. Хотя здесь есть одна оговорка. Перечислитель массива, по самому определению, является непрерывной последовательной последовательностью целых чисел. В идентификаторах таблиц легко могут быть пробелы, из-за удаления записи или повторного заполнения идентификатора. Простое определение середины путем деления диапазона идентификаторов на 2, не следует ожидать, что там будет запись с таким идентификатором. Вместо прямого поиска мне пришлось использовать функцию top (). Что-то вроде этого:

Select top(1) * from Table where id <= @id order by id desc

Я использовал “<=” и “desc” потому что я хотел найти значение либо равное или непосредственно перед целью. При условии @l, @r — это левая и правая границы соответственно, id — это середина, @dt – это время создания (creation datetime), tdt – это цель и idr реальный идентификатор таблицы (ID), алгоритм может выглядеть следующим образом:

while @l <@r

begin

    -- найти середину

    @id = @l +floor((@r-@l)/2)

    -- найти запись в таблице

    select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc

    -- переместить границу

    if(@dt<@tdt)

        @l = @id +1

    else

        @r = @id

end 

Последний найденный idr был бы идентификатор записи, после которой была нужная. Алгоритм имеет что-то вроде «левого» смещения, то есть тенденция выбирать крайнее левое из всех значений. Так как я хотел, чтобы запись со значением была как можно ближе к цели, я также проверил ближайших левых и правых соседей в таблице чтобы увидеть, был ли один из них лучше. Обратите внимание, что я не использовал реальный идентификатор из таблицы для процесса итерации, как в этом случае, с пробелами в значениях ID и при некоторых обстоятельствах, алгоритм мог уйти в бесконечный цикл.

Написание и тестирование скрипта заняли у меня около часа. Используя его, я нашел первую запись с определенной датой и временем создания. После этого я использовал простой оператор select с предложением where, которое содержало оба условия: id >= @ and creation_datetime >= @dt1 and creation_datetime < @dt2. Мне нужно было только убедиться, что оптимизатор выбрал бы использование первичного ключа вместо индекса или сканирования таблицы. В общем, я сделал это менее чем за 2 часа! Было удивительно вновь обнаружить, что алгоритмы не являются чем-то эзотерическим, похороненным глубоко внутри sql сервера, а скорее тем, что можно легко использовать в повседневной работе.

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

/* 
    Запустите этот скрипт на вашей бд
    Он найдет значение, равное или непосредственно перед целью. 
    Обратите внимание, что точность datetime ограничена 3 мс
*/
-- флаг отладки, если установлен, он будет показывать результаты для каждой итерации
declare @debug bit = 0
-- @Table - имя таблицы, в которой вы хотите искать.
declare @Table varchar(128) = 'TableX' 
-- @Id - имя столбца идентификатора (id) для таблицы 
declare @ID varchar(128) = 'Id' 
-- @DateTimeColumn - имя вашего datetime столбца со временем создания в таблице
declare @DateTimeColumn varchar(128) = 'created_dt'
-- это целевое значение даты и времени
declare @TargetDateTime datetime = '2020-01-03 18:23:03'
declare @Sql varchar(max)
set @sql = '
-- это ваш отладочный флаг
declare @debug bit = <debug>
-- это ваше целевое значение
declare @tdt datetime = ''<TargetDateTime>''
-- в этой переменной мы сохраняем промежуточное значение (результат деления) 
declare @id bigint 
-- это ваши левая и правая границы соответственно
declare @l bigint, @r bigint
-- это переменные, в которых мы храним результаты текущего шага поиска, datetime и идентификатор таблицы соответственно
declare @dt datetime, @idr bigint
-- найти первые «левые» и «правые» значения
select @l = min(<ID>), @r = max(<ID>) from <Table>
while @l < @r
begin
    -- ожидаемый идентификатор
    set @id = @l +floor((@r-@l)/2)
    -- найти значение и идентификатор записи
    select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc
    -- если требуется отладка, покажите текущие значения
    if( @debug = 1 )
    begin
        select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
    end
    if(@dt < @tdt)
        set @l = @id +1
    else
        set @r = @id
end
-- проверьте, есть ли у соседних записей лучшее совпадение
declare @t table(id bigint, dt datetime, dlt float)
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) 
  from <Table> 
 where <ID> < @idr 
order by <ID> desc
insert @t(id, dt, dlt) 
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) 
  from <Table> 
 where <ID> > @idr 
order by <ID>
insert @t(id, dt, dlt) 
select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))
select top(1) @dt = dt, @idr = id from @t order by dlt, id 
select ''Found Value'' = @dt, ''Record Id'' = @idr
'
set @sql = replace(
            replace(
             replace(
              replace(
               replace(@sql, '<ID>', @ID), 
              '<Table>', @Table), 
             '<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)),
            '<debug>', @debug),
           '<DateTimeColumn>', @DateTimeColumn)
exec (@sql)