обработка данных

Нажмите сюда, если долго загружается,
либо "ESC" - отмена
 
Заказ обратного звонка
Заказать звонок
Наш специалист свяжется с Вами и ответит на все вопросы
Обработка данных
Наш специалист свяжется с Вами и ответит на все вопросы.
OK

Индексы в PostgreSQL. Часть 1

Источник: https://habrahabr.ru
Время чтения: ~15 мин
Индексы в PostgreSQL. Часть 1
Статьи
986
Логотип PostgreSQL
Предисловие
В этой серии статей речь пойдет об индексах в PostgreSQL.

Любой вопрос можно рассматривать с разных точек зрения. Мы будем говорить о том, что должно интересовать прикладного разработчика, использующего СУБД: какие индексы существуют, почему в PostgreSQL их так много разных, и как их использовать для ускорения запросов. Пожалуй, тему можно было бы раскрыть и меньшим числом слов, но мы втайне надеемся на любознательного разработчика, которому также интересны и подробности внутреннего устройства, тем более, что понимание таких подробностей позволяет не только прислушиваться к чужому мнению, но и делать собственные выводы.

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

В этой части мы поговорим про разделение сфер ответственности между общим механизмом индексирования, относящимся к ядру СУБД, и отдельными методами индексного доступа, которые в PostgreSQL можно добавлять как расширения. В следующей части мы рассмотрим интерфейс метода доступа и такие важные понятия, как классы и семейства операторов. После такого длинного, но необходимого введения мы подробно рассмотрим устройство и применение различных типов индексов: Hash, B-tree, GiST, SP-GiST, GIN и RUM, BRIN, Bloom.
Индексы
Индексы в PostgreSQL — специальные объекты базы данных, предназначенные в основном для ускорения доступа к данным. Это вспомогательные структуры: любой индекс можно удалить и восстановить заново по информации в таблице. Иногда приходится слышать, что СУБД может работать и без индексов, просто медленно. Однако это не так, ведь индексы служат также для поддержки некоторых ограничений целостности.

В настоящее время в PostgreSQL 9.6 встроены шесть разных видов индексов, и еще один доступен как расширение — это стало возможным благодаря важным изменениям в версии 9.6. Так что в ближайшее время стоит ожидать появления и других типов индексов.

Несмотря на все различия между типами индексов (называемыми также методами доступа), в конечном счете любой из них устанавливает соответствие между ключом (например, значением проиндексированного столбца) и строками таблицы, в которых этот ключ встречается. Строки идентифицируются с помощью TID (tuple id), который состоит из номера блока файла и позиции строки внутри блока. Тогда, зная ключ или некоторую информацию о нем, можно быстро прочитать те строки, в которых может находиться интересующая нас информация, не просматривая всю таблицу полностью.

Важно понимать, что индекс, ускоряя доступ к данным, взамен требует определенных затрат на свое поддержание. При любой операции над проиндексированными данными — будь то вставка, удаление или обновление строк таблицы, — индексы, созданные для этой таблицы, должны быть перестроены, причем в рамках той же транзакции. Заметим, что обновление полей таблицы, по которым не создавались индексы, не приводит к перестроению индексов; этот механизм называется HOT (Heap-Only Tuples).

Расширяемость влечет некоторые следствия. Чтобы новый метод доступа можно было легко встроить в систему, в PostgreSQL выделен общий механизм индексирования. Его основной задачей является получение TID от метода доступа и работа с ними:

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

Механизм индексирования участвует в выполнении запросов; он вызывается в соответствии с планом, построенным на этапе оптимизации. Оптимизатор, перебирая и оценивая различные пути выполнения запроса, должен понимать возможности всех методов доступа, которые потенциально можно применить. Сможет ли метод доступа отдавать данные сразу в нужном порядке, или надо отдельно предусмотреть сортировку? можно ли применить метод доступа для поиска null? — такие вопросы постоянно решает оптимизатор.

Информация о методе доступа нужна не только оптимизатору. При создании индекса системе надо решить: можно ли построить индекс над несколькими столбцами? может ли данный индекс обеспечить уникальность?

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

В задачи же самого метода доступа входит все остальное:

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

