Hierarchical query to select `children` from `children`

Question

I have the following table mytable where id is a unique identifier at a given r (resolution) and children is an array of unique id's of r + 1.

id	r	children[]
0	2	{0,2467972595799031808,3620894100405878784,4773815605012725760,5926737109619572736,1315051091192184832}
1152921504606846976	2	{1152921504606846976,1188950301625810944,1170935903116328960,6503197861922996224,6521212260432478208,-6755399441055744000}
0	3	{0,2458965396544290816,3611886901151137792,4764808405757984768,5917729910364831744,1306043891937443840}
1152921504606846976	3	{1152921504606846976,1170935903116328960,1175439502743699456,1157425104234217472,6530219459687219200,-6764406640310484992}
1224979098644774912	3	{1224979098644774912,1242993497154256896,1247497096781627392,1229482698272145408,6241989083535507456,6494190662668255232,1161928703861587968}
0	4	{0,2460091296451133440,3613012801057980416,4765934305664827392,5918855810271674368,1307169791844286464}
1152921504606846976	4	{1152921504606846976,1155173304420532224,1154047404513689600,6531345359594061824,6532471259500904448,-6763280740403642368}
1157425104234217472	4	{1157425104234217472,1159676904047902720,1158551004141060096,6513330961084579840,6514456860991422464,6531345359594061824,1154047404513689600}
1161928703861587968	4	{1161928703861587968,1164180503675273216,1163054603768430592,6495316562575097856,6496442462481940480,6513330961084579840,1158551004141060096}
0	5	{0,2459528346497712128,3612449851104559104,4765371355711406080,5918292860318253056,1306606841890865152}
1152921504606846976	5	{1152921504606846976,1154047404513689600,1154328879490400256,1153202979583557632,6533034209454325760,-6763843690357063680}
1157425104234217472	5	{1157425104234217472,1158551004141060096,1158832479117770752,1157706579210928128,6515019810944843776,6530782409640640512,1153484454560268288}
1161928703861587968	5	{1161928703861587968,1163054603768430592,1163336078745141248,1162210178838298624,6497005412435361792,6512768011131158528,1157988054187638784}
1224979098644774912	5	{1224979098644774912,1226104998551617536,1226386473528328192,1225260573621485568,6244803833302614016,6494753612621676544,1162491653815009280}
0	6	{0,2459598715241889792,3612520219848736768,4765441724455583744,5918363229062430720,1306677210635042816}
1152921504606846976	6	{1152921504606846976,1153062242095202304,1152991873351024640,6533104578198503424,6533174946942681088,-6763773321612886016}
1153202979583557632	6	{1153202979583557632,1153343717071912960,1153273348327735296,6531978678291660800,6532049047035838464,6533104578198503424,1152991873351024640}
1153484454560268288	6	{1153484454560268288,1153625192048623616,1153554823304445952,6530852778384818176,6530923147128995840,6531978678291660800,1153273348327735296}
1157425104234217472	6	{1157425104234217472,1157565841722572800,1157495472978395136,6515090179689021440,6515160548433199104,6530852778384818176,1153554823304445952}
1157706579210928128	6	{1157706579210928128,1157847316699283456,1157776947955105792,6513964279782178816,6514034648526356480,6515090179689021440,1157495472978395136}
0	7	{0,2459563530869800960,3612485035476647936,4765406540083494912,5918328044690341888,1306642026262953984}
1152921504606846976	7	{1152921504606846976,1152991873351024640,1153009465537069056,1152939096792891392,6533210131314769920,-6763808505984974848}
1153202979583557632	7	{1153202979583557632,1153273348327735296,1153290940513779712,1153220571769602048,6532084231407927296,6533069393826414592,1152956688978935808}
1153484454560268288	7	{1153484454560268288,1153554823304445952,1153572415490490368,1153502046746312704,6530958331501084672,6531943493919571968,1153238163955646464}
1157425104234217472	7	{1157425104234217472,1157495472978395136,1157513065164439552,1157442696420261888,6515195732805287936,6530817594012729344,1153519638932357120}
1157706579210928128	7	{1157706579210928128,1157776947955105792,1157794540141150208,1157724171396972544,6514069832898445312,6515054995316932608,1157460288606306304}
1157988054187638784	7	{1157988054187638784,1158058422931816448,1158076015117860864,1158005646373683200,6512943932991602688,6513929095410089984,1157741763583016960}

