29.03.2022 10:50
Kilor 7 2700 Источник

Соблазн использовать модель EAV (Entity-Attribute-Value) при организации структуры БД весьма велик, особенно когда предметная область заранее плохо известна (или разработчик просто не хочет в нее углубляться). Это ведь так удобно - создать "универсальный" способ описания характеристик объектов, который больше не потребует доработок базы ни при появлении новых типов объектов, ни при возникновении новых атрибутов...

Однако, за любую универсальность приходится платить сложностью и производительностью запросов - так что json[b] может оказаться более эффективной заменой. Но если уж такая модификация невозможна - давайте попробуем выжать максимум производительности из доставшегося нам legacy на самом простом примере.

Ограничимся работой с единственной таблицей значений:

CREATE TABLE tst_eav AS
SELECT
  (random() * 1e4)::integer e -- 10k объектов
, (random() * 1e2)::integer a -- 100 характеристик
, (random() * 1e2)::integer v -- 100 вариантов значений
FROM
  generate_series(1, 1e6);    -- 1M записей о значениях

Попробуем найти такие объекты e, для которых одновременно существуют записи с (a, v) = (1, 1) и (a, v) = (2, 2) - это типичный вариант множественного фильтра в любом интернет-магазине: "смартфоны с экраном 6" и памятью 64GB".

JOIN

Самым первым вариантом решения, пришедшим в голову разработчика уровня "я уже освоил SQL!", наверняка, будет соединение:

SELECT
  e
FROM
  tst_eav r1
JOIN
  tst_eav r2
    USING(e)
WHERE
  (r1.a, r1.v) = (1, 1) AND
  (r2.a, r2.v) = (2, 2);

Очевидно, для этого нам понадобится, как минимум, индекс по (a, v):

CREATE INDEX eav_idx1 ON tst_eav(a, v);

Посмотрим, что у нас получится в плане:

JOIN'им два набора строк
JOIN'им два набора строк

Сначала отбор по одной паре значений и сортировка по e, потом - по второй паре и сортировка, а потом уже - слияние двух отсортированных наборов.

Этот вариант станет для нас отправной точкой: 432мкс + 207 buffers.

Неплохо для отбора из миллиона записей, но можно лучше!

INTERSECT

Ведь в предыдущем запросе мы искали вовсе не соединение, а пересечение множеств - так давайте его и попробуем использовать:

  SELECT
    e
  FROM
    tst_eav
  WHERE
    (a, v) = (1, 1)
INTERSECT
  SELECT
    e
  FROM
    tst_eav
  WHERE
    (a, v) = (2, 2);
INTERSECT'им наборы
INTERSECT'им наборы

А в плане теперь все получше - читаем ровно столько же, зато не пришлось тратить время на две сортировки: 301мск + 207 buffers.

GROUP BY

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

SELECT
  e
FROM
  tst_eav
WHERE
  (a, v) IN ((1, 1), (2, 2))
GROUP BY
  e
HAVING
  count(*) = 2; -- присутствуют оба условия
GROUP BY сразу пары условий
GROUP BY сразу пары условий

Сэкономили "копеечку": 296мкс + 202 buffers.

Конечно, тут мы пошли на допущение, что каждая пара (a, v) внутри одного объекта заведомо уникальна. Потому что если это не так, запрос станет существенно сложнее:

SELECT
  e
FROM
  tst_eav T
WHERE
  (a, v) IN ((1, 1), (2, 2))
GROUP BY
  e
HAVING
  array_length(array_agg(DISTINCT T), 1) = 2; -- оба уникальных условия

INCLUDE

Но всегда терзает мысль - может быть, можно сделать запрос еще быстрее?.. Оказывается, в нашем случае - можно!

Заметим, что львиная доля времени уходит на Bitmap Heap Scan - то есть вычитку страниц таблицы ради получения значения e, ведь его нет в нашем индексе, иначе мы могли бы обойтись Index Only Scan.

Но ведь еще с PostgreSQL 11 есть способ добавить неключевые поля в индекс:

CREATE INDEX eav_idx2 ON tst_eav(a, v) INCLUDE(e);
INCLUDE избавляет от Bitmap Heap Scan
INCLUDE избавляет от Bitmap Heap Scan

И вот теперь наш план для INTERSECT-варианта: 121мкс + 9 buffers.

А ведь чем меньше страниц данных (buffers) читается, тем меньше шансов сходить за ними на диск и потерять в скорости.

Напоминаю, что анализировать планы запросов и бороться за их производительность удобнее всего с помощью визуализаций на explain.tensor.ru.

