Hello everyone! I am a backend developer, writing microservices in Java + Spring. I work in one of the teams developing internal products at Tinkoff.
In our team, we often discuss optimizing queries in the DBMS. We always want it to be a bit faster, but sometimes well-thought-out indexes aren't enough — we have to find some workarounds. During one of those wanderings in search of sensible optimizations for working with databases, I found , the author of the book SQL Performance Explained. This is that rare type of blog where you can read all the articles one after another.
I want to translate a small article by Markus for you. It can be called somewhat of a manifesto, which aims to draw attention to an old but still relevant problem of performance with the offset operation according to the SQL standard.
In some places, I will supplement the author's explanations and comments. All such places will be marked as "note" for clarity.
A small introduction
I think many are aware of how problematic and slow pagination queries via offset can be. But do you know that it can be fairly easily replaced with a more efficient construct?
So, the key word offset instructs the database to skip the first n records in the query. However, the database still has to read those first n records from disk, in the specified order (note: apply sorting if specified), and only after that can it return records starting from n+1 and onwards. The most interesting part is that the problem doesn't lie in the specific implementation in the DBMS, but rather in the original definition according to the standard:
…the rows are first sorted according to the and then limited by dropping the number of rows specified in the from the beginning…
-SQL:2016, Part 2, 4.15.3 Derived tables (note: currently the most widely used standard)
The key point here is that offset takes a single parameter — the number of records to skip, and that's it. Following such a definition, the DBMS can only retrieve all records and then discard the unnecessary ones. It’s clear that such a definition of offset leads to unnecessary work. And it doesn't even matter whether it’s SQL or NoSQL.
A bit more pain
The issues with offset don't end here, and here's why. If a new record is inserted by another operation between reading two pages of data from the disk, what happens in this case?
When offset is used to skip records from previous pages, in a situation where a new record is added between reading different pages, you are likely to get duplicates (note: this can happen when we read page by page using the order by clause, thus a new record can end up in the middle of our results).
The diagram clearly illustrates this situation. The database reads the first 10 records, after which a new record is inserted, shifting all the previously read records by 1. Then the database retrieves the next page of 10 records and starts not from the 11th, as it should, but from the 10th, duplicating that record. There are other anomalies related to this expression, but this is the most common.
As we have established, this is not an issue with a specific DBMS or its implementations. The problem lies in the pagination definition according to the SQL standard. We tell the DBMS which page to retrieve or how many records to skip. The database simply cannot optimize such a query due to the lack of information.
It is also worth clarifying that this is not a problem with a specific keyword, but rather the semantics of the query. There are a few other syntaxes with similar issues:
- The keyword offset, as mentioned earlier.
- The two-keyword construct limit [offset] (although limit itself isn't that bad).
- Filtering based on lower bounds constructed on row numbering (e.g., row_number(), rownum, etc.).
All these expressions simply indicate how many rows need to be skipped, without any additional information or context.
Further in this article, the keyword offset is used as a generalization of all these variants.
Life Without OFFSET
Now let's imagine what our world would be like without all these problems. It turns out that life without offset isn't that difficult: we can select only those rows that we haven't seen yet (note: that is, those that weren't on the previous page), using a condition in the where clause.
In this case, we are starting from the fact that selects are executed over an ordered set (the good old order by). Since we have an ordered set, we can use a fairly simple filter to fetch only the data that is beyond the last entry of the previous page:
SELECT ...
FROM ...
WHERE ...
AND id < ?last_seen_id
ORDER BY id DESC
FETCH FIRST 10 ROWS ONLYAnd that's the entire principle of this approach. Of course, sorting by multiple columns makes things more interesting, but the idea remains the same. It is important to note that this construction is applicable in many -solutions.
This approach is called the seek method or keyset pagination. It solves the problem of floating results (note: the situation with records changing between page reads, as described earlier) and, of course, we all love it, it works faster and more reliably than the classic offset method. The stability lies in the fact that the processing time of the request does not increase proportionally to the number of the requested table (note: if you want to learn more about different pagination approaches, you can . There you can also find comparative benchmarks on various methods).
One of the slides , that key-based pagination is certainly not all-powerful — it has its limitations. The most significant one is that it cannot read random pages (note: non-sequentially). However, in the era of infinite scrolling (note: on the frontend), this is not such a problem. Indicating the page number to click is, in any case, a poor solution when developing UI (note: the author's opinion).
And what about tools?
Keyset pagination often does not fit due to the lack of tool support for this method. Most development tools, including various frameworks, do not provide a choice for how pagination will be executed.
The situation is exacerbated by the fact that the described method requires consistent support in the technologies used — from the database management system to the execution of AJAX requests in the browser during infinite scrolling. Instead of just indicating the page number, now you will have to specify a set of keys for all pages at once.
However, the number of frameworks supporting keyset pagination is gradually increasing. Here is what is currently available:
- for Java;
- for Ruby;
- and for Django;
- for Python;
- — criteria API for JPA implementations;
- for Perl;
- , мапер для Node.js .
(Note: some links were removed because at the time of translation, some libraries had not been updated since 2017-2018. If you are interested, you can check the original source.)
This is exactly where your help is needed. If you are developing or maintaining a framework that in any way uses pagination, I ask, I urge, I implore you to create native support for keyset pagination. If you have questions or need assistance, I would be happy to help (, , ) (Note: from my experience communicating with Markus, I can say that he is genuinely enthusiastic about promoting this topic).
If you are using existing solutions that you think deserve support for keyset pagination, please create a request or even propose a ready-made solution if possible. You can also reference this article in the link.
Conclusion
The reason why such a simple and useful approach as keyset pagination is not widely adopted is not that it is difficult to implement technically or requires significant effort. The main reason is that many are accustomed to seeing and working with offsets — this approach is dictated by the standard itself.
As a result, few consider switching to a different approach to pagination, and because of this, the tool support from frameworks and libraries develops slowly. Therefore, if you resonate with the idea and goal of offset-free pagination, please help spread it!
Source:
Author: Markus Winand
Source: habr.com
