Хэш-индексы

Обзор

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

Хэш-индексы поддерживают только построение индекса по одному столбцу и не допускают проверок на уникальность.

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

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

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

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

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

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

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

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

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

Реализация

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

Как для сканирования индекса, так и для добавления кортежей требуется определение местоположения сегмента, где должен располагаться данный кортеж. Для этого нужно знать число сегментов и значения highmask и lowmask из метастраницы; однако с точки зрения производительности нежелательно блокировать и закреплять метастраницу для каждой такой операции. Вместо этого в записи кэша отношений каждого внутреннего сервера сохраняется кэшированная копия метастраницы. Это приводит к правильному сопоставлению сегментов при условии, что целевой сегмент не был разделен с момента последнего обновления кэша.

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

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

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