Postgres - статьи

Что нужно знать об индексах


  • Индексы используются только для ускорения операций
  • Результат выполнения запроса не зависит от использования индексов
  • Индексы не всегда ускоряют операции
  • Для ускорения полнотекстового поиска можно использовать два индекса - на основе GiST [GIST] или GIN [GIN].
  • GIN индекс, или обобщенный обратный индекс - это структура данных, у которой для каждого ключа есть много значений. В случае полнотекстового поиска ключом является лексема, а значением - сортированный список идентификаторов документов, которые содержат эту лексему. Отметим, что позиционная информация не хранится в индексе, что связано с ограничениями PostgreSQL. Так как в обратном индексе используется бинарное дерево для поиска ключей, то он слабо зависит от их количества и потому хорошо шкалируется. Этот индекс используется практически всеми большими поисковыми машинами, однако его использование в базах данных для индексирования изменяющихся документов затруднено, так как любые изменения (добавление нового документа, обновление или удаление) приводят к большому количеству обновлений индекса. Например, добавление нового документа, который содержит N уникальных лексем приводит к обновлению N записей в индексе. Поэтому этот индекс лучше всего подходит для неменяющихся коллекций документов. GIN индекс поддерживает групповое обновление индекса, которое является очень эффективным, поэтому иногда быстрее создать индекс заново, чем обновлять индекс при добавке каждого документа.

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

    Сигнатура - это битовая строка фиксированной длины, в которой все биты изначально выставленны в '0'. С помощью хэш-функции слово отображается в определенный бит сигнатуры, который становится '1'. Сигнатура документа является наложением индивидуальных сигнатур всех слов. Такая техника называется superimposed coding и реализуется как bitwise OR, что является очень быстрой операцией.


    word signature ---------------- w1 -> 01000000 w2 -> 00010000 w3 -> 10000000 ---------------------- 11010000

    В этом примере, '11010000' является сигнатурой документа, состоящего из трех уникальных слов w1,w2,w3. Сигнатура является некоторым компактным представлением документа, что приводит к значительному уменьшению размера коллекции. Кроме того, фиксированный размер cигнатуры сильно облегчает операции сравнения. Все это делает использование сигнатур вместо документов привлекательным с точки зрения производительности.

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

    11010000 - сигнатура документа 00000001 - сигнатура запроса Q1, точно не содержится в документе 01000000 - сигнатура запроса Q2, возможно содержится в документе 01010000 - cигнатура запроса Q3, возможно содержится в документе

    Сигнатура Q2 является сигнатурой слова w1 и, таким образом, является правильным попаданием, в то время как сигнатура Q3 - ложным попаданием (false drop), несмотря на то, что она удовлетворяет сигнатуре документа. Ясно, что конечность размера сигнатуры и увеличение количества уникальных слов приводит к насыщению сигнатуры, т.е., когда все биты будут '1', что сильно уменьшает избирательность сигнатуры и ухудшает производительность поиска.



    Существуют несколько структур данных для хранения сигнатур, такие как сигнатурный файл (signature file),но они не являются индексами, так как требует полного просмотра. Дерево RD-Tree является аналогом R-Tree, приспособленное к работе со множествами для решения задачи поиска всех множеств, которые содержат в себе некое подмножество, является индексной структурой и может сильно ускорять поиск. Подробнее о RD-Tree можно прочитать в оригинальной статье [RDTREE]



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

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

    ROOT 11011011

    Internal nodes: 11011001 10010011 | | Leaves: 11010000, 11010001, 11011000 10010010,10010001

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

    Найденные результаты приходится дополнительно проверять на наличие "false drops", т.е., проверять сами исходные документы, действительно ли они удовлетворяют поисковому запросу, что требует произвольного доступа к "heap" (таблице) и это сильно сказывается на производительности. Степень неоднозначности (lossiness), а следовательно и производительность GiST-индекса, зависит от кол-ва уникальных лексем и количества документов, что ограничивает применимость этого индекса для больших коллекций.

    Но это не вся правда о GiST-индексе ! На самом деле, в листьях могут храниться не сигнатуры, а сами tsvector-а, если они не превышают TOAST_INDEX_TARGET байт, что-то около 512 байт. В этом случае попадание является точным и проверять ничего не надо. К сожалению, пока нет возможности индексу сказать какое было попадание, но в будущем, когда появится такая возможность, эта оптимизация может очень хорошо работать для новостных сайтов, где документы не очень большие. Чтобы изучить GiST-индекс, можно воспользоваться специальным модулем Gevel [GEVEL], который выдает полезную информацию об индексе. Вот пример такой выдачи для индекса gist_idx_50 для базы, которая содержит небольшие сообщения. Обратите внимание, что листья содержат как сами tsvector-а, так и сигнатуры, а внутренние ноды - только сигнатуры.



    arxiv=# select gist_stat('gist_idx_90'); gist_stat -------------------------------------------- Number of levels: 4 Number of pages: 18296 Number of leaf pages: 17496 Number of tuples: 435661 Number of invalid tuples: 0 Number of leaf tuples: 417366 Total size of tuples: 124776048 bytes Total size of leaf tuples: 119803816 bytes Total size of index: 149880832 bytes

    -- leaf node arxiv=# select * from gist_print('gist_idx_90') as t(level int,valid bool, fts gtsvector) where level =4; level | valid | fts -------+-------+-------------------------------- 4 | t | 130 true bits, 1886 false bits 4 | t | 95 unique words 4 | t | 33 unique words 4 | t | 77 unique words 4 | t | 68 unique words 4 | t | 86 unique words 4 | t | 77 unique words 4 | t | 51 unique words 4 | t | 122 unique words 4 | t | 127 true bits, 1889 false bits 4 | t | 105 unique words 4 | t | 170 true bits, 1846 false bits 4 | t | 77 unique words 4 | t | 121 true bits, 1895 false bits .................................... 4 | t | 61 unique words (417366 rows)

    -- internal node arxiv=# select * from gist_print('gist_idx_90') as t(level int, valid bool, fts gtsvector) where level =3;

    level | valid | fts -------+-------+-------------------------------- 3 | t | 852 true bits, 1164 false bits 3 | t | 861 true bits, 1155 false bits 3 | t | 858 true bits, 1158 false bits 3 | t | 872 true bits, 1144 false bits 3 | t | 858 true bits, 1158 false bits 3 | t | 855 true bits, 1161 false bits 3 | t | 853 true bits, 1163 false bits 3 | t | 857 true bits, 1159 false bits .................................................. 3 | t | 782 true bits, 1234 false bits 3 | t | 773 true bits, 1243 false bits (17496 rows)


    Содержание раздела