Комментарии (7)


  1. Akina
    29.03.2022 12:16
    #24212545
    +1

    Странно, что не рассмотрен вариант включения третьего поля в индекс. Не поленился, воспроизвёл. Результаты:

                    no index    (a,v)       (a,v),e     (a,v,e)
JOIN            391/491     3,65/29     0,710/192   0,550/192
INTERSECT       328/712     0,387/196   0,534/197   0,367/197
COUNT           217/548     0,425/194   0,619/195   0,400/195
COUNT DISTINCT  217/522     0,724/194   0,989/195   0,704/195

    https://dbfiddle.uk/?rdbms=postgres_12&fiddle=581825050ffad372d4618183569b73c4

    Как можно увидеть, включение третьего поля в индексное выражение улучшает производительность всех запросов приблизительно в полтора раза.

    PS. Никогда раньше не обращал внимания, что PostgreSQL не умеет тривиального COUNT(DISTINCT a,b)...


    1. Kilor Автор
      29.03.2022 12:26
      #24212601

      На моей выборке индекс (a, v, e) дает 131/10 против 121/9 у INCLUDE-версии:

      HashSetOp Intersect (actual time=0.130..0.131 rows=1 loops=1)
  Buffers: shared hit=10
  ->  Append (actual time=0.023..0.101 rows=202 loops=1)
        Buffers: shared hit=10
        ->  Subquery Scan on "*SELECT* 1" (actual time=0.022..0.053 rows=98 loops=1)
              Buffers: shared hit=5
              ->  Index Only Scan using eav_idx3 on tst_eav (actual time=0.020..0.039 rows=98 loops=1)
                    Index Cond: ((a = 1) AND (v = 1))
                    Heap Fetches: 0
                    Buffers: shared hit=5
        ->  Subquery Scan on "*SELECT* 2" (actual time=0.010..0.034 rows=104 loops=1)
              Buffers: shared hit=5
              ->  Index Only Scan using eav_idx3 on tst_eav tst_eav_1 (actual time=0.010..0.023 rows=104 loops=1)
                    Index Cond: ((a = 2) AND (v = 2))
                    Heap Fetches: 0
                    Buffers: shared hit=5

      А в вашем варианте INTERSECT + INCLUDE не дали Index Only Scan, а остались на Bitmap Heap Scan - потому и выигрыша не получилось.


      1. Akina
        29.03.2022 12:41
        #24212719

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

        Есть у постгресса хинты, позволяющие ему сказать, что он должен использовать именно Index Only Scan?


        1. Kilor Автор
          29.03.2022 12:53
          #24212773
          +2

          Есть у постгресса хинты, позволяющие ему сказать, что он должен использовать именно Index Only Scan?

          https://postgrespro.ru/docs/postgresql/14/runtime-config-query#RUNTIME-CONFIG-QUERY-CONSTANTS

          cpu_index_tuple_cost - можно укрутить "в ноль", например

          получается, что вся эта оптимизация не более чем игра в рулетку - повезёт или нет

          Не совсем так.

          В варианте отсутствия e в индексе мы гарантированно не можем получить Index Only Scan - данных просто нет. Будет или Bitmap Heap Scan, или Index Scan (с дочитыванием heap), если очень повезет, и данных окажется относительно немного.

          Если e будет ключевым полем, а не в INCLUDE - вероятность получить Index Only Scan становится ниже.

          Но вполне очевидно, что если у нас значению ключа будет соответствовать 100K записей из миллиона, то Bitmap Heap Scan все равно окажется статистически много выгоднее. А если 900K - то даже Seq Scan станет наиболее оптимальным вариантом.

          Поэтому варианта "гарантированно" получить IOS нету, да он и не нужен, поскольку не является оптимальным "вообще всегда". Но мы можем постараться увеличить его вероятность приведенными способами.


          1. mixsture
            29.03.2022 23:18
            #24215357

            postgrespro.ru/docs/postgresql/14/runtime-config-query#RUNTIME-CONFIG-QUERY-CONSTANTS

            cpu_index_tuple_cost — можно укрутить «в ноль», например


            думаю, речь о том, как в ms sql работает конструкция with index в запросе. Что отключает планировщик и принуждает использовать для таблицы именно этот индекс.


            1. Kilor Автор
              29.03.2022 23:32
              #24215389

              Не самый распространенный модуль, но все же: https://postgrespro.ru/docs/enterprise/13/pg-hint-plan


    1. Miha_S7
      30.03.2022 09:10
      #24216027

      Никогда раньше не обращал внимания, что PostgreSQL не умеет тривиального COUNT(DISTINCT a,b)

      Почему не умеет? А вот так:

       count(distinct (a, b))

      Или это не то, что вы имели в виду?