# Хеш-индекс Индекс LLMS: [llms.txt](/ru/llms.txt) --- ## 24.1. Общий принцип {#internal-ru-section-24-1} Хеш-индекс [^internal-ru-512-1] позволяет по ключу индексирования быстро найти идентификатор версии строки (tid). В первом приближении это просто хеш-таблица, хранящаяся на диске. Единственная операция, которую поддерживает хеш-индекс, — поиск по условию равенства. При вставке в индекс [^internal-ru-512-2] вычисляется хеш-функция от значения ключа индексирования. Хеш-функции в PostgreSQL возвращают 32-битные или 64-битные целые, а в качестве номера корзины используются несколько младших битов этого значения. В выбранную корзину добавляется идентификатор версии вместе с хеш-кодом ключа. Само значение ключа не сохраняется в индексе, поскольку реализации удобнее иметь дело с небольшими значениями фиксированной длины. Хеш-таблица индекса динамически расширяется[^internal-ru-512-3]. Минимальное число корзин равно двум. По мере увеличения количества индексируемых строк одна из корзин расщепляется на две. Для этого задействуется дополнительный бит хеш-кода, так что элементы перераспределяются только между двумя корзинами, участвующими в расщеплении, а состав остальных корзин хеш-таблицы не меняется[^internal-ru-512-4]. При поиске в индексе [^internal-ru-513-1] вычисляется хеш-функция от ключа индексирования и соответствующий этому значению номер корзины. Из всего содержимого корзины возвращаются только те идентификаторы версий, которые соответствуют хеш-коду ключа. Благодаря тому что элементы корзин упорядочены по хеш-кодам ключей, подходящие идентификаторы эффективно находятся двоичным поиском. Поскольку само значение ключа не сохраняется в хеш-таблице, индексный метод может вернуть лишние идентификаторы версий строк из-за хеш-коллизий. Поэтому механизм индексирования перепроверяет все полученные от метода доступа результаты по таблице. По этой же причине невозможно сканирование только индекса. (*с.* [411](/ru/19-index-access-methods/#internal-ru-page-412)) ## 24.2. Страничная организация {#internal-ru-section-24-2} В отличие от обычной хеш-таблицы, индекс хранится на диске. Поэтому вся необходимая информация должна быть разложена по страницам, причем желательно, чтобы операциям над индексом (поиск, вставка, удаление) требовался доступ к как можно меньшему количеству страниц. Хеш-индекс использует страницы четырех видов: - метастраница (meta page) — нулевая страница с «оглавлением» индекса; - страницы корзин (bucket page) — основные страницы индекса, по одной на каждую корзину; - страницы переполнения (overflow page) — дополнительные страницы, которые используются, когда основной страницы корзины не хватает для размещения всех элементов; - страницы битовой карты (bitmap page) — страницы с битовым массивом, в котором отмечены освободившиеся и доступные для повторного использования страницы переполнения. Заглянуть внутрь индексных страниц позволяет расширение `pageinspect`. Начнем с пустой таблицы: ```text {label="psql"} => CREATE EXTENSION pageinspect; => CREATE TABLE t(n integer); => ANALYZE t; => CREATE INDEX ON t USING hash(n); ``` Я проанализировал таблицу, чтобы получить индекс минимального размера; иначе количество корзин соответствовало бы таблице из 10 страниц[^internal-ru-514-1]. (v. 14) Сейчас в индексе четыре страницы: метастраница, две основные страницы корзин и одна страница битовой карты (сразу созданная «про запас»): ```text {label="psql"} => SELECT page, hash_page_type(get_raw_page('t_n_idx', page)) FROM generate_series(0,3) page; page | hash_page_type ------+---------------- 0 | metapage 1 | bucket 2 | bucket 3 | bitmap (4 rows) ``` ![Страничная организация: мета-битовая; корзина 0корзина 0корзина 1корзина 1; страницакарта](/images/internal/ru/p514-01.svg) {#internal-ru-fig-24-1 num="24.1" caption="Страничная организация" .book-original-figure width=390 height=65} Метастраница содержит всю управляющую информацию об индексе. Пока нас интересует несколько значений: ```text {label="psql"} => SELECT ntuples, ffactor, maxbucket FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); ntuples | ffactor | maxbucket ---------+---------+----------- 0 | 307 | 1 (1 row) ``` Расчетное количество строк на одну корзину показано в поле `ffactor`. Это значение вычисляется исходя из вместимости блока и установленного значения параметра хранения *fillfactor*. При совершенно равномерном распределении данных и отсутствии хеш-коллизий значение *fillfactor* можно было бы и увеличить, но в реальности это повышает вероятность того, что элементы одной корзины не поместятся на одну страницу. (*по умолчанию:* `75`) Самый плохой для хеш-индекса случай — сильный перекос в распределении данных, когда один ключ повторяется много раз. Поскольку хеш-функция будет выдавать одно и то же значение, все данные будут попадать в одну и ту же корзину, и увеличение количества корзин ничем не поможет. Сейчас индекс пуст, о чем говорит значение поля `ntuples`. Переполним страницу корзины, вставив в таблицу определенное количество строк с одинаковым значением индексируемого столбца. В индексе появится страница переполнения: ```text {label="psql" hl_lines="11"} => INSERT INTO t(n) SELECT 0 FROM generate_series(1,500); -- одно значение => SELECT page, hash_page_type(get_raw_page('t_n_idx', page)) FROM generate_series(0,4) page; page | hash_page_type ------+---------------- 0 | metapage 1 | bucket 2 | bucket 3 | bitmap 4 | overflow (5 rows) ``` ![Страничная организация: полнен; реие; пе; мета-битовая; корзина 0корзина 0корзина 1корзина 1корзина 1корзина 1корзина 1корзина 1; страницакарта](/images/internal/ru/p515-02.svg) {#internal-ru-fig-24-2 num="24.2" caption="Страничная организация" .book-original-figure width=502 height=126} Сводка информации по страницам показывает, что корзина 0 пуста, а все значения попали в корзину 1: часть на основную страницу, а те, что не поместились, — на страницу переполнения. ```text {label="psql"} => SELECT page, live_items, free_size, hasho_bucket FROM (VALUES (1), (2), (4)) p(page), hash_page_stats(get_raw_page('t_n_idx', page)); page | live_items | free_size | hasho_bucket ------+------------+-----------+-------------- 1 | 0 | 8148 | 0 2 | 407 | 8 | 1 4 | 93 | 6288 | 1 (3 rows) ``` Очевидно, что разброс элементов одной корзины по нескольким страницам плохо сказывается на производительности. Лучшие результаты хеш-индекс показывает на равномерно распределенных данных. Посмотрим теперь, как расщепляется корзина. Это происходит, когда количество строк в индексе превышает расчетное число `ffactor` для имеющихся корзин. В данном случае при двух корзинах и `ffactor` = 307 это произойдет, когда в индекс будет вставлена 615-я строка: ```text {label="psql"} => SELECT ntuples, ffactor, maxbucket, ovflpoint FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); ntuples | ffactor | maxbucket | ovflpoint ---------+---------+-----------+----------- 500 | 307 | 1 | 1 (1 row) => INSERT INTO t(n) SELECT n FROM generate_series(1,115) n; -- теперь разные => SELECT ntuples, ffactor, maxbucket, ovflpoint FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); ntuples | ffactor | maxbucket | ovflpoint ---------+---------+-----------+----------- 615 | 307 | 2 | 2 (1 row) ``` Значение `maxbucket` увеличилось до двух: теперь у нас есть три корзины с номерами от 0 до 2. Но хотя добавилась всего одна корзина, количество страниц удваивается: ```text {label="psql" hl_lines="10 11"} => SELECT page, hash_page_type(get_raw_page('t_n_idx', page)) FROM generate_series(0,6) page; page | hash_page_type ------+---------------- 0 | metapage 1 | bucket 2 | bucket 3 | bitmap 4 | overflow 5 | bucket 6 | unused (7 rows) ``` ![Страничная организация: мета-битовая; корзина 0корзина 0корзина 1корзина 1корзина 1корзина 1корзина 1корзина 1корзина 2корзина 2; страницакарта](/images/internal/ru/p517-03.svg) {#internal-ru-fig-24-3 num="24.3" caption="Страничная организация" .book-original-figure width=722 height=78} Одна из новых страниц задействована под корзину 2, а другая остается незанятой и будет использована для корзины 3, когда та появится. ```text {label="psql"} => SELECT page, live_items, free_size, hasho_bucket FROM (VALUES (1), (2), (4), (5)) p(page), hash_page_stats(get_raw_page('t_n_idx', page)); page | live_items | free_size | hasho_bucket ------+------------+-----------+-------------- 1 | 27 | 7608 | 0 2 | 407 | 8 | 1 4 | 158 | 4988 | 1 5 | 23 | 7688 | 2 (4 rows) ``` Таким образом, с точки зрения операционной системы размер хеш-индекса растет скачкообразно, хотя логически хеш-таблица увеличивается постепенно. Чтобы немного сгладить этот рост и не выделять сразу слишком много страниц, начиная с 10-го удвоения страницы выделяются не все сразу, а частями, по \(\frac14\) от расчетного количества. Еще два поля из метастраницы, представляющих собой битовые маски, раскрывают детали адресации корзин: ```text {label="psql"} => SELECT maxbucket, highmask::bit(4), lowmask::bit(4) FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); maxbucket | highmask | lowmask -----------+----------+--------- 2 | 0011 | 0001 (1 row) ``` Номер корзины определяется битами хеш-кода, соответствующими маске `highmask`. Но если полученный номер корзины не существует (превышает `maxbucket`), то надо взять биты, соответствующие маске `lowmask`[^internal-ru-518-1]. В данном случае мы берем два младших бита, что дает значения от 0 до 3; но если выпадает 3, то берем только один младший бит, то есть вместо третьей корзины используем первую. При каждом удвоении размера новые страницы корзин всегда выделяются одним непрерывным фрагментом, а страницы переполнения и битовой карты вставляются между этими фрагментами по необходимости. Метастраница хранит количество вставленных страниц для каждого из фрагментов в массиве `spares`, и это дает возможность по номеру корзины вычислить номер ее основной страницы[^internal-ru-518-2]. В данном случае после первого удвоения было вставлено две страницы (битовая карта и страница переполнения), а после второго пока не добавилось ничего нового: ```text {label="psql"} => SELECT spares[2], spares[3] FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); spares | spares --------+-------- 2 | 2 (1 row) ``` В метастранице также хранится массив ссылок на страницы битовой карты: ```text {label="psql"} => SELECT mapp[1] FROM hash_metapage_info(get_raw_page('t_n_idx', 0)); mapp ------ 3 (1 row) ``` ![Страничная организация: spares; мета-битовая; корзина 0корзина 0корзина 1корзина 1корзина 1корзина 1корзина 2корзина 2; страницакарта; mmap](/images/internal/ru/p519-04.svg) {#internal-ru-fig-24-4 num="24.4" caption="Страничная организация" .book-original-figure width=710 height=206} Место внутри индексных страниц освобождается при удалении ссылок на мертвые версии строк. Это происходит при самоочистке (она срабатывает при попытке вставки элемента в полностью заполненную страницу [^internal-ru-519-1]) или при обычной очистке. Но уменьшаться в размерах хеш-индекс не умеет, и однажды выделенные страницы уже не возвращаются операционной системе. Основные страницы всегда закреплены за своими корзинами, даже если в них нет ни одного элемента; опустевшие страницы переполнения отслеживаются в битовой карте и переиспользуются (возможно, уже для другой корзины). Единственный вариант уменьшить физический размер индекса — перестроить его командой `REINDEX` или `VACUUM FULL`. (*с.* [170](/ru/08-rebuilding-tables-and-indexes/#internal-ru-page-171)) В плане запроса тип индекса никак не отмечается: ```text {label="psql"} => CREATE INDEX ON flights USING hash(flight_no); ``` ```text {label="psql"} => EXPLAIN (costs off) SELECT * FROM flights WHERE flight_no = 'PG0001'; QUERY PLAN -------------------------------------------------- Bitmap Heap Scan on flights Recheck Cond: (flight_no = 'PG0001'::bpchar) -> Bitmap Index Scan on flights_flight_no_idx Index Cond: (flight_no = 'PG0001'::bpchar) (4 rows) ``` ## 24.3. Класс операторов {#internal-ru-section-24-3} До версии PostgreSQL 10 хеш-индексы не журналировались, то есть не были защищены от сбоев и не реплицировались, и, как следствие, не рекомендовались к использованию. Но даже в таком виде они представляли определенную ценность. Дело в том, что алгоритм хеширования применяется очень широко (в частности, для хеш-соединений и группировок), и системе требуется знать, какая хеш-функция предназначена для каждого типа данных. Но это соответствие не статично: его нельзя задать раз и навсегда, поскольку PostgreSQL позволяет добавлять новые типы данных на лету. Поэтому соответствие поддерживается классом операторов для хеш-индекса и конкретного типа данных. Собственно функция хеширования представлена опорной функцией класса: (*с.* [457](/ru/22-hashing/#internal-ru-page-458)) (*с.* [397](/ru/19-index-access-methods/#internal-ru-page-398)) (psql: `\dAp`) ```text {label="psql"} => SELECT opfname AS opfamily_name, amproc::regproc AS opfamily_procedure FROM pg_am am JOIN pg_opfamily opf ON opfmethod = am.oid JOIN pg_amproc amproc ON amprocfamily = opf.oid WHERE amname = 'hash' AND amprocnum = 1 ORDER BY opfamily_name, opfamily_procedure; opfamily_name | opfamily_procedure --------------------+-------------------- aclitem_ops | hash_aclitem array_ops | hash_array bool_ops | hashbool bpchar_ops | hashbpchar bpchar_pattern_ops | hashbpchar bytea_ops | hashbytea ... timestamptz_ops | timestamptz_hash timetz_ops | timetz_hash uuid_ops | uuid_hash xid8_ops | hashxid8 xid_ops | hashxid (38 rows) ``` Эти функции возвращают 32-битные целые числа. Хотя они и не документированы, их можно использовать для вычисления хеш-кода значения соответствующего типа. Например, для семейства `text_ops` используется функция `hashtext`: ```text {label="psql"} => SELECT hashtext('раз'), hashtext('два'); hashtext | hashtext -----------+----------- 127722028 | 345620034 (1 row) ``` В класс операторов хеш-индекса входит один оператор — «равно». Обычно именно он используется для системных проверок значений на равенство. (psql: `\dAo`) ```text {label="psql"} => SELECT opfname AS opfamily_name, left(amopopr::regoperator::text, 20) AS opfamily_operator FROM pg_am am JOIN pg_opfamily opf ON opfmethod = am.oid JOIN pg_amop amop ON amopfamily = opf.oid WHERE amname = 'hash' ORDER BY opfamily_name, opfamily_operator; opfamily_name | opfamily_operator --------------------+---------------------- aclitem_ops | =(aclitem,aclitem) array_ops | =(anyarray,anyarray) bool_ops | =(boolean,boolean) ... xid8_ops | =(xid8,xid8) xid_ops | =(xid,xid) (48 rows) ``` ## 24.4. Свойства {#internal-ru-section-24-4} Посмотрим свойства хеш-индекса, которые этот метод доступа сообщает о себе системе. (*с.* [404](/ru/19-index-access-methods/#internal-ru-page-405)) ### Свойства уровня метода доступа {#internal-ru-subsection-star-357} ```text {label="psql"} => SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name) FROM pg_am a, unnest(array[ 'can_order', 'can_unique', 'can_multi_col', 'can_exclude', 'can_include' ]) p(name) WHERE a.amname = 'hash'; amname | name | pg_indexam_has_property --------+---------------+------------------------- hash | can_order | f hash | can_unique | f hash | can_multi_col | f hash | can_exclude | t hash | can_include | f (5 rows) ``` Очевидно, что хеш-индексы не позволяют упорядочивать строки: хеш-функция перемешивает данные более или менее случайным образом. Не поддерживается и ограничение уникальности. Правда, хеш-индексы можно использовать для ограничения исключения, а с единственной функцией «равно» исключение приобретает смысл уникальности: (*с.* [408](/ru/19-index-access-methods/#internal-ru-page-409)) ```text {label="psql"} => ALTER TABLE aircrafts_data ADD CONSTRAINT unique_range EXCLUDE USING hash(range WITH =); => INSERT INTO aircrafts_data VALUES ('744','{"ru": "Боинг 747-400"}',11100); ERROR: conflicting key value violates exclusion constraint "unique_range" DETAIL: Key (range)=(11100) conflicts with existing key (range)=(11100). ``` Также не поддерживаются многоколоночные хеш-индексы и возможность добавлять к индексу дополнительные include-столбцы. ### Свойства уровня индекса {#internal-ru-subsection-star-359} ```text {label="psql"} => SELECT p.name, pg_index_has_property('flights_flight_no_idx', p.name) FROM unnest(array[ 'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan' ]) p(name); name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t bitmap_scan | t backward_scan | t (4 rows) ``` Хеш-индекс работает как с обычным индексным сканированием, так и со сканированием по битовой карте. Кластеризация таблицы по хеш-индексу не предусмотрена. Это логично, поскольку сложно представить, зачем может понадобиться физически упорядочить данные в таблице по значению хеш-функции. ### Свойства уровня столбца {#internal-ru-subsection-star-361} Фактически свойства столбцов полностью определены на уровне метода доступа и всегда принимают одни и те же значения. ```text {label="psql"} => SELECT p.name, pg_index_column_has_property('flights_flight_no_idx', 1, p.name) FROM unnest(array[ 'asc', 'desc', 'nulls_first', 'nulls_last', 'orderable', 'distance_orderable', 'returnable', 'search_array', 'search_nulls' ]) p(name); name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f (9 rows) ``` Поскольку хеш-функция не сохраняет отношение порядка, к хеш-индексу не применимы свойства, касающиеся упорядоченности. Хеш-индекс не может участвовать в сканировании только индекса, поскольку не сохраняет ключ индексации и требует перепроверки по таблице. Хеш-индекс не работает с неопределенными значениями: операция «равно» не имеет смысла для `NULL`. Поиск значений из массива не реализован. [^internal-ru-512-1]: [postgrespro.ru/docs/postgresql/18/hash-index](); [backend/access/hash/README](). [^internal-ru-512-2]: [backend/access/hash/hashinsert.c](). [^internal-ru-512-3]: [backend/access/hash/hashpage.c](), функция \_hash\_expandtable. [^internal-ru-512-4]: [backend/access/hash/hashpage.c](), функция \_hash\_getbucketbuf\_from\_hashkey. [^internal-ru-513-1]: [backend/access/hash/hashsearch.c](). [^internal-ru-514-1]: [backend/access/table/tableam.c](), функция table\_block\_relation\_estimate\_size. [^internal-ru-518-1]: [backend/access/hash/hashutil.c](), функция \_hash\_hashkey2bucket. [^internal-ru-518-2]: [include/access/hash.h](), макрос BUCKET\_TO\_BLKNO. [^internal-ru-519-1]: [backend/access/hash/hashinsert.c](), функция \_hash\_vacuum\_one\_page.