В первой статье мы рассмотрели механизм индексирования PostgreSQL, во второй — интерфейс методов доступа, и теперь готовы к разговору о конкретных типах индексов. Начнем с хеш-индекса.

Hash

Устройство

Общая теория

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

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

Идея хеширования состоит в том, чтобы значению любого типа данных сопоставить некоторое небольшое число (от 0 до N−1, всего N значений). Такое сопоставление называют хеш-функцией. Полученное число можно использовать как индекс обычного массива, куда и складывать ссылки на строки таблицы (TID). Элементы такого массива называют корзинами хеш-таблицы — в одной корзине могут лежать несколько TID-ов, если одно и то же проиндексированное значение встречается в разных строках.

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

Предисловие

В этой серии статей речь пойдет об индексах в PostgreSQL.

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

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

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