DDL. Индексы. Введение, виды индексов

Сегодня мы познакомимся с механизмом индексов в PostgreSQL. В целом, индексы присутствуют в любой реляционной (и ряде нереляционных) СУБД, но виды индексов могут быть различны.

Что такое индекс?

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

Определение выше в некоторой степени упрощенное, мы его расширим в рамках следующего урока.

В качестве простой аналогии из Java можно представить индекс как отдельную упорядоченную коллекцию (например, TreeMap), ссылающуюся на элементы другой коллекции - неупорядоченной.

Как можно догадаться из аналогии выше, индексы позволяют оптимизировать поиск данных, в сравнении с  таковым в неупорядоченном множестве элементов, а также сортировку элементов (в ряде случаев).

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

О последнем немного более подробно поговорим в следующем пункте.

Проблемы индексов

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

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

• Потребление памяти. Индексы требуют память для хранения собственной структуры, тем самым увеличивая общий вес БД. Это не выглядит критичным, если данных в таблице мало. Но представьте таблицы с сотнями миллионов или миллиардами записей (а ведь это всего лишь данные какой-нибудь телеметрии, поступающие ежечасно в течении 10 лет для 10 тысяч объектов - вполне реальный сценарий), которые обслуживаются десятками индексов. Это гигабайты памяти, которая будет затрачена сверх той, которая требуется для хранения самих данных. А ведь сами структуры тоже могут храниться физически не оптимально в памяти, еще больше усугубляя эти проблемы;
• Замедление работы операций записи (вставки, обновления и удаления). Это также было сказано выше. Представьте, что добавление каждой строки в таблицу должно также перестроить десятки индексов. Если система является нагруженной, с изменением сотен или тысяч записей в секунду/минуту, дополнительные расходы на индексацию будут ощутимы. Если система требует быстродействия - могут оказаться критичными;
• Кроме прочего, сами индексы могут быть построены не эффективно (скажем, могут быть проблемы при балансировке деревьев, на базе которых и строится большинство индексов). Изначально или вследствии дальнейшей жизнедеятельности (при множественном изменении состава записей в таблице). Вплоть до того, что использование индекса при SELECT’е данных будет давать худший результат, чем фильтрация и сортировка данных без него. Если первое целиком остается ответственностью того, кто индекс добавил, то для второго СУБД предоставляют различные инструменты - общие, или характерные для конкретной СУБД, включая возможность перестроить существующий индекс прямой командой или же функциональность по прямому указанию СУБД, какие индексы использовать для конкретного запроса;
• Влияние на план запроса. Этот пункт плотно связан с предыдущим. Его суть в том, что SQL - декларативный язык, соответственно, он сам выбирает способ поиска и фильтрации данных - включая выбор индекса (или его игнорирование) при получении данных. Это происходит на базе собираемой СУБД статистики, которая и решает, какой план запроса будет оптимальным в каждом конкретном случае. Избыточное число индексов может приводить к тому, что статистика будет менее показательной, а значит - формируемый план запроса может быть не оптимальным;
• Фрагментация индексов. По сути, это - квинтэссенция описанных выше пунктов. Проблема кроется в способе физического хранения индексов в памяти. Он состоит в использовании страниц - небольших (обычно 4-8 кб), логически обособленных областей памяти диска, призванном оптимизировать работу операций ввода-вывода. При большом числе операций вставки/изменения/удаления записей, эти страницы могут прийти в не оптимальное состояние - быть частично незаполненными, например. Что, в свою очередь, увеличивает число фактических операций ввода-вывода при обращении к индексу. Вкупе с описанной проблемой неоптимальной структуры самого индекса, это влечет дополнительные расходы при использовании самого индекса и еще больше увеличивает его размер. В последнем, по сути, проблема та же, что и при фрагментации диска, с которой вы можете быть знакомы;
• Обслуживание. Структура БД и набор индексов могут изменяться в течении развития и поддержки системы. Соответственно, это дополнительные человеко-часы, затрачиваемые на поддержание таблицы и связанных с ней индексов в актуальном состоянии. Чем больше индексов - тем больше человеческих ресурсов требуется на их поддержку и сопровождение.

Исходя из описанных пунктов можно выделить и другие проблемы. Кроме того, есть более узкие болезни, характерные для конкретных индексов. Скажем, порядок столбцов в составных индексах (использующих несколько столбцов/выражений), с которыми мы познакомимся чуть позже.

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

В ряде случаев, может быть полезным отказ от индексов вообще - скажем, если состав строк таблицы часто изменяется, а операции чтения происходят редко или не чувствительны к скорости выполнения. Например, если чтение из таблицы происходит в фоновых процессах, которые не блокируют работу пользователя.

Классификация индексов

Можно выделить различные виды индексов по различным признакам. Часть из них мы разберем подробнее в следующем уроке, с остальными познакомимся сегодня.

Кластеризованные и некластеризованные индексы

Эта тема вынесена в отдельный урок, чтобы не перегружать текущий - он и так получился достаточно нагруженным новой информацией.

Классификация по структуре

Индексы могут представлять из себя различные структуры данных. Для PostgreSQL актуальны следующие виды:

