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.
I am currently working on an application which needs to store ordered trees in a PostgreSQL database. The elements in a single tree may be re-ordered by the user. For the trees themselves, I'm using something very similar to what depesz's post describes. There is a catch, however.
In order to allow the user to change the ordering of the tree's elements, the easiest way is to set the "moved" element's ordering index to ( 1 + ordering index of the element it's being added after). However, if element B has been moved after element A, and element C is then moved to after element A as well, this would cause an unique index violation. This may also happen on insertion (if a new element D is inserted after element A). Because of that, the ordering of the tree's elements need to be reset whenever such an operation takes place.
For starters, it is necessary to start by moving the objects "out of the way" before actually re-ordering: for example, if 3 rows are present with ordering indexes 2, 3 and 4, the middle row would have its ordering index set to 4 and that would fail.
UPDATE objects SET object_ordering = object_ordering + ( SELECT 1 + 2 * max( object_ordering ) FROM objects );
It is then possible to reset the ordering index; the "trick" I used to do that relies on window functions, so it will only work on PostgreSQL 8.4 or 9.x.
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 ) o2 WHERE o1.object_id = o2.object_id;