Обзор

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

Хеш-индексы поддерживают только одноколоночные индексы и не позволяют проверять уникальность.

Хеш-индексы поддерживают только оператор =, поэтому в формулах WHERE, задающих операции с диапазонами, не будет возможности использовать преимущества хеш-индексов.

Каждый кортеж хеш-индекса хранит только 4-байтовое хеш-значение, а не фактическое значение столбца. В результате хеш-индексы могут быть гораздо меньше B-деревьев при индексировании длинных элементов данных, таких как UUID, URL и т.д. Отсутствие значения столбца также делает все сканирования хеш-индекса с потерями. Хеш-индексы могут участвовать в сканировании растровых индексов и обратном сканировании.

Хеш-индексы лучше всего оптимизировать для тяжелых рабочих нагрузок SELECT и UPDATE, использующих сканирование равенства в больших таблицах. В индексе B-дерева поиск должен спускаться по дереву, пока не будет найдена страница листа. В таблицах с миллионами строк такой спуск может увеличить время доступа к данным. Эквивалент страницы листа в хеш-индексе называется страницей ведра. В отличие от него, хеш-индекс позволяет обращаться к страницам ведра напрямую, тем самым потенциально сокращая время доступа к индексу в больших таблицах. Это сокращение «логического ввода-вывода» становится еще более заметным для индексов/данных, размер которых превышает размер разделяемой памяти/ОЗУ.

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

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

Как и B-деревья, хеш-индексы выполняют простое удаление кортежей индекса. Это операция отложенного обслуживания, при которой удаляются кортежи индекса, о которых известно, что их безопасно удалять (т.е., у которых бит LP_DEAD идентификатора элемента уже установлен). Если при вставке обнаруживается, что на странице нет свободного места, мы пытаемся избежать создания новой страницы переполнения, пытаясь удалить мертвые индексные кортежи. Удаление не может произойти, если страница в это время заблокирована. Удаление мертвых индексных указателей также происходит во время VACUUM.

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

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

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