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.
Yesterday I ran into something rather weird with PostgreSQL (9.1rc).
A bit of context first: the database in which the problem occurred contains tables which represent an ordered tree, something quite similar to what depesz's post describes; in addition, most of the operations on the structure of the tree are done through stored procedures, and these stored procedures usually re-order the tree's items when they're done.
The main table had a trigger that basically looked like the following:
CREATE OR REPLACE FUNCTION objects_bu( ) RETURNS TRIGGER SECURITY DEFINER AS $objects_bu$ BEGIN -- Various other checks here IF OLD.object_ordering = NEW.object_ordering AND OLD.object_id_parent IS NOT DISTINCT FROM NEW.object_id_parent THEN RETURN NEW; END IF; IF NEW.object_id_parent IS NULL THEN NEW.object_ordering_path := to_char( NEW.object_ordering , '000000000000' ); ELSE SELECT object_ordering_path || '/' || to_char( NEW.object_ordering , '000000000000') INTO NEW.object_ordering_path FROM objects WHERE object_id = NEW.object_id_parent; END IF; UPDATE objects SET object_ordering_path = regexp_replace( object_ordering_path , '^' || OLD.object_ordering_path, NEW.object_ordering_path ) WHERE object_id IN ( SELECT object_id_child FROM objects_tree WHERE object_id_parent = NEW.object_id AND ot_depth > 0 ); RETURN NEW; END; $objects_bu$ LANGUAGE plpgsql; CREATE TRIGGER objects_bu BEFORE UPDATE ON objects FOR EACH ROW EXECUTE PROCEDURE objects_bu( );
In most cases, this trigger works: it does what it's supposed to do, and the ordering path column is updated just fine. However, if an operation that causes this trigger to execute is followed by another update in the same transaction (for example calling the function that resets the ordering indexes), things get really weird.
For example, if the table contains 3 entries, two of which are children of another, and you try to invert both items (by setting the first item's ordering index to the second item's, plus one) then reorder the tree, it will look like the inversion of the child items did not work. This will not happen systematically - sometimes it will work, but in most cases it won't. Upon closer examination, it appears that:
- the inversion itself works,
- the first update of the re-ordering code sometimes updates all 3 rows (which is what it is supposed to do), but in many cases only changes the rows that have not been updated,
- because that first update "failed" silently, the second update of the re-ordering query will do exactly what it's supposed to do, but since the first child still has its low, non-reordered index, it will stay where it was before the operation.
The whole mess is caused by the last update in the trigger above. It somehow makes PostgreSQL a little confused. To fix it, moving that update to another trigger, which is executed after the update, suffices - and is more logical anyway.
What I am unhappy about here is not the fact that doing updates on the table in a "before update" trigger on the same table does not work. That was a rather silly idea to begin with. But it seems to me that PostgreSQL should behave consistently when that happens - either make it work, or cause an error - instead of going Hannibal Lecter and randomly failing in silence.
I have not reported this bug yet, because it seems related to bug #6123 and I know there is some work in progress on that. Still, this bug results in a behaviour that's weird enough to be worth mentioning.