Five ways of pagination in Postgres, from basic to bizarre

You may be surprised by the fact that pagination, common as such, web applications can easily be implemented inefficiently. In this article, we'll try different ways of pagination on the server side and discuss their convenience when using PostgreSQL. Article will help You to understand which technique is more appropriate in Your situation, including some You may not have seen before, namely those that rely on physical clustering and collector database statistics.

Before continuing, I should mention the pagination on the side of the application. Some applications tolerate all (or most) server information in the client and share her page there. For small amounts of data, pagination in your app can be a good choice, reducing the number of HTTP calls. This approach becomes impractical when the records start in the thousands. Pagination on the server side has the following advantages:

the

the
• faster loading time for start page
the
• better precision when shared data is modified
the
• faster operations on large amounts of data

Encapsulate business logic the

• better performance for clients with limited resources

PostgreSQL gives us a certain number of techniques of pagination on the server side, which differ in speed, integrity (not losing) but also support templates access to certain pages. Not all methods work in all situations, some require special data or queries. Consider the methods in order of generality, starting with those that work with any requests, and continuing those that require ordered data. Finish we a number of exotic methods, which are based on the internals of PostgreSQL.

the

Split arbitrary queries

the

Limit-Offset

The easiest method of pagination limit, offset, and is the most risky. Unfortunately, he is one of the foundations of tutorials on web development. Object-relational mapping (ORM) to make using this method easy and tempting, from SQLAlchemy'wow .slice(1, 3) to ActiveRecord'wow .limit(1).offset(3) and to Sequelize'wow .findAll({ offset: 3, limit: 1 }). It's not a coincidence that the limit offset is used everywhere, you can attach it to any request without further modification.

ORM methods limit'and offset is one thing, a utility library for pagination can be even more deceptive. For example, the popular Ruby library Kaminari uses limit-offset by default, hiding it behind a high-level interface.

This technique has two big problems, inconsistency of result and effectiveness of the offset. Consistency stems from the fact that the passage of the results should receive each item is strictly once, without omissions or repetitions. The ineffectiveness of offsets is associated with a delay arising from the shift results in a large displacement.

That's the way limit-offset pagination can be inconsistently. Suppose the user navigates from the page n n + 1, while at the same time a new element is inserted on the page n. This will cause the duplication (the last element from the page n pushed to the page n + 1), and pass (a new item). Alternatively, suppose that the removed n, in that moment, when the user came to the page n + 1. Pre-loaded initial page item n + 1 will move to the page n and will be ignored.

Now on the subject of inefficiency. Large shifts in reality expensive. Even if there is an index, the database will have to scan the entire vault, including the row. For index usage we need to filter the column by value, but in this case we require a certain number of rows, regardless of column values. Additionally, strings are not required to have the same size in storage, and some of them may be present on disk but to be marked as deleted so that the database will not be able to use simple arithmetic to find the place on the disk and start reading results. Let's measure the deceleration.
the

-- Create a table with random strings of varying size
CREATE TABLE medley AS
SELECT
generate_series(1,10000000) AS n,
substr(concat(md5(random()::text), md5(random()::text)), 1, (random() * 64)::integer + 1) AS description;

-- Inform the scheduler about radically changing the table size
VACUUM ANALYZE;

-- Small shifts refreshingly quick
EXPLAIN ANALYZE SELECT * FROM medley LIMIT 100;

The estimated cost is low enough:

the

 the QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..1.85 rows=100 width=38) (actual time=0.008..0.036 rows=100 loops=1)
-> Seq Scan on medley (cost=0.00..185460.60 rows=9999660 width=38) (actual time=0.007..0.017 rows=100 loops=1)
Planning time: 0.040 ms
Execution time: 0.059 ms
(4 rows)

Choice offset = 1000, changing its value to 19 and the lead time to 0.609 MS. Once offset = 5000000, the cost becomes 92734 and lead time 758.484 MS.

These problems do not necessarily mean that the limit-offset method is not applicable in Your case. In some applications, users usually are not a lot of pages in results, and You can even use the maximum number of pages the server-side. If inconsistency of data and page limits are not a problem in Your application, the limit-offset method is well suited for You.

When to use Limit-Offset. Applications with limited depth of pagination and tolerant of consistently result.

the

Cursors

Despite its shortcomings, the method of limit-offset is a plus in the form of a lack of influence on the server. In contrast to this approach, there is another method of paging, cursors. As an offset, cursors can be used with any inquiries, but they differ in that they require a separate server connections and transactions using the HTTP client.

Here's how it can be used cursors:

the

-- We should be in transaction
BEGIN;
-- Open the cursor for the query
Medley_cur DECLARE CURSOR FOR SELECT * FROM medley;
-- Get 10 rows
FETCH 10 FROM medley_cur;
-- ...
-- Get 10 rows from where stopped last time
FETCH 10 FROM medley_cur;
- All ready
COMMIT;

Cursors have the desirable property of consistency of pagination on any queries, showing the results existing in the database at the time the transaction started. isolation Level transaction guarantees that the paginated result will not change.

Each approach of paging has its weaknesses, and cursors — are no exception: they are dependent on the use of resources and the bundles of client-server. Each open transaction consumes resources base, and not massturbate for a large number of clients. Of course, there are the "WITH HOLD" cursors, which can exist outside transactions, but they have to materialize the data.Thus, these errors do pagination with cursors suitable only for a narrow range of situations, for example for the internal network.

Adding a connection via HTTP to cursor makes a complications. Servers need to identify clients between requests, whether in a token, or maintaining an identifier such as the IP address of the client within the session. The servers also need to decide when to release transactions in connection with their downtime. Finally, load balancing on the server gets complicated, as the client must connect to a specific server every time.

When to use Cursors. Application within the network, on a single server, which is divided into page requests with variable order and variable, especially when an important consistency result.

the

Pagination-ordered queries

the

Pagination on a set of keys

Equipment listed above can be divided into page the results of queries of any type, including unordered queries. If we are willing to abandon this community, we will be able to reap the benefits of optimization. In particular, when order by indexed column, the user can use values from the current page to select which places to show on the next page. This is called pagination on a set of keys.
For example, let's return to our example:

the

-- Add an index for pagination (btrees support inequality)
CREATE INDEX n_idx ON medley USING btree (n);
SELECT * FROM medley ORDER BY n ASC LIMIT 5;

With my random data it returns:

the

 n | description
---+-------------------------------------------------------------
1 | 74f70e009396
2 | 8dac5a085eb670a29058d
3 | fce303a32e89181bf5df1601487
4 | fddcced2c12e83516b3bd6cc94f23a012dfd
5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(5 rows)

The user can now look at the maximum n from the result and use it to call the following page:

the

SELECT * FROM medley
WHERE n > 5
ORDER BY n ASC
LIMIT 5;

Even when you filter with n > 5000000 is faster than limit-offset example.

the

 the QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..0.62 rows=5 width=38) (actual time=0.101..0.103 rows=5 loops=1)
-> Index Scan using n_idx on medley (cost=0.43..185579.42 rows=5013485 width=38) (actual time=0.100..0.102 rows=5 loops=1)
Index Cond: (n > 5000000)
Planning time: 0.071 ms
Execution time: 0.119 ms
(5 rows)

Such pagination is fast and ensures data integrity. Any additions/deletion to the current page will leave the result unchanged. Two weaknesses of this method is the lack of random access and the possible connection between the client and the server.

In General, there is no way to navigate to the selected page without visiting the previous to determine their maximal elements. Under certain conditions, however, we can do better. If the values in the indexed column are evenly distributed (or even better, connecting rooms without the spaces), you can produce some mathematical calculations to find the interesting page, because the index makes cheap finding the highest values:

the

EXPLAIN ANALYZE SELECT max(n) FROM medley;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Result (cost=0.46..0.47 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=1)
InitPlan 1 (returns $0)
-> Limit (cost=0.43..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1)
-> Index Only Scan Backward using n_idx on medley (cost=0.43..284688.43 rows=10000000 width=4) (actual time=0.017..0.017 rows=1 loops=1)
Index Cond: (n IS NOT NULL)
Heap Fetches: 0
Planning time: 0.087 ms
Execution time: 0.042 ms
(8 rows)

