You are viewing a plain text version of this content. The canonical link for it is here.
Posted to slide-dev@jakarta.apache.org by Max Pfingsthorn <m....@hippo.nl> on 2004/12/08 13:53:19 UTC
Optimizing SQL tree
Dear Developers,
I was recently looking up different algorithms to store trees in an SQL database. I have found these very interesting articles from 1996.
The author, Joe Celko, writes that trees can be represented as Nested Sets (see the first article for some explanation). I think, this might be useful to Slide's SQL backend and the querying of the WebDAV tree. 'Recursive' searches, i.e. depth=infinity, reduce to mere SELECTs comparing integers rather than making the DB match strings. And, with a little extra, depth=1 is also a simple SELECT. However, inserts are a bit more expensive, which would be fine, however, since in general, the WebDAV repository is not written to so often in comparison to the reads.
What do you think about restructuring the SQL to take advantage of this?
For complete reference on the Nested Sets, see:
http://www.dbmsmag.com/9603d06.html
http://www.dbmsmag.com/9604d06.html
http://www.dbmsmag.com/9605d06.html
http://www.dbmsmag.com/9606d06.html
In general, I am very interested in optimizing the SQL backend a bit more. I noticed that the LIMIT clause is actually emulated within the backend instead of using the SQL feature. We are using MySQL behind Slide, so that would help us a lot. What do you think about specializing the backend(s) even more to take full advantage of the different vendor-specific implementations? Of course, maintenance would be harder, but it sure would give performance a kick.
Best regards,
Max Pfingsthorn
Hippo
Oosteinde 11
1017WT
Amsterdam
The Netherlands
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: Optimizing SQL tree
Posted by Richard Emberson <re...@edgedynamics.com>.
I had to mine for it:
google: Tropashko Farey
and
google: Tropashko Continued
Eirikur Hrafnsson wrote:
> Do you have any website references to that?
>
>
> On 8.12.2004, at 13:58, Richard Emberson wrote:
>
>> Forget Mr. Celko's work on nested sets - its old stuff. Look for
>> Vadim Tropashko's work on Farey Sequences and Continued Fractions -
>> a much improved way of creating trees with generic SQL.
>>
>> Richard
>>
>>
>> Max Pfingsthorn wrote:
>>
>>> Dear Developers,
>>> I was recently looking up different algorithms to store trees in an
>>> SQL database. I have found these very interesting articles from 1996.
>>> The author, Joe Celko, writes that trees can be represented as Nested
>>> Sets (see the first article for some explanation). I think, this
>>> might be useful to Slide's SQL backend and the querying of the WebDAV
>>> tree. 'Recursive' searches, i.e. depth=infinity, reduce to mere
>>> SELECTs comparing integers rather than making the DB match strings.
>>> And, with a little extra, depth=1 is also a simple SELECT. However,
>>> inserts are a bit more expensive, which would be fine, however, since
>>> in general, the WebDAV repository is not written to so often in
>>> comparison to the reads.
>>> What do you think about restructuring the SQL to take advantage of this?
>>> For complete reference on the Nested Sets, see:
>>> http://www.dbmsmag.com/9603d06.html
>>> http://www.dbmsmag.com/9604d06.html
>>> http://www.dbmsmag.com/9605d06.html
>>> http://www.dbmsmag.com/9606d06.html
>>> In general, I am very interested in optimizing the SQL backend a bit
>>> more. I noticed that the LIMIT clause is actually emulated within the
>>> backend instead of using the SQL feature. We are using MySQL behind
>>> Slide, so that would help us a lot. What do you think about
>>> specializing the backend(s) even more to take full advantage of the
>>> different vendor-specific implementations? Of course, maintenance
>>> would be harder, but it sure would give performance a kick.
>>> Best regards,
>>> Max Pfingsthorn
>>> Hippo
>>> Oosteinde 11
>>> 1017WT
>>> Amsterdam
>>> The Netherlands
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
>>> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>>
>>
>>
>> --
>> This email message is for the sole use of the intended recipient(s) and
>> may contain confidential information. Any unauthorized review, use,
>> disclosure or distribution is prohibited. If you are not the intended
>> recipient, please contact the sender by reply email and destroy all
>> copies of the original message.
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
>> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>>
>>
>>
> Best Regards
>
> Eirikur S. Hrafnsson, eiki@idega.is
> Chief Software Engineer
> Idega Software
> http://www.idega.com
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
--
This email message is for the sole use of the intended recipient(s) and
may contain confidential information. Any unauthorized review, use,
disclosure or distribution is prohibited. If you are not the intended
recipient, please contact the sender by reply email and destroy all
copies of the original message.
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: Optimizing SQL tree
Posted by Eirikur Hrafnsson <ei...@idega.is>.
Do you have any website references to that?
On 8.12.2004, at 13:58, Richard Emberson wrote:
> Forget Mr. Celko's work on nested sets - its old stuff. Look for
> Vadim Tropashko's work on Farey Sequences and Continued Fractions -
> a much improved way of creating trees with generic SQL.
>
> Richard
>
>
> Max Pfingsthorn wrote:
>> Dear Developers,
>> I was recently looking up different algorithms to store trees in an
>> SQL database. I have found these very interesting articles from 1996.
>> The author, Joe Celko, writes that trees can be represented as Nested
>> Sets (see the first article for some explanation). I think, this
>> might be useful to Slide's SQL backend and the querying of the WebDAV
>> tree. 'Recursive' searches, i.e. depth=infinity, reduce to mere
>> SELECTs comparing integers rather than making the DB match strings.
>> And, with a little extra, depth=1 is also a simple SELECT. However,
>> inserts are a bit more expensive, which would be fine, however, since
>> in general, the WebDAV repository is not written to so often in
>> comparison to the reads.
>> What do you think about restructuring the SQL to take advantage of
>> this?
>> For complete reference on the Nested Sets, see:
>> http://www.dbmsmag.com/9603d06.html
>> http://www.dbmsmag.com/9604d06.html
>> http://www.dbmsmag.com/9605d06.html
>> http://www.dbmsmag.com/9606d06.html
>> In general, I am very interested in optimizing the SQL backend a bit
>> more. I noticed that the LIMIT clause is actually emulated within the
>> backend instead of using the SQL feature. We are using MySQL behind
>> Slide, so that would help us a lot. What do you think about
>> specializing the backend(s) even more to take full advantage of the
>> different vendor-specific implementations? Of course, maintenance
>> would be harder, but it sure would give performance a kick.
>> Best regards,
>> Max Pfingsthorn
>> Hippo
>> Oosteinde 11
>> 1017WT
>> Amsterdam
>> The Netherlands
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
>> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
>
> --
> This email message is for the sole use of the intended recipient(s) and
> may contain confidential information. Any unauthorized review, use,
> disclosure or distribution is prohibited. If you are not the intended
> recipient, please contact the sender by reply email and destroy all
> copies of the original message.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
>
>
Best Regards
Eirikur S. Hrafnsson, eiki@idega.is
Chief Software Engineer
Idega Software
http://www.idega.com
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: Optimizing SQL tree
Posted by Richard Emberson <re...@edgedynamics.com>.
Forget Mr. Celko's work on nested sets - its old stuff. Look for
Vadim Tropashko's work on Farey Sequences and Continued Fractions -
a much improved way of creating trees with generic SQL.
Richard
Max Pfingsthorn wrote:
> Dear Developers,
>
> I was recently looking up different algorithms to store trees in an SQL database. I have found these very interesting articles from 1996.
>
> The author, Joe Celko, writes that trees can be represented as Nested Sets (see the first article for some explanation). I think, this might be useful to Slide's SQL backend and the querying of the WebDAV tree. 'Recursive' searches, i.e. depth=infinity, reduce to mere SELECTs comparing integers rather than making the DB match strings. And, with a little extra, depth=1 is also a simple SELECT. However, inserts are a bit more expensive, which would be fine, however, since in general, the WebDAV repository is not written to so often in comparison to the reads.
> What do you think about restructuring the SQL to take advantage of this?
>
> For complete reference on the Nested Sets, see:
> http://www.dbmsmag.com/9603d06.html
> http://www.dbmsmag.com/9604d06.html
> http://www.dbmsmag.com/9605d06.html
> http://www.dbmsmag.com/9606d06.html
>
> In general, I am very interested in optimizing the SQL backend a bit more. I noticed that the LIMIT clause is actually emulated within the backend instead of using the SQL feature. We are using MySQL behind Slide, so that would help us a lot. What do you think about specializing the backend(s) even more to take full advantage of the different vendor-specific implementations? Of course, maintenance would be harder, but it sure would give performance a kick.
>
> Best regards,
> Max Pfingsthorn
>
> Hippo
> Oosteinde 11
> 1017WT
> Amsterdam
> The Netherlands
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
--
This email message is for the sole use of the intended recipient(s) and
may contain confidential information. Any unauthorized review, use,
disclosure or distribution is prohibited. If you are not the intended
recipient, please contact the sender by reply email and destroy all
copies of the original message.
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org