Title: Tree_sortkey improvements for performance and concurrency on postgresql
Created: Thursday, 13 November 2003
The current implementation of tree_sortkey for acs_objects has 2 serious flaws. The first is that it is easy for a busy system to produce duplicate tree_sortkey (since the current implementation does table scans without locking to determine the next available sortkey). The second is that the performance can be abysmal for larger databases (for example creating a dotlrn community can take 2 minutes on a system with 200k objects). By changing the implementation the performance can be improved by an order of magnitude and the risk of a duplicate tree_sortkey being generated reduced greatly (although not eliminated entirely).
The current implementation uses a single tree_sortkey column in acs_objects and has triggers to maintain the relation between context_id and the tree sortkey.
- Here is the current insert trigger
create function acs_objects_insert_tr () returns opaque as ' declare v_parent_sk varbit default null; v_max_value integer; begin if new.context_id is null then select max(tree_leaf_key_to_int(tree_sortkey)) into v_max_value from acs_objects where context_id is null; else select max(tree_leaf_key_to_int(tree_sortkey)) into v_max_value from acs_objects where context_id = new.context_id; select tree_sortkey into v_parent_sk from acs_objects where object_id = new.context_id; end if; new.tree_sortkey := tree_next_key(v_parent_sk, v_max_value); return new; end;' language 'plpgsql';
The performance and concurrency issues are rooted in the queries to select the max(tree_leaf_key_to_int(tree_sortkey)) for a nodes siblings. It does no locking and in many cases can force a table scan on acs_objects. Since it does not lock the table (and there is no particular row to lock), two processes simulataneously inserting into the same parent can end up with the same v_max_value (openacs.org has 244 duplicated tree_sortkeys in acs_objects -- currently they are all leaf nodes so it has not caused a problem but creating children of any of these would create an malformed tree).
- Forums uses the following code to generate it's tree sortkey
create function forums_mess_insert_tr returns opaque as ' declare v_max_child_sortkey forums_forums.max_child_sortkey%TYPE; v_parent_sortkey forums_messages.tree_sortkey%TYPE; begin if new.parent_id is null then select '''', max_child_sortkey into v_parent_sortkey, v_max_child_sortkey from forums_forums where forum_id = new.forum_id for update; v_max_child_sortkey := tree_increment_key(v_max_child_sortkey); update forums_forums set max_child_sortkey = v_max_child_sortkey where forum_id = new.forum_id; else select coalesce(tree_sortkey, ''''), max_child_sortkey into v_parent_sortkey, v_max_child_sortkey from forums_messages where message_id = new.parent_id for update; v_max_child_sortkey := tree_increment_key(v_max_child_sortkey); update forums_messages set max_child_sortkey = v_max_child_sortkey where message_id = new.parent_id; end if; new.tree_sortkey := v_parent_sortkey || v_max_child_sortkey; return new; end;
It uses max_child_sortkey in forums_forums for assigning the initial tree_sortkey for a thread and uses max_child_sortkey from the parent for generating the childrens tree_sortkey; It also uses select ... for update to lock the row which should insure that no duplicates get created (there is however one dup in the database, two new threads have the same root tree_sortkey although this may be the result of a historical bug in 7.2, OpenACS, or happened via direct manipulation of the DB).
I would like to implement the scheme used for forums with some small modifications:
Add a max_child_sortkey to acs_objects
recreate the tree_sortkey indexes eliminating duplicate entries (disambiguating via context_id), and using object_id as the root node (A change from forums and would eliminate having to have a parent table which contained the max_child_sortkey)
add a unique not null constraint to tree_sortkey
replace the triggers which maintain tree_sortkey
This should be a relatively straightforward upgrade for 4.6 or 5.0 as this code is identical in both places. The only difficulty arises in dealing with duplicated tree_sortkeys with children (and in the case of acs_objects the context_id should allow the tree_sortkey to be corrected with no data lost or incorrect inheritance). And it should be entirely transparent to all existing code.
The same problem exists in a number of other places (most notably in the cr_items table) and should be fixed similiarly.
- Jeff Davis
acs_object__new slowness... http://openacs.org/forums/message-view?message_id=142769
- Patrick McNeill
tree_sortkey race condition, with fix http://openacs.org/forums/message-view?message_id=79102
- Don Baccus
New implementation of tree_sortkey http://openacs.org/forums/message-view?message_id=27402
- Jade Rubick
New documentation for tree_sortkey http://openacs.org/forums/message-view?message_id=112943
- Sebastian Skracic
CONNECT BY solution http://openacs.org/forums/message-view?message_id=16799