Best way to count number of descendants from ancestors array?

Question

Table tree is a sample table with ancestors array in PostgreSQL 8.3+:

----+-----------
 id | ancestors 
----+-----------
  1 | {}
  2 | {1}
  3 | {1,2}
  4 | {1}
  5 | {1,2}
  6 | {1,2}
  7 | {1,4}
  8 | {1}
  9 | {1,2,3}
 10 | {1,2,5}

for to get each id count number of descendant, I can do this:

SELECT 1 AS id, COUNT(id) AS descendant_count FROM tree WHERE 1 = ANY(ancestors)
  UNION
SELECT 2 AS id, COUNT(id) AS descendant_count FROM tree WHERE 2 = ANY(ancestors)
  UNION
SELECT 3 AS id, COUNT(id) AS descendant_count FROM tree WHERE 3 = ANY(ancestors)
  UNION
SELECT 4 AS id, COUNT(id) AS descendant_count FROM tree WHERE 4 = ANY(ancestors)
  UNION
SELECT 5 AS id, COUNT(id) AS descendant_count FROM tree WHERE 5 = ANY(ancestors)
  UNION
SELECT 6 AS id, COUNT(id) AS descendant_count FROM tree WHERE 6 = ANY(ancestors)
  UNION
SELECT 7 AS id, COUNT(id) AS descendant_count FROM tree WHERE 7 = ANY(ancestors)
  UNION
SELECT 8 AS id, COUNT(id) AS descendant_count FROM tree WHERE 8 = ANY(ancestors)
  UNION
SELECT 9 AS id, COUNT(id) AS descendant_count FROM tree WHERE 9 = ANY(ancestors)
  UNION
SELECT 10 AS id, COUNT(id) AS descendant_count FROM tree WHERE 10 = ANY(ancestors)

and get result as:

----+------------------
 id | descendant_count
----+------------------
  1 | 9
  2 | 5
  3 | 1
  4 | 1
  5 | 1
  6 | 0
  7 | 0
  8 | 0
  9 | 0
 10 | 0

I guess it should exist that shorter or smart query statement to get same result, is it possible? Maybe like WITH RECURSIVE or create function with loop to generate query?

[Postgres 8.3 was released in 2008 and is unsupported since 2013.](https://www.postgresql.org/support/versioning) You are not actually using that, are you? — Erwin Brandstetter, Nov 18 '18 at 02:00
My case is extend some old example code, and it work in v8.3, I hope the answer of case is effective also. In fact, I test it with v11+ — Liao San Kai, Nov 18 '18 at 14:46

Erwin Brandstetter · Answer 1 · 2018-11-18T09:03:13.753

Looks like a case for a recursive query on a first glance, but this one is simpler:
just unnest, group and count:

SELECT id AS ancestor, COALESCE (a1.id, 0) AS descendants_count
FROM   tree
LEFT   JOIN (
   SELECT a.id, count(*) AS descendant_count
   FROM   tree t, unnest(t.ancestors) AS a(id)
   GROUP  BY 1
   ) a1 USING (id)
ORDER  BY 1;

And, to include ancestors without any descendants at all, throw in the LEFT JOIN.

There is an implicit LATERAL join to the set-returning function unnest(). See:

What is the difference between LATERAL and a subquery in PostgreSQL?

Aside:
If you ever end up in a tight spot where you actually have to use multiple UNION clauses, consider UNION ALL. See:

Find unmatched rows between two tables dynamically

score 1 · Accepted Answer · answered Nov 18 '18 at 10:11

1

Your set of unions is literally just a self join...

SELECT
    tree.id,
    COUNT(descendant.id) AS descendant_count
FROM
    tree
LEFT JOIN
    tree   AS descendant
        ON tree.id = ANY(descendant.ancestors)
GROUP BY
    tree.id

answered Nov 18 '18 at 10:11

MatBailie

83,401
18
103
137

Best way to count number of descendants from ancestors array?

2 Answers2