By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
Help with an interesting Postgres question: Why isn't an Index Only Scan used on a partition accessed via the parent table?.
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