PostgreSQL Antipatterns: ударим словарем по тяжелому JOIN

    Продолжаем серию статей, посвященных исследованию малоизвестных способов улучшения производительности «вроде бы простых» запросов на PostgreSQL:


    Не подумайте, что я так сильно не люблю JOIN… :)

    Но зачастую без него запрос получается ощутимо производительнее, чем с ним. Поэтому сегодня попробуем вообще избавиться от ресурсоемкого JOIN — с помощью словаря.



    Начиная с PostgreSQL 12 часть описанных ниже ситуаций может воспроизводиться чуть иначе из-за не-материализации CTE по умолчанию. Это поведение может быть возвращено к прежнему с помощью указания ключа MATERIALIZED.

    Много «фактов» по ограниченному словарю


    Давайте возьмем вполне реальную прикладную задачу — надо вывести список входящих сообщений или активных задач с отправителями:

    25.01 | Иванов И.И. | Подготовить описание нового алгоритма.
    22.01 | Иванов И.И. | Написать статью на Хабр: жизнь без JOIN.
    20.01 | Петров П.П. | Помочь оптимизировать запрос.
    18.01 | Иванов И.И. | Написать статью на Хабр: JOIN с учетом распределения данных.
    16.01 | Петров П.П. | Помочь оптимизировать запрос.
    

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

    Давайте примем, что в нашей организации из 1000 человек только 20 авторов (обычно даже меньше) ставят задачи в адрес каждого конкретного исполнителя и воспользуемся этим предметным знанием, чтобы ускорить «традиционный» запрос.

    Скрипт-генератор
    -- сотрудники
    CREATE TABLE person AS
    SELECT
      id
    , repeat(chr(ascii('a') + (id % 26)), (id % 32) + 1) "name"
    , '2000-01-01'::date - (random() * 1e4)::integer birth_date
    FROM
      generate_series(1, 1000) id;
    
    ALTER TABLE person ADD PRIMARY KEY(id);
    
    -- задачи с указанным распределением
    CREATE TABLE task AS
    WITH aid AS (
      SELECT
        id
      , array_agg((random() * 999)::integer + 1) aids
      FROM
        generate_series(1, 1000) id
      , generate_series(1, 20)
      GROUP BY
        1
    )
    SELECT
      *
    FROM
      (
        SELECT
          id
        , '2020-01-01'::date - (random() * 1e3)::integer task_date
        , (random() * 999)::integer + 1 owner_id
        FROM
          generate_series(1, 100000) id
      ) T
    , LATERAL(
        SELECT
          aids[(random() * (array_length(aids, 1) - 1))::integer + 1] author_id
        FROM
          aid
        WHERE
          id = T.owner_id
        LIMIT 1
      ) a;
    
    ALTER TABLE task ADD PRIMARY KEY(id);
    CREATE INDEX ON task(owner_id, task_date);
    CREATE INDEX ON task(author_id);
    

    Покажем последние 100 задач для конкретного исполнителя:

    SELECT
      task.*
    , person.name
    FROM
      task
    LEFT JOIN
      person
        ON person.id = task.author_id
    WHERE
      owner_id = 777
    ORDER BY
      task_date DESC
    LIMIT 100;


    [посмотреть на explain.tensor.ru]

    Получается, что 1/3 всего времени и 3/4 чтений страниц данных были сделаны только для того, чтобы 100 раз поискать автора — для каждой выводимой задачи. Но мы же знаем, что среди этой сотни всего 20 разных — нельзя ли использовать это знание?

    hstore-словарь


    Воспользуемся типом hstore для генерации «словаря» ключ-значение:

    CREATE EXTENSION hstore

    В словарь нам достаточно поместить ID автора и его имя, чтобы потом иметь возможность извлечь по этому ключу:

    -- формируем целевую выборку
    WITH T AS (
      SELECT
        *
      FROM
        task
      WHERE
        owner_id = 777
      ORDER BY
        task_date DESC
      LIMIT 100
    )
    -- формируем словарь для уникальных значений
    , dict AS (
      SELECT
        hstore( -- hstore(keys::text[], values::text[])
          array_agg(id)::text[]
        , array_agg(name)::text[]
        )
      FROM
        person
      WHERE
        id = ANY(ARRAY(
          SELECT DISTINCT
            author_id
          FROM
            T
        ))
    )
    -- получаем связанные значения словаря
    SELECT
      *
    , (TABLE dict) -> author_id::text -- hstore -> key
    FROM
      T;


    [посмотреть на explain.tensor.ru]

    На получение информации о персонах затрачено в 2 раза меньше времени и в 7 раз меньше прочитано данных! Помимо «ословаривания», этих результатов нам помогло достичь еще и массовое извлечение записей из таблицы за единственный проход с помощью = ANY(ARRAY(...)).

    Записи таблицы: сериализация и десериализация


    Но что делать, если нам нужно сохранить в словаре не одно текстовое поле, а целую запись? В этом случае нам поможет способность PostgreSQL работать с записью таблицы как с единым значением:

    ...
    , dict AS (
      SELECT
        hstore(
          array_agg(id)::text[]
        , array_agg(p)::text[] -- магия #1
        )
      FROM
        person p
      WHERE
        ...
    )
    SELECT
      *
    , (((TABLE dict) -> author_id::text)::person).* -- магия #2
    FROM
      T;

    Давайте разберем, что тут вообще происходило:

    1. Мы взяли p как алиас к полной записи таблицы person и собрали из них массив.
    2. Этот массив записей перекастовали в массив текстовых строк (person[]::text[]), чтобы поместить его в hstore-словарь в качестве массива значений.
    3. При получении связанной записи мы ее вытащили из словаря по ключу как текстовую строку.
    4. Текст нам нужно превратить в значение типа таблицы person (для каждой таблицы автоматически создается одноименный ей тип).
    5. «Развернули» типизованную запись в столбцы с помощью (...).*.

    json-словарь


    Но такой фокус, как мы применили выше, не пройдет, если нет соответствующего табличного типа, чтобы сделать «раскастовку». Ровно такая же ситуация возникнет, и если в качестве источника данных для сериализации мы попробуем использовать строку CTE, а не «реальной» таблицы.

    В этом случае нам помогут функции для работы с json:

    ...
    , p AS ( -- это уже CTE
      SELECT
        *
      FROM
        person
      WHERE
        ...
    )
    , dict AS (
      SELECT
        json_object( -- теперь это уже json
          array_agg(id)::text[]
        , array_agg(row_to_json(p))::text[] -- и внутри json для каждой строки
        )
      FROM
        p
    )
    SELECT
      *
    FROM
      T
    , LATERAL(
        SELECT
          *
        FROM
          json_to_record(
            ((TABLE dict) ->> author_id::text)::json -- извлекли из словаря как json
          ) AS j(name text, birth_date date) -- заполнили нужную нам структуру
      ) j;

    Надо отметить, что при описании целевой структуры мы можем перечислять не все поля исходной строки, а только те, которые нам действительно нужны. Если же у нас есть «родная» таблица, то лучше воспользоваться функцией json_populate_record.

    Доступ к словарю у нас происходит по-прежнему однократно, но издержки на json-[де]сериализацию достаточно велики, поэтому таким способом разумно пользоваться только в некоторых случаях, когда «честный» CTE Scan показывает себя хуже.

    Тестируем производительность


    Итак, мы получили два способа сериализации данных в словарь — hstore / json_object. Помимо этого, сами массивы ключей и значений можно породить тоже двумя способами, с внутренним или внешним преобразованием к тексту: array_agg(i::text) / array_agg(i)::text[].

    Проверим эффективность разных видов сериализации на сугубо синтетическом примере — сериализуем разное количество ключей:

    WITH dict AS (
      SELECT
        hstore(
          array_agg(i::text)
        , array_agg(i::text)
        )
      FROM
        generate_series(1, ...) i
    )
    TABLE dict;

    Оценочный скрипт : сериализация
    WITH T AS (
      SELECT
        *
      , (
          SELECT
            regexp_replace(ea[array_length(ea, 1)], '^Execution Time: (\d+\.\d+) ms$', '\1')::real et
          FROM
            (
              SELECT
                array_agg(el) ea
              FROM
                dblink('port= ' || current_setting('port') || ' dbname=' || current_database(), $$
                  explain analyze
                  WITH dict AS (
                    SELECT
                      hstore(
                        array_agg(i::text)
                      , array_agg(i::text)
                      )
                    FROM
                      generate_series(1, $$ || (1 << v) || $$) i
                  )
                  TABLE dict
                $$) T(el text)
            ) T
        ) et
      FROM
        generate_series(0, 19) v
      ,   LATERAL generate_series(1, 7) i
      ORDER BY
        1, 2
    )
    SELECT
      v
    , avg(et)::numeric(32,3)
    FROM
      T
    GROUP BY
      1
    ORDER BY
      1;



    На PostgreSQL 11 примерно до размера словаря в 2^12 ключей сериализация в json требует меньше времени. При этом наиболее эффективной является комбинация json_object и «внутреннего» преобразования типов array_agg(i::text).

    Теперь давайте попробуем прочитать значение каждого ключа по 8 раз — ведь если к словарю не обращаться, то зачем он нужен?

    Оценочный скрипт : чтение из словаря
    WITH T AS (
      SELECT
        *
      , (
          SELECT
            regexp_replace(ea[array_length(ea, 1)], '^Execution Time: (\d+\.\d+) ms$', '\1')::real et
          FROM
            (
              SELECT
                array_agg(el) ea
              FROM
                dblink('port= ' || current_setting('port') || ' dbname=' || current_database(), $$
                  explain analyze
                  WITH dict AS (
                    SELECT
                      json_object(
                        array_agg(i::text)
                      , array_agg(i::text)
                      )
                    FROM
                      generate_series(1, $$ || (1 << v) || $$) i
                  )
                  SELECT
                    (TABLE dict) -> (i % ($$ || (1 << v) || $$) + 1)::text
                  FROM
                    generate_series(1, $$ || (1 << (v + 3)) || $$) i
                $$) T(el text)
            ) T
        ) et
      FROM
        generate_series(0, 19) v
      , LATERAL generate_series(1, 7) i
      ORDER BY
        1, 2
    )
    SELECT
      v
    , avg(et)::numeric(32,3)
    FROM
      T
    GROUP BY
      1
    ORDER BY
      1;



    И… уже примерно при 2^6 ключей чтение из json-словаря начинает кратно проигрывать чтению из hstore, для jsonb то же самое происходит при 2^9.
    Итоговые выводы:

    • если надо сделать JOIN с многократно повторяющимися записями — лучше использовать «ословаривание» таблицы
    • если ваш словарь ожидаемо маленький и читать вы из него будете немного — можно использовать json[b]
    • во всех остальных случаях hstore + array_agg(i::text) будет эффективнее
    Тензор
    Разработчик системы СБИС

    Похожие публикации

    Комментарии 14

      0
      А почему индексированный hstore сравнивается с текстовым json, а не с jsonb? У вас до сих пор PostgreSQL <= 9.4?
        0
        Он, скорее, не «индексированный», а «более упакованный». Добавил в итоговый график.
          0

          На сколько я помню, табличка с json-ами занимает чуть меньше чем табличка с jsonb (в частных случаях может быть наоборот), но при этом с jsonb больше возможностей и он работает быстрее.


          В целом, для большинства применений jsonb выглядит выигрышнее hstore: асимптотика похожая, но для jsonb не нужны расширения, да и возможностей без конвертации в строку больше.

            0
            У hstore есть небольшое преимущество — встроенная реализация akeys(). Ее можно эмулировать через ARRAY(json_each), но это менее удобно. Зато у json — json_to_recordset / json_populate_recordset.
            Но иерархические структуры необходимы достаточно редко (кроме случая JSON уже на входе, конечно), так что в целом — паритет.
              0

              Гм… Не использую hstore, но судя по описанию, аналог для jsonb — jsonb_object_keys

                0
                Почти. json_object_keys возвращает setof text, как skeys. А akeys возвращает сразу массив ключей.
        0
        Это, конечно, увлекательное упражнение. Но первая мысль, которая приходит в голову — зачем Nested Loop, почему бы не прочитать person целиком и не соединить хешированием? Тогда вместо накрутки буферов из-за индексного сканирования получим константу.
        Решил я воспроизвести пример (на 12) и только собрался отключить индексное сканирование, как таблицы проанализировались и планировщик сам догадался до такого решения:

        habr=# EXPLAIN (analyze, costs off, timing off, buffers)
        SELECT
          task.*
        , person.name
        FROM
          task
        LEFT JOIN
          person
            ON person.id = task.author_id
        WHERE
          owner_id = 777
        ORDER BY
          task_date DESC
        LIMIT 100;
        
                                                     QUERY PLAN                                             
        ----------------------------------------------------------------------------------------------------
         Limit (actual rows=100 loops=1)
           Buffers: shared hit=116
           ->  Sort (actual rows=100 loops=1)
                 Sort Key: task.task_date DESC
                 Sort Method: quicksort  Memory: 34kB
                 Buffers: shared hit=116
                 ->  Hash Left Join (actual rows=116 loops=1)
                       Hash Cond: (task.author_id = person.id)
                       Buffers: shared hit=116
                       ->  Bitmap Heap Scan on task (actual rows=116 loops=1)
                             Recheck Cond: (owner_id = 777)
                             Heap Blocks: exact=107
                             Buffers: shared hit=109
                             ->  Bitmap Index Scan on task_owner_id_task_date_idx (actual rows=116 loops=1)
                                   Index Cond: (owner_id = 777)
                                   Buffers: shared hit=2
                       ->  Hash (actual rows=1000 loops=1)
                             Buckets: 1024  Batches: 1  Memory Usage: 62kB
                             Buffers: shared hit=7
                             ->  Seq Scan on person (actual rows=1000 loops=1)
                                   Buffers: shared hit=7
        

        То есть без всяких костылей мы читаем 116 страниц вместо 142 в решении с hstore.
        Ммм?
          0
          На v12 планировщик еще немного поумнел, потому в начале статьи я и оставил дисклаймер. :)
          Замечание вполне справедливо, но достаточно person расширить до 10k, 100k,… — и в какой-то момент Seq Scan заведомо проиграет. Я же рассматриваю ситуацию именно джойна с узким срезом из словаря. А таким срезом бывает и несколько активных контрагентов из миллионной выборки.

          Заменим task на email, person на counteragent, умножим размеры таблиц в 100 раз — и…
            +2
            На v12 планировщик еще немного поумнел

            У меня нет под рукой 11, но 10-ка выдает точно такой же план после ANALYZE. Так что тестовые данные так себе.

            но достаточно person расширить до 10k, 100k,…

            Ну хорошо, допустим, что на больших таблицах эффект будет иметь место. Но я не понимаю, зачем все эти приплясывания вокруг hstore/json, если можно сделать просто

            WITH T AS (
              SELECT *
              FROM task
              WHERE owner_id = 777
              ORDER BY task_date DESC
              LIMIT 100
            )
            , dict AS (
              SELECT *
              FROM person
              WHERE id IN (
                  SELECT author_id FROM T -- DISTINCT тут не нужен
                )
            )
            SELECT *
            FROM T LEFT JOIN dict ON T.author_id = dict.id;
            

            и получить то же самое, а скорее всего и лучше?
              0
              Ровно пара проблем:
              1. Если IN внезапно развернется в Join, то и DISTINCT будет иметь значение. Поэтому = ANY(ARRAY(DISTINCT)) дает более стабильный результат.
              2. CTE join CTE если развернется во что-то похожее на Nested Loop — будут тормоза.
                +1
                1. Ну может, но DISTINCT там все равно не нужен, потому что =ANY сам по себе не пропустит дубликаты. А в варианте с DISTINCT вы на ровном месте получили лишний HashAggregate в плане.
                2. В отсутствие индексов (CTE ведь у нас) у Nested Loop нет никаких шансов. Hash Join будет гарантированно, что нам и надо.

                Если других проблем нет, то делаю вывод: не надо тут hstore/json использовать (:
                  0
                  1. Давайте воспроизведу:
                  CREATE TABLE tbl(a integer PRIMARY KEY);
                  INSERT INTO tbl
                  SELECT generate_series(1, 100000);
                  ANALYZE tbl;

                  1.1. выбор по массиву из 2 разных элементов (всего 2)
                  explain (analyze)
                  SELECT
                    *
                  FROM
                    tbl
                  WHERE
                    a = ANY(ARRAY(
                      SELECT 1
                    UNION ALL
                      SELECT 2
                    ));

                  сам Index Only Scan = 0.028ms
                  https://explain.tensor.ru/archive/explain/1d3bbda6cd190d55307661517a579e77:0:2020-01-29

                  1.2. выбор по массиву из 2 разных элементов (всего 2000)
                  explain (analyze)
                  SELECT
                    *
                  FROM
                    tbl
                  WHERE
                    a = ANY(ARRAY(
                      SELECT 1 FROM generate_series(1, 1000)
                    UNION ALL
                      SELECT 2 FROM generate_series(1, 1000)
                    ));

                  сам Index Only Scan = 0.202ms
                  https://explain.tensor.ru/archive/explain/47953182a2ae3cd7f5d7be96fc1f8072:0:2020-01-29

                  Понятно, что HashAggregate тоже сколько-то «скушает», но и скармливать много дублей в массиве ключей — небесплатно.

                  1.3. то же через IN
                  explain (analyze)
                  SELECT
                    *
                  FROM
                    tbl
                  WHERE
                    a IN (
                      SELECT 1 FROM generate_series(1, 1000)
                    UNION ALL
                      SELECT 2 FROM generate_series(1, 1000)
                    );

                  HashAggregate на месте, но мы проиграли еще 300ms суммарно к предущему результату
                  https://explain.tensor.ru/archive/explain/3779beff9df45843f8dce9d5fe40cab7:0:2020-01-29

                  2. Вот кусок из реального плана нашел — таки иногда Nested Loop между CTE все-таки бывает, и тогда бывает больно:
                    0
                    Понятно, что HashAggregate тоже сколько-то «скушает», но и скармливать много дублей в массиве ключей — небесплатно.

                    Понятное дело небесплатно. Но что с чем вы сравниваете? В 1.3 же совсем другой план получился. Давайте сравнивать 1.2 с таким же запросом, только заменим UNION ALL на UNION.
                    Я увеличил в примере все числа в 10 раз, чтобы цифры были заметнее, и вот что получил в среднем:


                    • UNION ALL — 28.8 мс,
                    • UNION — 35.3 мс.

                    Без DISTINCT все-таки лучше.

                      0
                      Согласен, в среднем HashAggregate стоит дороже выигрыша от передачи меньшего массива.
                      У меня получилось примерно так:

                      • UNION ALL — 72.134ms
                      • UNION — 84.905ms

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

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