Ordering materialized path searches

[Ovid]

Hi all,

You can read about materialized paths at:

  http://www.dbazine.com/oracle/or-articles/tropashko4

Having trouble ordering a search on a materialized path.  Let's say I have an object with an id of 17, it might have a materialized path which looks like:  '2.23.84.17'.  This is a branch in a tree with the 2 being the top of the tree and the 17 being a leaf.  To find the ancestors of a leaf, we have the following method:

I have the following DBIx::Class code.

    sub ancestors_rs {
        my $self = shift;
       
        my @ids = split /\./, $self->materialized_path;
        pop @ids;   # remove self
        if (!@ids) {
            @ids = ('NOSUCHID'); # XXX :(
        }  
       
        return $self->_default_resultset('PCE')
          ->search( { 'me.id' => { -in => \@ids } } );
    }

 
The problem is that I need to walk up the tree from bottom to top but I can't figure out how to order the results correctly (they get returned in an effectively random order).  Thoughts?

Cheers,
Ovid
--
Buy the book         - http://www.oreilly.com/catalog/perlhks/
Tech blog            - http://use.perl.org/~Ovid/journal/
Twitter              - http://twitter.com/OvidPerl
Official Perl 6 Wiki - http://www.perlfoundation.org/perl6


_______________________________________________
List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
IRC: irc.perl.org#dbix-class
SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
Searchable Archive: http://www.grokbase.com/group/dbix-class@...

[Rob Kinyon]

On Fri, Aug 14, 2009 at 09:23, Ovid<[hidden email]> wrote:

> Having trouble ordering a search on a materialized path.  Let's say I have an object with an id of 17, it might have a materialized path which looks like:  '2.23.84.17'.  This is a branch in a tree with the 2 being the top of the tree and the 17 being a leaf.  To find the ancestors of a leaf, we have the following method:
>
> I have the following DBIx::Class code.
>
>    sub ancestors_rs {
>        my $self = shift;
>
>        my @ids = split /\./, $self->materialized_path;
>        pop @ids;   # remove self
>        if (!@ids) {
>            @ids = ('NOSUCHID'); # XXX :(
>        }
>
>        return $self->_default_resultset('PCE')
>          ->search( { 'me.id' => { -in => \@ids } } );
>    }
>
>
> The problem is that I need to walk up the tree from bottom to top but I can't figure out how to order the results correctly (they get returned in an effectively random order).  Thoughts?

You need to add an orderby on a depth column that you add in based on
the index of the id in @ids. If you're in mysql, that'll be some huge
CASE statement. So, something like:

my %ids = map { $_ => $ids[$_] } 0 .. $#ids;
my $orderby = 'CASE ' . join( ' ', map { "WHEN $_ THEN $ids{$_}" }
keys %ids ) . ' ELSE NULL END AS depth';

return $self->_default_resultset('PCE')->search( {
    'me.id' => { -in => \@ids },
}, {
    '+select' => [ \$orderby ],
    'orderby' => 'depth DESC',
});

HTH.

Rob

_______________________________________________
List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
IRC: irc.perl.org#dbix-class
SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
Searchable Archive: http://www.grokbase.com/group/dbix-class@...

[Ovid]

----- Original Message ----

> From: Rob Kinyon <[hidden email]>

> > I have the following DBIx::Class code.
> >
> >    sub ancestors_rs {
> >        my $self = shift;
> >
> >        my @ids = split /\./, $self->materialized_path;
> >        pop @ids;   # remove self
> >        if (!@ids) {
> >            @ids = ('NOSUCHID'); # XXX :(
> >        }
> >
> >        return $self->_default_resultset('PCE')
> >          ->search( { 'me.id' => { -in => \@ids } } );
> >    }
> >
> >
> > The problem is that I need to walk up the tree from bottom to top but I can't
> figure out how to order the results correctly (they get returned in an
> effectively random order).  Thoughts?
>
> You need to add an orderby on a depth column that you add in based on
> the index of the id in @ids. If you're in mysql, that'll be some huge
> CASE statement. So, something like:

Actually, after walking around and talking to many colleagues, one of them pointed out that I can just order by the length of the materialized path.  It's guaranteed to work because that's an inherent property of how materialized paths are created.  It's very counter-intuitive, but it works :)

Cheers,
Ovid
--
Buy the book         - http://www.oreilly.com/catalog/perlhks/
Tech blog            - http://use.perl.org/~Ovid/journal/
Twitter              - http://twitter.com/OvidPerl
Official Perl 6 Wiki - http://www.perlfoundation.org/perl6

_______________________________________________
List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
IRC: irc.perl.org#dbix-class
SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
Searchable Archive: http://www.grokbase.com/group/dbix-class@...