Forum OpenACS Development: New implementation of tree_sortkey

This affects only CVS copies after Dec 6 right?

I have a Dec 3 tree which should be ok right?

As with Gilbert question how are the upper levels will be affected?  Is this something transparent to us or do we have to make some changes on the packages that has been made?

As far as the triggers go ... for starters, your own custom tables could  continue to use the "text" type triggers, there's no need for every table to do it the same way.  Though overall it's cleaner, of course.  The triggers do need changing but the changes are very minor.  Probably the best thing to do is to look at some examples after I commit my changes this weekend and decide if the benefits are worth your changing this stuff for *your* tables.

Breaking the coupling with the collation sequence is the most important benefit of doing it the new way, IMO.

Jun ... no guarantees on the Dec 3rd CVS tree.  I was making some changes to the use of the old style sortkeys (using BETWEEN rather than LIKE in order to pick up the index on tree_sortkey) and was doing some testing before updating.  But ... that's transition code.  We're not making promises that every night's CVS tree will work.  Overall, the nightly tarballs have been in good shape for all but a handfull of nights but I'd consider that "luck".

To use "create or replace" to create a recursive function you first
issue a create function command that returns the proper content type
but is not recursive.  Then you replace that function using "create
or replace" with the final version that is recursive.

It might be considered a hack but it isn't too bad, especially
compared to the hack I did to get recursive functions into PG 7.1
(although that one could be worse.  I did not have to edit any
source code to do it).

Hopefully they'll just support recursive functions directly and we
won't have any trouble.

The current scheme I've got leads to simple enough queries to find all parents, once you get the hang of it:

select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
  where tree_ancestor_p(parents.tree_sortkey, child.tree_sortkey);

Generating the correct prefixes via a recursive SQL function would allow you to say something like

select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
  and parents.tree_sortkey in tree_ancestor_sortkeys(child.tree_sorktey);

Now ... generating the list of parent sortkeys separately and passing a list of literal tree_sortkeys as the right operand to "in" might do so ... but I'm not sure. I may do some testing.

But ... using the GiST index method and defining proper "contains" and "contained by operators would use the index on tree_sortkey and be readable, as well ("@" is the PG "contains" operator):

select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
  and child.tree_sortkey @ parents.tree_sortkey;

Meaning we're home free with just a bit more work.  Cool...

These queries should really be faster than the equivalent "connect by" queries in Oracle.  The penalty we pay, though, is a slight increase in storage and an increase in update/insert/delete times (the time required to calculate and update new tree_sortkeys).  Since these DML operations are much less frequent that selects I really don't care.

As far as the space required for the new tree_sortkeys, after loading up all the openacs.org users, forums, categories and messages the maximum tree_sortkey for acs_objects is 8 bytes + 4 bytes for the variable length counter (text, bit varying, etc are all stored in counter + data form), for a key that's at the 7th level in the object tree.

Not bad.

Of course, more complex sites will have deeper trees with correspondingly longer keys but most nodes won't have more than 128 immediate children, thus taking a byte for each level in the tree.

Actually my checked-out copy's pretty good, and I'll be committing my changes tomorrow.

Using Dave's hack makes finding parents very cool, though the actual technique's quite different than Dave's example, being based entirely on the tree_sortkey for the child node:

select parent_nodes.*
from (select tree_ancestor_keys(acs_object_get_tree_sortkey(:child_object_id)) as tree_sortkey) parent_keys,
  acs_objects parent_nodes
where parent_nodes.object_id = parent_keys.object_id;

And it's even somewhat readable, a bonus! tree_ancestor_keys is the recursive SQL function, and acs_object_get_root_key is necessary because, well, you can play around and figure out why yourselves :)

Kudos to Dave once again for what is truly a deviously sneakily deliciously decadent hack on the PG internal tables!

Limiting the number of number of nodes per-level to 2^15 nodes seems to be too restrictive and it's likely to cause problems as the size of a site grows. A probable problem area in the kernel is the acs_objects table. The tree formed by acs_objects is likely to be wide and shallow, so it's not too hard to imagine more than 2^15 objects with identical context_ids. The length of the key value at each level is currently encoded with one bit. I think it would be prudent to either allocate two bits per-level for encoding the length, thus allowing key lengths of 6,14,22 or 30 bits, or as an alternative the current default key lengths could be changed from 7 and 15 bits to 15 and 31 bits. The first method would allow ~ 2^30 nodes per level while the second method would allow ~ 2^31 nodes per level. The storage requirements for the sortkeys would increase, but you would still have byte aligned data, I don't think the overall increase in query time would be significant. It should still be better than the old text based sortkeys.

There is a comment in acs-kernel/sql/postgresql/postgres.sql that the old text-based sortkey method was limited to 25k nodes per level. This is an incorrect statement. The old text-based sortkeys, for all practical purposes, had no limit on the number of nodes per-level. If you wanted to be pedantic, the limit = 159^159 ~ 1e350, and there was a tradeoff between the depth of the tree and the number of nodes per-level.

