Русский
Русский
English
Статистика
Реклама

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

Проблема



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

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



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

Поиск



Для всех кто, как и я, закончил обучение довольно давно, переподготовка по теории должна быть в порядке вещей. Бинарный поиск это простой, но чрезвычайно эффективный способ поиска значения в отсортированном массиве (в нашем случае в столбце таблицы). Массив должен быть предварительно отсортирован и конечен. Поиск осуществляется путем сравнения среднего элемента вашего массива с целью. Если они равны, то поиск окончен. Если нет, вы удаляете половину, в которой искомый элемент заведомо отсутствует, и повторяете предыдущий шаг пока не останется один. Найдите середину, сравните цель с ней, если они не равны, снова уберите половину и так далее. Общее количество шагов, необходимых для нахождения цели в худшем случае, когда вы найдете ее к самому последнему шагу, будет 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 <@rbegin -- найти середину @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 = @idend 


Последний найденный 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 < @rbegin -- ожидаемый идентификатор 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 = @idend-- проверьте, есть ли у соседних записей лучшее совпадение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> descinsert @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)
Источник: habr.com
К списку статей
Опубликовано: 03.07.2020 00:15:20
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Microsoft sql server

Sql

Алгоритмы

Db

Rdbms

Algorithms

Binary search

Категории

Последние комментарии

© 2006-2020, personeltest.ru