1

Situation

I have two simple tables, one called "node_relations" and one called "node_information". The table "node_relations" represents a simple parent-child hierarchy, having only two columns "id" and "parent", with "parent" referring to the "id" column. "node_information" on the other hand stores custom information about the nodes in our hierarchy, each entry identified by a column called "info_id". A third table referring to "node_relations"."id" and "node_information"."info_id" relates those two tables in the way of a many-many-relationship.

For a given entry of the "node_information" table, I want to list all entries of "node_relations" that are either directly related by the third table or a descendant of such a related entry. This can easily be done by using PostgreSQLs "WITH RECURSIVE" functionality, creating a temporary working table containing the list of all ancestors for each node, and then listing all nodes containing an ancestor related to the given "node_information" entry. However, as the "node_relations" table grows, this gets awfully inefficient, at least the way I'm currently doing this.

My problem seems to be that PostgreSQL first completely creates the whole recursive table, and only when joining it with my other tables discards the obsolete rows. Is there a way to tell PostgreSQL to start the recursion only?

Details

To reproduce, create a table such with the following query:

    /* Create table storing parent-child relations */
    CREATE TABLE node_relations(
            id INTEGER NOT NULL, 
            parent INTEGER, 
            PRIMARY KEY (id), 
            FOREIGN KEY (parent) REFERENCES node_relations(id)
    );

Fill it with random data:

    /* Random references created as (random()*generate_series+0.5)::int in order to only refer to nodes with smaller id. */
    /* This, in combination with the removal of self-references, makes sure there are no cycles */
    INSERT INTO node_relations(id,parent) 
    SELECT generate_series, (random()*generate_series+0.5)::int 
    FROM generate_series(1,1000000);
    UPDATE node_relations SET parent=NULL WHERE id=parent;

Look up an interesting entry. In my case, it was 56:

    /* Find the entry which is refered the most often.*/
    SELECT parent as id,count(*) as refs 
    FROM node_relations GROUP BY parent 
    ORDER by refs DESC LIMIT 1;

Then list all descendants for that specific node, which works quite smoothly:

    WITH RECURSIVE hierarchy(root_id,id) AS (
            VALUES(56,56) UNION ALL
            SELECT hierarchy.root_id,node_relations.id FROM node_relations
            INNER JOIN hierarchy ON hierarchy.id=node_relations.parent
    ) 
    SELECT root_id,id FROM hierarchy;

However, while returning the same result, the following query seems to create the whole hierarchy and then discards the part that is not required:

    WITH RECURSIVE hierarchy(root_id,id) AS (
            SELECT id,id FROM node_relations UNION ALL
            SELECT hierarchy.root_id,node_relations.id FROM node_relations
            INNER JOIN hierarchy ON hierarchy.id=node_relations.parent
    ) 
    SELECT count(*) FROM hierarchy WHERE root_id=56;

Is there a way to restructure my recursive temporary table such that only the relevant rows are created? I would expect PostgreSQL to show the same (inefficient) behavior when joining rows as in my last example. Is there a way to make PostgreSQL start the recursion only on the limited set to begin with?

Semi-Answer

By creating a temporary table "temp_table" containing the IDs of the nodes related to the "node_information" entry, we could adjust the last of the above queries by replacing the first instance of "node_relations" by "temp_table". Is this the way to go?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.