# Looking for a simpler alternative to a recursive query

The actual query is more involved, but the problem I'm facing can be distilled to this:

A query to filter a rowset of monotonically increasing integers so that - in the final result set, row(n+1).value >= row(n).value + 5.

For the actual problem I need to solve, the rowset count is in the 1000s.

A few examples to clarify:

• if rows are: 1,2,3,4,5 : then query should return: 1
• if rows are: 1,5,7,10,11,12,13 : then query should return: 1,7,12
• if rows are: 6,8,11,16,20,23: then query should return: 6,11,16,23
• if rows are: 6,8,12,16,20,23: then query should return: 6,12,20

I've managed to get the required results with the following query, but it seems overly complicated. Uncomment the different "..with t(k).." to try them out.

I'm looking for any simplifications or alternative approaches to get the same results.

``````with recursive r(n, pri) as (
with t(k) as (values (1),(2),(3),(4),(5))   -- the data we want to filter
-- with t(k) as (values (1),(5),(7),(10),(11),(12),(13))
-- with t(k) as (values (6),(8),(11),(16),(20),(23))
-- with t(k) as (values (6),(8),(12),(16),(20),(23))
select min(k), 1::bigint from t             -- bootstrap for recursive processing. 1 here represents rank().
UNION
select k, (rank() over(order by k)) rr      -- rank() is required just to filter out the rows we dont want from the final result set, and no other reason
from r, t
where t.k >= r.n+5 and r.pri = 1            -- capture the rows we want, AND unfortunately a bunch of rows we dont want
)
select n from r where pri = 1;
``````
• For the rule `row(n+1).value >= row(n).value + 5` and the rows `1,5,7,10,11,12,13` you say it should return `1,7,12` but that disagrees with the rule. The rule should also state that you always return the first row. So then starting with the first row 1, `5 >= 1 + 5` is false so 5 is excluded. Then `7 >= 5 + 5` is also false so 7 should be excluded according to the rule, yet it is included. Your rule is more like "starting with the first row, find the next row that is at least five more than the current value, repeating" – Davos Mar 12 at 16:02

This was hard! I don't know if this is simpler, but at least it doesn't use window function nor produce rows that require being filtered out.

``````with recursive r(k, n) as (
with t(k) as (values (1),(2),(3),(4),(5))   -- the data we want to filter
-- with t(k) as (values (1),(5),(7),(10),(11),(12),(13))
-- with t(k) as (values (6),(8),(11),(16),(20),(23))
-- with t(k) as (values (6),(8),(12),(16),(20),(23))
,t2(k,n) AS (select k, (select min(k) from t tt where k >= t.k+5) from t) -- precalculate what's next
select * from (select * from t2 limit 1) x   -- limit 1 directly fails in a union!
UNION ALL
select t2.* from r, t2 where t2.k = r.n      -- on each iteration, keep only the value that matches the previous precalculated next one
)
select k from r
``````

Testing

This alternative seems to be less efficient for very small sets, but more or less linear in performance, whilst the original seems to be exponentially more sluggish.

``````drop table if exists t;
create temp table t(k) AS
with recursive r(n) as (
select floor(random()*10)::int + 1
UNION ALL
select n + floor(random()*10)::int + 1
from r
where n < 100000)        -- change to increase or reduce set
select * from r;           -- surprisingly fast! Go PG!
create index on t(k);

with recursive r(n, pri) as (
select min(k), 1::bigint from t
UNION
select k, (rank() over(order by k)) rr
from r, t
where t.k >= r.n+5 and r.pri = 1
)
select count(*) from r where pri = 1; -- I aborted it after waiting for a minute

with recursive r(k, n) as (
with t2(k,n) AS (select k, (select min(k) from t tt where k >= t.k+5) from t)
select * from (select * from t2 limit 1) x
UNION ALL
select t2.* from r, t2 where t2.k = r.n
)
select count(*) from r -- 26" in my server
``````

Normally you can utilize windowed aggregate functions when you need to access the previous row's data, but here the current row's calculation is based on the previous result, not row. For this a kind of question I never found a set based solution with acceptable performance.

But it's easy to write using row-by-row logic. I prefer materializing a `ROW_NUMBER` in a temporary table, then finding the next row is simply `n+1`:

``````CREATE TABLE temp AS
( SELECT k,
ROW_NUMBER() OVER (ORDER BY k) AS rn
FROM t
)
;
-- I don't know enough about PostgreSQL, but this is probably needed for performance
create unique index on temp(rn)
;

WITH RECURSIVE cte(k,rn, k1) AS
(
SELECT k, rn, k AS k1
FROM tmp
UNION ALL
SELECT tmp.k, tmp.rn,
CASE
WHEN tmp.k >= cte.k1 + 5
THEN tmp.k   -- use the new value
ELSE cte.k1  -- keep the old value
END
FROM tmp JOIN cte
ON tmp.rn = cte.rn+1 -- next row
)
SELECT count(k)
FROM cte
WHERE k = k1
``````

This performs quite fast, I hijacked @ZiggyCrueltyfreeZeitgeister's fiddle.

In fact this is old-style cursor-logic processing and a cursor might actually be faster (you don't need a temp table plus `ROW_NUMBER` and recursion). My PostgreSQL knowledge is very limited and I don't know what's preferred in PG-land :)