Обзор

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

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

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

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

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

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

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

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

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

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

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