> On Aug 21, 2019, at 3:35 AM, Francisco Olarte <fola...@peoplecall.com> wrote:
>
> Pablo:
>
> On Tue, Aug 20, 2019 at 6:49 PM pabloa98 <pablo...@gmail.com> wrote:
>> Thank you for your responses Rob. Appreciated. The problem with recursive
>> queries is that they are executed several times and it has and impact in
>> performance.
>> I need a subset of those rows and I want them in one pass.
>> I discovered that ltree extension could be useful. I will play with it
>> today. I am sure there's a way to find al the nodes in O(n) time with n =
>> size of the resulset ...
>
> Unless you have some extra conditions in a table ( like
> "autoincremented immutable primary key and parents are always created
> before childs" ) I think your problem of "get all the descendant ( i
> do not like to call them children ) nodes of a given id" can not be
> solved in one pass.
>
> I mean, if you are getting descendants of the node N1, you need to
> read the last node, NL, of the table to know if it is a child of N1.
> But then you have to read the table again to find childs of NL.
>
> Of course, if you have something like "hierarchical ids" you can
> traverse ordering by it and know NL MUST be childless, and build the
> tree rooted on node N1 as you go, but without some of this conditions
> I do not think it can be done in an "ideal" db ( which lets you scan
> in any order you can define from just a row without cost ) in one scan
> ( storing and prunning the whole tree as you go is cheating ).
>
> Also, if your node ids come from a serial and are immutables, or you
> take a little care when mutating them, you can do it traversing by id,
> but you need a full scan, a recursive query with several index scans
> may easily be faster in wide trees.
>
>
> Francisco Olarte.
If you accept Francisco’s thesis then you may be interested in this
with recursive descendants (last, children) as
(select c.c, array[null::int] from kids c where not exists (select 1 from kids
p where c.c = p.p)
union all
select k.p, array[k.c] || l.children from kids k, descendants l where k.c =
l.last)
select a.last, array_agg(distinct(a.kids))as clan from (select last,
unnest(array_remove(children, null)) as kids from descendants where children[1]
is not null) as a group by last order by last
last | clan
------+--------------------------
1 | {2,3,4,21,22,23,221,222}
2 | {21,22,23,221,222}
22 | {221,222}
(3 rows)
No comment on performance other than to say that if you are interested in the
result for a given seed parent then performance would likely correlate with the
average depth of your lineages.
I believe the ascending order of the members of each clan is completely
fortuitous unless it’s a consequence of distinct?
