Индексы в PostgreSQL — 10


    В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.

    Bloom


    Общая идея


    Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).

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

    В случае индекса СУБД мы фактически имеем N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.

    Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.

    Устройство


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



    Создание и выбор значений параметров


    При создании Блум-индекса в параметрах хранения указывается общий размер сигнатуры (length) и число устанавливаемых битов отдельно для каждого поля, включенного в индекс (col1—col32):

    create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...);

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

    Как выбрать подходящие значения? Теория говорит о том, что если задаться вероятностью p ложного срабатывания фильтра, то оптимальное число бит сигнатуры можно оценить как
    m = −n log2(p) / ln(2), где n — число полей в индексе, а число устанавливаемых бит k = −log2(p).

    Внутри индекса сигнатура хранится как массив двубайтовых целых чисел, так что значение m можно смело округлять сверху до 16.

    Выбирая вероятность p, следует учитывать размер индекса, который будет равен примерно
    (m/8 + 6)N, где N — число строк в таблице, а 6 — размер указателя TID в байтах.

    Несколько моментов:
    • Вероятность ложного срабатывания p относится к одному фильтру; при сканировании таблицы мы ожидаем получить Np ложных срабатываний (для запроса, который возвращает мало строк, конечно). Например, для таблицы в миллион строк и вероятности 0,01 в среднем можно ожидать в плане запроса «Rows Removed by Index Recheck: 10000».
    • Фильтр Блума — вероятностная структура. Говорить о конкретных числах имеет смысл, только усредняя достаточно много значений, а в каждом конкретном случае можно получить все, что угодно.
    • Приведенные выше оценки основаны на идеализированной математической модели и ряде допущений. На практике же результат скорее всего получается хуже. Так что к формулам стоит относиться спокойно: это просто способ выбрать начальные значения для дальнейших экспериментов.
    • Метод доступа позволяет выбрать число устанавливаемых бит отдельно для каждого поля. Есть разумное предположение, что на самом деле оптимальное число зависит от распределения значений в столбце. Если хочется заморочиться, можно посмотреть, например, эту статью (буду признателен за ссылки на другие исследования). Но сначала перечитайте предыдущий пункт.

    Обновление


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

    Обычный фильтр Блума не поддерживает удаления элементов, но для Блум-индекса этого и не требуется: при удалении строки из таблицы удаляется вся сигнатура целиком вместе со строкой индекса.

    Изменение, как обычно, состоит из удаления старой версии строки и вставке новой (при этом сигнатура вычисляется заново).

    Сканирование


    Поскольку единственное, что умеет фильтр Блума — это проверять принадлежность элемента множеству, то и единственная поддерживаемая Блум-индексом операция — проверка на равенство (как в хеш-индексе).

    Как мы говорили, Блум-индекс является плоским, так что при индексном доступе он всегда читается подряд и целиком. В процессе чтения строится битовая карта, которая затем используется для доступа к таблице.

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

    Следует учесть, что чем больше размер Блум-индекса, тем менее привлекательным он будет казаться планировщику — эта зависимость линейна, в отличие от древовидных индексов.

    Пример


    Таблица


    Посмотрим на Блум-индекс на примере большой таблицы flights_bi из прошлой статьи. Напомню, что размер этой таблицы составляет 4 ГБ при примерно 30 миллионах строк. Определение таблицы:

    demo=# \d flights_bi
                              Table "bookings.flights_bi"
           Column       |           Type           | Collation | Nullable | Default
    --------------------+--------------------------+-----------+----------+---------
     airport_code       | character(3)             |           |          |
     airport_coord      | point                    |           |          |
     airport_utc_offset | interval                 |           |          |
     flight_no          | character(6)             |           |          |
     flight_type        | text                     |           |          |
     scheduled_time     | timestamp with time zone |           |          |
     actual_time        | timestamp with time zone |           |          |
     aircraft_code      | character(3)             |           |          |
     seat_no            | character varying(4)     |           |          |
     fare_conditions    | character varying(10)    |           |          |
     passenger_id       | character varying(20)    |           |          |
     passenger_name     | text                     |           |          |

    Начнем с создания расширения — Блум-индекс входит в стандартную поставку начиная с версии 9.6, но недоступен по умолчанию.

    demo=# create extension bloom;
    CREATE EXTENSION

    С помощью BRIN в прошлый раз нам удалось проиндексировать три поля (scheduled_time, actual_time, airport_utc_offset). Блум-индексы не зависят от физического расположения данных, поэтому попробуем включить в индекс почти все поля таблицы. Однако исключим время (scheduled_time и actual_time) — методом поддерживается только сравнение на равенство, но запрос по точному времени вряд ли кому-то интересен (можно было бы построить индекс по выражению, округлив время до суток, но мы не будем этого делать). Еще нам придется исключить координаты аэропорта (airport_coord) — забегая вперед, тип point не поддерживается.

    Чтобы выбрать значения параметров, возьмем вероятность ложного срабатывания 0,01 (понимая, что реально получится больше). Приведенные выше формулы для n = 9 и N = 30 000 000 дают размер сигнатуры 96 бит и предлагают устанавливать 7 бит на элемент. Расчетный размер индекса — 515 МБ (примерно восьмая часть таблицы).

    (При минимальном размере сигнатуры в 16 бит формулы обещают в два раза меньший индекс, но позволяют надеяться лишь на вероятность 0,5, что совсем плохо.)

    Классы операторов


    Итак, пробуем создать индекс.

    demo=# create index flights_bi_bloom on flights_bi
    using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
    with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
    ERROR:  data type character has no default operator class for access method "bloom"
    HINT:  You must specify an operator class for the index or define a default operator class for the data type.

    Печаль: в расширении нам дают всего лишь два класса операторов:

    demo=# select opcname, opcintype::regtype
    from pg_opclass
    where opcmethod = (select oid from pg_am where amname = 'bloom')
    order by opcintype::regtype::text;
     opcname  | opcintype
    ----------+-----------
     int4_ops | integer
     text_ops | text
    (2 rows)

    К счастью, не составляет труда создать аналогичные классы и для других типов данных. В класс операторов для метода bloom должен входить ровно один оператор — равенство — и ровно одна вспомогательная функция — хеширование. Самый простой способ найти нужные операторы и функции для произвольного типа — заглянуть в системный каталог на классы операторов метода hash:

    demo=# select distinct
           opc.opcintype::regtype::text,
           amop.amopopr::regoperator,
           ampr.amproc
      from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr
     where am.amname = 'hash'
       and opc.opcmethod = am.oid
       and amop.amopfamily = opc.opcfamily
       and amop.amoplefttype = opc.opcintype
       and amop.amoprighttype = opc.opcintype
       and ampr.amprocfamily = opc.opcfamily
       and ampr.amproclefttype = opc.opcintype
    order by opc.opcintype::regtype::text;
     opcintype |       amopopr        |    amproc    
    -----------+----------------------+--------------
     abstime   | =(abstime,abstime)   | hashint4
     aclitem   | =(aclitem,aclitem)   | hash_aclitem
     anyarray  | =(anyarray,anyarray) | hash_array
     anyenum   | =(anyenum,anyenum)   | hashenum
     anyrange  | =(anyrange,anyrange) | hash_range
     ...

    Имея эту информацию, создадим два недостающих класса:

    demo=# CREATE OPERATOR CLASS character_ops
    DEFAULT FOR TYPE character USING bloom AS
      OPERATOR  1  =(character,character),
      FUNCTION  1  hashbpchar;
    CREATE OPERATOR CLASS

    demo=# CREATE OPERATOR CLASS interval_ops
    DEFAULT FOR TYPE interval USING bloom AS
      OPERATOR  1  =(interval,interval),
      FUNCTION  1  interval_hash;
    CREATE OPERATOR CLASS

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

    Пробуем снова:

    demo=# create index flights_bi_bloom on flights_bi
    using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name)
    with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7);
    CREATE INDEX

    Размер индекса составляет 526 МБ, что несколько больше рассчетного — из-за того, что в формуле мы не учитываем накладных расходов на служебную информацию в каждом блоке.

    demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom'));
     pg_size_pretty
    ----------------
     526 MB
    (1 row)

    Запросы


    Теперь мы можем выполнять поиск по самым разным критериям, и он будет поддержан индексом.

    Как мы говорили, фильтр Блума — вероятностная структура, поэтому эффективность в каждом конкретном случае может получиться разная. Например, посмотрим записи, относящиеся к двум пассажирам, Мирославу Сидорову:

    demo=# explain(costs off,analyze)
    select * from flights_bi where passenger_name='MIROSLAV SIDOROV';
                                                QUERY PLAN
    --------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1)
       Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
       Rows Removed by Index Recheck: 38562
       Heap Blocks: exact=21726
       ->  Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1)
             Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text)
     Planning time: 0.109 ms
     Execution time: 3010.736 ms

    и Марфе Соловьевой:

    demo=# explain(costs off,analyze)
    select * from flights_bi where passenger_name='MARFA SOLOVEVA';
                                                QUERY PLAN
    ---------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1)
       Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
       Rows Removed by Index Recheck: 3950168
       Heap Blocks: exact=45757 lossy=67332
       ->  Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1)
             Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text)
     Planning time: 0.157 ms
     Execution time: 10142.730 ms

    В одном случае фильтр допустил всего 40 тысяч ложных срабатываний, в другом — аж 4 миллиона. Соответственно отличается и время выполнения запросов.

    А вот результаты для поиска тех же самых строк, используя не имя, а номер документа. Мирослав:

    demo=# explain(costs off,analyze)
    demo-# select * from flights_bi where passenger_id='5864 006033';
                                               QUERY PLAN
    -------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1)
       Recheck Cond: ((passenger_id)::text = '5864 006033'::text)
       Rows Removed by Index Recheck: 9620258
       Heap Blocks: exact=50510 lossy=165722
       ->  Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1)
             Index Cond: ((passenger_id)::text = '5864 006033'::text)
     Planning time: 0.110 ms
     Execution time: 16907.423 ms

    И Марфа:

    demo=# explain(costs off,analyze)
    select * from flights_bi where passenger_id='2461 559238';
                                                QUERY PLAN
    --------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1)
       Recheck Cond: ((passenger_id)::text = '2461 559238'::text)
       Rows Removed by Index Recheck: 30669
       Heap Blocks: exact=27513
       ->  Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1)
             Index Cond: ((passenger_id)::text = '2461 559238'::text)
     Planning time: 0.120 ms
     Execution time: 3934.517 ms

    Эффективность снова сильно отличается, на этот раз больше повезло Марфе.

    Заметим, что поиск одновременно по двум полям будет выполняться значительно эффективнее, поскольку вероятность ложного срабатывания p превращается в p2:

    demo=# explain(costs off,analyze)
    select * from flights_bi
    where passenger_name='MIROSLAV SIDOROV'
      and passenger_id='5864 006033';
                                                         QUERY PLAN
    --------------------------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1)
       Recheck Cond: (((passenger_id)::text = '5864 006033'::text)
                   AND (passenger_name = 'MIROSLAV SIDOROV'::text))
       Rows Removed by Index Recheck: 357
       Heap Blocks: exact=356
       ->  Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1)
             Index Cond: (((passenger_id)::text = '5864 006033'::text)
                       AND (passenger_name = 'MIROSLAV SIDOROV'::text))
     Planning time: 0.524 ms
     Execution time: 877.967 ms

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

    Сравнение с BRIN и Hash


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

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

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

    Свойства


    По традиции посмотрим на свойства (запросы приводились ранее).

    Свойства метода:

     amname |     name      | pg_indexam_has_property
    --------+---------------+-------------------------
     bloom  | can_order     | f
     bloom  | can_unique    | f
     bloom  | can_multi_col | t
     bloom  | can_exclude   | f

    Очевидно, метод доступа позволяет строить индексы по нескольким столбцам — Блум-индекс по одному стоблцу вряд ли имеет смысл.

    Свойства индекса:

         name      | pg_index_has_property
    ---------------+-----------------------
     clusterable   | f
     index_scan    | f
     bitmap_scan   | t
     backward_scan | f

    Единственно возможный способ сканирования — по битовой карте. Поскольку индекс всегда сканируется целиком, нет смысла реализовывать обычный индексный доступ, при котором TID-ы возвращаются по одному.

            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

    Здесь все «прочерки», и даже с неопределенными значениями этот метод доступа работать не умеет.

    И напоследок


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

    Хочу выразить благодарность своим коллегам из Postgres Professional (некоторые из которых являются авторами многих рассмотренных методов доступа) за чтение черновиков и высказанные замечания. И, конечно же, я признателен вам за терпение и ценные комментарии. Ваше внимание дало мне силы дойти до этой точки. Спасибо!
    Postgres Professional 204,28
    Российский вендор PostgreSQL
    Поделиться публикацией
    Похожие публикации
    Комментарии 12
      0
      BITMAP индекс в оракле также устроен, правильно я понимаю?
        0
        Не-не, это совсем разные вещи.
        Грубо говоря, в bitmap-индексе для каждого уникального значения столбца строится своя битовая карта, в которой отмечено, в каких строках присутствует это значение. Когда ищем значение, читаем готовую битовую карту для него и сразу понимаем, какие табличные строки нам нужны. Особая прелесть в том, что битовые карты можно легко объединять по условиям and и or.
        Прямого аналога в Постгресе нет, но он зато умеет строить битовые карты на лету, используя данные любого индекса.
          0
          А, точно, понял.
        0
        Плохой индекс. Его нельзя использовать для аналитики, так как время работы непредсказуемо, а пользователя это сильно раздражает.

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

          а можно про это немного поподробней? а то, честно говоря, непонятно, что имеется в виду
            0
            Речь о том, что BRIN рассчитан на физически упорядоченные данные, поскольку делит таблицу на зоны, состоящие из последовательно расположенных страниц, и считает для них некоторую сводную статистику. В прошлой части это подробно рассматривалось.
              0
              а, всё, понял. спасибо!
            0
            1. Когда ждать inmemory?
            2. на видюхах…
              +1
              1. Есть шанс, что в PostgreSQL 12 сделают интерфейс для подключаемых хранилищ. Там появятся и расширения с разными хранилищами, среди которых будут и всякие in-memory. Поначалу, конечно, все это будет глючить и тормозить, но еще через несколько лет наверняка уже можно будет пользоваться… Как-то так.
              2. А что не так с виндой?
                0
                1. спасибо
                2. видеокарты, размещение в видеопамяти данных и обработка там.
                  0
                  А-а, видюхи. Тут я не в курсе новостей, ничего не скажу.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое