There are periodic tasks of finding related data by a set of keys, until we gather the required total number of records..
The most 'realistic' example is to output the 20 oldest tasks, listed on the employee roster (for example, within a single department). For various management 'dashboards' with concise summaries of work areas, similar themes are often required.
In this article, we will consider the implementation in PostgreSQL of a 'naive' version of solving such a task, of a 'smarter' and a completely complex algorithm of a 'cycle' in SQL with a condition for exit from found data, which can be useful for both general development and for application in other similar cases.
Let's take a test dataset from . To ensure that the displayed records do not 'jump' from time to time when sorting values match, we will expand the subject index by adding the primary key.This will also give it uniqueness right away and guarantee us the unambiguity of the sorting order:
CREATE INDEX ON task(owner_id, task_date, id);
-- and we'll delete the old one
DROP INDEX task_owner_id_task_date_idx;As it sounds, so it is written
First, let’s sketch the simplest query option, passing the IDs of performers :
SELECT
*
FROM
task
WHERE
owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
task_date, id
LIMIT 20; 
It's a bit sad — we ordered only 20 records, but the Index Scan returned us 960 rows, which then had to be sorted... Let's try reading less.
unnest + ARRAY
The first thought that will help us — if we need a total of 20 sorted records, then it's enough to read no more than 20 sorted in the same order for each key. Fortunately, we have a suitable index (owner_id, task_date, id).
We will use the same extraction and 'pivoting to columns' mechanism of the complete record of the table, just as in . We will also apply aggregation into an array using the function ARRAY():
WITH T AS (
SELECT
unnest(ARRAY(
SELECT
t
FROM
task t
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 20 -- we limit here...
)) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
(r).*
FROM
T
ORDER BY
(r).task_date, (r).id
LIMIT 20; -- ... and here too 
Oh, already much better! 40% faster, and reading 4.5 times less data had to be done.
Materialization of table records through CTEI would like to note that in some cases trying to work with record fields immediately after searching for them in a subquery, without 'wrapping' them in a CTE can lead to the 'multiplication' of InitPlan proportional to the number of those same fields:
SELECT
((
SELECT
t
FROM
task t
WHERE
owner_id = 1
ORDER BY
task_date, id
LIMIT 1
).*);Result (cost=4.77..4.78 rows=1 width=16) (actual time=0.063..0.063 rows=1 loops=1)
Buffers: shared hit=16
InitPlan 1 (returns $0)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.031..0.032 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t (cost=0.42..387.57 rows=500 width=48) (actual time=0.030..0.030 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 2 (returns $1)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_1 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 3 (returns $2)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_2 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4"
InitPlan 4 (returns $3)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_3 (cost=0.42..387.57 rows=500 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
The same record was 'searched' 4 times... Until PostgreSQL 11, this behavior occurred regularly, and the solution was to 'wrap' it in a CTE, which serves as an unconditional boundary for optimizers in these versions.
Recursive accumulator
In the previous version, we read a total of 200 rows for the needed 20. Not 960 anymore, but even less — can we?
Let's try to use the knowledge that we need a total of 20 records. That is, we will iterate the data extraction only until we reach the required amount.
Step 1: initial list
Clearly, our 'target' list of 20 records should start with the 'first' records from one of our owner_id keys. So first, we will find such 'earliest' ones for each key and add them to the list, sorting it in the order we want — (task_date, id).
Step 2: finding the 'next' records
Now, if we take the first record from our list and start 'stepping' further along the index with the owner_id key preserved, all found records are precisely the next ones in the result set. Of course, only until we cross the application key the second record in the list.
If it turns out that we have "crossed" the second record, then the last read record should be added to the list instead of the first one (with the same owner_id), after which the list is sorted again.
This means that we always get a situation where there is no more than one record per key in the list (if the records have run out and we haven't "crossed", the first record simply disappears from the list, and nothing will be added), and they are always sorted in ascending order of the application key (task_date, id).
Step 3: filter and "unroll" records
In some rows of our recursive selection, some records rv are duplicated — first, we find those like "crossing the boundary of the 2nd record in the list", and then substitute them as the 1st in the list. So the first occurrence must be filtered out.
The terrifying final query
WITH RECURSIVE T AS (
-- #1 : adding the "first" records for each key in the set to the list
WITH wrap AS ( -- "materializing" records so that accessing fields does not cause InitPlan/SubPlan multiplication
WITH T AS (
SELECT
(
SELECT
r
FROM
task r
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 1
) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
array_agg(r ORDER BY (r).task_date, (r).id) list -- sorting the list in the desired order
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNION ALL
-- #2 : reading the records of the 1st key in order, until we exceed the record of the 2nd
SELECT
CASE
-- if nothing is found for the 1st record key
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- removing it from the list
-- if we do NOT cross the application key of the 2nd record
WHEN X.not_cross THEN
T.list -- simply extending the same list without modifications
-- if there is no 2nd record in the list
WHEN T.list[2] IS NULL THEN
-- just returning an empty list
'{}'
-- reshuffling the dictionary, removing the 1st record and adding the last found
ELSE (
SELECT
coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
FROM
unnest(T.list[3:] || X._r) r
)
END
, X._r
, X.not_cross
, T.size + X.not_cross::integer
FROM
T
, LATERAL(
WITH wrap AS ( -- "materializing" record
SELECT
CASE
-- if we indeed "crossed over" the 2nd record
WHEN NOT T.not_cross
-- then the required record is the first from the list
THEN T.list[1]
ELSE ( -- if not crossed, then the key remained as in the previous record - we base from it
SELECT
_r
FROM
task _r
WHERE
owner_id = (rv).owner_id AND
(task_date, id) > ((rv).task_date, (rv).id)
ORDER BY
task_date, id
LIMIT 1
)
END _r
)
SELECT
_r
, CASE
-- if the 2nd record is no longer in the list, but we found something
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- found nothing or "crossed over"
coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
END not_cross
FROM
wrap
) X
WHERE
T.size < 20 AND -- limiting the count here
T.list IS DISTINCT FROM '{}' -- or while the list is not exhausted
)
-- #3 : "unfolding" records - order is guaranteed by construction
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- taking only the "non-crossing" records 
Thus, we exchanged 50% of data reads for 20% of execution timeThis means that if you have reasons to believe that reading may take a long time (for example, data is often not cached and needs to be accessed from disk), then this method can help reduce dependency on reading.
In any case, the execution time turned out to be better than in the 'naive' first variant. But which of these 3 options to use is up to you.
Source: habr.com