Сначала мы посмотрим возможности общего механизма индексирования, а затем перейдем к рассмотрению различных методов доступа.
Механизм индексирования
Механизм индексирования позволяет PostgreSQL одинаково работать с самыми разными методами доступа, учитывая их возможности.
Основные способы сканирования
Индексное сканирование
Можно по-разному работать с TID, поставляемыми индексом. Рассмотрим пример:
CODE
Мы создали таблицу с тремя полями. Первое поле содержит числа от 1 до 100000, и по нему создан индекс (пока нам не важно, какой именно). Второе поле содержит различные ASCII-символы, кроме непечатных. Наконец, третье поле содержит логическое значение, истинное примерно для 1% строк, и ложное для остальных. Строки вставлены в таблицу в случайном порядке.

Попробуем выбрать значение по условию «a = 1». Заметим, что условие имеет вид «индексированное-поле оператор выражение», где в качестве оператора используется «равно», а выражением (ключом поиска) является «1». В большинстве случаев условие должно иметь именно такой вид, чтобы индекс мог использоваться.
CODE
В данном случае оптимизатор принял решение использовать индексное сканирование (Index Scan). При индексном просмотре метод доступа возвращает значения TID по одному, до тех пор, пока подходящие строки не закончатся. Механизм индексирования по очереди обращается к тем страницам таблицы, на которые указывают TID, получает версию строки, проверяет ее видимость в соответствии с правилами многоверсионности, и возвращает полученные данные.
Сканирование по битовой карте
Индексное сканирование хорошо работает, когда речь идет всего о нескольких значениях. Однако при увеличении выборки возрастают шансы, что придется возвращаться к одной и той же табличной странице несколько раз. Поэтому в таком случае оптимизатор переключается на сканирование по битовой карте (bitmap scan):
CODE
Сначала метод доступа возвращает все TID, соответствующие условию (узел Bitmap Index Scan), и по ним строится битовая карта версий строк. Затем версии строк читаются из таблицы (Bitmap Heap Scan) — при этом каждая страница будет прочитана только один раз.

Обратите внимание, что на втором шаге условие может перепроверяться (Recheck Cond). Выборка может оказаться слишком велика, чтобы битовая карта версий строк могла целиком поместиться в оперативную память (ограниченную параметром work_mem). В этом случае строится только битовая карта страниц, содержащих хотя бы одну подходящую версию строки. Такая «грубая» карта занимает меньше места, но при чтении страницы приходится перепроверять условия для каждой хранящейся там строки. Заметим, что даже в случае небольшой выборки (как в нашем примере) шаг «Recheck Cond» все равно отображается в плане, хотя реально и не выполняется.

Если условия наложены на несколько полей таблицы, и эти поля проиндексированы, сканирование битовой карты позволяет (если оптимизатор сочтет это выгодным) использовать несколько индексов одновременно. Для каждого индекса строятся битовые карты версий строк, которые затем побитово логически умножаются (если выражения соединены условием AND), либо логически складываются (если выражения соединены условием OR). Например:
CODE
Здесь узел BitmapAnd объединяет две битовые карты с помощью битовой операции «и».

Сканирование по битовой карте позволяет избежать повторных обращений к одной и той же странице данных. Но что, если данные в страницах таблицы физически упорядочены точно так же, как и записи индекса? Безусловно, нельзя полностью полагаться на физический порядок данных в страницах — если нужны отсортированные данные, в запросе необходимо явно указывать предложение ORDER BY. Но вполне возможны ситуации, в которых на самом деле «почти все» данные упорядочены: например, если строки добавляются в нужном порядке и не изменяются после этого, или после выполнения команды CLUSTER. Тогда построение битовой карты — лишний шаг, обычное индексное сканирование будет ничем не хуже (если не учитывать возможность объединения нескольких индексов). Поэтому при выборе метода доступа планировщик заглядывает в специальную статистику, которая показывает степень упорядоченности данных:
CODE
Значения, близкие по модулю к единице, говорят о высокой упорядоченности (как для столбца c), а близкие к нулю — наоборот, о хаотичном распределении (столбец a).
Последовательное сканирование
Для полноты картины следует сказать, что при неселективном условии оптимизатор предпочтет использованию индекса последовательное сканирование таблицы целиком:
CODE
И будет прав. Дело в том, что индексы работают тем лучше, чем выше селективность условия, то есть чем меньше строк ему удовлетворяет. При увеличении выборки возрастают и накладные расходы на чтение страниц индекса.

