PostgreSQL - efficient recursion with aggregation

Question

I have a PostgreSQL 9.1 database that stores a number of "areas" with the borders and I need to work out the effective border for an area. Some of the areas store a border directly (as a PostGIS geometry), while others are composed of multiple child areas, which need to be aggregated together.

For each child are there is an "operation" that determines whether its added to the previous one or subtracted from it or intersected with it. This means that the order matters, too, so there is a sequence number.

I have an aggregate function that work this out, but the problem is that the structure is recursive - a child area may itself be composed of child areas.

A simplified schema:

CREATE TABLE area
    (id integer NOT NULL
    , border geometry NULL
    );
CREATE TABLE area_part
    (parent_area_id integer NOT NULL
    , sequence integer NOT NULL
    , operation text NOT NULL
    , child_area_id integer NOT NULL
    );

Aggregate function signature (it expects the rows ordered by sequence):

CREATE AGGREGATE aggregate_geometry(area geometry, operation text)
-- RETURNS geometry

I've created a normal PL/pgSQL function that calls itself recursively and it works, but it's slow, because it performs many sub-queries. Any ideas on how this can be done more efficiently?

I've also tried writing a query with a recursive CTE:

WITH RECURSIVE area_rec AS
(
    SELECT *
    FROM area
    WHERE id = the_if_of_interest

    UNION ALL

    SELECT c.*
    FROM area_rec rec
    JOIN area_part p ON rec.id = p.parent_area_id
    JOIN area c ON p.child_area_id = c.id
)
SELECT *
FROM area_rec

That's fine for returning all the rows needed for a given area, but I don't know how to then plug the values into my aggregate function. I need some kind of an "aggregate recursive function" here!

Answer 1

You really have to approach this sort of problem in two phases. The first is to create a data set you can aggregate across (recursion, the CTE) and the second is the aggregation. The approach for the aggregation would seem to me to be a window function. Then if you need to you could include this inside another CTE for further post-processing. Remember, CTE's can be nested to an arbitrary depth but you shouldn't need more than two levels for this. You do want to keep this as simple as possible.

Without the function I don't really know what the query would look like but this should be enough to get your started.