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

Автор оригинала: Alex Chamchourine
  • Перевод

Проблема


У всех нас есть дни на работе, когда кто-то приходит к нам с по-настоящему невыполнимым требованием, для выполнения которого требуется чудо. Мой случай произошел, когда коллега по маркетингу подошел ко мне с на первый взгляд простым вопросом: если бы я мог получить данные из одной таблицы за определенный месяц пару лет назад. Можно сказать, ничего страшного, но я смутно вспомнил, что таблица была очень большой. У таблицы было поле 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)

Комментарии 40

    +2

    Какой-то адовый автоперевод. На русском читать это тяжело

      0
      а теперь такой же челлендж, только если вообще нету столбца ID с первичным индексом.
      Таблица-куча. Какие есть варианты?
        +1
        Не знаю, наверное никаких.
        Еще нужно будет постараться адаптировать это решение к таблицам где в качестве первичного ключа Guid.
          0
          Посмотрите например на Hadoop/Hive. Пожалуй в большинстве случаев там индексов нет (в старых версиях они просто не поддерживались).

          Понятно что это не вариант для классической СУБД. В их случае близким аналогом будет пожалуй шардирование. Если вы распараллелить чтение миллиарда записей по железкам можете — вы прочитаете их быстрее. Так что вопрос будет уже в обработке и ее распараллеливании.
          +6
          Краткое содержание.
          У автора в таблице был индекс primary key, и записи не пишутся прошедшей датой. И он косвенным путем нашел крайние ID записей для нужных дат.
          Ясненько-понятненько.
          А теперь пусть сделает это в таблице, где нет PK.
          Откуда взялась такая таблица в БД? Это вопрос уже к разработчикам, в другом городе.
            +1
            Не знакомы с ms sql, но все же — а разве есть сейчас современные sql движки, где нет PK в принципе?
            Даже в innodb если его нет, то он есть "Every InnoDB table has a PRIMARY KEY. If you do not provide one, then the first non-NULL UNIQUE key is used. If that can't be done, then a 6-byte, hidden, integer is provided. "
            Мы просто кроме mysql давно уже ни с чем не работали, любопытно.
              0
              Не знакомы с ms sql, но все же — а разве есть сейчас современные sql движки, где нет PK в принципе?

              Да. В MS SQL, если PK нет, его нет. Таблица будет кучей.

                0
                Не придирки ради, разве не clustered index определяет то, является ли таблица кучей? Соответственно, можно создать таблицу с PK, но без индекса и наоборот.
                  0

                  Ну наверное, да. Я уже не помню, как там точно детали устроены, но создать таблицу без PK (как явного так и неявного) точно было можно.

                    0

                    Вы правы, PK и кластерный индекс-это не одно и тоже.
                    Можно создать таблицу как без PK, так и без кластерного индекса, так и без того и другого.
                    Однако, рекомендуется для всех таблиц (кроме быть может небольших временных, постоянно меняющихся) определять кластерный индекс.

                0

                Бинарный поиск это отлично если данные полностью отсортированы. Вот только они не отсортированы. Даже несмотря на то что записи не пишутся задним числом нету ни какой гарантии что даты будут монотонно возрастать. Если не стыке дня/секунды два инсерта в базу прилетят одновременно даты вполне себе могут оказаться в неправильном порядке. ИМХО тут бага

                0

                … а в этой таблице правда нет индекса, никакого?

                  0
                  Не знаю как в этой, но вообще такие бывают, да. Таблица — лог, для аудита, типовой пример. Там даже есть поле ID — но оно заполняется из sequence, и индекса по нему реально нет.

                  P.S. Но зато там есть партиционирование, например.
                    0

                    Я знаю, что вообще бывают.

                      0

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

                        0
                        Вообще-то, по этой таблице возможно никогда не ищут. Зачем искать по логу аудита, если все нормально? Это аудит на случай инцидентов.

                        А проиндексировать условный терабайт-другой — это во-первых, работа, а во-вторых, индекс тоже займет место. Так что не факт, что индексы вообще всегда нужны.
                          0

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

                            0
                            >Потому что по логу если понадобится искать,
                            вот именно что если… С тем же успехом в случае инцидента раз в год можно один раз и просканировать все. Партиционированное — и подавно.
                              0

                              Одного раза хватит, чтобы в лучшем случае уволили, а в худшем, бизнес загнулся.

                                0
                                Вы слово партиционированный видели? Терабайт с партиционированием по дате — это может быть всего пара гигов в сутки, что есть вообще ни о чем.
                                  0

                                  Вообще о чём.
                                  Ни раз логи в гигабайты и терабайты как раз секционировал по дате, и скорость существенно выше при доступе к данным, чем без секционирования, т к секции позволяют с одной стороны минимизировать блокировки, а с другой-запустить асинхронный поиск в нескольких секциях при необходимости.
                                  P.S.: лучше использовать слово секционирование, т к партиционирование-это недоперевод от partition.

                                    0
                                    Не знаю, что у вас там за железки, у нас типовой узел кластера имеет полтерабайта оперативки. Поэтому даже терабайтовая таблица — это вообще ничто, ее два-три узла спокойно читают в память, и делают там что угодно и как угодно. Какие-то проблемы возможны примерно на два порядка позже — при объемах порядка 10 терабайт в сутки.
                                      +1
                                      Хорошо у вас там. А в народе 32ГБ ОЗУ, 400Гб база, и дохлый недоRAID с временем ожидания до 10 секунд.
                                      Каждый раз людям предлагаю, купите уже нормальный игровой комп вместо сервера, это будет другая статья расхода в бюджете и купят быстрее… полгода уже покупают.
                                        0
                                        >Хорошо у вас там.
                                        Ну, это как поглядеть. Следите за руками, как говорится :) Это хорошо, когда у вас данных всего 10 терабайт. А когда их становится 10 петабайт, возникают те же самые в общем проблемы, просто в профиль — когда в общем чатике задают вопросы типа: «Какая сволочь потребила 10000 ядер на кластере, и уже два часа их не отдает?».

                                        Причем как вы понимаете, это не обязательно будет 10 петабайт одним куском — это просто будет 1000 штук по чуть-чуть. Все равно оно упирается в проблемы масштабирования — просто в другом месте.
                                          0
                                          Ну это понятно, сам однажды смеялся над ситуацией, когда в один момент времени было:
                                          — на одном сервере на диске свободно 200 Гб, и это мало-мало-надо-срочно-что-то-делать.
                                          — на другом сервере на диске свободно 200 Мб, и этого хватит еще на пару лет.
                                            0

                                            У Вас было 10 пегабайт?
                                            А что за проект?
                                            Просто не встречал системы, где одно хранилище или одна база данных была бы больше 500 ТБ.

                                              +1
                                              У нас есть примерно 10 петабайт. Я думаю даже больше — но это не совсем корректно считать одним хранилищем, потому что это на самом деле несколько хадуп кластеров. Их можно объединить, теоретически, чтобы выглядело как один — но думаю проблемы масштабирования при этом вылезут по полной программе.

                                              И потом, там же уровень репликации 3 по умолчанию, так что если считать диски — то будет скажем 30, а не 10. В общем, в зависимости от того, какой линейкой мерять, будет получаться разное значение.

                                              Это платформа для аналитики, так что на вопрос откуда это берется, могу сказать без деталей, что отовсюду. Сколько там из одного источника — я могу только примерно прикинуть, но думаю что 500Тб это близко к реальности.
                                                +1
                                                Логи с пары десятков серверов за год будут занимать чуть меньше терабайта в Elasticsearch.
                                                И это без логов приложений, которые могут слать свои портянки.
                                                Другой вопрос, что никто их не хранит больше пары месяцев.
                                                  0

                                                  Видел размеры логов от десятков тысяч серверов с приложениями, выходило около 10 ТБ в год. И да, обычно годами все логи не хранят, периодически делая чистку.

                                            0

                                            Большое заблуждение, что при больших объемах оперативки, индексы не нужны.
                                            Индексы ещё быстрее позволят информацию вытащить и не занимать лишний раз объемы ОЗУ, которые нужны для оперативных запросов реального времени.
                                            Да и не у всех такие объемы есть по ОЗУ.
                                            В любом случае DBA платят за то, чтобы система не падала, а архитектору-чтоды система работала на любом "говне из палок"

                                              0
                                              Я никогда не говорил, что они не нужны. Я говорю, что DBA должен понимать, что вот эти вот запросы может быть будут выполняться раз в год — и тогда один раз в год возможно тупой фуллскан будет самым оптимальным вариантом (в зависимости от железа). А построение и поддержание индекса будет жрать немного ресурсов каждый день. Ну то есть, любое решение — почти всегда компромисс.
                                                0

                                                Там в любом случае будет немного жрать ресурсов даже если нет кластерного индекса. Но лучше, когда есть правила на как хранить данные, чем когда система как-то хранит данные.
                                                С другой стороны, если потом таблица вся выгружается куда-то и потом уже там проводится анализ, тогда возможно кластерный индекс и не нужен.
                                                Но лучше провести сравнение при вставках в большую таблицу и посмотреть разницу-где будет быстрее вставляться с кластерный индексом или без.
                                                У меня получалось, что в 100+ млн строк вставка с кластерный индексом была быстрее, чем без кластерного индекса. Однако, если записей всего несколько тысяч или десятков тысяч, то наоборот-вставка в таблицу без кластерного индекса была быстрее, чем с кластерным.

                                                  +1
                                                  Идея померять (ну или посчитать) — она всегда здравая!
                                                    0

                                                    Да, т к у Вас могут получиться совершенно другие результаты при Ваших условиях.
                                                    И не нужно никому доверять-всегда необходимо перепроверить для Ваших нужд и при Ваших условиях.
                                                    Т к что хорошо одним-может быть смертью для других ИС и БД.

                                        +1
                                        Да всем пофиг, по факту. Живут ведь как-то люди, без бэкапов, без аудита, без резервного сервера. Иногда один сервер на три организации, и тд и тп. Тысячи их…
                                        Что они делают, когда у них шифруется все, или последний диск помирает, для меня загадка.
                                          0

                                          Да и такое бывает, и это больно как для организации, так и для специалиста в плане профессионально роста.

                            0

                            Это частный случай, хотя и достаточно распространённый (когда таблица имеет свой суррогат, и при этом фиксируется ещё и дата/время создания записи). Если выбирать записи нужно по диапазону дат (особенно «отчетных» — месяц/квартал/год), можно сделать computed persisted колонку с формулой вида convert(date, ‘1/‘ + month(date_created) + ‘/‘ + year(date_created)) и по этой колонке уже построить индекс. Но он все равно будет огромный, так как SQL не знает, что в данном конкретном случае отображение create_date -> id сурьективно и неубывающе.


                            Знает это только человек-разработчик, поэтому для обслуживания этой большой таблицы он может построить рядом маленькую (и заполнять ее джобом по мере того, как наполняется большая таблица): month_date | min_ID | max_ID — тогда по ней можно будет сразу выбрать диапазон ID, соответствующий граничным датам, и затем уже выбрать данные из основной через clustered index seek / key lookup

                              +1
                              Только обычно проблема в том, что таблица уже есть, а индекса еще нет.
                              А бонусом идет то, что индекс на текущей БД нельзя построить в онлайне (у MS SQL редакция не та), а в ночное окно мы не успеваем, потому что замену сервера не заложили в прошлогодний бюджет.
                              +3

                              В вашей непрерывной последовательной последовательности перевода пропущен абзац с числами 30 и 500 000 000 на который осталась ссылка. А там, между прочим, на оригинального автора снизошло озарение, что идентификатор и дата связаны. Поэтому можно использовать бинарный поиск, который далее в статье и расписывается.

                                0
                                Спасибо! Добавил потерянный абзац.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое