In depth understanding of the problem of paging data duplication by postgresql
- 2020-05-06 11:56:04
- OfStack
problem background
Many developers and testers have probably encountered a list of data that shows up on the previous page when the next page is turned, meaning that there is duplicate data when the page is turned.
What about ?
The reason for this problem is that the selected sort fields are duplicated, and it is common practice to add unique fields when sorting, so that the data will not be duplicated during paging. The documentation on this issue also has an explanation that it is not an bug. Instead, when sorting, you need to select a unique field to do the sorting, otherwise the result returned is not sure
What is the root cause of the duplication of data returned by sort?
Those of you who regularly optimize sql may find that the execution plan contains the keyword Sort Method, which is the sort selection method. The sort of abase is divided into three kinds of
quicksort
Es75en-heapsort heap sort
external merge
speculates that
The problem of page repetition is related to the stability of the execution schedule selection sorting algorithm.
briefly introduces the scenario of these three sorting algorithms:
In the case of an index: sort can go directly to the index. In the absence of an index: select quicksort when the amount of data in the table is small (sorting must require less memory than work_mem), heap sort when the sort has limit and consumes no more memory than work_mem, and merge sort when work_mem is insufficient.
verification speculates
1. Create the table and initialize the data
abase=# create table t_sort(n_int int,c_id varchar(300));
CREATE TABLE
abase=# insert into t_sort(n_int,c_id) select 100,generate_series(1,9);
INSERT 0 9
abase=# insert into t_sort(n_int,c_id) select 200,generate_series(1,9);
INSERT 0 9
abase=# insert into t_sort(n_int,c_id) select 300,generate_series(1,9);
INSERT 0 9
abase=# insert into t_sort(n_int,c_id) select 400,generate_series(1,9);
INSERT 0 9
abase=# insert into t_sort(n_int,c_id) select 500,generate_series(1,9);
INSERT 0 9
abase=# insert into t_sort(n_int,c_id) select 600,generate_series(1,9);
INSERT 0 9
three sorts of sorting
-- Quick sort quicksort
abase=# explain analyze select ctid,n_int,c_id from t_sort order by n_int asc;
QUERY PLAN
------------------------------------------------------------
Sort (cost=3.09..3.23 rows=54 width=12) (actual time=0.058..0.061 rows=54 loops=1)
Sort Key: n_int
Sort Method: quicksort Memory: 27kB
-> Seq Scan on t_sort (cost=0.00..1.54 rows=54 width=12) (actual time=0.021..0.032 rows=54 loops=1)
Planning time: 0.161 ms
Execution time: 0.104 ms
(6 rows)
-- Heap sort top-N heapsort
abase=# explain analyze select ctid,n_int,c_id from t_sort order by n_int asc limit 10;
QUERY PLAN
------------------------------------------------------------
Limit (cost=2.71..2.73 rows=10 width=12) (actual time=0.066..0.068 rows=10 loops=1)
-> Sort (cost=2.71..2.84 rows=54 width=12) (actual time=0.065..0.066 rows=10 loops=1)
Sort Key: n_int
Sort Method: top-N heapsort Memory: 25kB
-> Seq Scan on t_sort (cost=0.00..1.54 rows=54 width=12) (actual time=0.022..0.031 rows=54 loops=1
)
Planning time: 0.215 ms
Execution time: 0.124 ms
(7 rows)
-- Merge sort external sort Disk
-- Insert a large number of values of a The data of
abase=# insert into t_sort(n_int,c_id) select generate_series(1000,2000),'a';
INSERT 0 1001
abase=# set work_mem = '64kB';
SET
abase=# explain analyze select ctid,n_int,c_id from t_sort order by n_int asc;
QUERY PLAN
-------------------------------------------------------------
Sort (cost=18.60..19.28 rows=270 width=12) (actual time=1.235..1.386 rows=1055 loops=1)
Sort Key: n_int
Sort Method: external sort Disk: 32kB
-> Seq Scan on t_sort (cost=0.00..7.70 rows=270 width=12) (actual time=0.030..0.247 rows=1055 loops=1)
Planning time: 0.198 ms
Execution time: 1.663 ms
(6 rows)
quicksort
-- Quick sort
abase=# explain analyze select ctid,n_int,c_id from t_sort order by n_int asc;
QUERY PLAN
------------------------------------------------------------
Sort (cost=3.09..3.23 rows=54 width=12) (actual time=0.058..0.061 rows=54 loops=1)
Sort Key: n_int
Sort Method: quicksort Memory: 27kB
-> Seq Scan on t_sort (cost=0.00..1.54 rows=54 width=12) (actual time=0.021..0.032 rows=54 loops=1)
Planning time: 0.161 ms
Execution time: 0.104 ms
(6 rows)
-- The first 20 The data
abase=# select ctid,n_int,c_id from t_sort order by n_int asc limit 20;
ctid | n_int | c_id
--------+-------+------
(0,7) | 100 | 7
(0,2) | 100 | 2
(0,4) | 100 | 4
(0,8) | 100 | 8
(0,3) | 100 | 3
(0,6) | 100 | 6
(0,5) | 100 | 5
(0,9) | 100 | 9
(0,1) | 100 | 1
(0,14) | 200 | 5
(0,13) | 200 | 4
(0,12) | 200 | 3
(0,10) | 200 | 1
(0,15) | 200 | 6
(0,16) | 200 | 7
(0,17) | 200 | 8
(0,11) | 200 | 2
(0,18) | 200 | 9
(0,20) | 300 | 2
(0,19) | 300 | 1
(20 rows) -- Before paging 10 The data
abase=# select ctid,n_int,c_id from t_sort order by n_int asc limit 10 offset 0;
ctid | n_int | c_id
--------+-------+------
(0,1) | 100 | 1
(0,3) | 100 | 3
(0,4) | 100 | 4
(0,2) | 100 | 2
(0,6) | 100 | 6
(0,7) | 100 | 7
(0,8) | 100 | 8
(0,9) | 100 | 9
(0,5) | 100 | 5
(0,10) | 200 | 1
(10 rows)
-- From the first page 10 Bar start fetch 10 article
abase=# select ctid,n_int,c_id from t_sort order by n_int asc limit 10 offset 10;
ctid | n_int | c_id
--------+-------+------
(0,13) | 200 | 4
(0,12) | 200 | 3
(0,10) | 200 | 1
(0,15) | 200 | 6
(0,16) | 200 | 7
(0,17) | 200 | 8
(0,11) | 200 | 2
(0,18) | 200 | 9
(0,20) | 300 | 2
(0,19) | 300 | 1
(10 rows)
limit 10 offset 0,limit 10 offset 10 , take two pages of data in a row Here you can see that in the limit 10 offset 10 result, the third data item repeats the last item on the first page: (0,10) | 200 | 1
And n_int = 200 and c_id = 5 is "omitted".
heap sort
abase=# select count(*) from t_sort;
count
-------
1055
(1 row)
-- Set up the work_mem 4MB
abase=# show work_mem ;
work_mem
----------
4MB
(1 row)
--top-N heapsort
abase=# explain analyze select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 0) td limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Limit (cost=2061.33..2061.45 rows=10 width=13) (actual time=15.247..15.251 rows=10 loops=1)
-> Limit (cost=2061.33..2063.83 rows=1001 width=13) (actual time=15.245..15.247 rows=10 loops=1)
-> Sort (cost=2061.33..2135.72 rows=29757 width=13) (actual time=15.244..15.245 rows=10 loops=1)
Sort Key: test.n_int
Sort Method: top-N heapsort Memory: 95kB
-> Seq Scan on test (cost=0.00..429.57 rows=29757 width=13) (actual time=0.042..7.627 rows=2
9757 loops=1)
Planning time: 0.376 ms
Execution time: 15.415 ms
(8 rows)
-- To obtain limit 1001 offset 0 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 0) td limit 10;
ctid | n_int | c_id
----------+-------+------
(0,6) | 100 | 6
(0,2) | 100 | 2
(0,5) | 100 | 5
(87,195) | 100 | 888
(0,3) | 100 | 3
(0,1) | 100 | 1
(0,8) | 100 | 8
(0,55) | 100 | 888
(44,12) | 100 | 888
(0,9) | 100 | 9
(10 rows)
--- To obtain limit 1001 offset 1 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 1) td limit 10;
ctid | n_int | c_id
----------+-------+------
(44,12) | 100 | 888
(0,8) | 100 | 8
(0,1) | 100 | 1
(0,5) | 100 | 5
(0,9) | 100 | 9
(87,195) | 100 | 888
(0,7) | 100 | 7
(0,6) | 100 | 6
(0,3) | 100 | 3
(0,4) | 100 | 4
(10 rows)
--- To obtain limit 1001 offset 2 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 2) td limit 10;
ctid | n_int | c_id
----------+-------+------
(0,5) | 100 | 5
(0,55) | 100 | 888
(0,1) | 100 | 1
(0,9) | 100 | 9
(0,2) | 100 | 2
(0,3) | 100 | 3
(44,12) | 100 | 888
(0,7) | 100 | 7
(87,195) | 100 | 888
(0,4) | 100 | 4
(10 rows)
Heap sort USES memory: Sort Method: top-N heapsort Memory: 95kB
When offset changes from 0 to 1, and then to 2, it will be found that the 10 pieces of data are not sequenced.
merge sort
-- will work_mem Set to 64kb Let's go merge sort.
abase=# set work_mem ='64kB';
SET
abase=# show work_mem;
work_mem
----------
64kB
(1 row)
-- external merge Disk
abase=# explain analyze select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 0) td limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Limit (cost=2061.33..2061.45 rows=10 width=13) (actual time=27.912..27.916 rows=10 loops=1)
-> Limit (cost=2061.33..2063.83 rows=1001 width=13) (actual time=27.910..27.913 rows=10 loops=1)
-> Sort (cost=2061.33..2135.72 rows=29757 width=13) (actual time=27.909..27.911 rows=10 loops=1)
Sort Key: test.n_int
Sort Method: external merge Disk: 784kB
-> Seq Scan on test (cost=0.00..429.57 rows=29757 width=13) (actual time=0.024..6.730 rows=29757 loops=1)
Planning time: 0.218 ms
Execution time: 28.358 ms
(8 rows)
-- Same as heap sort, get limit 1001 offset 0 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 0) td limit 10;
ctid | n_int | c_id
--------+-------+------
(0,1) | 100 | 1
(0,2) | 100 | 2
(0,4) | 100 | 4
(0,8) | 100 | 8
(0,9) | 100 | 9
(0,5) | 100 | 5
(0,3) | 100 | 3
(0,6) | 100 | 6
(0,55) | 100 | 888
(0,7) | 100 | 7
(10 rows)
-- Same as heap sort, get limit 1001 offset 1 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 1) td limit 10;
ctid | n_int | c_id
----------+-------+------
(0,2) | 100 | 2
(0,4) | 100 | 4
(0,8) | 100 | 8
(0,9) | 100 | 9
(0,5) | 100 | 5
(0,3) | 100 | 3
(0,6) | 100 | 6
(0,55) | 100 | 888
(0,7) | 100 | 7
(87,195) | 100 | 888
(10 rows)
-- Same as heap sort, get limit 1001 offset 2 And then take 10 before 10 The data
abase=# select * from ( select ctid,n_int,c_id from test order by n_int asc limit 1001 offset 2) td limit 10;
ctid | n_int | c_id
----------+-------+------
(0,4) | 100 | 4
(0,8) | 100 | 8
(0,9) | 100 | 9
(0,5) | 100 | 5
(0,3) | 100 | 3
(0,6) | 100 | 6
(0,55) | 100 | 888
(0,7) | 100 | 7
(87,195) | 100 | 888
(44,12) | 100 | 888
(10 rows)
When work_mem is used for merge sort, offset is still in order after going from 0 to 1 and after going to 2.
There is also a case where there is a repetition in the query of the first few pages, but the further you go, the less likely you are to repeat it, and now you can explain it.
If you have 10 pieces of data per page, you use less memory when offse is smaller. As the offse grows, the more memory it consumes.
-- Set up the work_mem =64kb
abase=# show work_mem;
work_mem
----------
64kB
(1 row)
-- The query limit 10 offset 10
abase=# explain analyze select * from ( select ctid,n_int,c_id from test order by n_int asc limit 10 offset 10) td limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Limit (cost=1221.42..1221.54 rows=10 width=13) (actual time=12.881..12.884 rows=10 loops=1)
-> Limit (cost=1221.42..1221.44 rows=10 width=13) (actual time=12.879..12.881 rows=10 loops=1)
-> Sort (cost=1221.39..1295.79 rows=29757 width=13) (actual time=12.877..12.879 rows=20 loops=1)
Sort Key: test.n_int
Sort Method: top-N heapsort Memory: 25kB
-> Seq Scan on test (cost=0.00..429.57 rows=29757 width=13) (actual time=0.058..6.363 rows=29757 loops=1)
Planning time: 0.230 ms
Execution time: 12.976 ms
(8 rows)
-- The query limit 10 offset 1000
abase=# explain analyze select * from ( select ctid,n_int,c_id from test order by n_int asc limit 10 offset 1000) td limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Limit (cost=2065.75..2065.88 rows=10 width=13) (actual time=27.188..27.192 rows=10 loops=1)
-> Limit (cost=2065.75..2065.78 rows=10 width=13) (actual time=27.186..27.188 rows=10 loops=1)
-> Sort (cost=2063.25..2137.64 rows=29757 width=13) (actual time=26.940..27.138 rows=1010 loops=1)
Sort Key: test.n_int
Sort Method: external merge Disk: 784kB
-> Seq Scan on test (cost=0.00..429.57 rows=29757 width=13) (actual time=0.026..6.374 rows=29757 loops=1)
Planning time: 0.207 ms
Execution time: 27.718 ms
(8 rows)
You can see that as offset increases from 10 to 1000, the amount of memory used increases, and the sort method changes from heap sort to merge sort. Merge sort is a stable sort, so the next page does not have the same page as the previous page.
Resources: PostgreSQL-repeating rows from LIMIT OFFSET
Resources: LIMIT and OFFSET
conclusion
1. The problem with paging duplicate data is mainly caused by the fact that the sort fields are not unique and the execution plan goes through quicksort and heap sort.
2. When sorting has duplicate fields, but if the query is merge sort, there is no problem with duplicate data.
3. When sorting with duplicate fields, the previous page repeats, and work_mem is insufficient with the increase of offset, there is no duplicate data.
4. Sorting is related to the stability of the algorithm. When different sorting algorithms are selected in the execution plan, different results are returned.
5. A common way to handle duplicate data is to sort by adding c_bh(unique field) after the sort field d_larq(filing date).
order by d_larq,c_bh;
summary