Problem

Given id and r I want to get all child id's for r + x.

Example

id = 1152921504606846976 and r = 2 I know the children are {1152921504606846976, 1188950301625810944, 1170935903116328960, 6503197861922996224, 6521212260432478208, -6755399441055744000} and they are resolution r + 1 = 3. I want to get all children at r = 6

Current Solution

I came up with this query to get the child id's for a given id and r.

WITH lvl1 AS (SELECT children[1] AS id FROM mytable WHERE id = ANY(ARRAY[1152921504606846976]) AND r = 2 GROUP BY children[1]),
     lvl2 AS (SELECT UNNEST(children) AS gid FROM mytable WHERE id IN (SELECT id FROM lvl1) AND r = 3 GROUP BY UNNEST(children)),
     lvl3 AS (SELECT UNNEST(children) AS gid FROM mytable WHERE id IN (SELECT id FROM lvl2) AND r = 4 GROUP BY UNNEST(children)),
     lvl4 AS (SELECT UNNEST(children) AS gid FROM mytable WHERE id IN (SELECT id FROM lvl3) AND r = 5 GROUP BY UNNEST(children)),
     lvl5 AS (SELECT UNNEST(children) AS gid FROM mytable WHERE id IN (SELECT id FROM lvl4) AND r = 6 GROUP BY UNNEST(children))
SELECT id FROM lvl5;

Query plan

