7

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
2

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
| improve this answer | |
2
+50

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 
   WHERE rn = 1  -- start with the minimum value
   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 :)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.