company_banner

«Под капотом» индексов Postgres

http://blog.codeship.com/discovering-computer-science-behind-postgres-indexes/
  • Перевод

Капитан Немо у штурвала «Наутилуса»

Индексы — один из самых мощных инструментов в реляционных базах данных. Мы используем их, когда нужно быстро найти какие-то значения, когда объединяем базы данных, когда нужно ускорить работу SQL-операторов и т.д. Но что представляют собой индексы? И как они помогают ускорять поиск по БД? Для ответа на эти вопросы я изучил исходный код PostgreSQL, отследив, как происходит поиск индекса для простого строкового значения. Я ожидал найти сложные алгоритмы и эффективные структуры данных. И нашёл.

Здесь я расскажу о том, как устроены индексы и как они работают. Однако я не ожидал, что в их основе лежит информатика. В понимании подноготной индексов также помогли комментарии в коде, объясняющие не только как работает Postgres, но и почему он так работает.

Поиск последовательностей


Алгоритм поиска последовательностей в Postgres демонстрирует странности: он зачем-то просматривает все значения в таблице. В моём прошлом посте использовался вот такой простой SQL-оператор для поиска значения “Captain Nemo”:



Postgres спарсил, проанализировал и спланировал запрос. Затем ExecSeqScan (встроенная функция на языке С, реализующая поиск последовательностей SEQSCAN) быстро нашла нужное значение:



Но затем по необъяснимой причине Postgres продолжил сканировать всю базу, сравнивая каждое значение с искомым, хотя оно уже было найдено!



Если бы таблица содержала миллионы значений, то поиск занял бы очень много времени. Конечно, этого можно избежать, если убрать сортировку и переписать запрос так, чтобы он останавливался на первом найденном совпадении. Но проблема более глубока, и заключается она в неэффективности самого механизма поиска в Postgres. Использование поиска последовательностей для сравнения каждого значения в таблице — процесс медленный, неэффективный и зависящий от порядка размещения записей. Должен быть другой способ!

Решение простое: нужно создать индекс.

Создание индекса


Сделать это просто, достаточно выполнить команду:


Разработчики на Ruby предпочли бы использовать миграцию add_index с помощью ActiveRecord, при которой была бы выполнена та же команда CREATE INDEX. Обычно, когда мы перезапускаем select, Postgres создаёт дерево планирования. Но в данном случае оно будет несколько отличаться:



Обратите внимание, что в нижней части используется INDEXSCAN вместо SEQSCAN. INDEXSCAN не будет сканировать всю базу в отличие от SEQSCAN. Вместо этого он использует только что созданный индекс, чтобы быстро и эффективно найти нужную запись.

Создание индекса позволяет решить проблему производительности, но не даёт ответов на ряд вопросов:
  • Что именно представляет собой индекс в Postgres?
  • Как именно он выглядит, какова его структура?
  • Каким образом индекс ускоряет поиск?

Давайте ответим на эти вопросы, изучив исходники на языке С.

Что собой представляет индекс в Postgres


Начнём с документации для команды CREATE INDEX:



Здесь отображены все параметры, которые можно использовать при создании индекса. Обратите внимание на параметр USING method: он описывает, индекс какого вида нам нужен. На той же странице приведена информация о method, аргументе ключевого слова USING:



Оказывается, в Postgres реализовано четыре разных вида индексов. Их можно использовать для различных типов данных или в зависимости от ситуации. Поскольку мы не определяли параметр USING, то index_users_on_name по умолчанию представляет собой индекс вида “btree” (B-Tree).

Что такое B-Tree и где найти о нём информацию? Для этого изучим соответствующий файл с исходным кодом Postgres:



Вот что говорится о нём в README:



Кстати, сам README является 12-страничным документом. То есть нам доступны не только полезные комментарии в коде на С, но и вся необходимая информация о теории и конкретной реализации сервера БД. Чтение и разбор кода в opensource-проектах часто является непростой задачей, но только не в Postgres. Разработчики постарались облегчить нам процесс понимания устройства их детища.

Обратите внимание, что в первом же предложении есть ссылка на научную публикацию, в которой объяснено, что такое B-Tree (а значит, и как работают индексы в Postgres): Efficient Locking for Concurrent Operations on B-Trees за авторством Лемана (Lehman) и Яо (Yao).

Что такое B-Tree


В статье описывается улучшение, внесённое авторами в алгоритм B-Tree в 1981 году. Об этом мы поговорим чуть позже. Сам алгоритм был разработан в 1972 году, так выглядит пример простого B-Tree:



Название является сокращением от англ. “balanced tree”. Алгоритм позволяет ускорить операцию поиска. Например, нам нужно найти значение 53. Начнём с корневого узла, содержащего значение 40:



Оно сравнивается с искомым значением. Поскольку 53 > 40, то далее мы следуем по правой ветви дерева. А если бы мы искали, например, значение 29, то пошли бы по левой ветви, потому что 29 < 40. Следуя по правой ветви, мы попадаем в дочерний узел, содержащий два значения:



На этот раз мы сравниваем 53 со значениями 47 и 62: 47 < 53 < 62. Обратите внимание, что значения внутри узлов отсортированы. Поскольку искомое значение меньше одного и больше другого, то далее мы следуем по центральной ветви и попадаем в дочерний узел, содержащий три значения:



Сравниваем со списком отсортированных значений (51 < 53 < 56), идём по второй из четырёх ветвей и наконец попадаем в дочерний узел с искомым значением:



За счёт чего этот алгоритм ускоряет поиск:
  1. Значения (ключи) внутри каждого узла отсортированы.
  2. Алгоритм сбалансирован: ключи равномерно распределены по узлам, что позволяет минимизировать количество переходов. Каждая ветвь ведёт к дочернему узлу, содержащему примерно такое же количество ключей, что и все остальные дочерние узлы.


Как выглядит индекс в Postgres


Леман и Яо нарисовали свою диаграмму больше 30 лет назад, какое она имеет отношение к современному Postgres? Оказывается, созданный нами index_users_on_name очень похож на эту самую диаграмму. При выполнении команды CREATE INDEX Postgres сохраняет все значения из пользовательской таблицы в виде ключей дерева B-Tree. Так выглядит узел индекса:



Каждая запись в индексе состоит из структуры на языке С, называющейся IndexTupleData, а также содержит значение и битовый массив (bitmap). Последний используется для экономии места, в него записывается информация о том, принимают ли атрибуты индекса в ключе значение NULL. Сами значения следуют в индексе за битовым массивом.

Вот как выглядит структура IndexTupleData:



t_tid: это указатель на какой-либо другой индекс или запись в БД. Обратите внимание, что это не указатель на физическую память из языка С. Здесь содержатся данные, по которым Postgres ищет сопоставленные страницы памяти.

t_info: здесь содержится информация об элементах индекса. Например, сколько значений в нём хранится, равны ли они NULL и т.д.

Для лучшего понимания, рассмотрим несколько записей из index_users_on_name:



Здесь вместо value вставлены некоторые имена из БД. Узел из верхнего дерева содержит ключи “Dr. Edna Kunde” и “Julius Powlowski”, а узел нижнего — “Julius Powlowski” и “Juston Quitzon”. В отличие от диаграммы Лемана и Яо, Postgres повторяет родительские ключи в каждом дочернем узле. Например, “Julius Powlowski” является ключом в верхнем дереве и в дочернем узле. Указатель t_tid ссылается с Julius в верхнем узле на такое же имя в нижнем узле. Если вы хотите глубже изучить хранение значений ключей в узлах B-Tree, обратитесь к файлу itup.h:



Поиск узла B-Tree, содержащего наше значение


Вернёмся к нашему исходному оператору SELECT:

Как именно в Postgres осуществляется поиск значения “Captain Nemo” в индексе index_users_on_name? Почему использование индекса позволяет искать быстрее по сравнению с поиском последовательности? Давайте взглянем на некоторые имена, хранящиеся в нашем индексе:



Это корневой узел в index_users_on_name. Я просто развернул дерево так, чтобы имена умещались целиком. Здесь четыре имени и одно значение NULL. Postgres автоматически создал этот корневой узел, как только был создан сам индекс. Обратите внимание, что за исключением NULL, обозначающего начало индекса, остальные четыре имени идут в алфавитном порядке.

Как вы помните, B-Tree является сбалансированным деревом. Поэтому в данном примере дерево имеет пять дочерних узлов:
  • Имена, идущие в алфавитном порядке до “Dr. Edna Kunde”
  • Имена между “Dr. Edna Kunde” и “Julius Powlowski”
  • Имена между “Julius Powlowski” и “Monte Nicolas”
    …и т.д.


Поскольку мы ищем “Captain Nemo”, то Postgres идёт по первой ветви направо (при алфавитной сортировке искомое значение идёт до “Dr. Edna Kunde”):



Как видно из иллюстрации, далее Postgres находит узел с нужным значением. Для теста я добавил в таблицу 1000 имён. Этот правый узел содержал 240 из них. Так что дерево существенно ускорило процесс поиска, поскольку остальные 760 значений остались «за бортом».

Если вы хотите узнать больше об алгоритме поиска нужного узла в B-Tree, обратитесь к комментариям к функции _bt_search.



Поиск нашего значения внутри узла


Итак, Postgres перешёл в узел, содержащий 240 имён, среди которых ему нужно найти значение “Captain Nemo”.



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



Искомое значение идёт по алфавиту после “Breana Witting”, поэтому Postgres перескакивает к ключу, находящемуся на позиции 75% (три четверти списка):



На этот раз наше значение должно быть выше. Тогда Postgres прыгает на некоторое значение выше. В моём случае системе понадобилось восемь раз прыгать по списку ключей в узле, пока она не нашла наконец нужное значение:



Подробнее об алгоритме поиска значения внутри узла можно почитать в комментариях к функции _bt_binsrch:



Другие интересные вещи


Если у вас есть желание, то некоторое количество теории о деревьях B-Tree можно почерпнуть из научной работы Efficient Locking for Concurrent Operations on B-Trees.

Добавление ключей в B-Tree. Процедура внесения новых ключей в дерево выполняется по очень интересному алгоритму. Обычно ключ записывается в узел в соответствии с принятой сортировкой. Но что делать, если в узле уже нет свободного места? В этом случае Postgres разделяет узел на два более мелких и вставляет в один из них ключ. Также добавляет в родительский узел ключ из «точки разделения» и указатель на новый дочерний узел. Конечно, родительский узел тоже приходится разделять, чтобы вставить этот ключ, в результате процедура добавления в дерево одного единственного ключа превращается в сложную рекурсивную операцию.

Удаление ключей из B-Tree. Тоже довольно любопытная процедура. При удалении ключа из какого-то узла Postgres, если это возможно, объединяет его дочерние узлы. Это тоже может быть рекурсивная операция.

Деревья B-Link-Tree. На самом деле, в работе Лемана и Яо описывается придуманное ими нововведение, связанное с параллелизмом и блокированием, когда одно дерево используется несколькими потоками. Код Postgres и его алгоритмы должны поддерживать многопоточность, потому что к одному индексу могут обращаться (или модифицировать его) одновременно несколько клиентов. Если добавить по указателю от каждого узла на следующий дочерний узел («стрелка вправо»), то один поток может искать по дереву, в то время как другой будет разделять узел без блокирования всего индекса:



Не бойтесь исследовать


Возможно, вы знаете всё о том, как использовать Postgres, но знаете ли вы, как он устроен внутри, что у него «под капотом»? Изучение информатики, помимо работы над текущими проектами, не досужее развлечение, а часть процесса развития разработчика. Год от года наши программные инструменты становятся сложнее, многограннее, лучше, облегчая нам процесс создания сайтов и приложений. Но мы не должны забывать, что в основе всего этого лежит наука информатика. Мы, как и всё сообщество opensource-разработчиков Postgres, стоим на плечах наших предшественников, таких как Леман и Яо. Поэтому не доверяйтесь слепо инструментам, которые вы повседневно используете, изучайте их устройство. Это поможет вам достичь более высокого профессионального уровня, вы сможете найти для себя информацию и решения, о которых ранее и не подозревали.
Mail.Ru Group 788,77
Строим Интернет
Поделиться публикацией
Комментарии 21
  • +2
    Может быть вы знаете, как у Postgres обстоят дела с поиском вхождения строки, т.е. если бы вы в вашем примере искали «tain Ne»?
    • +2
      Не слишком круто, но кое-что есть:
      www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike
      Для словарного и префиксного поиска есть лучшие решения:
      stackoverflow.com/questions/17633344/is-there-a-way-to-index-in-postgres-for-fast-substring-searches

      Впрочем, задача ускорения поиска по подстроке сама по себе не имеет, видимо, эффективного решения.
      • 0
        Впрочем, задача ускорения поиска по подстроке сама по себе не имеет, видимо, эффективного решения.

        Я пока к такому же выводу пришел.
        • +1
          Есть префиксные деревья, которые могут помочь решить эту задачу.
          • 0
            а ещё есть gist_trgm_ops он же может матчинг с регулярками ускорять
            • 0
              про это первая ссылка galaxy. В текущей реализации у них ограничени на длину строки.
    • 0
      Отличная статья. А можете пояснить, каким образом в узле может закончиться место? Есть какие-то ограничения постгреса на размер узла?
      • 0
        Обычно размер узла подбирается так, чтобы он был равен одной странице ввода/вывода(или нескольким 2/4/8).
      • –2
        Для того, чтобы выяснить, как работает B-Tree индекс, вовсе не обязательно погружаться по локоть в исходные коды. Ожидал какого-то более существенного срыва покровов.
        • +2
          Следует уточнить, что для индексов используются не то что понимается под B-tree, а B* или B+ -tree. В обычных B-tree информация может храниться в узлах дерева, а в B+ — только в листьях, что дает некоторый простор для оптимизаций.
          • +1
            -Но затем по необъяснимой причине Postgres продолжил сканировать всю базу, сравнивая каждое значение с искомым, хотя оно уже было найдено!

            ожидал услышать ответ на этот вопрос, ведь вы покопались в исходниках… а вы покопались в исходниках и открыли америку
            • +2
              Ответ мне кажется очевидным, там же стоит сортировка по полю id, а это значит, что (поскольку значения name не уникальны, ведь никто не сказал обратного) даже когда мы нашли запись, удовлетворяющую условию, то это вовсе не значит, что мы нашли запись с минимальным id (поскольку нам также никто не сказал, что мы просматриваем id в нужном порядке — по возрастанию).
              • 0
                Твою дивизию ) А я уж думал, Tom Lane где-то exit for пропустил ))
              • +1
                На всякий случай замечу, что это перевод :)
                • 0
                  Потому, что запрос выглядит как «дай мне всех пользователей с именем таким-то». Нигде не говорится, что такое имя единственно. Limit применяется уже к результату выборки и на время работы запроса не влияет.
                  • +1
                    Не скажите. Если бы не было order by, было бы логично после нахождения первых N совпадений поиск прекращать…
                • 0
                  Это все, конечно, хорошо (почти хорошо, см. выше коммент про сортировку по id), но такими темпами придется очень долго исследовать то, что у Постгресса под капотом…
                  • –1
                    >> Индексы — один из самых мощных инструментов в реляционных базах данных.

                    Строго говоря индексы к реляционной модели данных никакого отношения не имеют.
                    Индексы это способ ускорить обработку данных.
                  • +2
                    Прекрасное издание Жюля Верна с отличными иллюстрациями, простите за офтоп.
                    • 0
                      Я правильно понял, что «поиск последовательностей» это перевед сочетания «sequential scan»? Если да, то по-русски это называется «последовательный перебор» или «последовательный просмотр»

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

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