Postgres 16

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
explain analyze with recursive data as (
    select
        n as len,
        (250 - n * (n + 1) / 2) / n + 1 as range,
        floor((sqrt(8 * 250 + 1) - 1) / 2)::int as maxlen
    from generate_series(2, floor((sqrt(8 * 250 + 1) - 1) / 2)::int) n
), candidates as (
    select ofs + 1 s, ofs + len e,
        row_number() over (partition by ofs order by len desc) as rnk
    from data cross join generate_series(0, (select max(range) - 1 from data)) ofs
    where ofs < range and (len = maxlen or ofs >= maxlen)
        and 250 - (ofs + 1 + (len - 1) / 2::float) * len < ofs + len + 1
), chain as (
    select * from candidates where s = 1
    union all
    select rc.* from chain c inner join candidates rc on rc.s = c.e + 1
)
select s, least(e, 10000) as e from chain where s <= 10000
union all
select n, n from generate_series((select max(e) + 1 from chain), 10000) n
order by s;


QUERY PLAN


Sort  (cost=1668.29..1672.04 rows=1501 width=8) (actual time=6.568..7.041 rows=9912 loops=1)

  Sort Key: chain.s

  Sort Method: quicksort  Memory: 694kB

  CTE data

    ->  Function Scan on generate_series n_1  (cost=0.00..0.50 rows=20 width=12) (actual time=0.022..0.025 rows=20 loops=1)

  CTE candidates

    ->  WindowAgg  (cost=1236.57..1255.27 rows=748 width=24) (actual time=0.522..0.589 rows=104 loops=1)

          InitPlan 2 (returns $1)

            ->  Aggregate  (cost=0.45..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1)

                  ->  CTE Scan on data  (cost=0.00..0.40 rows=20 width=4) (actual time=0.000..0.008 rows=20 loops=1)

          ->  Sort  (cost=1236.11..1237.98 rows=748 width=8) (actual time=0.509..0.516 rows=104 loops=1)

                Sort Key: ofs.ofs, data_1.len DESC

                Sort Method: quicksort  Memory: 28kB

                ->  Nested Loop  (cost=0.00..1200.40 rows=748 width=8) (actual time=0.102..0.454 rows=104 loops=1)

                      Join Filter: ((ofs.ofs < data_1.range) AND ((data_1.len = data_1.maxlen) OR (ofs.ofs >= data_1.maxlen)) AND (('250'::double precision - ((((ofs.ofs + 1))::double precision + (((data_1.len - 1))::double precision / '2'::double precision)) * (data_1.len)::double precision)) < (((ofs.ofs + data_1.len) + 1))::double precision))

                      Rows Removed by Join Filter: 2376

                      ->  CTE Scan on data data_1  (cost=0.00..0.40 rows=20 width=12) (actual time=0.022..0.025 rows=20 loops=1)

                      ->  Function Scan on generate_series ofs  (cost=0.00..10.00 rows=1000 width=4) (actual time=0.002..0.009 rows=124 loops=20)

  CTE chain

    ->  Recursive Union  (cost=0.00..246.87 rows=1504 width=16) (actual time=0.525..1.496 rows=36 loops=1)

          ->  CTE Scan on candidates  (cost=0.00..16.83 rows=4 width=16) (actual time=0.524..0.632 rows=1 loops=1)

                Filter: (s = 1)

                Rows Removed by Filter: 103

          ->  Hash Join  (cost=1.30..21.50 rows=150 width=16) (actual time=0.015..0.023 rows=1 loops=36)

                Hash Cond: (rc.s = (c.e + 1))

                ->  CTE Scan on candidates rc  (cost=0.00..14.96 rows=748 width=16) (actual time=0.000..0.013 rows=104 loops=36)

                ->  Hash  (cost=0.80..0.80 rows=40 width=4) (actual time=0.001..0.001 rows=1 loops=36)

                      Buckets: 1024  Batches: 1  Memory Usage: 9kB

                      ->  WorkTable Scan on chain c  (cost=0.00..0.80 rows=40 width=4) (actual time=0.000..0.000 rows=1 loops=36)

  InitPlan 5 (returns $5)

    ->  Aggregate  (cost=33.84..33.85 rows=1 width=4) (actual time=0.007..0.008 rows=1 loops=1)

          ->  CTE Scan on chain chain_1  (cost=0.00..30.08 rows=1504 width=4) (actual time=0.000..0.003 rows=36 loops=1)

  ->  Append  (cost=0.00..52.60 rows=1501 width=8) (actual time=0.539..4.543 rows=9912 loops=1)

        ->  CTE Scan on chain  (cost=0.00..35.09 rows=501 width=8) (actual time=0.535..1.518 rows=36 loops=1)

              Filter: (s <= 10000)

        ->  Function Scan on generate_series n  (cost=0.00..10.00 rows=1000 width=8) (actual time=1.332..2.301 rows=9876 loops=1)

