Какой индекс использовать с множеством повторяющихся значений?

Давайте сделаем несколько предположений:

У меня есть таблица, которая выглядит так:

 a | b
---+---
 a | -1
 a | 17
  ...
 a | 21
 c | 17
 c | -3
  ...
 c | 22

Факты о моем наборе:

• Размер всей таблицы ~ 10 ¹⁰ строк.

• У меня есть ~ 100 000 строк со значением aв столбце a, аналогично для других значений (например c).

• Это означает ~ 100 тыс. Различных значений в столбце «а».

• Большинство моих запросов будут читать все или большинство значений для данного значения в, например select sum(b) from t where a = 'c'.

• Таблица написана таким образом, что последовательные значения физически близки (либо она написана по порядку, либо мы предполагаем, что CLUSTERона использовалась для этой таблицы и столбца a).

• Таблица редко обновляется, если вообще обновляется, нас интересует только скорость чтения.

• Таблица является относительно узкой (скажем, ~ 25 байт на кортеж, + 23 байта служебных данных).

Теперь вопрос в том, какой индекс мне использовать? Мое понимание таково:

• BTree Моя проблема здесь в том, что индекс BTree будет огромным, поскольку, насколько я знаю, он будет хранить повторяющиеся значения (это необходимо, поскольку он не может предполагать, что таблица физически отсортирована). Если BTree огромен, мне приходится читать как индекс, так и части таблицы, на которые указывает индекс. (Мы можем использовать, fillfactor = 100чтобы немного уменьшить размер индекса.)

• Брин Я понимаю, что я могу иметь небольшой индекс за счет чтения бесполезных страниц. Использование маленького pages_per_rangeозначает, что индекс больше (что является проблемой для BRIN, так как мне нужно прочитать весь индекс), имея большое значение pages_per_range, я буду читать много бесполезных страниц. Есть ли волшебная формула, чтобы найти хорошее значение, pages_per_rangeкоторое учитывает эти компромиссы?

• GIN / GiST Не уверен, что они здесь уместны, поскольку они в основном используются для полнотекстового поиска, но я также слышал, что они хорошо справляются с дублирующимися ключами. Поможет ли здесь GINили GiSTиндекс?

Другой вопрос заключается в том, будет ли Postgres использовать тот факт, что таблица CLUSTERредактируется (при условии отсутствия обновлений) в планировщике запросов (например, путем двоичного поиска соответствующих начальных / конечных страниц)? Что-то связанное, могу ли я просто сохранить все свои столбцы в BTree и полностью удалить таблицу (или достичь чего-то эквивалентного, я считаю, что это кластерные индексы в SQL-сервере)? Есть ли какой-нибудь гибридный индекс BTree / BRIN, который бы здесь помог?

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

BTree

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

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

BRIN

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

Если вы не можете позволить себе нехватку хранилища для покрывающего индекса btree, BRIN идеально подходит для вас, потому что у вас уже есть кластеризация (это важно для BRIN, чтобы быть полезным). Индексы BRIN крошечные , поэтому все страницы, вероятно, будут в памяти, если вы выберете подходящее значение pages_per_range.

Есть ли волшебная формула, чтобы найти хорошее значение pages_per_range, которое учитывает эти компромиссы?

Нет волшебной формулы, но начнем с pages_per_range несколько меньшего, чем средний размер (в страницах), занятый среднимa значением. Возможно, вы пытаетесь свести к минимуму: (количество отсканированных страниц BRIN) + (количество отсканированных страниц кучи) для типичного запроса. Найдите Heap Blocks: lossy=nв плане выполнения pages_per_range=1и сравните с другими значениями pages_per_range- то есть посмотрите, сколько ненужных блоков кучи сканируется.

GIN / GiST

Не уверен, что они здесь уместны, поскольку они в основном используются для полнотекстового поиска, но я также слышал, что они хорошо справляются с дублирующимися ключами. Будет лиGINGiST здесь помочь / index?

Возможно, стоит рассмотреть GIN, но, вероятно, не GiST - однако, если естественная кластеризация действительно хороша, то BRIN, вероятно, будет лучшим выбором.

Вот пример сравнения между различными типами индексов для фиктивных данных, немного похожих на ваш:

таблица и индексы:

create table foo(a,b,c) as
select *, lpad('',20)
from (select chr(g) a from generate_series(97,122) g) a
     cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;

размеры отношения:

select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
      from pg_class c join pg_namespace n on n.oid = c.relnamespace
      where nspname = current_schema ) z;

имя | размер | страницы | Строки / страница
: ----------------- | : ------ | ----: | --------:
фу | 149 МБ | 19118 | 135
foo_btree_covering | 56 МБ | 7132 | 364
foo_btree | 56 МБ | 7132 | 364
foo_gin | 2928 кБ | 366 | 7103
foo_brin_2 | 264 кБ | 33 | 78787
foo_brin_4 | 136 кБ | 17 | 152941

покрытие btree:

explain analyze select sum(b) from foo where a='a';

| QUERY PLAN |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------------------- |
| Агрегат (стоимость = 3282.57..3282.58 строк = 1 ширина = 8) (фактическое время = 45.942..45.942 строк = 1 цикл = 1) |
| -> Индексировать только сканирование, используя foo_btree_covering для foo (стоимость = 0,43..3017.80 строк = 105907 ширина = 4) (фактическое время = 0,038..27.286 строк = 100000 циклов = 1) |
| Index Cond: (a = 'a' :: text) |
| Выборок из кучи: 0 |
| Время планирования: 0,099 мс |
| Время выполнения: 45,968 мс |

обычный btree:

drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';