Ситуация усугубляется тем, что последовательное чтение выполняется быстрее, чем чтение страниц «вразнобой». Это особенно верно для жестких дисков, где механическая операция подведения головки к дорожке занимает существенно больше времени, чем само чтение данных; в случае дисков SSD этот эффект менее выражен. Для учета разницы стоимости доступа существуют два параметра seq_page_cost и random_page_cost, которые можно устанавливать не только глобально, но и на уровне табличных пространств, учитывая таким образом характеристики разных дисковых подсистем.
Покрывающие индексы
Как правило, основная задача метода доступа — вернуть идентификаторы подходящих строк таблицы, чтобы механизм индексирования мог прочитать из них необходимые данные. Но что, если индекс уже содержит все необходимые для запроса данные? Такой индекс называется покрывающим (covering), и в этом случае оптимизатор может применить исключительно индексное сканирование (Index Only Scan):
CODE
Название может навести на мысль, что механизм индексирования совсем не обращается к таблице, получая всю необходимую информацию исключительно от метода доступа. Но это не совсем так, потому что индексы в PostgreSQL не содержат информации, позволяющей судить о видимости строк. Поэтому метод доступа возвращает все версии строк, попадающие под условие поиска, независимо от того, видны они текущей транзакции или нет.

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

Проблема решается тем, что PostgreSQL поддерживает для таблиц так называемую карту видимости, в которой процесс очистки (vacuum) отмечает страницы, в которых данные не менялись достаточно давно для того, чтобы их видели все транзакции, независимо от времени начала и уровня изоляции. Если идентификатор строки, возвращенной индексом, относится к такой странице, то видимость можно не проверять.

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

Число вынужденных обращений к таблице можно узнать, используя команду explain analyze:
CODE
В данном случае обращаться к таблице не понадобилось (Heap Fetches: 0), так как только что была выполнена очистка. Вообще, чем ближе это число к нулю, тем лучше.

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

Но особое значение требует и особого к себе отношения. Обычная булева логика превращается в трехзначную; непонятно, должно ли неопределенное значение быть меньше обычных значений или больше (отсюда специальные конструкции для сортировки NULLS FIRST и NULLS LAST); не очевидно, надо ли учитывать неопределенные значения в агрегатных функциях или нет; требуется специальная статистика для планировщика…С точки зрения индексной поддержки с неопределенными значениями тоже имеется неясность: надо ли индексировать такие значения или нет? Если не индексировать null, то индекс может получиться компактнее. Зато если индексировать, то появляется возможность использовать индекс для условий вида «индексированное-поле IS [NOT] NULL», а также в качестве покрывающего индекса при полном отсутствии условий на таблицу (поскольку в этом случае индекс должен вернуть данные всех строк таблицы, в том числе и с неопределенными значениями).

Для каждого метода доступа его разработчики принимают свое решение, индексировать ли неопределенные значения или нет. Но, как правило, они все-таки индексируются.
Индексы по нескольким полям
Условия на несколько полей могут быть поддержаны с помощью многоколоночных индексов. Например, мы могли бы создать индекс по двум полям нашей таблицы:
CODE
Оптимизатор скорее всего предпочтет такой индекс объединению битовых карт, поскольку здесь мы сразу получаем нужные TID без каких-либо вспомогательных действий:
CODE
Многоколоночный индекс может использоваться и для ускорения выборки по условию на часть полей — начиная с первого:
CODE
А можно прочитать данные с помощью индекса сразу в порядке сортировки:
CODE
Из всех методов доступа только btree умеет возвращать данные в отсортированном виде, так что отложим более подробный разговор до рассмотрения этого типа индекса.
Параллельное построение
Обычно построение индекса требует установки блокировки типа SHARE на таблицу. Такая блокировка позволяет читать данные из таблицы, но запрещает любые изменения, пока строится индекс.

В этом можно убедиться, если в момент создания индекса, скажем, на таблице t, в другом сеансе выполнить запрос:
CODE
Если таблица достаточно большая и активно используется в режиме вставки, обновления или удаления, это может оказаться недопустимым — изменяющие сеансы будут ожидать освобождения блокировки длительное время.

В этом случае можно воспользоваться параллельным созданием индекса:
CODE
Такая команда устанавливает блокировку типа SHARE UPDATE EXCLUSIVE, которая разрешает и чтение, и изменение данных (запрещается только изменение структуры таблицы, а также одновременное выполнение очистки, анализа, или построения другого индекса на той же таблице).

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

Во-вторых, при параллельном построении индекса может возникнуть взаимоблокировка или нарушение ограничения уникальности. Индекс тем не менее создается, но в «нерабочем» состоянии; в таком случае его надо удалить и пересоздать еще раз. Нерабочие индексы отмечены словом INVALID в выводе команды psql d, а полный список можно получить запросом:
CODE
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Подписка на новости. Получайте важное первым
ПОДПИСАТЬСЯ