Forum OpenACS Q&A: Great tree_sortkey Documentation!

Collapse
Posted by Frank Bergmann on
Hi,

we (Toni Vila, Juanjo Ruiz and myself) have started porting Project/Open to PostgreSQL, so the tree_sortkey documentation was a great start for learning how to reorganize the hierarchical parts of our code such as cost centers, menus, employees, etc. Worked out reasonably well...

However, I am wondering why the tree_sortkey stuff is restricted to the PosgresSQL implementation only. The implementation could work with the same code both on Oracle and PostgreSQL (when using VARCHAR instead of SET VARYING..), which would reduce the need to maintain two different implementations of acs_object_types for example and thus save time and debugging hassle...

Bests,
Frank

http://www.project-open.org/

Collapse
Posted by Don Baccus on
First, the history lesson ... ACS 4.x was originally written for Oracle, and took advantage of that RDBMS's hierarchical queries (CONNECT BY).  The tree_sortkey mechanism for PG was developed by Dan Wickstrom and myself to give us a way to work with trees in Postgres when we began the migration project.

Adopting this for Oracle would've required a lot of rewriting of existing Oracle datamodels and queries, not to mention the generation of a great many upgrade scripts.  Far too much work for us to consider at the time on top of the migration work, the kernel work for the support of multiple DBs, the fixing of a very very large number of bugs in ACS 4.x, etc.

It also would've violated our goal of being able to support existing ArsDigita ACS 4.x Oracle packages directly and without modification with our OpenACS core.  The simplicity of the migration process from traditional aD ACS 4.x to the Oracle version of OpenACS was extremely important early in the project - we picked up a fair number of skilled people for the project this way.

Now ... when OpenForce wrote the Forums package, they did use sortkeys in the Oracle version.  I helped them figure out how to do it - turns out the datatype that's wanted is RAW, not VARCHAR (VARCHAR would have the same problems it had when we first tried it in Postgres).  Works fine.

Why not migrate over entirely?  Well, to be honest, I want to investigate the hierarchical queries supported in (I think) PG 8.1 or whatever 7.5 got renamed to, to see if we can get rid of the sortkeys.

Because the sortkeys do take up a fair amount of space, and slow insertion of objects, without providing any particular benefit in execution speed AFAICT.  You also have to add a sortkey for every class of hierarchical query you want to support, i.e. forums have the basic object tree_sortkey and the forum_message type itself has a second tree_sortkey used to do the threaded post mapping.

Oracle 9 and 10 have both removed some of the most annoying restrictions on CONNECT BY, too, making those queries easier to right.

Moving away from tree_sortkeys is a lot easier than moving to them, because you only have to rewrite queries, not the datamodel (other than to remove tree_sortkeys if we want).

Of course a lot depends here on the efficiency of the PG hierarchical queries.

Now before the PG folks announced the addition of hierarchical queries I had been thinking about moving in the sortkey direction for Oracle, too, long-term for the reasons you mention but moving the opposite direction is more attractive now (assuming, once again, that the PG folks have done a good job implementing hierarchical queries).

Collapse
Posted by Frank Bergmann on
Hi Don,

thanks for the in-depth reply.

<blockquote> would have the same problems it had when we first
tried it in Postgres
</blockquote>

Could you explain these problem, please? We've added tree_sortkey to our "im_menu" object so far at Project/Open using VARCHAR and didn't encounter any problems yet. However, there are very few menu objects (some 30), so we are actually using a TCL procedure to calculate the sortkeys. Very slow and ugly, but it works for both Oracle and Postgres...

Bests,
Frank

http://www.project-open.com/

Collapse
Posted by Nis Jørgensen on
Don, could you provide a link to the PG announcement you are talking about?

I have seen the patch here: http://themes.freshmeat.net/projects/hier_pg/

but not been able to find anywhere a statement about this being adopted by mainstream PG.

Collapse
Posted by Don Baccus on
Nils, it's been on their todo list for some time ... I think SQL 99 calls them recursive queries or something like that, I'll need to do some research.

Frank, you should just take the Oracle sortkey code for forums, look in forums/sql/oracle/forums-messages-create.sql and forums-tree-create.sql.  Also acs-kernel/sql/oracle/tree-create.sql which creates the underlying package to manipulate keys.

RAW is a form of variable length byte storage that doesn't suffer from collation issues as does VARCHAR when you're using multibyte characters.  They're used much like VARCHARs as you'll see when you inspect the code.

Still, it would be best to use native Oracle CONNECT BY queries I believe as we've done everywhere in the toolkit other than in forums.

Hi Tree-Experts,

we are checking the tree_sortkey code and have already adapted it for our Project objects.

However, I'm wondering after reading all the documentation, comments etc. how the system deals with the case that a parent gets the 257th child.

According to the new varbit approach, children's subkeys are stored in a single-byte value (max. 256). So when the 257th child is being added, the encoding length needs to become two bytes instead of one byte, right? (It seems to get to 4 bytes though...)

