🥇PostgreSQL Antipatterns: let's hit a heavy JOIN with a dictionary

We continue our series of articles dedicated to exploring lesser-known ways to improve the performance of seemingly simple queries on PostgreSQL:

Don't think that I dislike JOIN that much… 🙂

But often, the query performs noticeably better without it. Therefore, today we'll try to completely get rid of the resource-intensive JOIN — using a dictionary.

PostgreSQL Antipatterns: hitting the dictionary with a heavy JOIN

Starting with PostgreSQL 12, some of the situations described below may behave slightly differently due to the non-materialization of CTE by default. This behavior can be reverted to the previous one by specifying the key MATERIALIZED.

Many "facts" about the limited dictionary

Let's take a realistic application task — we need to display a list of incoming messages or active tasks from senders:

25.01 | Ivanov I.I. | Prepare a description of the new algorithm.
22.01 | Ivanov I.I. | Write an article on Habr: life without JOIN.
20.01 | Petrov P.P. | Help optimize the query.
18.01 | Ivanov I.I. | Write an article on Habr: JOIN considering data distribution.
16.01 | Petrov P.P. | Help optimize the query.

In an abstract world, task authors would be evenly distributed among all employees of our organization, but in reality tasks usually come from a fairly limited number of people — "from the management" up the hierarchy or "from teammates" from neighboring departments (analysts, designers, marketing, …).

Let's assume that in our organization of 1000 people, only 20 authors (even less usually) assign tasks to each specific executor and we'll use this subject knowledge, to speed up the "traditional" query.

Script generator

-- employees
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);

-- tasks with specified distribution
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);

Let's show the last 100 tasks for a specific executor:

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;

PostgreSQL Antipatterns: hitting the dictionary with a heavy JOIN
[view on explain.tensor.ru]

This means that 1/3 of the total time and 3/4 of the reads data pages were created just to search for the author 100 times — for each task displayed. But we know that among this hundred there are only 20 different — can't we use this knowledge?

hstore dictionary

Let's use hstore type for generating a key-value "dictionary":

CREATE EXTENSION hstore

In the dictionary, we only need to put the author's ID and name, so that we can later extract by this key:

-- forming the target selection
WITH T AS (
  SELECT
    *
  FROM
    task
  WHERE
    owner_id = 777
  ORDER BY
    task_date DESC
  LIMIT 100
)
-- forming a dictionary for unique values
, 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
    ))
)
-- retrieving related values from the dictionary
SELECT
  *
, (TABLE dict) -> author_id::text -- hstore -> key
FROM
  T;

PostgreSQL Antipatterns: hitting the dictionary with a heavy JOIN
[view on explain.tensor.ru]

The information retrieval about persons took twice as less time and seven times less data was read! In addition to the "dictionarizing", these results were achieved also through mass data extraction from the table in a single pass using = ANY(ARRAY(...)).

Table records: serialization and deserialization

But what if we need to store not just one text field in the dictionary, but a whole record? In this case, PostgreSQL's ability to work with a table record as a single value will help us:

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

Let's analyze what happened here:

We took p as an alias for the full record of the person table and collected arrays from them.
This array of records has been cast into an array of text strings (person[]::text[]), to store it in an hstore dictionary as an array of values.
When retrieving a related record, we extracted it from the dictionary by key as a text string.
We need to convert the text into a table type value person (for each table, a corresponding type is automatically created).
We "expanded" the typed record into columns using (...).*.

json dictionary

However, the trick we applied above won't work if there is no corresponding table type to perform the "cast." A similar situation will arise if we try to use a CTE string instead of a "real" table.

In this case, we can use functions for working with json:

...
, p AS ( -- this is already a CTE
  SELECT
    *
  FROM
    person
  WHERE
    ...
)
, dict AS (
  SELECT
    json_object( -- now this is already json
      array_agg(id)::text[]
    , array_agg(row_to_json(p))::text[] -- and inside json for each row
    )
  FROM
    p
)
SELECT
  *
FROM
  T
, LATERAL(
    SELECT
      *
    FROM
      json_to_record(
        ((TABLE dict) -> author_id::text)::json -- extracted from the dictionary as json
      ) AS j(name text, birth_date date) -- filled the structure we need
  ) j;

It should be noted that when describing the target structure, we can list not all fields of the source row, but only those we actually need. If we have a "native" table, it's better to use the json_populate_record.

Accessing the dictionary still occurs only once, but the costs for json-[de]serialization are quite high,, so it is reasonable to use this method only in certain cases when a "proper" CTE Scan performs worse.

Testing performance

Thus, we have obtained two ways to serialize data into a dictionary — hstore / json_object. In addition, the arrays of keys and values can also be generated in two ways, with internal or external conversion to text: array_agg(i::text) / array_agg(i)::text[].

Let's check the efficiency of different types of serialization using a purely synthetic example — serializing a different number of keys:

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

Estimation script: serialization

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 Antipatterns: hitting the dictionary with a heavy JOIN

In PostgreSQL 11, approximately up to a dictionary size of 2^12 keys serialization to json takes less time. The most efficient combination is json_object and 'internal' type conversion array_agg(i::text).

Now let's try to read the value of each key 8 times — after all, if you don't access the dictionary, what's the point of having it?

Evaluation script: reading from the dictionary

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 < (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;

PostgreSQL Antipatterns: hitting the dictionary with a heavy JOIN

And... approximately already with 2^6 keys, reading from the json dictionary starts to lag behind reading from hstore, the same happens for jsonb at 2^9.

Final conclusions:

if you need to make a JOIN with repeatedly occurring records — it's better to use 'dictionary-izing' the table

if your dictionary is predictably small and you will be reading from it occasionally — you can use json[b]

in all other cases hstore + array_agg(i::text) will be more efficient

Source: habr.com