Предисловие

В этой серии статей речь пойдет об индексах в 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, поставляемыми индексом. Рассмотрим пример:

postgres=# create table t(a integer, b text, c boolean);
CREATE TABLE
postgres=# insert into t(a,b,c)
  select s.id, chr((32+random()*94)::integer), random() < 0.01
  from generate_series(1,100000) as s(id)
  order by random();
INSERT 0 100000
postgres=# create index on t(a);
CREATE INDEX
postgres=# analyze t;
ANALYZE

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

Попробуем выбрать значение по условию «a = 1». Заметим, что условие имеет вид «индексированное-поле оператор выражение», где в качестве оператора используется «равно», а выражением (ключом поиска) является «1». В большинстве случаев условие должно иметь именно такой вид, чтобы индекс мог использоваться.

postgres=# explain (costs off) select * from t where a = 1;
          QUERY PLAN          
-------------------------------
 Index Scan using t_a_idx on t
   Index Cond: (a = 1)
(2 rows)

В данном случае оптимизатор принял решение использовать индексное сканирование (Index Scan). При индексном просмотре метод доступа возвращает значения TID по одному, до тех пор, пока подходящие строки не закончатся. Механизм индексирования по очереди обращается к тем страницам таблицы, на которые указывают TID, получает версию строки, проверяет ее видимость в соответствии с правилами многоверсионности, и возвращает полученные данные.

Сканирование по битовой карте

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

postgres=# explain (costs off) select * from t where a <= 100;
             QUERY PLAN            
------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (a <= 100)
   ->  Bitmap Index Scan on t_a_idx
         Index Cond: (a <= 100)
(4 rows)

Сначала метод доступа возвращает все TID, соответствующие условию (узел Bitmap Index Scan), и по ним строится битовая карта версий строк. Затем версии строк читаются из таблицы (Bitmap Heap Scan) — при этом каждая страница будет прочитана только один раз.

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

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

postgres=# create index on t(b);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
                    QUERY PLAN                    
--------------------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: ((a <= 100) AND (b = 'a'::text))
   ->  BitmapAnd
         ->  Bitmap Index Scan on t_a_idx
               Index Cond: (a <= 100)
         ->  Bitmap Index Scan on t_b_idx
               Index Cond: (b = 'a'::text)
(7 rows)

Здесь узел BitmapAnd объединяет две битовые карты с помощью битовой операции «и».

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

postgres=# select attname, correlation from pg_stats where tablename = 't';
 attname | correlation
---------+-------------
 b       |    0.533512
 c       |    0.942365
 a       | -0.00768816
(3 rows)

Значения, близкие по модулю к единице, говорят о высокой упорядоченности (как для столбца c), а близкие к нулю — наоборот, о хаотичном распределении (столбец a).

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

Для полноты картины следует сказать, что при неселективном условии оптимизатор предпочтет использованию индекса последовательное сканирование таблицы целиком:

postgres=# explain (costs off) select * from t where a <= 40000;
       QUERY PLAN      
------------------------
 Seq Scan on t
   Filter: (a <= 40000)
(2 rows)

И будет прав. Дело в том, что индексы работают тем лучше, чем выше селективность условия, то есть чем меньше строк ему удовлетворяет. При увеличении выборки возрастают и накладные расходы на чтение страниц индекса.

Ситуация усугубляется тем, что последовательное чтение выполняется быстрее, чем чтение страниц «вразнобой». Это особенно верно для жестких дисков, где механическая операция подведения головки к дорожке занимает существенно больше времени, чем само чтение данных; в случае дисков SSD этот эффект менее выражен. Для учета разницы стоимости доступа существуют два параметра seq_page_cost и random_page_cost, которые можно устанавливать не только глобально, но и на уровне табличных пространств, учитывая таким образом характеристики разных дисковых подсистем.

Покрывающие индексы

Как правило, основная задача метода доступа — вернуть идентификаторы подходящих строк таблицы, чтобы механизм индексирования мог прочитать из них необходимые данные. Но что, если индекс уже содержит все необходимые для запроса данные? Такой индекс называется покрывающим (covering), и в этом случае оптимизатор может применить исключительно индексное сканирование (Index Only Scan):

postgres=# vacuum t;
VACUUM
postgres=# explain (costs off) select a from t where a < 100;
             QUERY PLAN            
------------------------------------
 Index Only Scan using t_a_idx on t
   Index Cond: (a < 100)
(2 rows)

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

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

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

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

Число вынужденных обращений к таблице можно узнать, используя команду explain analyze:

postgres=# explain (analyze, costs off) select a from t where a < 100;
                                  QUERY PLAN                                  
-------------------------------------------------------------------------------
 Index Only Scan using t_a_idx on t (actual time=0.025..0.036 rows=99 loops=1)
   Index Cond: (a < 100)
   Heap Fetches: 0
 Planning time: 0.092 ms
 Execution time: 0.059 ms
(5 rows)

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

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

Null

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

Но особое значение требует и особого к себе отношения. Обычная булева логика превращается в трехзначную; непонятно, должно ли неопределенное значение быть меньше обычных значений или больше (отсюда специальные конструкции для сортировки NULLS FIRST и NULLS LAST); не очевидно, надо ли учитывать неопределенные значения в агрегатных функциях или нет; требуется специальная статистика для планировщика…

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

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

Индексы по нескольким полям

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

