grains of gold in the registry

In most accounting systems, such as our VLSIsooner or later there will be a problem quick registry displaywhich, at the request of business users, contains several combinable filters with a very rare selection, which, well, do not fit into your beautiful database structure and indexes of the base registry table – something like “list of sales to customers whose birthday falls on February 29“.

There is no universal way to do “good” here, but I will talk about a request model that will allow you give the user a quick responsebut very efficient from a PostgreSQL point of view.

Traditionally, there are several basic approaches to working with registry navigation:

  • subtract everything in general (at the same time count the number of entries for the “correct” paging)

  • subtract a specific “page” using OFFSET

  • subtract a block of records “at the cursor”

I have already discussed the main pitfalls of each of these options and ways to bypass them in the articles “PostgreSQL Antipatterns: Registry Navigation” and “PostgreSQL 13: happy pagination WITH TIES”.

If everything is clear with the first two options, and there will not even be any “efficiency” there, then it is quite possible to work with the third.

Let’s take the following database structure as an example:

CREATE TABLE client(
  client_id
    serial
      PRIMARY KEY
, client_dt
    date
);

CREATE TABLE sale(
  sale_id
    serial
      PRIMARY KEY
, sale_dt
    date
, client_id
    integer
      REFERENCES client
        ON DELETE RESTRICT
);

It is clear that there is not enough index to support foreign key(client_id)and in real life you can sip grief without it, but for our task it is not required, and we will not create it.

But a unique index for navigation in reverse chronological order will definitely come in handy for us:

-- индекс для итераций по реестру
CREATE UNIQUE INDEX ON sale(sale_dt DESC, sale_id DESC);

Let’s fill our tables with test data:

INSERT INTO client(client_dt)
SELECT
	(now() - random() * '10 year'::interval)::date
FROM
	generate_series(1, 1e5); -- 100K клиентов

INSERT INTO sale(client_id, sale_dt)
SELECT
	(random() * (1e5 - 1))::integer + 1
,	(now() - random() * '10 year'::interval)::date
FROM
	generate_series(1, 1e6); -- 1M продаж за 10 лет

Thanks to the articles mentioned above, we know that reading a block of data at each next iteration will be very fast:

SELECT
  *
FROM
  sale
WHERE
  (sale_dt, sale_id) < ($1, $2) -- последние полученные на предыдущем шаге значения
ORDER BY
  sale_dt DESC, sale_id DESC
LIMIT 25;

Iteration on the client, filtering on the business logic

In many cases, trying to add filtering in iterative development will result in the beloved set forwarding pattern of many ORMs. id between base and business logic:

ids <- `SELECT id FROM ... LIMIT 25`
key <- last(ids)
res <- `SELECT * FROM ... WHERE id IN (${ids.join(',')}) AND <cond>`

Such a case is discussed in detail in the article “PostgreSQL Antipatterns: “too much gold””, and would be fixed quite trivially – by introducing a subquery with filtering into the main query, if it were not for the need to return the next segment for reading “unfiltered” key.

That is, the rendering of the registry in such a model looks something like this:

  1. the browser sends a request for a segment of up to 25 records to the BL (approximately this number fits on the first screen without scrolling) = ~30ms – depends on lags on the network from the client to our server

  2. BL out spends 10ms for reading a block of 25 document records, processing them and memorizing the “next key”

  3. BL spends more 10ms for an additional database check for 25 previously received identifiers

If the required document occurs with a frequency of 1:1000, then to fill the first screen with 25 entries, we will have to make 1000 iterations of 25 entries from the client, spending (30ms + 10ms + 10ms) x 1000 = 50 seconds.

It would seem that the solution is obvious – let’s query with BL segments not by 25, but by 100 or even 1000 records! But in this case, we run the risk of getting all these 1000 records (if the filter turned out to be not so rare) with the need to immediately draw in the interface – and it’s long!

Iteration and filtering on the database

The problem is clear – let’s try to “ground” all operations as close to the data as possible. To do this, we will use the techniques described in the articles “SQL HowTo: writing a while-loop directly in the query, or “Elementary three-way”” and “SQL HowTo: racing against time”.

In general, what we want:

  • each individual “client” iteration should be time limited – that is, do not last longer than the user is psychologically ready to wait until the first data appears, if any – say, 100ms

  • such an iteration should return not much more than the requested limit records (fit at least 2x)

  • we may want limit search depth a specific date – for example, to show a warning in the interface

Now let’s put together a suitable query.

Return “unfiltered” key

Obviously, since we need to do some iterations on the base, but in the SQL query this will turn into a recursive selection:

WITH RECURSIVE R AS (
  ... -- передаваемый с клиента JSON с ключом с предыдущей итерации
UNION ALL
  ... -- итерация по базе
)
( -- первая запись в resultset - ключ для следующей итерации
  ...
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  ...
);

The first entry in our resultset will be just the last entry of the “before filtering” block, and the rest will be the already filtered segment.

Assume the following structure for a recursive CTE:

  • i – iteration number

  • k – key entry to start iteration

  • a – array of filtered records

  • s – total number of records already found

Then part of the query above will turn into this:

