如何自下而上遍历树以计算 PostgreSQL 中节点值的（加权）平均值？

Question

典型的例子例如在 PostgreSQL 中对整棵树求和是使用 WITH RECURSIVE (Common Table Expressions)。但是，这些示例通常从上到下，将树展平并对整个结果集执行聚合函数。对于我要解决的问题，我还没有找到合适的示例（在 Whosebug、Google 等）：

考虑一棵不平衡的树，其中每个节点都可以有一个关联值。大多数值都附加到叶节点，但其他值也可能有值。如果一个节点（无论是否为叶子）有一个明确的附加值，这个值可以直接使用而不需要进一步计算（子树可以忽略）。如果该节点没有值，则该值应计算为其直接子节点的平均值。

但是，由于 none 个节点保证有附加值，我需要自下而上以获得总平均值。简而言之，从叶子开始，我需要将 AVG() 应用于每组兄弟节点，并将此（中间）结果用作父节点的值（如果它具有 none）。该父项的（新）值（明确附加，或其子项的平均值）依次用于计算下一级的平均值（父项及其兄弟项的平均值）。

示例情况：

A
+- B (6)
+- C
   +- D
      +- E (10)
      +- F (2)
+- H (18)
   +- I (102)
   +- J (301)

我需要计算 A 的平均值，它应该是 10（因为 (6+6+18)/3 = 10 和 I、J 被忽略了）。

Answer 1

您的数据可以存储为：

create table tree(id int primary key, parent int, caption text, node_value int);
insert into tree values
(1, 0, 'A', null),
(2, 1, 'B', 6),
(3, 1, 'C', null),
(4, 3, 'D', null),
(5, 4, 'E', 10),
(6, 4, 'F', 2),
(7, 1, 'H', 18),
(8, 7, 'I', 102),
(9, 7, 'J', 301);

进行自下而上聚合的最简单方法是递归函数。

create or replace function get_node_value(node_id int)
returns int language plpgsql as $$
declare
    val int;
begin
    select node_value
    from tree 
    where id = node_id
    into val;
    if val isnull then
        select avg(get_node_value(id))
        from tree
        where parent = node_id
        into val;
    end if;
    return val;
end;
$$;

select get_node_value(1);

 get_node_value 
----------------
             10
(1 row)

Test it here.

可以在 sql 函数中实现相同的目的。功能代码不是很明显，但可能比plpgsql.

快一点

create or replace function get_node_value_sql(node_id int)
returns int language sql as $$
    select coalesce(
        node_value,
        (
            select avg(get_node_value_sql(id))::int
            from tree
            where parent = node_id
        )
    )
    from tree 
    where id = node_id;
$$;

使用 cte 从下往上查看树并不是特别复杂。在这种特殊情况下，困难在于应该分别计算每个级别的平均值。

with recursive bottom_up(id, parent, caption, node_value, level, calculated) as (
    select 
        *, 
        0, 
        node_value calculated
    from tree t
    where not exists (
        select id
        from tree
        where parent = t.id)
union all
    select 
        t.*, 
        b.level+ 1,
        case when t.node_value is null then b.calculated else t.node_value end
    from tree t
    join bottom_up b on t.id = b.parent
)

select id, parent, caption, avg(calculated)::int calculated
from (
    select id, parent, caption, level, avg(calculated)::int calculated
    from bottom_up
    group by 1, 2, 3, 4
    ) s
group by 1, 2, 3
order by 1;

Test it here.

如何自下而上遍历树以计算 PostgreSQL 中节点值的（加权）平均值？

How can I traverse a tree bottom-up to calculate a (weighted) average of node values in PostgreSQL?

sql

postgresql

tree

recursive-query

common-table-expression