Group  (cost=223908.95..223909.03 rows=10 width=8) (actual time=389.088..389.186 rows=326 loops=1)
   Group Key: (unnest(mytable.children))
   ->  Sort  (cost=223908.95..223908.98 rows=10 width=8) (actual time=389.074..389.105 rows=671 loops=1)
         Sort Key: (unnest(mytable.children))
         Sort Method: quicksort  Memory: 25kB
         ->  ProjectSet  (cost=179975.80..223908.79 rows=10 width=8) (actual time=314.588..389.004 rows=671 loops=1)
               ->  Hash Semi Join  (cost=179975.80..223908.73 rows=1 width=76) (actual time=314.585..388.928 rows=96 loops=1)
                     Hash Cond: (mytable.id = (unnest(mytable_1.children)))
                     ->  Foreign Scan on mytable  (cost=100.00..44012.41 rows=7818 width=84) (actual time=38.185..111.931 rows=7292 loops=1)
                     ->  Hash  (cost=179875.67..179875.67 rows=10 width=8) (actual time=276.373..276.379 rows=96 loops=1)
                           Buckets: 1024  Batches: 1  Memory Usage: 12kB
                           ->  Group  (cost=179875.50..179875.57 rows=10 width=8) (actual time=276.315..276.349 rows=96 loops=1)
                                 Group Key: (unnest(mytable_1.children))
                                 ->  Sort  (cost=179875.50..179875.52 rows=10 width=8) (actual time=276.302..276.314 rows=181 loops=1)
                                       Sort Key: (unnest(mytable_1.children))
                                       Sort Method: quicksort  Memory: 25kB
                                       ->  ProjectSet  (cost=136069.06..179875.33 rows=10 width=8) (actual time=216.479..276.273 rows=181 loops=1)
                                             ->  Hash Semi Join  (cost=136069.06..179875.27 rows=1 width=76) (actual time=216.475..276.247 rows=26 loops=1)
                                                   Hash Cond: (mytable_1.id = (unnest(mytable_2.children)))
                                                   ->  Foreign Scan on mytable mytable_1  (cost=100.00..43900.39 rows=2217 width=84) (actual time=32.290..91.850 rows=2432 loops=1)
                                                   ->  Hash  (cost=135968.94..135968.94 rows=10 width=8) (actual time=184.168..184.172 rows=26 loops=1)
                                                         Buckets: 1024  Batches: 1  Memory Usage: 10kB
                                                         ->  Group  (cost=135968.76..135968.84 rows=10 width=8) (actual time=184.133..184.146 rows=26 loops=1)
                                                               Group Key: (unnest(mytable_2.children))
                                                               ->  Sort  (cost=135968.76..135968.79 rows=10 width=8) (actual time=184.119..184.125 rows=41 loops=1)
                                                                     Sort Key: (unnest(mytable_2.children))
                                                                     Sort Method: quicksort  Memory: 25kB
                                                                     ->  ProjectSet  (cost=92207.22..135968.60 rows=10 width=8) (actual time=130.968..184.097 rows=41 loops=1)
                                                                           ->  Hash Semi Join  (cost=92207.22..135968.54 rows=1 width=76) (actual time=130.963..184.081 rows=6 loops=1)
                                                                                 Hash Cond: (mytable_2.id = (unnest(mytable_3.children)))
                                                                                 ->  Foreign Scan on mytable mytable_2  (cost=100.00..43860.71 rows=233 width=84) (actual time=33.208..86.242 rows=812 loops=1)
                                                                                 ->  Hash  (cost=92107.09..92107.09 rows=10 width=8) (actual time=97.736..97.738 rows=6 loops=1)
                                                                                       Buckets: 1024  Batches: 1  Memory Usage: 9kB
                                                                                       ->  Group  (cost=92106.92..92106.99 rows=10 width=8) (actual time=97.712..97.717 rows=6 loops=1)
                                                                                             Group Key: (unnest(mytable_3.children))
                                                                                             ->  Sort  (cost=92106.92..92106.94 rows=10 width=8) (actual time=97.699..97.700 rows=6 loops=1)
                                                                                                   Sort Key: (unnest(mytable_3.children))
                                                                                                   Sort Method: quicksort  Memory: 25kB
                                                                                                   ->  ProjectSet  (cost=200.00..92106.75 rows=10 width=8) (actual time=81.586..97.675 rows=6 loops=1)
                                                                                                         ->  Nested Loop  (cost=200.00..92106.70 rows=1 width=76) (actual time=81.581..97.669 rows=1 loops.
.=1)
                                                                                                               Join Filter: (mytable_3.id = (mytable_4.children[1]))
                                                                                                               Rows Removed by Join Filter: 271
                                                                                                               ->  Foreign Scan  (cost=100.00..48231.69 rows=1 width=8) (actual time=3.300..3.301 rows=1 l.
.oops=1)
                                                                                                                     Relations: Aggregate on (mytable mytable_4)
                                                                                                               ->  Foreign Scan on mytable mytable_3  (cost=100.00..43867.71 rows=583 width=84) (actual time=68..
.037..84.110 rows=272 loops=1)
 Planning Time: 0.349 ms
 JIT:
   Functions: 37
   Options: Inlining false, Optimization false, Expressions true, Deforming true
   Timing: Generation 1.059 ms, Inlining 0.000 ms, Optimization 0.426 ms, Emission 9.890 ms, Total 11.375 ms
 Execution Time: 391.161 ms

Question

This query becomes slower and slower the higher the resolution r gets, as there are more and more rows (by factor 3) from resolution to the next higher r. Where could I optimize this query (please see the Notes about what I did)? What my query does is essentially recursion, would a proper query using RECURSION improve performance? Thanks!

Notes

• mytable has Millions of rows
• table has all relevant indices
• I updated the statistics and ran ANALYSE on the table
• maximum number of children is 7
• all r resolutions are connected = at each resolution I know with 100% certainty that there are children.
• The query becomes very slow for higher resolutions.
• A child of one parent id can also be a child of another id.