Предисловие


В этой серии статей речь пойдет об индексах в 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)

Продолжение следует.
Поделиться с друзьями
-->

Комментарии (47)


  1. vadv
    19.04.2017 14:39
    +3

    Очень доступно и круто!


    1. erogov
      19.04.2017 14:51
      +3

      Спасибо, Дим. Дальше — больше.


      1. GlukKazan
        19.04.2017 15:11
        +1

        Я правильно понимаю, что GiST и GIN в продолжении (которое следует)?
        Спасибо, хорошая статья.


        1. erogov
          19.04.2017 15:43
          +4

          Совершенно верно.


          1. Shaz
            19.04.2017 18:26

            А там будет про работу с json? Насколько помню, этот тип данных налагает некоторые ограничения на использования индексов.


            1. erogov
              19.04.2017 18:50
              +1

              Не планировал, но подумаю. Может, какой-то пример приведу.
              По уму про json надо отдельную большую статью писать, равно как и про полнотекстовый поиск.


              1. rraderio
                25.04.2017 14:51
                +1

                +1 про полнотекстовый поиск


  1. erwins22
    19.04.2017 16:06

    Индексы в PostgreSQL «минус» 1

    прочитал так заголовок


    1. erogov
      19.04.2017 16:12
      +3

      Если это единственное замечание к статье, то я удовлетворен (:


      1. erwins22
        19.04.2017 16:19

        Мало. Вкусно. Интересно.


        1. erogov
          19.04.2017 16:28
          +2

          Оставайтесь с нами!


  1. ploop
    19.04.2017 17:20

    Очень интересно, спасибо!


    1. erogov
      19.04.2017 17:28
      +1

      Всегда пожалуйста. Продолжение следует.


  1. Rhim
    19.04.2017 17:33

    Спасибо за статью, ждем продолжение.


    1. erogov
      19.04.2017 17:33
      +1

      На здоровье!


  1. Warlock_29A
    19.04.2017 21:27

    Спасибо за статью.


    Скажите, а инструменты по визуализации содержимого индекса для постгреса есть какие нибудь (для btree, GIN, GIST индексов)? Иногда кажется полезным такой инструмент, в плане исследования как работают и как устроены те или иные индексы.


    1. erogov
      19.04.2017 22:35
      +1

      Есть pageinspect для btree, git и brin, есть gevel для gist и gin.
      Про это все тоже будет, когда доживем до конкретных индексов.


  1. SXN
    19.04.2017 22:15

    Спасибо за статью, ждем продолжение. можете подсказать примерно когда можно будет публикация 2 часть?


    1. erogov
      19.04.2017 22:39

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


  1. vlakarados
    20.04.2017 10:36

    Безумно крутая статья. Конкретно и доступно. С нетерпением жду продолжение. Будут ли еще статьи по Postgre не связанные с индексами?


    1. erogov
      20.04.2017 10:38

      Спасибо, рад, что понравилось. Статьи мы писали, пишем и останавливаться не собираемся (:


  1. ElectroGuard
    20.04.2017 12:43

    Спасибо, интересное чтиво.


    1. erogov
      20.04.2017 14:42

      На здоровье, хотя «чтиво» и звучит несколько пренебрежительно.


  1. akhkmed
    20.04.2017 15:39

    Спасибо за интересную статью.

    Напишите пожалуйста, как правильно обслуживать btree-индексы, чтобы они не разрастались?

    Если по месячной партиции количество UPDATE в 6 (может и более) раз превышает количество INSERT, то reindex в конце месяца практически всегда сокращает объём индексов на 75% от исходного. При этом пересоздание таблицы даёт чаще всего меньший выигрыш по объёму самой таблицы, не более 20 %, что указывает на то, что сам vacuum всё-таки успевает.

    Что ещё интересно, reindex даёт наибольший выигрыш по объёму не на всех индексах: на трёх выигрыш около 5.3 раз, на трёх — от 3.5 до 4.2 раз, на двух — от 2.8 до 3.4 раз, при этом, ни один из индексов не содержит ни колонок, значения которых меняются в UPDATE, ни колонок переменной длины, а содержит в основном значения типов integer и timestamp.

    Неужели единственный выход в периодическом пересоздании индексов?


    1. vadv
      20.04.2017 15:46

      ни колонок переменной длины, а содержит в основном значения типов integer и timestamp.

      дело в движке:


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

      обслуживание

      обычно через concurrency создают такой же индекс и удаляют старый, были баги в 9.4 с репликами, когда новый индекс не подхватывался, сейчас устранено.


    1. erogov
      20.04.2017 15:57
      +1

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


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


      1. k_simakov
        21.04.2017 12:46

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

        Вообще-то в B-деревьях склеивание разряжённых блоков — дело обычное. Неужели это не реализовано в PostgreSQL?


        1. erogov
          21.04.2017 14:10

          src/backend/access/nbtree/README


          We consider deleting an entire page from the btree only when it's become
          completely empty of items. (Merging partly-full pages would allow better
          space reuse, but it seems impractical to move existing data items left or
          right to make this happen — a scan moving in the opposite direction
          might miss the items if so.)


  1. k_simakov
    21.04.2017 13:00

    Ещё в статье не совсем понятно написано про битовые карты. Как я понял из статьи, метод доступа возвращает множество TID, по которым можно просто пройтись и прочитать значения соответствующих строк, предварительно проверяя их видимость. Зачем в этой схеме отдельно строить карту? Ведь чтобы построить карту, нужно как минимум сделать точно такой же проход, чтобы проверить каждую строку на предмет видимости и проставить в соответствии с этим единичку в битовой карте. Получается для построения битовой карты нужно пройтись один раз по страницам таблицы. А потом, при непосредственном обходе карты, сделать это ещё раз при выборке целевых значений. Поясните, пожалуйста, как всё-таки на самом деле происходит работа с картами и за счёт чего в итоге получается выигрыш.


    1. erogov
      21.04.2017 14:29
      +1

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


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


  1. k_simakov
    21.04.2017 13:01

    Ещё в статье не совсем понятно написано про битовые карты. Как я понял из статьи, метод доступа возвращает множество TID, по которым можно просто пройтись и прочитать значения соответствующих строк, предварительно проверяя их видимость. Зачем в этой схеме отдельно строить карту? Ведь чтобы построить карту, нужно как минимум сделать точно такой же проход, чтобы проверить каждую строку на предмет видимости и проставить в соответствии с этим единичку в битовой карте. Получается для построения битовой карты нужно пройтись один раз по страницам таблицы. А потом, при непосредственном обходе карты, сделать это ещё раз при выборке целевых значений. Поясните, пожалуйста, как всё-таки на самом деле происходит работа с картами и за счёт чего в итоге получается выигрыш.


  1. k_simakov
    21.04.2017 13:07

    Ещё один вопрос возник по поводу частичных индексов. Правильно ли я понял, если в таблице встречается высокочастотное значение, оно просто не добавляется в индекс? При этом, когда происходит выборка по этому значению делается обход таблицы и возвращаются все строки, которых нет в индексе?


    1. erogov
      21.04.2017 14:43
      +1

      В частичный индекс попадают только строки, подходящие по явно указанному условию (никакой автоматики на обнаружение высокочастотных значений нет). В нашем примере: create index on t(c) where c; таким условием является c.


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


      Вот другой пример для наглядности:


      postgres=# create table test as select * from t;
      SELECT 100000
      
      postgres=# create index on test(a) where a < 1000;
      CREATE INDEX

      Вот так индекс будет использоваться:


      postgres=# explain (costs off) select * from test where a < 1000;
                    QUERY PLAN               
      ---------------------------------------
       Bitmap Heap Scan on test
         Recheck Cond: (a < 1000)
         ->  Bitmap Index Scan on test_a_idx
      (3 rows)

      И вот так планировщик догадается:


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

      А вот так — уже нельзя:


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


  1. Saladin
    23.04.2017 13:04
    -1

    Вопрос к сообществу, есть ли аналог процесса очистки в MS SQL Server?


  1. Saladin
    23.04.2017 13:20
    -1

    И ещё один вопрос, влияет ли порядок индексируемых столбцов по которым создан индекс, на выбор оптимизатора при создании плана выполнения запроса?
    И второй вопрос на эту же тему, стоит ли создавать(и если да то что нужно учитывать?) два разных индекса которые отличаются лишь порядком индексируемы столбцов?
    Например индекc t(a,b) и t(b,a)


    1. erogov
      23.04.2017 13:53
      +1

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


    1. sasha1024
      25.04.2017 19:47

      Например индекc t(a,b)


      AFAIK, индекc t(a,b) позволяет ускорить запросы вида:
      • SELECT * FROM t WHERE a=… AND b=…
      • SELECT * FROM t WHERE a=…


      Но не такой:
      • SELECT * FROM t WHERE b=…


      P.S.: Т.е. индекс t(a1, a2, …, aN), считай, работает не только как t(a1, a2, …, aN), но и как t(a1), t(a1, a2), …, t(a1, a2, …, a(N-1)).


      1. erogov
        25.04.2017 22:55

        На самом деле и SELECT * FROM t WHERE b=... тоже, особенно если вместо * там несколько полей. Это может иметь смысл, если индекс покрывающий — может оказаться проще просмотреть индекс (пусть и весь), чем таблицу (тоже всю).


        1. sasha1024
          25.04.2017 23:07

          Эээ, а можно подробнее, как индекс по (a, b) позволяет ускорить поиск по b? (При условии, что a могут принимать разные значения.) Я не то, чтобы спорю, просто не в курсе.


          1. erogov
            26.04.2017 11:48

            Все значения a, конечно, придется перебрать. То есть, грубо говоря, индекс придется просмотреть весь или почти весь. Но если индекс по размеру меньше таблицы, то это все равно может оказаться эффективнее, чем просматривать всю таблицу. Речь, конечно, о случае, когда на таблице нет индекса t(b), который, естественно, будет значительно эффективнее.


            Постгрес так умеет:


            postgres=# \d t
                   Table "public.t"
             Column |  Type   | Modifiers 
            --------+---------+-----------
             a      | integer | 
             b      | text    | 
             c      | boolean | 
            Indexes:
                "t_a_b_idx" btree (a, b)
            
            postgres=# set enable_seqscan = off;
            SET
            
            postgres=# explain select * from t where b = '!';
                                              QUERY PLAN                                  
            ------------------------------------------------------------------------------
             Bitmap Heap Scan on t  (cost=1854.54..2310.04 rows=1000 width=7)
               Recheck Cond: (b = '!'::text)
               ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..1854.29 rows=1000 width=0)
                     Index Cond: (b = '!'::text)
            (4 rows)


            1. sasha1024
              26.04.2017 14:40

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


      1. sasha1024
        25.04.2017 23:02

        Поэтому, предполагая условия только с равенствами, индексов, например, t(a, b) и t(b) более чем достаточно: они покроют случаи и «a=…», и «a=… AND b=…», и «b=…» — индексы t(a) и t(b, a) были бы (при условии наличия первых двух) уже избыточны.

        Однако, например, «WHERE a=7 AND b>=100» теоретически можно интерпретировать как «WHERE (a, b) BETWEEN (7, 100) AND (7, +INFINITY)», но не как «WHERE (b, a) BETWEEN … AND …» — поэтому в таком условии индекс t(a, b) явно более подходящ, чем t(b, a) — второй может быть использован лишь в той степени, в которой может быть использован t(b).


  1. HKA
    26.04.2017 15:42

    Заметим, что обновление полей таблицы, по которым не создавались индексы, не приводит к перестроению индексов
    В нашумевшем переходе Uber с PostgreSQL на MySQL они жаловались на обновление всех индексов. Как я понимаю, вы намеренно акцентировали внимание на Heap-Only Tuples, чтобы показать, что проблема решена при миграции с 9.2 на 9.6? Или раньше?


    1. erogov
      26.04.2017 16:16

      HOT-то работает с незапамятных времен, с 8.3 начиная. Но работает он (что раньше, что сейчас) так: если какое-то поле есть хотя бы в одном индексе, то при его изменениях будут обновляться все индексы, независимо от того, есть в них это поле или нет. Как я понимаю, на это Убер и наступил.


      1. HKA
        26.04.2017 16:35

        Значит я неверно вас понял. Прочел как «индексы, не включающие изменяемое поле, не перестраиваются». Наверное, сбило с толку то, что изначальный смысл в общем-то ожидаем по дефолту. Спасибо.


      1. rraderio
        26.04.2017 16:36

        Хм, интересно, а какие плюсы есть в том чтобы обновлять все индексы?


        1. erogov
          26.04.2017 16:44

          Тут скорее не в плюсах дело, а в особенностях реализации. Если интересно, можно заглянуть в слайды и демонстрацию темы № 3 нашего курса DBA2, там все нарисовано подробно.