| QUERY PLAN |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Агрегат (стоимость = 4064.57..4064.58 строк = 1 ширина = 8) (фактическое время = 54.242..54.242 строк = 1 цикл = 1) |
| -> Сканирование индекса с использованием foo_btree для foo (стоимость = 0.43..3799.80 строк = 105907 ширина = 4) (фактическое время = 0.037..33.084 строк = 100000 циклов = 1) |
| Index Cond: (a = 'a' :: text) |
| Время планирования: 0,135 мс |
| Время выполнения: 54,280 мс |

BRIN pages_per_range = 4:

drop index foo_btree;
explain analyze select sum(b) from foo where a='a';

| QUERY PLAN |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Агрегат (стоимость = 21595,38,21595,39 строк = 1 ширина = 8) (фактическое время = 52,455,52,455 строк = 1 цикл = 1) |
| -> Сканирование кучи растровых изображений на foo (стоимость = 888.78..21330.61 строк = ширина 105907 = 4) (фактическое время = 2.738..31.967 строк = 100000 циклов = 1) |
| Перепроверьте Cond: (a = 'a' :: text) |
| Строки, удаленные при повторной проверке индекса: 96 |
| Блоки кучи: с потерями = 736 |
| -> Сканирование индекса растрового изображения на foo_brin_4 (стоимость = 0.00..862.30 строк = 105907 ширина = 0) (фактическое время = 2.720..2.720 строк = 7360 циклов = 1) |
| Index Cond: (a = 'a' :: text) |
| Время планирования: 0,101 мс |
| Время выполнения: 52,501 мс |

BRIN pages_per_range = 2:

drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';

| QUERY PLAN |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Агрегат (стоимость = 21659.38..21659.39 строк = 1 ширина = 8) (фактическое время = 53.971..53.971 строк = 1 цикл = 1) |
| -> Сканирование кучи растрового изображения на foo (стоимость = 952.78..21394.61 строк = ширина 105907 = 4) (фактическое время = 5.286..33.492 строки = 100000 циклов = 1) |
| Перепроверьте Cond: (a = 'a' :: text) |
| Строки, удаленные при повторной проверке индекса: 96 |
| Блоки кучи: с потерями = 736 |
| -> Сканирование индекса растрового изображения на foo_brin_2 (стоимость = 0.00..926.30 строк = 105907 ширина = 0) (фактическое время = 5.275..5.275 строк = 7360 циклов = 1) |
| Index Cond: (a = 'a' :: text) |
| Время планирования: 0,095 мс |
| Время выполнения: 54,016 мс |

ДЖИН:

drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';

| QUERY PLAN |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------ |
| Агрегат (стоимость = 21687.38..21687.39 строк = 1 ширина = 8) (фактическое время = 55.331..55.331 строк = 1 цикл = 1) |
| -> Сканирование кучи растрового изображения на foo (стоимость = 980.78..21422.61 строк = ширина 105907 = 4) (фактическое время = 12.377..33.956 строк = 100000 циклов = 1) |
| Перепроверьте Cond: (a = 'a' :: text) |
| Блоки кучи: точный = 736 |
| -> Сканирование индекса растрового изображения на foo_gin (стоимость = 0.00..954.30 строк = 105907 ширина = 0) (фактическое время = 12.271..12.271 строк = 100000 циклов = 1) |
| Index Cond: (a = 'a' :: text) |
| Время планирования: 0,118 мс |
| Время выполнения: 55,366 мс |

dbfiddle здесь

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

• INCLUDEиндексов . Надеюсь, что они появятся в следующей основной версии (10) Postgres, где-то в сентябре 2017 года. Индекс on (a) INCLUDE (b)имеет ту же структуру, что и индекс, (a)но включает в листовые страницы все значения b(но неупорядоченные). Это означает, что вы не можете использовать его, например, для SELECT * FROM t WHERE a = 'a' AND b = 2 ;. Индекс можно использовать, но хотя (a,b)индекс найдет совпадающие строки с помощью одного запроса, включаемый индекс должен будет пройти через (возможно, 100 КБ, как в вашем случае) значения, которые соответствуют, a = 'a'и проверить bзначения.
  С другой стороны, индекс немного менее широк, чем (a,b)индекс, и вам не нужен порядок bдля запроса, чтобы вычислитьSUM(b) . Вы также можете иметь, например,(a) INCLUDE (b,c,d) который можно использовать для запросов, похожих на ваш, которые объединяются по всем 3 столбцам.

• Отфильтрованные (частичные) индексы . На первый взгляд это может показаться немного сумасшедшим ^* :

  CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
  ---
  CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;

  Один индекс для каждого aзначения. В вашем случае около 100К индексов. Хотя это звучит много, учтите, что каждый индекс будет очень маленьким, как по размеру (количеству строк), так и по ширине (поскольку он будет хранить только bзначения). Однако во всех других аспектах он (индексы 100К вместе) будет действовать как индекс b-дерева (a,b)при использовании пространства (b)индекса.
  Недостатком является то, что вам придется создавать и поддерживать их самостоятельно, каждый раз, когда aв таблицу добавляется новое значение . Поскольку ваша таблица довольно стабильна, без многих (или каких-либо) вставок / обновлений, это не кажется проблемой.

• Сводные таблицы. Поскольку таблица достаточно стабильна, вы всегда можете создать и заполнить сводную таблицу наиболее распространенными агрегатами, которые вам понадобятся ( sum(b), sum(c), sum(d), avg(b), count(distinct b)и т. Д.). Он будет небольшим (всего 100 тыс. Строк) и будет заполняться только один раз и обновляться только тогда, когда строки будут добавлены / обновлены / удалены в основной таблице.

^{*: идея скопирована с этой компании, которая управляет 10 миллионами индексов в своей производственной системе: Куча: запуск 10 миллионов индексов Postgresql в производстве (и подсчет) .}