TIP: 29
Title: Tree_sortkey improvements for performance and concurrency on postgresql
State: Draft
Type: Project
OpenACS-Version: 5.0
Vote: Pending
Created: Thursday, 13 November 2003
Abstract
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).
Current Implementation
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
- 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).
Proposed change
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
Upgradability
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.
Notes
The same problem exists in a number of other places (most notably in the cr_items table) and should be fixed similiarly.
References
- Jeff Davis
acs_object__new slowness... https://openacs.org/forums/message-view?message_id=142769
- Patrick McNeill
tree_sortkey race condition, with fix https://openacs.org/forums/message-view?message_id=79102
- Don Baccus
New implementation of tree_sortkey https://openacs.org/forums/message-view?message_id=27402
- Jade Rubick
New documentation for tree_sortkey https://openacs.org/forums/message-view?message_id=112943
- Sebastian Skracic
CONNECT BY solution https://openacs.org/forums/message-view?message_id=16799