However, in the same moment when adding the 257th child you need to upgrade all the other children of the same parent to work with a new two-byte key instead of a one-byte value.

We are experiencing some strange effects with our Projects when adding more then 127 subprojects. It seems to be 127 instead of 256 because the system seems to revert to a 4 byte representation with a negative sign for some reasons. Please find below a listing.

We have checked the code then and I haven't seen any code in the acs_objects_insert_tr that would deal the cases above. Also, acs_objects_update_tr contains some code that deals with the case that the object_id or the context_id change of an object, but no about the case of a code length change.

Maybe I missed something...

Bests,
Frank

http://www.project-open.com/



project_id | parent_id |                          tree_sortkey
------------+-----------+------------------------------------------------------------------
      2095 |          | 10000000000000000000110000010111
      2112 |      2095 | 1000000000000000000011000001011100000000
      2113 |      2095 | 1000000000000000000011000001011100000001
      2114 |      2095 | 1000000000000000000011000001011100000010
      2115 |      2095 | 1000000000000000000011000001011100000011
      2116 |      2095 | 1000000000000000000011000001011100000100
      2117 |      2095 | 1000000000000000000011000001011100000101
      2118 |      2095 | 1000000000000000000011000001011100000110
      2119 |      2095 | 1000000000000000000011000001011100000111

...

      2237 |      2095 | 1000000000000000000011000001011101111101
      2238 |      2095 | 1000000000000000000011000001011101111110
      2239 |      2095 | 1000000000000000000011000001011101111111
      2240 |      2095 | 1000000000000000000011000001011110000000000000000000000010000000
      2241 |      2095 | 1000000000000000000011000001011110000000000000000000000010000001
      2242 |      2095 | 1000000000000000000011000001011110000000000000000000000010000010
      2243 |      2095 | 1000000000000000000011000001011110000000000000000000000010000011
      2244 |      2095 | 1000000000000000000011000001011110000000000000000000000010000100
      2245 |      2095 | 1000000000000000000011000001011110000000000000000000000010000101
      2246 |      2095 | 1000000000000000000011000001011110000000000000000000000010000110
      2247 |      2095 | 1000000000000000000011000001011110000000000000000000000010000111
      2248 |      2095 | 1000000000000000000011000001011110000000000000000000000010001000
      2249 |      2095 | 1000000000000000000011000001011110000000000000000000000010001001

Collapse
Posted by Nis Jørgensen on
Dun, Oracles "CONNECT BY" and SQL99 recursive queries are two quite different beasts. I am not sure which one you expect will be included into PG

This quite recent thread discusses the matter

http://archives.postgresql.org/pgsql-hackers/2004-06/msg00969.php

and seems to indicate that

- "CONNECT BY", or at least the currently existing implementation, will not be included any time soon.
- SQL99 recursion had not been implemented then.

/Nis

BTW: How come most mail archives suck so greatly  for  viewing articles by thread (ie the way you want to do it 99% of the time).

Collapse
Posted by Don Baccus on
Frank, key values between 0 and 127 are encoded in a single byte.  Key values greater than 128 are stored as the value + 2^32 in four bytes.

What "strange effects" are you seeing?  The keys sort correctly using this scheme...

Collapse
Posted by Don Baccus on
I meant 2^31 not 2^32 up there :(

Also it's important to realize that varbits are bit strings, not integers, which means they sort as strings.

The siblings of the 127th key don't need to be extended to sort correctly, that's a beauty of this scheme.

Collapse
Posted by Frank Bergmann on
Hi Don,

that's correct. However, I see some differences between the "SQL for smarties" stuff and yours:

Your representation allows to query directly:

    "give me all children of project X"

All other queries are probably quite slow because they require PxSQL iterations for each item:

    "in which level of the hierarchy do I live" and
    "give me my parent" and
    "give me the list of my siblings"

However, "give me my parent" is already covered by the parent_id that is usually present in any hierarchical data type and asking for the level is normally associated with a db_foreach loop in order to draw the indentation, so speed shouldn't matter that much anyway.

I think what most confused us is that the documentation refers to one, two, three and four byte representations and that it doesn't explain the use of the first bit as a separator between your one-byte and your four-byte representations...

Great stuff anyway!
Frank

http://www.project-open.com/

Collapse
Posted by Don Baccus on
Oh, once upon a time there was a one, two, and four byte representation I ditched it for the one or four byte representation used now.

We've not experienced any performance problems with the operations you mention.  PL/pgSQL isn't all that slow, queries are pre-compiled and stored so it's just a matter of executing the PL/pgSQL bytecode and the query tree.

None of queries involved refer to any database table, they operate on a bitstring parameter.  It's roughly equivalent to doing such operations in any compiled interpretive language, probably a bit slower than Tcl because PL/pgSQL and the query executor aren't optimized for doing simple operations rather than "real" (complex) SQL queries but probably not enough for us to care.