Planning Time: 2.174 ms

Execution Time: 7.921 ms



EXPLAIN


explain analyze WITH RECURSIVE A(GroupNum, n, RollingSum) AS (
    /* Start with the minimum element */
    SELECT 1, 1, 1
    UNION ALL
    /* Add the next element, but first test if it can be added within the current group */
    SELECT 
        CASE WHEN RollingSum+T.n > 75 THEN GroupNum+1 ELSE GroupNum END,
        T.n,
        CASE WHEN RollingSum+T.n > 75 THEN T.n ELSE RollingSum+T.n END
    FROM A
    JOIN generate_series(1,8000) AS T(n) ON a.n + 1 = T.n
)
SELECT GroupNum, min(n), max(n), sum(n)
FROM A
GROUP BY GroupNum
order by GroupNum


QUERY PLAN


Sort  (cost=1472.97..1473.47 rows=200 width=20) (actual time=9094.284..9094.723 rows=7973 loops=1)

  Sort Key: a.groupnum

  Sort Method: quicksort  Memory: 566kB

  CTE a

    ->  Recursive Union  (cost=0.00..1343.29 rows=4001 width=12) (actual time=0.003..9074.278 rows=8000 loops=1)

          ->  Result  (cost=0.00..0.01 rows=1 width=12) (actual time=0.002..0.002 rows=1 loops=1)

          ->  Hash Join  (cost=0.33..130.33 rows=400 width=12) (actual time=0.568..1.133 rows=1 loops=8000)

                Hash Cond: (t.n = (a_1.n + 1))

                ->  Function Scan on generate_series t  (cost=0.00..80.00 rows=8000 width=4) (actual time=0.000..0.444 rows=8000 loops=8000)

                ->  Hash  (cost=0.20..0.20 rows=10 width=12) (actual time=0.001..0.001 rows=1 loops=8000)

                      Buckets: 1024  Batches: 1  Memory Usage: 9kB

                      ->  WorkTable Scan on a a_1  (cost=0.00..0.20 rows=10 width=12) (actual time=0.000..0.000 rows=1 loops=8000)

  ->  HashAggregate  (cost=120.03..122.03 rows=200 width=20) (actual time=9090.424..9092.248 rows=7973 loops=1)

        Group Key: a.groupnum

        Batches: 1  Memory Usage: 1441kB

        ->  CTE Scan on a  (cost=0.00..80.02 rows=4001 width=8) (actual time=0.004..9077.838 rows=8000 loops=1)

Planning Time: 0.353 ms

Execution Time: 9095.348 ms



EXPLAIN


explain analyze WITH RECURSIVE numbers as (
   select generate_series as gg
   from generate_series(1,10000)
)
,so AS (
  SELECT ARRAY_AGG(g) as g, MAX(gs) as gs, MAX(g) as m
  FROM (
  SELECT
    gg g,
    SUM(gg) OVER (ORDER BY gg) as gs
  FROM numbers
  )
  WHERE gs < 50
  UNION 
  SELECT ARRAY_AGG(g) as g, MAX(gs) as gs, MAX(g) as m
  FROM (
  SELECT
    generate_series g,
    SUM(generate_series) OVER (ORDER BY generate_series) as gs
  FROM (SELECT m+1 m FROM so WHERE m<250 and not m is null) as mmm
  CROSS JOIN generate_series(mmm.m,250)
  )
  WHERE gs<50 and not g is null
)
,so2 as (
    select array[generate_series] as g1,generate_series as g2
    from generate_series((select max(m)+1 from so ),10000)
)
select g,gs 
from so 
where not gs is null
union all 
select g1,g2
from so2
order by g;


