Lets say I have this table:

CREATE TABLE nodes (node_path ltree);
INSERT INTO nodes VALUES ('Top.Science');
INSERT INTO nodes VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO nodes VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO nodes VALUES ('Top.Hobbies');
INSERT INTO nodes VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO nodes VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
INSERT INTO nodes VALUES ('Top.Dislikes');
CREATE INDEX ON nodes USING GIST (node_path);
CREATE INDEX ON nodes USING BTREE (node_path);

Notice that following paths are missing in this table:


How can I recursively query this table to get the tree like structure (without those missing rows)?

If the paths were not missing, then the following query would get me the result:

with recursive
base as (
  select node_path, 
         array[row_number() over (order by node_path)] as sort_path
    from nodes 
   where nlevel(node_path) = 1
  union all
  select c.node_path, 
         p.sort_path||row_number() over (order by c.node_path)
    from base p
    join nodes c 
      on subpath(c.node_path, 0, -1) = p.node_path
select * from base order by sort_path;

But because the rows are missing, it breaks the chain. As a result, things like:

nlevel(node_path) = 1

subpath(c.node_path, 0, -1) = p.node_path

don't make sense.

How can I query this to get the tree?

Note that I posted a question on Stack Overflow and I think if I can get an answer to the above question, then I might be able to resolve my SO question too. This current question was born out of the SO question:


1 Answer 1


This is a possible solution:

      SELECT n1.node_path,
             1 AS level
      FROM nodes AS n1
                        WHERE n2.node_path @> n1.node_path
                          AND n2.node_path <> n1.node_path)
      SELECT c.node_path,
             cte.level + 1
      FROM cte
         CROSS JOIN LATERAL (SELECT n1.node_path
                             FROM nodes AS n1
                             WHERE n1.node_path <@ cte.node_path
                               AND n1.node_path <> cte.node_path
                               AND NOT EXISTS (SELECT FROM nodes AS n2
                                               WHERE n1.node_path <@ n2.node_path
                                                 AND n2.node_path <@ cte.node_path
                                                 AND n2.node_path <> n1.node_path
                                                 AND n2.node_path <> cte.node_path)
                            ) AS c(node_path)

I start with the nodes that have no ancestor, and in the recursive step I find direct descendants (with no shorter intermediate descendant).

  • It does seem to work thanks. Though it seems fairly complex for such a simple task. Jul 11 at 8:07
  • You could write an auxiliary SQL function to find the "next descendants" using the NOT EXISTS subquery, then the actual query would look much simpler. Jul 11 at 8:15
  • Sorry, what's an auxiliary SQL function? Jul 11 at 8:28
  • 1
    Something that starts with CREATE FUNCTION get_immediate_descendants(ltree) RETURNS SETOF ltree LANGUAGE sql. Jul 11 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.