Forum OpenACS Development: Response to New implementation of tree_sortkey

Collapse
Posted by Don Baccus on
Actually, in an effort to oversimplify I've cast the query in a much worst style than necessary using the current scheme of things. The toolkit never queries an entire table in this way, since objects, bookmarks, bboard threads, content folders etc are created by packages. Rather the queries do something like "show all the parents for the child in the subtree starting with the root folder for this package", giving us two rather than one opportunity to restrict the query, leading to a "between" with left and right values determined by the package-specific root object (folder whatever) id and the given child.

Even the general case can be improved:

select parents.*
from foo_table parents, foo_table child
where child.foo_key = :foo_key
  and parents.tree_sortkey <= child.tree_sortkey
  and tree_ancestor_p(parents.tree_sortkey, child.tree_sortkey);
The index on tree_sortkey can be used on the "<=" (or on the "between" in the more complex example alluded to above) so rather than searching the entire tree, we'll search the tree "above and to the left" of the child node. Of course if the child's the rightmost leaf of the entire tree than we'll still end up searching the entire table. On a more cheerful note, if the child's the leftmost leaf of the entire tree we'll grab just the parents with the "<=". The average case will lie between the two extremes.

This makes the current system a bit more palatable until I either implement a GiST index and the proper "contains" operator, or someone comes up with another bright idea that we can show will make effective use of the index on tree_sortkey.

Also "tree_ancestor_p" only compares the keys, it doesn't touch the RDBMS. It's one line is "return substring(potential_parent, potential_child) = 1". I've encapsulated it in a PL/pgSQL function in order to make it easier to change things in the future if we need or want to.

(PG's bitstrings are pretty cool, supporting "substring", "position", and "length" operators just like text strings)