• B-tree (BTREE) (ни в коем случае не путайте с бинарным деревом). Саму структуру данных рекомендую загуглить и хотя бы верхнеуровнево разобрать, если не сделали этого после статьи, посвященной деревьям.
  Тип индекса по умолчанию. Представляет из себя упорядоченную древовидную структуру, что позволяет как использовать такой индекс для сортировки, так и для поиска данных по операторам равенства (=, IS, IN), так и по операторам неравенства (>, >=, <, <=, BETWEEN). Кроме того, в ряде случаев такой индекс может использоваться для фильтрации по LIKE, но для оптимизации работы именно с LIKE рекомендую смотреть в сторону более подходящих для этого видов. Например, GIN или GiST, упомянутых ниже;
• Хэш (HASH). Данный тип индекса представляет собой хэштаблицу, с которыми мы уже знакомы по Java. Такая структура оптимальна для поиска по “=”, обеспечивая O(1) сложность (против O(log(n) у B-tree), но бесполезна при поиске с помощью операторов неравенства и сортировке. По сути, здесь можно проводить аналогии с HashMap (с поправкой на отсутствие бакетов) и TreeMap в Java;
• GiST (GIST). Этот тип индекса построен на базе более сложной структуры данных R-tree (можно погуглить, но не уверен, что имеет смысл сильно углубляться). В отличии от B-tree, позволяет работать с более широким числом типов данных (например, геометрические). Кроме того, предоставляет инфраструктуру, которая позволяет создавать индексы для собственных типов данных (что делает их актуальными при работе с расширениями СУБД, которые могут такие типы привнести). Также это позволяет поддерживать более широкий спектр операторов, которые можно использовать  при работе с этим индексом. Так, например, в документации приводится пример сортировки записей в выборке по удаленности от заданных координат.
  На мой взгляд, за пределами Hash и B-tree, с видами индексов в этой классификации можно ознакомиться поверхностно - оптимальное использование остальных видов индексов выходит за пределы квалификации junior-специалиста;
• SP-GiST (SPGIST). Еще более специализированный вид индекса. Верхнеуровнево, он все еще работает на базе древовидной структуры, но вводит понятие “пространство” - неперекрывающийся с другими раздел множества данных, и подходящий для работы со сложными структурами (вроде многомерных массивов), в которых классические древовидные структуры не так эффективны;
• GIN. Довольно интересный вид индекса, хорошо подходящий для работы с “комплексными” - состоящими из более простых типов - типами. Например, строками (как наборами символов), массивами (как наборами элементов) и пр. Суть в том, что индекс строится на базе отдельных элементов - элементов массива, лексем (например, триграмм) для строк и т.д. Таким образом, индекс предлагает эффективный поиск комплексного значения по его отдельному элементу. Т.е. поиск строки, у которой в колонке типа массив, присутствует искомый элемент, или полнотекстовый поиск.
  Еще одной особенностью данного индекса является то, что он не удаляет атомарные элементы (элемент массива, лексема и т.д), даже если в таблице не осталось строк, которые таковой элемент содержат. Это связано с тем, что предполагается возможность появления таких элементов в новых записях, которые будут добавлены позже. Но это может сделать индекс не избыточно большим и не эффективным, если уже существующие атомарные элементы не появляются в новых записях и продолжают висеть мертвым грузом. Ситуация не слишком распространенная, но возможная;
• BRIN. Тип индекса, строящегося вокруг взаимодействия с диапазоном значений, а не атомарными элементами составных типов (как GIN) или отдельными значениями (как все остальные виды индексов). Т.е. он разделяет данные на области (диапазоны), для которых учитывает минимальное и максимальное значение диапазона. В конечном итоге, это уменьшает количество операций ввода-вывода при поиске. Актуально для больших таблиц с последовательными данными (например, индекс по колонке created с датой вставки записи), особенно при поиске по диапазону (например, по BETWEEN).

Как видите, индексы могут быть достаточно разнообразны по структуре хранения, что позволяет оптимизировать поиск по различным типам данных и различным видам поиска. Помните, что большинство индексов плохо работают с неупорядоченными типами (утрированно, это те, у которых не очевидно правило сравнения по > и <).

Также стоит понимать, что при выборе типа индекса стоит учитывать не только его тип данных, но и предполагаемые (или определенные статистически) типы фильтрации (а также чувствительность этих запросов к времени исполнения) - нет смысла использовать GIN для эффективного поиска по LIKE, если 99.9% фильтров по интересующему вас столбу происходит через =. 

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

Уникальный индекс

Кроме классификации по типу, существует понятие уникального индекса - такой индекс будет гарантировать, что в таблицу нельзя добавить запись с неуникальным значением заданного столбца (или совокупности значений нескольких столбцов). Именно уникальный индекс лежит в основе UNIQUE-constraint’а.

При работе с уникальностью записей не забывайте, что NULL != NULL - возможно, стоит сделать интересующие вас колонки NOT NULL или иным образом обрабатывать возможные множественные null-значения.

В PostgreSQL в качестве уникального индекса можно использовать только структуру индекса по умолчанию - B-tree.

Составные индексы

Индексы могут строиться как на базе одной колонки (или выражения), так и на базе нескольких. Последние индексы называются составными.

В целом, это достаточно простая коллекция, но стоит учитывать два нюанса.

Во-первых, составной индекс в postgres может использовать только B-tree,  GiST, GIN и BRIN. На практике, это обычно означает лишь недопустимость HASH-индекса. 

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

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

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

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

С теорией на сегодня все!

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

Практика также будет в рамках следующей статьи.

Если что-то непонятно или не получается – welcome в комменты к посту или в лс:)

Канал: https://t.me/ViamSupervadetVadens

Мой тг: https://t.me/ironicMotherfucker

Дорогу осилит идущий!