Another issue is pagination on the key values, client/server, requires attention. Initially the user does not know which columns are indexed. The server is likely to provide the endpoint with a fixed result, rather than allow the client to change the order. Provided to the client code may not know which column is ordered, the server should provide a hint as to request the next page. RFC5988 defines the relationship of the previous and following HTTP references for encoding references to the user that he needs to go.

Because users typically turn to the pages of information in a linear form, the pagination on the key values is normally preferred for the paging of records on web servers.

When to use: Pagination on key values. Scalable applications that serve data sequentially from the column(s) indexed for comparison. Supports filtering.

the

Strange specialized pagination

the

Clustered TID Scan

We can get non-standard methods of paging for particular situations with the use of PostgreSQL functions to the low level. For example, we can get really random data access, if we

the
1. is Not required from pages that they were the same size
the
2. Supported only a single order for paginated rows

The trick here is to choose the returned pages that are associated with pages from the database on disk, or with certain parts of these pages on disk. Each table in a PostgreSQL database contains a secret column called ctid and identificeret her line:
the

SELECT ctid, * FROM medley WHERE n <= 10;
ctid | n | description
--------+----+-------------------------------------------------------------
(0,1) | 1 | 74f70e009396
(0,2) | 2 | 8dac5a085eb670a29058d
(0,3) | 3 | fce303a32e89181bf5df1601487
(0,4) | 4 | fddcced2c12e83516b3bd6cc94f23a012dfd
(0,5) | 5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(0,6) | 6 | eb9fe1dfe1e421903f96b3b5c5dfe1ee1253582d728c35b4ee7330b
(0,7) | 7 | e95202d7f5c612f8523ae705d
(0,8) | 8 | 6573b64aff262a2b940326
(0,9) | 9 | a0a43
(0,10) | 10 | 82cdc134bd249a612cfddd3088dd09e32de5f4fa33
(10 rows)

Each ctid is as follows: (page, line). PostgreSQL can get the row very fast for ctid'have, in fact, so are the indexes — they associate column values with ctid'mi.

You should pay attention, though, PostgreSQL and determines the order relation on the basis of tid type, it can not effectively to ctid''s inequality

the

EXPLAIN ANALYZE SELECT count(1) FROM medley WHERE ctid > = '(0,1)'::tid AND ctid < '(1,0)'::tid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=235589.00 235589.01..rows=1 width=0) (actual time=..1241.851 1241.852 rows=1 loops=1)
-> Seq Scan on medley (cost=0.00..235464.00 rows=50000 width=0) (actual time=..477.933 1241.802 rows=116 loops=1)
Filter: ((ctid > = '(0,1)'::tid) AND (ctid < '(1,0)'::tid))
Rows Removed by Filter: 9999884
Planning time: 0.047 ms
Execution time: 1241.889 ms
(6 rows)

The query ranges does not work, but there is still a way to effectively query all rows from the page on disk. Each page contains current_setting('block_size') byte data (typically 8K). Rows have a 32-bit pointer, so for the most part, have block_size/4 rows per page. (In fact, the line generally larger than the minimum size and a quarter of the size of the block provides the upper limit of rows per page.) The following sequence will generate all possible ctid's on j-th

the

SELECT ('(' || j || ',' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i);

Let's use her to get all the rows in our example on the zero page.

the

SELECT * FROM medley WHERE ctid = ANY (ARRAY
(SELECT ('(0,' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i)
)
);

The scheduler has determined the cost of this query is equal to cost=25.03..65.12 and performs his 2.765 MS. The page request number 10000 has the same cost. So we get a real random access, why not love him?

Here are three bottlenecks:

the
1. When lines are removed they leave holes in the pages.
the
2. the Order of rows may not be significant. Database inserts rows into the holes left from removing lines that will lead to the loss of lines from the sequence.
the
3. "Where" is not supported

In some situations this is not a problem. One case is the data, a natural order which corresponds with the order you added, such as only increasing the data time intervals. The other is the data that do not change frequently. This is due to the fact that we have control over the location of rows on the page using the CLUSTER command.

Let's return to our example. His line on the disk is ordered by the n column in ascending order, since this is the order in which we added them to the database. But what if we want to sort by description? For this we have to physically rebuild the table by creating an index on the column description and perform the clustering.

