Betternestedset talk - Feb 2007 - MySQL performance with large tables

Hi all,

Just joined the list, I checked through the archives & tickets, but
couldn''t find anything similar.

I''ve recently started using better nested set on a project, and found
that the performance was rather horrible on an InnoDB table with ~2.2
million rows (~27 seconds on  a self_and_ancestors call, set is about
5 levels deep)

After a bit of digging I discovered that MySQL was ignoring the
indexes I''d set on the lft & rgt columns when using the BETWEEN
operator.
According to the MySQL docs, between is equivalent to (min <= expr AND
expr <= max)
<http://dev.mysql.com/doc/refman/5.0/en/comparison-operators.html#operator_between>,
after replacing all the instances with this syntax, the query time
went down to ~0.5sec, quite an improvement :)

This has been working fine for me so far, but it would be great to
hear others opinions on whether this will cause any other problems.

I''ve attached a patch if anyone wants to check it out for themselves.
I haven''t tested this very extensively apart from in my app, just ran
the unit tests & they all passed (after updating the test_sql_for to
use the same syntax).
I''ve also only tested this with MySQL 5, so I have no idea how these
changes would effect other databases.

-- 
Lindsay Evans
http://lindsayevans.com/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: better_nested_set.rb.diff
Type: application/octet-stream
Size: 6686 bytes
Desc: not available
Url :
http://rubyforge.org/pipermail/betternestedset-talk/attachments/20070216/abf328cb/attachment.obj

Hi Lindsay,

Welcome to the list. Thanks a lot for letting us know about this.

I''ve looked into it some, and what I have seen is puzzling. For the
relatively small (16,000 row) table I''m working on, I saw no
difference between the two types of syntax for an ancestors query:
http://pastie.caboo.se/40831

The odd part was that when I dropped the indexes, the descendants
query got slower (as expected) but the ancestors query got faster
using both ''between'' and ''<='' syntax:
http://pastie.caboo.se/40850

I''m not enough of a database person to know if this behavior is
expected on small tables, but I thought it was odd. (I tried all of
these queries several times, and the times were consistent). I have
heard that while the descendants query in a nested set is
straightforward, the ancestors query is inherently difficult for
databases to deal with.

Thanks for the patch-- I''ll do some more testing with larger tables
and see what I can figure out.

Cheers,
Krishna




On 2/15/07, Lindsay Evans <lindsaye at gmail.com>
wrote:
> Hi all,
>
> Just joined the list, I checked through the archives & tickets, but
> couldn''t find anything similar.
>
> I''ve recently started using better nested set on a project, and
found
> that the performance was rather horrible on an InnoDB table with ~2.2
> million rows (~27 seconds on  a self_and_ancestors call, set is about
> 5 levels deep)
>
> After a bit of digging I discovered that MySQL was ignoring the
> indexes I''d set on the lft & rgt columns when using the
BETWEEN
> operator.
> According to the MySQL docs, between is equivalent to (min <= expr AND
> expr <= max)
<http://dev.mysql.com/doc/refman/5.0/en/comparison-operators.html#operator_between>,
> after replacing all the instances with this syntax, the query time
> went down to ~0.5sec, quite an improvement :)
>
> This has been working fine for me so far, but it would be great to
> hear others opinions on whether this will cause any other problems.
>
> I''ve attached a patch if anyone wants to check it out for
themselves.
> I haven''t tested this very extensively apart from in my app, just
ran
> the unit tests & they all passed (after updating the test_sql_for to
> use the same syntax).
> I''ve also only tested this with MySQL 5, so I have no idea how
these
> changes would effect other databases.
>
> --
> Lindsay Evans
> http://lindsayevans.com/
>
> _______________________________________________
> Betternestedset-talk mailing list
> Betternestedset-talk at rubyforge.org
> http://rubyforge.org/mailman/listinfo/betternestedset-talk
>
>
>