[ N O C T E R N I T Y ] Contributing to the general pollution of the internet

PostgreSQL ordered trees, final post

Well, at least I hope it will be the last ;-p

I have recently posted a little about my attempts at making ordered tree structures work in PostgreSQL. While the initial approach works quite well with a single update, trying to re-order the whole tree triggers incoherent behaviour, even with this workaround applied. Because of that, I have given up on triggers and re-implemented the whole ordering code as stored procedures.

A bit of context first, as every case is different:

• the tree is rarely modified, so bad performance isn't much of an issue there;
• it is however very likely for the tree to be modified concurrently;
• all updates to the tree are done through stored procedures, which all lock the whole table before updating anything and then call the re-ordering function once they're done;
• there is at the most one update to the tree for each transaction.

The approach I chose is to compute all ordering paths when the tree is being modified, storing the results in a temporary table, then re-ordering the real table based on these values. Not the most efficient way of doing things, but it has the advantage of actually working.

I started by removing the extra ordering path column, and all ordering triggers.

ALTER TABLE objects
        DROP COLUMN object_ordering_path CASCADE;

DROP TRIGGER objects_ordering_bi ON objects;
DROP TRIGGER objects_ordering_bu ON objects;
DROP TRIGGER objects_ordering_au ON objects;

DROP FUNCTION objects_ordering_bi( );
DROP FUNCTION objects_ordering_bu( );
DROP FUNCTION objects_ordering_au( );

The next step was to create a function which computes ordering paths for all known objects. This function needs to go through the objects by order of increasing depth, to make sure that the path to an object's parent has been computed before the path to the object is. It uses a table with two fields: the object's identifier and path.

CREATE OR REPLACE FUNCTION objects_compute_paths( )
                RETURNS VOID
                STRICT VOLATILE
                SECURITY INVOKER
        AS $objects_compute_paths$
DECLARE
        o_id INT;
        o_parent INT;
        o_ordering INT;
        o_path TEXT;
BEGIN
        FOR o_id , o_parent , o_ordering IN
                SELECT o.object_id , o.object_id_parent , o.object_ordering
                        FROM objects o
                                INNER JOIN objects_tree ot
                                        ON ot.object_id_child = o.object_id
                        GROUP BY o.object_id , o.object_id_parent , o.object_ordering
                        ORDER BY MAX( ot.ot_depth )
        LOOP
                IF o_parent IS NULL THEN
                        o_path := '';
                ELSE
                        SELECT INTO o_path
                                        object_ordering_path || '/'
                            FROM objects_ordering
                            WHERE object_id = o_parent;
                END IF;
                o_path := o_path || to_char( o_ordering , '000000000000' );
                INSERT INTO objects_ordering VALUES ( o_id , o_path );
        END LOOP;
END;
$objects_compute_paths$ LANGUAGE plpgsql;

Finally the re-ordering function needs to be replaced so it creates the temporary table, calls the function above to fill it, and then uses that table instead of the main table to re-order the objects.

CREATE OR REPLACE FUNCTION objects_reorder( )
                RETURNS VOID
                STRICT VOLATILE
                SECURITY INVOKER
        AS $objects_reorder$
BEGIN
        -- Create and fill temporary table
        CREATE TEMPORARY TABLE objects_ordering (
                object_id               INT NOT NULL PRIMARY KEY ,
                object_ordering_path    TEXT NOT NULL
        ) ON COMMIT DROP;
        PERFORM objects_compute_paths( );

        -- Move all rows out of the way
        UPDATE objects SET object_ordering = object_ordering + (
                        SELECT 1 + 2 * MAX( object_ordering ) FROM objects );

        -- Re-order objects
        UPDATE objects o1 SET object_ordering = 2 * o2.rn
                FROM ( SELECT object_id , row_number() OVER(
                                ORDER BY object_ordering_path ) AS rn
                        FROM objects_ordering ) o2
                WHERE o1.object_id = o2.object_id;
END;
$objects_reorder$ LANGUAGE plpgsql;

Note: there is no object_ordering_path column in the main table any more, but since the objects are always sorted correctly, it is possible to select using the object_ordering integer column to order the objects.