From: Brian Candler <B.Candler@...>
Date: 2004-10-08T22:11:30+09:00
Subject: Re: [ANN] ndb Object-Relational Mapper

On Fri, Oct 08, 2004 at 09:29:44PM +0900, George Moschovitis wrote:
> >Yep. The trouble with just having a child/parent link is that it's very
> >inefficient to do a search which is limited to all nodes within a subtree,
> ... anyone wants to play.
> >
> 
> Have a look at the SqlTreeTraversable Mixin in the file n/db/mixins.rb
> If you include this mixin in your managed Object you can efficiently 
> serach in subtrees. This mixin implements the common Preorder Tree 
> Traversal SQL pattern. Is this what you are looking for?

I don't think so, but I'm afraid I couldn't work out what the
"SqlTreeTraversable" module actually does from its rdoc comment or code.

An example of what I want to do is as follows. Say I have a tree of E-mail
accounts, ordered hierarchically:

       . (root)
       |
   resellers
       |
     VISPS
       |
     Users
       |
    Mailboxes

A reseller "owns" a set of VISPs, each of which "own" their users, each of
which "owns" some mailboxes. Let's say we have 10 resellers, each with 100
VISPs, each with 2000 users, each with 5 mailboxes; that makes 10M mailboxes
altogether.

If I'm logged in as a particular reseller, I should only be able to see my
portion of the tree. Then I want to be able to ask efficiently: "find all
E-mail addresses like brianc% which are underneath me", as a single SQL
query.

It can be implemented as a join using the parent-child relationship, but is
unlikely to be efficient (probably will end up enumerating all 1 million
nodes which are underneath this reseller, just to find the ones which start
'brianc%')

Then consider that I make the tree recursive, so a User can have their own
VISPs, which can have Users, which can have VISPs... etc. Now, finding
mailboxes like brianc% under a particular User or VISP is not at all easy.
Oracle has SQL extensions for tree traversal, but it's not efficient if you
end up walking a very large section of tree.

However, if path strings like I described before are allocated to each node,
it becomes easy:

   select .... where e.path like 'A%' and e.address like 'brianc%';

('A' being the point in the tree I am searching below). A good SQL query
optimiser will then be able to estimate for itself whether it is more
efficient to find all nodes under A% and then limit that to those which
match brianc%, or find all nodes which match brianc% and limit them to those
under A%. Typically one or the other will dominate.

For XML-heads, it may be clearer to observe that XPATH queries can be
translated directly into SQL: e.g.

    id(123)//bar     # all 'bar' nodes under subtree rooted at id(123)

becomes

    select ... where e.path like '123%' and e.type = 'bar';

Thus you have the possibility of treating your database as one huge XML
document (but without having to load it all into RAM, and with the
concurrent access and transaction safety that a SQL database allows). The
XPATH stuff is still a long way from being implemented though.

Cheers,

Brian.