postgres=# create index on t(a,b);
CREATE INDEX
postgres=# analyze t;
ANALYZE

Оптимизатор скорее всего предпочтет такой индекс объединению битовых карт, поскольку здесь мы сразу получаем нужные TID без каких-либо вспомогательных действий:

postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
                   QUERY PLAN                  
------------------------------------------------
 Index Scan using t_a_b_idx on t
   Index Cond: ((a <= 100) AND (b = 'a'::text))
(2 rows)

Многоколоночный индекс может использоваться и для ускорения выборки по условию на часть полей — начиная с первого:

postgres=# explain (costs off) select * from t where a <= 100;
              QUERY PLAN              
--------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (a <= 100)
   ->  Bitmap Index Scan on t_a_b_idx
         Index Cond: (a <= 100)
(4 rows)

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

Не все методы доступа поддерживают создание индексов по нескольким столбцам.

Индексы по выражениям

Мы говорили о том, что условие поиска должно иметь вид «индексированное-поле оператор выражение». В примере, приведенном ниже, индекс не будет использоваться, поскольку вместо самого имени поля используется выражение с ним:

postgres=# explain (costs off) select * from t where lower(b) = 'a';
                QUERY PLAN                
------------------------------------------
 Seq Scan on t
   Filter: (lower((b)::text) = 'a'::text)
(2 rows)

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

postgres=# create index on t(lower(b));
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where lower(b) = 'a';
                     QUERY PLAN                    
----------------------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (lower((b)::text) = 'a'::text)
   ->  Bitmap Index Scan on t_lower_idx
         Index Cond: (lower((b)::text) = 'a'::text)
(4 rows)

Функциональный индекс создается не по полю таблицы, а по произвольному выражению; оптимизатор будет принимать во внимание такой индекс для условий вида «индексированное-выражение оператор выражение». Если вычисление индексируемого выражения — затратная операция, то и обновление индекса будет требовать значительных вычислительных ресурсов.

Стоит также иметь в виду, что по индексированному выражению собирается отдельная статистика. Ее можно увидеть в представлении pg_stats по имени индекса:

postgres=# \d t
       Table "public.t"
 Column |  Type   | Modifiers
--------+---------+-----------
 a      | integer |
 b      | text    |
 c      | boolean |
Indexes:
    "t_a_b_idx" btree (a, b)
    "t_a_idx" btree (a)
    "t_b_idx" btree (b)
    "t_lower_idx" btree (lower(b))

postgres=# select * from pg_stats where tablename = 't_lower_idx';
...

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

postgres=# \d t_lower_idx
 Index "public.t_lower_idx"
 Column | Type | Definition
--------+------+------------
 lower  | text | lower(b)
btree, for table "public.t"

postgres=# alter index t_lower_idx alter column "lower" set statistics 69;
ALTER INDEX


Частичные индексы

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

Разумеется, можно построить обычный индекс по столбцу «c», и он будет работать так, как мы ожидаем:

postgres=# create index on t(c);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where c;
          QUERY PLAN          
-------------------------------
 Index Scan using t_c_idx on t
   Index Cond: (c = true)
   Filter: c
(3 rows)

postgres=# explain (costs off) select * from t where not c;
    QUERY PLAN    
-------------------
 Seq Scan on t
   Filter: (NOT c)
(2 rows)

При этом индекс занимает 276 страниц:

postgres=# select relpages from pg_class where relname='t_c_idx';
 relpages
----------
      276
(1 row)

Но, поскольку столбец «c» имеет значение true только для одного процента строк, 99% индекса просто никогда не используются. В этом случае можно построить частичный индекс:

postgres=# create index on t(c) where c;
CREATE INDEX
postgres=# analyze t;
ANALYZE

Размер такого индекса уменьшился до 5 страниц:

postgres=# select relpages from pg_class where relname='t_c_idx1';
 relpages
----------
        5
(1 row)

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

Сортировка

Если метод доступа возвращает идентификаторы строк в порядке сортировки, это дает оптимизатору дополнительные варианты выполнения запроса.

Можно просканировать таблицу и затем отсортировать данные:

postgres=# set enable_indexscan=off;
SET
postgres=# explain (costs off) select * from t order by a;
     QUERY PLAN      
---------------------
 Sort
   Sort Key: a
   ->  Seq Scan on t
(3 rows)

А можно прочитать данные с помощью индекса сразу в порядке сортировки:

postgres=# set enable_indexscan=on;
SET
postgres=# explain (costs off) select * from t order by a;
          QUERY PLAN          
-------------------------------
 Index Scan using t_a_idx on t
(1 row)

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

Параллельное построение

Обычно построение индекса требует установки блокировки типа SHARE на таблицу. Такая блокировка позволяет читать данные из таблицы, но запрещает любые изменения, пока строится индекс.

В этом можно убедиться, если в момент создания индекса, скажем, на таблице t, в другом сеансе выполнить запрос:

postgres=# select mode, granted from pg_locks where relation = 't'::regclass;
   mode    | granted
-----------+---------
 ShareLock | t
(1 row)

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

В этом случае можно воспользоваться параллельным созданием индекса:

postgres=# create index concurrently on t(a);
CREATE INDEX

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

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

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

postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name from pg_index where not indisvalid;
 index_name | table_name
------------+------------
 t_a_idx    | t
(1 row)

Продолжение следует.