the

CREATE INDEX description_idx ON medley USING btree (description);
CLUSTER medley USING description_idx;

Now select all the rows from the first page returns us the data sorted in alphabetical order based on the column description. If the table changes, then a new row will be dropped from the alphabetical list, but while the table is unchanged, the returned objects are in order. In addition, it can be periodically pereklikaetsya after the changes, despite the fact that this operation locks the table and can not be performed when people need access to it.

Finally, it is possible to determine the total number of pages for the table using its total size in bytes.

the

SELECT pg_relation_size('medley') / current_setting('block_size')::int;

When to use: TID Scan.  When you want fast random access and does not require filtering. Works especially well with just increasing the data time, with practically not changing width of the line.
 

 
the 
a Set of keys with an estimated bookmarks
 
As we have seen, the normal pagination through sets of keys allows you to navigate to specific pages, except with the guesswork of the user. However, the statistics collector PostgreSQL supports a histogram of the distribution of values in columns. We can use these estimates in conjunction with the limitations and small offsets to get quick pagination with random access via a hybrid approach.
 

 
First, let's look at the numbers in our example:
 

 
the 
SELECT array_length(histogram_bounds, 1) - 1
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n';

 
In my database the column " n " 101 boundary index, i.e., 100 ranges in-between. Specific values are not too distracting, since the data is uniformly distributed.
 

 
the 
{719,103188,193973,288794, ... ,9690475,9791775,9905770,9999847}
 

 
Please note that values are approximate. The first number is not exactly 0, and the latter is not exactly ten million. Ranges share our information in the block size B = 10,000,000 / 100 = 100,000 lines.
 

 
We can use the ranges of the histograms of the PostgreSQL statistics collector to obtain probabilistic correct pages. If we choose the page size on the client side equal to W, then we get the i-th page? She will be in the unit IW / B, offset IW% B.
 

 
Choosing W = 20, let's request a page 270000 from our test table.
 

 
the 
bookmark WITH AS (
SELECT (histogram_bounds::text::int[])[((270000 * 20) / 100000)+1] AS start,
(histogram_bounds::text::int[])[((270000 * 20) / 100000)+2] AS stop
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n'
LIMIT 1
)
SELECT *
FROM medley
WHERE n >= (select start from bookmark)
AND n < (select stop from bookmark)
ORDER BY n ASC
LIMIT 20
OFFSET ((270000 * 20) % 100000);

 
It runs super-fast (please note that shift occurs during the time close to zero in this case). The query returns the rows with n=5407259 to 5407278. The true meaning on the page 270000 equal to n = 5400001 to 5400020. The penalty is 7239, or approximately 0.1%.
 

 
We were lucky with the page selection in this case. For contrast, the page is 74999 requires a shift in 99980. We know that our offset is not more than 100000. The upper border is under our control, if we want to reach a compromise. Configuring the statistics collector PostgreSQL, we can get a more accurate histogram on the columns.
 

 
the 
ALTER TABLE medley n ALTER COLUMN SET statistics 1000;
VACUUM ANALYZE;

 
Now we have 1000 instead of 100 values of the histogram. In my database it looks like the following:
 

 
the 
{10,10230,20863, ..., 9980444,9989948,9999995}

 
In this step of our displacement will not be more than 10,000. The tradeoff is that the scheduler now looks at more variables, but slowing down. So it's somewhere between the inefficient offset and overhead of the statistics collector.
 

 
This hybrid "set of keys/shift" method is probably not suitable for many uses pagination in real life. And then will not work the condition "where". In addition, it is inaccurate and it only gets more and more inaccurate if you change the table, and if the collector statistics have not been run.
 

 
When to use: a Set of keys with value bookmarks.  When the user needs deep, but approximate random access, without any additional filtering.
 

 
the 
Insights
 
Like many other engineering solutions, selection of equipment pagination requires compromise. It's safe to say that the pagination on the set of keys most applicable for medium site with an orderly linear access. However, even the limit/offset method has its strengths, and more exotic methods provide special performance characteristics for certain types of data. As you can see, there are quite a few possibilities. Choose the right tool for the job and don't  let  @ be a closed book.

Article based on information from habrahabr.ru