Re: SELECT all the rows where id is children of other node.

From: Francisco Olarte <folarte(at)peoplecall(dot)com>
To: pabloa98 <pabloa98(at)gmail(dot)com>
Cc: Rob Sargent <robjsargent(at)gmail(dot)com>, Postgres General <pgsql-general(at)postgresql(dot)org>
Subject: Re: SELECT all the rows where id is children of other node.
Date: 2019-08-21 09:35:53
Message-ID: CA+bJJbzW8F8F_A3cYypk6qiu3tp34f2nXU2uBS3enf1jJ5cjCw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

Pablo:

On Tue, Aug 20, 2019 at 6:49 PM pabloa98 <pabloa98(at)gmail(dot)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.

In response to

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Johann 'Myrkraverk' Oskarsson 2019-08-21 12:31:16 Re: Retroactively adding send and recv functions to a type?
Previous Message Karl Martin Skoldebrand 2019-08-21 08:18:23 SV: Databases and servers