WITH RECURSIVE R AS (
  SELECT
    -- номер итерации
    0 i
    -- запись для начала итерации
  , json_populate_record(
      -- таблица, по которой будем итерировать
      NULL::sale
      -- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
    , '{"sale_dt" : "infinity", "sale_id" : 0}'::json
    ) k
    -- массив отфильтрованных записей
  , '{}'::sale[] a
    -- общее количество уже найденных записей
  , 0 s
UNION ALL
  ...
)
( -- первая запись в resultset - ключ для следующей итерации
  SELECT
    (k).* -- разворачиваем поле-запись в отдельные столбцы
  FROM
    R
  ORDER BY
    i DESC -- ключ с последней итерации
  LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  SELECT
    (unnest(a)).* -- разворачиваем массивы записей, а затем - записи
  FROM
    R
);

To better understand what is happening, let’s look at the scheme of the query we are building:

How the request works
How the request works

It remains to implement the recursion step and its limitations.

Since we want to limit both the total number of already filtered records returned in one iteration, and request running timeboth of these conditions must be used together:

  WHERE
    -- limit time
    clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
    -- limit resultset
    R.s < 25 -- pageLimit

And, here it is, the most difficult to understand request block, in which the main “magic” occurs:

  SELECT
    -- увеличиваем счетчик итераций
    R.i + 1
    -- подставляем новый ключ
  , T.kn
    -- сохраняем блок отфильтрованных записей
  , T.a
    -- увеличиваем счетчик найденного
  , R.s + coalesce(array_length(T.a, 1), 0)
  FROM
    R
  , LATERAL (
      -- находим сегмент из pageLimit нефильтрованных записей
      WITH Ts AS (
        SELECT
          T
        FROM
          sale T
        WHERE
          (sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
        ORDER BY
          sale_dt DESC, sale_id DESC -- !!! должно соответствовать индексу
        LIMIT 25 -- pageLimit
      )
      SELECT
        (
          -- последняя запись сегмента - следующий ключ
          TABLE Ts OFFSET 24 -- pageLimit - 1
        ) kn
        -- сворачиваем в массив записей
      , ARRAY(
          SELECT
            T
          FROM
            Ts
          WHERE
            -- прикладной фильтр по сегменту документов сразу
            (T).client_id = ANY(ARRAY(
              SELECT
                client_id
              FROM
                client
              WHERE
                client_id = ANY(ARRAY( -- свертка идентификаторов
                  SELECT
                    (T).client_id
                  FROM
                    Ts
                )) AND
                client_dt::text ~ '-02-29$' -- условие фильтрации
            ))
        ) a
    ) T
Full text of the request
WITH RECURSIVE R AS (
  SELECT
    -- номер итерации
    0 i
    -- запись для начала итерации
  , json_populate_record(
      -- таблица, по которой будем итерировать
      NULL::sale
      -- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
    , '{"sale_dt" : "infinity", "sale_id" : 0}'::json
    ) k
    -- массив отфильтрованных записей
  , '{}'::sale[] a
    -- общее количество уже найденных записей
  , 0 s
UNION ALL
  SELECT
    -- увеличиваем счетчик итераций
    R.i + 1
    -- подставляем новый ключ
  , T.kn
    -- сохраняем блок отфильтрованных записей
  , T.a
    -- увеличиваем счетчик найденного
  , R.s + coalesce(array_length(T.a, 1), 0)
  FROM
    R
  , LATERAL (
      -- находим сегмент из pageLimit нефильтрованных записей
      WITH Ts AS (
        SELECT
          T
        FROM
          sale T
        WHERE
          (sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
        ORDER BY
          sale_dt DESC, sale_id DESC -- !!!
        LIMIT 25 -- pageLimit
      )
      SELECT
        (
          -- последняя запись сегмента - следующий ключ
          TABLE Ts OFFSET 24 -- pageLimit - 1
        ) kn
        -- сворачиваем в массив записей
      , ARRAY(
          SELECT
            T
          FROM
            Ts
          WHERE
            -- прикладной фильтр по сегменту документов сразу
            (T).client_id = ANY(ARRAY(
              SELECT
                client_id
              FROM
                client
              WHERE
                client_id = ANY(ARRAY( -- свертка идентификаторов
                  SELECT
                    (T).client_id
                  FROM
                    Ts
                )) AND
                client_dt::text ~ '-02-29$' -- условие фильтрации
            ))
        ) a
    ) T
  WHERE
    -- limit time
    clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
    -- limit resultset
    R.s < 25 -- pageLimit
)
( -- первая запись в resultset - ключ для следующей итерации
  SELECT
    (k).* -- разворачиваем поле-запись в отдельные столбцы
  FROM
    R
  ORDER BY
    i DESC -- ключ с последней итерации
  LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  SELECT
    (unnest(a)).* -- разворачиваем массивы записей, а затем - записи
  FROM
    R
);

Let’s check plan of our request for the starting iteration on our test data:

Plan of our request
Plan of our request

As we can see, it worked timeout cutoff for 100ms, after which the client will receive the already filtered 10 found records. To do this “inside” PostgreSQL had to commit 637 iterations proofreading-filtering 25 records. If we return to the initial estimate that each iteration from the client lasts about 50ms, then 637 – about 30 seconds!

So we can assume that we have just sped up 300 times!

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *