PostgreSQL Antipatterns: Navigation through the Registry

Today there will be no complex cases or intricate SQL algorithms. Everything will be very simple, at the level of Captain Obvious — we just do it. viewing the event registry sorted by time.

So there is a table in the database events, and it has a field ts — exactly that time, by which we want to display these records in an ordered manner:

CREATE TABLE events(
  id
    serial
      PRIMARY KEY
, ts
    timestamp
, data
    json
);

CREATE INDEX ON events(ts DESC);

It's clear that there won't just be a few entries, so we will need some form of pagination.

#0. «Я у мамы погроммист»

cur.execute("SELECT * FROM events;")
rows = cur.fetchall();
rows.sort(key=lambda row: row.ts, reverse=True);
limit = 26
print(rows[offset:offset+limit]);

It's almost not a joke — it rarely happens, but it does occur in the wild. Sometimes after working with ORM, it can be difficult to switch back to 'direct' SQL work.

But let's move on to more common and less obvious issues.

#1. OFFSET

SELECT
  ...
FROM
  events
ORDER BY
  ts DESC
LIMIT 26 OFFSET $1; -- 26 - records per page, $1 - start of the page

Where does the number 26 come from? This is the approximate number of records to fill one screen. More precisely, 25 displayed records, plus 1, signaling that there is something further in the selection and it makes sense to move on.

Of course, this value can be passed as a parameter instead of being 'baked' into the query. But in this case, the PostgreSQL planner will not be able to rely on the knowledge that there should be relatively few records — and can easily choose an inefficient plan.

And while in the application's interface the viewing of the registry is implemented as switching between visual 'pages', no one notices anything suspicious for a long time. Exactly until the moment when, in the struggle for UI/UX convenience, it is decided to redo the interface to 'infinite scroll' — that is, all registry entries are drawn in a single list that the user can scroll up and down.

And then, during another test, you get caught duplicating records in the registry. Why, if there is a normal index on the table (ts), on which your query relies?

Precisely because you didn't consider that ts is not a unique key in this table. In fact, the values are not unique., like any "time" in real conditions — therefore, the same entry in two adjacent queries can easily "jump" from page to page due to a different final order within the sorting of the same key value.

In fact, there is a second problem hidden here, which is much harder to notice — some entries will not be shown at all! After all, the "duplicate" entries have taken someone else's place. A detailed explanation with nice pictures can be read here.

Extending the index

A clever developer understands — it’s necessary to make the index key unique, and the simplest way is to extend it with a deliberately unique field, for which PK works great:

CREATE UNIQUE INDEX ON events(ts DESC, id DESC);

And the query mutates:

SELECT
  ...
ORDER BY
  ts DESC, id DESC
LIMIT 26 OFFSET $1;

#2. Переход на «курсоры»

Some time later, a DBA comes to you and "delights" you by saying that your queries are wreaking havoc on the server with their enormous OFFSETs, and in general, it’s time to switch to navigation from the last shown value. Your query mutates again:

SELECT
  ...
WHERE
  (ts, id) < ($1, $2) -- the last values obtained in the previous step
ORDER BY
  ts DESC, id DESC
LIMIT 26;

You sighed with relief until…

#3. Чистка индексов

Because once your DBA read an article about finding inefficient indexes and understood that a "non-latest" timestamp is not good. And he came to you again — now with the thought that that index should indeed revert back to (ts DESC).

But what to do about the original "jumping" problem between pages?.. It's simple — you need to select blocks with an unfixed number of records!

Who actually forbids us from reading not "exactly 26", but "at least 26"? For example, in such a way that the next block contains entries with distinctly different values ts — then there will be no problems with "jumping" entries between blocks!

Here’s how to achieve this:

SELECT
  ...
WHERE
  ts = coalesce((
    SELECT
      ts
    FROM
      events
    WHERE
      ts < $1
    ORDER BY
      ts DESC
    LIMIT 1 OFFSET 25
  ), '-infinity')
ORDER BY
  ts DESC;

What is actually happening here?

1. We step down 25 entries and get the "boundary" value ts.
2. If there is nothing there, we replace the NULL value with -infinity.
3. We subtract the entire segment of values between the obtained value ts and the passed interface parameter $1 (the previous "last" rendered value).
4. If the block returned has fewer than 26 entries, it is the last one.

Or the same as an image:

Since we now have the sample does not have a specific 'start', there is nothing preventing us from 'unfolding' this query in reverse and implementing dynamic loading of data blocks from a 'reference point' in both directions — both down and up.

Note

1. Yes, in this case we access the index twice, but everything is 'purely by the index'. Therefore, the nested query will result in just one additional Index Only Scan.
2. It is quite obvious that this method can only be used when you have values ts that can only intersect by coincidence, and there are few of them. However, if your typical case is 'a million records at 00:00:00.000', this approach should not be taken. In other words, such a case should be avoided. But if it has happened, use the extended index option.

Source: habr.com