обработка данных

Нажмите сюда, если долго загружается,
либо "ESC" - отмена
 
Заказ обратного звонка
Заказать звонок
Наш специалист свяжется с Вами и ответит на все вопросы
Обработка данных
Наш специалист свяжется с Вами и ответит на все вопросы.
OK

Индексы в PostgreSQL. Часть 3

Источник: https://habrahabr.ru
Время чтения: ~8 мин
Индексы в PostgreSQL. Часть 3
Статьи
674
Логотип PostgreSQL
В первой статье мы рассмотрели механизм индексирования PostgreSQL, во второй — интерфейс методов доступа, и теперь готовы к разговору о конкретных типах индексов. Начнем с хеш-индекса.
Hash
Устройство
Общая теория
Многие современные языки программирования включают хеш-таблицы в качестве базового типа данных. Внешне это выглядит, как обычный массив, но в качестве индекса используется не целое число, а любой тип данных (например, строка). Хеш-индекс в PostgreSQL устроен похожим образом. Как это работает?

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

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

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

Просто в качестве примера: какую хеш-функцию можно придумать для строк? Пусть число корзин равно 256. Тогда в качестве номера корзины можно взять код первого символа (допустим, у нас однобайтовая кодировка). Хорошая ли это хеш-функция? Очевидно, нет: если все строки начинаются с одного и того же символа, все они попадут в одну корзину; о равномерности тут нет и речи, придется перепроверять все значения и весь смысл хеширования потеряется. Что, если просуммировать коды всех символов по модулю 256? Будет гораздо лучше, хотя тоже далеко не идеально. Если интересно, как на самом деле устроена такая хеш-функция в PostgreSQL, посмотрите определение hash_any() в hashfunc.c.
Устройство индекса
Вернемся к хеш-индексу. Наша задача состоит в том, чтобы по значению некоторого типа данных (ключ индексирования) быстро найти соответствующий TID.

При вставке в индекс вычислим хеш-функцию для ключа. Хеш-функции в PostgreSQL всегда возвращают тип integer, что соответствует диапазону 2^32 ≈ 4 миллиарда значений. Число корзин изначально равно двум и увеличивается динамически, подстраиваясь под объем данных; номер корзины можно вычислить по хеш-коду с помощью битовой арифметики. В эту корзину и положим наш TID.

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

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

Но может так получиться, что два разных ключа не просто попадут в одну корзину, но и будут иметь одинаковые 4-байтовые хеш-коды — коллизии никто не отменял. Поэтому метод доступа просит общий механизм индексирования контролировать каждый TID, перепроверяя условие по табличной строке (механизм умеет это делать заодно с проверкой видимости).
Страничная организация
Если посмотреть на индекс не с точки зрения планирования и выполнения запроса, а глазами менеджера буферного кеша, то окажется, что вся информация, все индексные записи должны быть упакованы в страницы. Такие индексные страницы помещаются в буферный кеш и вытесняются оттуда точно так же, как и табличные страницы.
Индексы в PostgreSQL. Часть 3
Источник: habrahabr.ru
Хеш-индекс, как видно на картинке, использует страницы (серые прямоугольники) четырех видов:

- Метастраница (meta page) — нулевая страница, содержит информацию о том, что находится внутри индекса;
- Страницы корзин (bucket page) — основные страницы индекса, хранят данные в виде пар «хеш-код — TID»;
- Страницы переполнения (overflow page) — устроены так же, как страницы корзин, и используются в случае, когда одной страницы для корзины не хватает;
- Страницы битовой карты (bitmap page) — в них отмечаются освободившиеся страницы переполнения, которые можно использовать для других корзин.

Стрелочки вниз, идущие от элементов индексных страниц, символизируют TID-ы — ссылки на табличные строки.При очередном увеличении индекса одномоментно создается в два раза больше корзин (и, соответственно, страниц), чем в прошлый раз. Чтобы не выделять сразу такое, потенциально большое, количество страниц, в версии 10 сделали более плавное увеличение размера. Ну а страницы переполнения выделяются просто по мере необходимости и отслеживаются в страницах битовой карты, которые также выделяются по мере надобности.

Заметим, что хеш-индекс не умеет уменьшаться в размере. Если удалить часть проиндексированных строк, однажды выделенные страницы уже не возвращаются операционной системе, а только переиспользуются для новых данных после очистки (VACUUM). Единственный вариант уменьшить физический размер индекса — перестроить его с нуля командой REINDEX или VACUUM FULL.
Пример
Приведем пример создания хеш-индекса. Чтобы не изобретать свои таблицы, здесь и дальше мы будем пользоваться демонстрационной базой данных по авиаперевозкам, и на этот раз возьмем таблицу рейсов.
CODE
Неприятной особенностью текущей реализации хеш-индекса является то, что действия с ним не попадают в журнал упреждающей записи (о чем нас и предупреждает PostgreSQL при создании индекса). Как следствие, хеш-индексы не могут быть восстановлены после сбоя и не участвуют в репликации. Кроме того, хеш-индекс значительно уступает B-дереву по универсальности применения, и его эффективность тоже вызывает вопросы. То есть сейчас применять такие индексы не имеет практического смысла.

Впрочем, ситуация изменится уже этой осенью с выходом десятой версии PostgreSQL. В ней хеш-индекс снабдили наконец поддержкой журнала и дополнительно оптимизировали выделение памяти и эффективность одновременной работы.
Семантика хеширования
Почему же хеш-индекс просуществовал чуть не от самого рождения PostgreSQL до наших дней в состоянии, в котором им нельзя воспользоваться? Дело в том, что алгоритм хеширования используется в СУБД очень широко (в частности, для хеш-соединений и группировок), и системе надо знать, какую хеш-функцию применять к каким типам данных. Но это соответствие не статично, его нельзя задать раз и навсегда — PostgreSQL позволяет добавлять новые типы на лету. Вот в методе доступа по хешу такое соответствие и содержится, а представлено оно в виде привязки вспомогательных функций к семействам операторов:
CODE
Хотя эти функции и не документированы, ими можно воспользоваться для вычисления хеш-кода значения соответствующего типа. Например, для семейства text_ops используется функция hashtext:
CODE
Свойства
Посмотрим свойства хеш-индекса, которые этот метод доступа сообщает о себе системе. Запросы мы приводили в прошлый раз; сейчас ограничимся только результатами:
CODE
Хеш-функция не сохраняет отношение порядка: из того, что значение хеш-функции одного ключа меньше значения функции другого ключа, нельзя сделать никаких выводов о том, как упорядочены сами ключи. Поэтому хеш-индекс в принципе может поддерживать единственную операцию «равно»:
CODE
Соответственно хеш-индекс не может выдавать упорядоченные данные (can_order, orderable). По той же причине хеш-индекс не работает с неопределенными значениями: операция «равно» не имеет смысла для null (search_nulls).

Поскольку в хеш-индексе не сохраняются ключи (а только хеш-коды ключей), он не может использоваться для исключительно индексного доступа (returnable).

Многоколоночные индексы (can_multi_col) этот метод доступа не поддерживает.
Внутренности
Начиная с версии 10, во внутреннюю структуру хеш-индекса можно будет заглянуть с помощью расширения pageinspect. Вот как это будет выглядеть:
CODE
Метастраница (получаем число строк в индексе и максимальный задействованный номер корзины):
CODE
Страница корзины (получаем число актуальных строк и строк, которые могут быть очищены):
CODE
И так далее. Но понять смысл всех доступных полей вряд ли получится без изучения исходного кода. При наличии такого желания начать стоит с README.
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Подписка на новости. Получайте важное первым
ПОДПИСАТЬСЯ