Why is a helper function required to get the tree_sortkey for a table when using the tree_ancestor_keys function? I've tried replacing the helper function with a select and I don't see any difference in the cost or execution time of the query. There is a quote in postgres.sql that indicates that the query will not work without the helper function:

"This query will use the index on tree_sortkey to scan acs_objects. The function to grab the tree_sortkey for the node is necessary (and must be defined for each table that uses our hierarchical query scheme) to avoid restrictions on the use of SQL functions that return sets. "

This however, doesn't seem to be the case as shown by the example below.

testtree=# select o.*
testtree-#  from tree_view o,
testtree-#    (select tree_ancestor_keys(acs_objects_get_tree_sortkey(2051)) as tree_sortkey) parents
testtree-#  where o.tree_sortkey = parents.tree_sortkey;
 level |     object_id     | context_id |                       tree_sortkey                       
-------+-------------------+------------+----------------------------------------------------------
     1 |  1                |            | 00000000
     2 |    307            |          1 | 0000000000000000
     3 |      311          |        307 | 000000000000000000000000
     4 |        323        |        311 | 00000000000000000000000000000000
     5 |          371      |        323 | 0000000000000000000000000000000000000000
     6 |            611    |        371 | 000000000000000000000000000000000000000000000000
     7 |              2051 |        611 | 00000000000000000000000000000000000000000000000000000000
(7 rows)

testtree=# explain select o.*
testtree-#  from tree_view o,
testtree-#    (select tree_ancestor_keys(acs_objects_get_tree_sortkey(2051)) as tree_sortkey) parents
testtree-#  where o.tree_sortkey = parents.tree_sortkey;
NOTICE:  QUERY PLAN:

Nested Loop  (cost=0.00..2.03 rows=1 width=32)
  ->  Subquery Scan parents  (cost=0.00..0.00 rows=0 width=0)
        ->  Result  (cost=0.00..0.00 rows=0 width=0)
  ->  Index Scan using acs_objs_tree_skey_idx on acs_objects  (cost=0.00..2.02 rows=1 width=20)

EXPLAIN
testtree=# select o.*
testtree-#  from tree_view o,
testtree-#    (select tree_ancestor_keys((select tree_sortkey from acs_objects where object_id = 2051)) as tree_sortkey) parents
testtree-#  where o.tree_sortkey = parents.tree_sortkey;
 level |     object_id     | context_id |                       tree_sortkey                       
-------+-------------------+------------+----------------------------------------------------------
     1 |  1                |            | 00000000
     2 |    307            |          1 | 0000000000000000
     3 |      311          |        307 | 000000000000000000000000
     4 |        323        |        311 | 00000000000000000000000000000000
     5 |          371      |        323 | 0000000000000000000000000000000000000000
     6 |            611    |        371 | 000000000000000000000000000000000000000000000000
     7 |              2051 |        611 | 00000000000000000000000000000000000000000000000000000000
(7 rows)

testtree=# explain select o.*
testtree-#  from tree_view o,
testtree-#    (select tree_ancestor_keys((select tree_sortkey from acs_objects where object_id = 2051)) as tree_sortkey) parents
testtree-#  where o.tree_sortkey = parents.tree_sortkey;
NOTICE:  QUERY PLAN:

Nested Loop  (cost=0.00..2.03 rows=1 width=32)
  ->  Subquery Scan parents  (cost=0.00..0.00 rows=0 width=0)
        ->  Result  (cost=0.00..0.00 rows=0 width=0)
              InitPlan
                ->  Index Scan using acs_objects_pkey on acs_objects  (cost=0.00..2.02 rows=1 width=12)
  ->  Index Scan using acs_objs_tree_skey_idx on acs_objects  (cost=0.00..2.02 rows=1 width=20)

EXPLAIN
testtree=# 

Overall, the implementation looks good, and it's nice to be able to eliminate the LANG=C requirement and the dependence on the collation order.

But reducing the space overhead seems important to me if we can do so without penalizing ourselves in some other significant way.  There are all sorts of reasons for this.  A simple one - in PG, when you join tables you drag rows around, so the longer rows are the more time is spent in byte-shuffling.  I mentioned the impact on indexes somewhere above in a previous post, I think.

I think the 7-bit/31-bit split is a reasonable compromise.  While the text approach implemented unlimited keys (I think I confused your implementation with Philip's old 2-char-per-level implementation for bboard), 2^31 (2 billion plus) direct ancestors per node should be sufficient.

There's no way to use a delimiter ala the text approach unless we go to unary rather than binary keys! :)  Getting rid of the collation dependency (LANG=C) was the only reason I switched representations...

Have you done the commit already?  What did you need to change in order to move to the 31 bit keys?  I guess what I'm asking is what would I need to change in order to get the 31 bit keys.  I have one table which uses a copy of the acs_objects tree_sortkey insert/update/delete triggers.  Thanks.