QUERY PLAN


Sort  (cost=4477.66..4480.19 rows=1011 width=40) (actual time=22.104..22.602 rows=9983 loops=1)

  Sort Key: so.g

  Sort Method: quicksort  Memory: 1008kB

  CTE so

    ->  Recursive Union  (cost=1089.39..4399.17 rows=11 width=44) (actual time=8.374..15.226 rows=33 loops=1)

          ->  Aggregate  (cost=1089.39..1089.40 rows=1 width=44) (actual time=8.358..8.359 rows=1 loops=1)

                ->  Subquery Scan on unnamed_subquery  (cost=764.39..1064.39 rows=3333 width=12) (actual time=1.885..8.342 rows=9 loops=1)

                      Filter: (unnamed_subquery.gs < 50)

                      Rows Removed by Filter: 9991

                      ->  WindowAgg  (cost=764.39..939.39 rows=10000 width=12) (actual time=1.885..7.768 rows=10000 loops=1)

                            ->  Sort  (cost=764.39..789.39 rows=10000 width=4) (actual time=1.869..2.511 rows=10000 loops=1)

                                  Sort Key: generate_series_1.generate_series

                                  Sort Method: quicksort  Memory: 385kB

                                  ->  Function Scan on generate_series generate_series_1  (cost=0.00..100.00 rows=10000 width=4) (actual time=0.661..1.209 rows=10000 loops=1)

          ->  Aggregate  (cost=330.96..330.97 rows=1 width=44) (actual time=0.206..0.206 rows=1 loops=33)

                ->  Subquery Scan on unnamed_subquery_1  (cost=233.49..323.49 rows=995 width=12) (actual time=0.072..0.205 rows=1 loops=33)

                      Filter: ((unnamed_subquery_1.g IS NOT NULL) AND (unnamed_subquery_1.gs < 50))

                      Rows Removed by Filter: 209

                      ->  WindowAgg  (cost=233.49..285.99 rows=3000 width=12) (actual time=0.068..0.191 rows=211 loops=33)

                            ->  Sort  (cost=233.49..240.99 rows=3000 width=4) (actual time=0.066..0.079 rows=211 loops=33)

                                  Sort Key: generate_series_2.generate_series

                                  Sort Method: quicksort  Memory: 25kB

                                  ->  Nested Loop  (cost=0.01..60.23 rows=3000 width=4) (actual time=0.018..0.055 rows=211 loops=33)

                                        ->  WorkTable Scan on so so_1  (cost=0.00..0.22 rows=3 width=4) (actual time=0.000..0.000 rows=1 loops=33)

                                              Filter: ((m IS NOT NULL) AND (m < 250))

                                              Rows Removed by Filter: 0

                                        ->  Function Scan on generate_series generate_series_2  (cost=0.01..10.01 rows=1000 width=4) (actual time=0.015..0.029 rows=217 loops=32)

  ->  Append  (cost=0.00..28.04 rows=1011 width=40) (actual time=8.377..19.585 rows=9983 loops=1)

        ->  CTE Scan on so  (cost=0.00..0.22 rows=11 width=40) (actual time=8.376..15.241 rows=32 loops=1)

              Filter: (gs IS NOT NULL)

              Rows Removed by Filter: 1

        ->  Subquery Scan on "*SELECT* 2"  (cost=0.26..22.76 rows=1000 width=40) (actual time=0.802..3.624 rows=9951 loops=1)

              ->  Function Scan on generate_series  (cost=0.26..10.26 rows=1000 width=36) (actual time=0.802..2.560 rows=9951 loops=1)

                    InitPlan 2 (returns $3)

                      ->  Aggregate  (cost=0.25..0.26 rows=1 width=4) (actual time=0.007..0.008 rows=1 loops=1)

                            ->  CTE Scan on so so_2  (cost=0.00..0.22 rows=11 width=4) (actual time=0.000..0.003 rows=33 loops=1)

Planning Time: 0.416 ms

Execution Time: 23.323 ms



EXPLAIN