Хеш-индексы
Обзор
В QHB включена реализация хеш-индексов, постоянно хранящихся на диске и поэтому полностью восстанавливающихся после сбоя. По хеш-индексу можно проиндексировать любой тип данных, включая типы, для которых нет четко определенного линейного порядка. Хеш-индексы хранят только хеш-значения индексируемых данных, поэтому ограничение на размер индексируемого столбца данных отсутствует.
Хеш-индексы поддерживают только построение индекса по одному столбцу и не допускают проверок на уникальность.
Хеш-индексы поддерживают только оператор =, поэтому для предложений WHERE,
в которых задаются операции с диапазонами, хеш-индексы будут бесполезны.
Каждый кортеж хеш-индекса хранит только 4-байтовое хеш-значение, а не фактическое значение столбца. Как следствие, хеш-индексы могут быть гораздо меньше B-деревьев при индексировании более длинных объектов данных, например UUID, URL-адресов и т. д. Из-за отсутствия значения столбцов все сканирования хеш-индекса являются неточными. Хеш-индексы могут принимать участие в сканированиях индекса по битовой карте и обратных сканированиях.
Хеш-индексы лучше всего оптимизированы для нагрузок с большим количеством операций
SELECT и UPDATE, выполняющих сканирование с проверкой равенства на больших
таблицах. В индексе B-дереве поиск должен спускаться по дереву, пока не найдется
листовая страница. В таблицах с миллионами строк такой спуск может увеличить время
обращения к данным. Аналог листовой страницы называется в хеш-индексе страницей
сегментов. В отличие от B-деревьев, хеш-индекс позволяет обращаться к страницам
сегментов напрямую, тем самым потенциально сокращая время доступа по индексу в
больших таблицах. Это сокращение «логического ввода/вывода» становится еще более
выраженным для индексов/данных, не помещающихся в общих буферах/ОЗУ.
Хеш-индексы были разработаны специально, чтобы управляться с неравномерными распределениями хеш-значений. Но прямое обращение к страницам сегментов лучше работает, если хеш-значения распределены равномерно. Когда при добавлениях страница сегментов заполняется до конца, к этой странице привязываются дополнительные страницы переполнения, локально расширяя хранилище индексных кортежей, соответствующих этому хеш-значению. Позже при сканировании хеш-сегмента во время выполнения запросов, потребуется просканировать все страницы переполнения. Поэтому для некоторых данных несбалансированный хеш-индекс на деле может оказаться хуже B-дерева в контексте количества требуемых обращений к блокам.
В связи с ситуациями, возникающими при переполнении, можно сказать, что хеш-индексы лучше всего подходят для уникальных и почти уникальных данных или для данных с малым числом строк в одном хеш-сегменте. Один из возможных способов избежать проблем — исключить из индекса значения с низкой степенью уникальности с помощью условия частичного индекса, но во многих случаях этот способ может не подойти.
Как и B-деревья, хеш-индексы осуществляют простое удаление индексных кортежей.
Это отложенная операция обслуживания, которая удаляет индексные кортежи, о которых
известно, что их можно безопасно удалить (те, у которых для идентификатора элемента
уже установлен бит LP_DEAD). Если при добавлении на странице не обнаруживается
свободное место, эта операция пытается избежать создания новой страницы
переполнения путем удаления неиспользуемых индексных кортежей. Удаление не произойдет,
если страница на этот момент закреплена. Удаление неиспользуемых индексных указателей
также происходит во время выполнения команды VACUUM.
Если это возможно, команда VACUUM также попытается втиснуть индексные кортежи
в наименьшее возможное число страниц переполнения, сводя к минимуму цепочку
переполнения. Если страница переполнения становится пустой, ее можно переработать
для повторного использования в других сегментах, однако они никогда не возвращаются
в операционную систему. В настоящее время нет иной возможности ужать индекс,
кроме как перестроить его командой REINDEX. Возможности уменьшить число
сегментов пока тоже не имеется.
Хеш-индексы могут увеличивать число страниц сегментов по мере увеличения числа индексируемых строк. Сопоставление ключа с номером сегмента в хеше выбирается так, чтобы индекс мог расширяться постепенно. Когда в индекс нужно будет добавить новый сегмент, потребуется «разделить» ровно один существующий сегмент; при этом некоторые из его кортежей будут перемещены в новый сегмент в соответствии с измененным сопоставлением ключа с номером сегмента.
Это расширение производится на переднем плане, что может увеличить время выполнения для добавления данных пользователями. Поэтому хеш-индексы могут не подходить для таблиц с быстро увеличивающимся числом строк.
Реализация
В хеш-индексе существует четыре вида страниц: метастраница (нулевая страница), содержащая статически размещенную управляющую информацию, основные страницы сегментов, страницы переполнения и страницы битовой карты, отслеживающие страницы переполнения, которые освободились и доступны для повторного использования. Для целей адресации битовые страницы рассматриваются как подмножество страниц переполнения.
Как для сканирования индекса, так и для добавления кортежей требуется определение местоположения сегмента, где должен располагаться данный кортеж. Для этого нужно знать число сегментов и значения highmask и lowmask из метастраницы; однако с точки зрения производительности нежелательно блокировать и закреплять метастраницу для каждой такой операции. Вместо этого в записи кэша отношений каждого внутреннего сервера сохраняется кэшированная копия метастраницы. Это приводит к правильному сопоставлению сегментов при условии, что целевой сегмент не был разделен с момента последнего обновления кэша.
Основные страницы сегментов и страницы переполнения выделяются независимо, поскольку каждому отдельному индексу может понадобиться больше или меньше страниц переполнения относительно числа сегментов в нем. Хеш-код использует интересный набор правил адресации, поддерживающих переменное количество страниц переполнения без необходимости перемещать основные страницы сегментов после их создания.
Каждая индексированная строка в таблице представлена в хеш-индексе одним индексным кортежем. Кортежи хеш-индекса хранятся в страницах сегментов и (если они существуют) в страницах переполнения. Для ускорения поиска записи индекса хранятся в каждой отдельной странице индекса отсортированными по хеш-коду, тем самым позволяя применять в этой странице двоичный поиск. Однако обратите внимание, что никаких предположений об относительном порядке хеш-кодов в разных индексных страницах сегмента не делается.
Алгоритмы разделения сегментов для расширения хеш-индекса слишком сложны и поэтому здесь не рассматриваются. Алгоритм разделения защищен от сбоев и может быть перезапущен, если не был завершен.