Recursive Common Table Expression Tree Plugin

116 views
Skip to first unread message

Jeremy Evans

unread,
Mar 19, 2010, 2:21:43 PM3/19/10
to sequel-talk
I've been working on a plugin for Sequel that uses recursive common
table expressions to implement eager loading of tree like structures
in an SQL database. It's available at http://pastie.org/877511.txt,
and based on earlier work shown in the Advanced Associations RDoc
page. It's inspired by comparisons of the adjacency list model to the
nested set model at Explain Extended (see
http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/).
It allows the lazy and eager loading of all ancestors and descendants,
as well as the eager loading of all descendants to a given level,
along with caching the necessary parent-child relationships so
iterating over the tree structure after eager loading causes no
database access.

I'm posting this to the list for early comment as to whether people
think this plugin should be shipped with Sequel, or whether it should
be an external plugin (available as a separate gem, similar to
sequel_validation_helpers_block). If you have feelings either way,
please post here.

Thanks,
Jeremy

Scott LaBounty

unread,
Mar 19, 2010, 3:39:27 PM3/19/10
to seque...@googlegroups.com
Since you asked for "feelings" and not rationale, I'm going to go with "shipped with".

Scott


--
You received this message because you are subscribed to the Google Groups "sequel-talk" group.
To post to this group, send email to seque...@googlegroups.com.
To unsubscribe from this group, send email to sequel-talk...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sequel-talk?hl=en.




--
Scott
http://steamcode.blogspot.com/

Michael Lang

unread,
Mar 19, 2010, 3:55:11 PM3/19/10
to seque...@googlegroups.com
I don't know if it makes any difference, but I actually first attempt at using the recursive select stuff to build my tree plugin in the "sequel_plus" gem, but found right off the bat that not all DBMS supports such fancy syntax, so I fell back to a safer implementation.

Also, I started reading that linked article, but didn't get too far into it before getting distracted by real work and deadlines, so we may be talking about two different things with regards to trees and adjacency plugins...

Michael
http://codeconnoisseur.org

Jeremy Evans

unread,
Mar 19, 2010, 6:57:10 PM3/19/10
to sequel-talk
On Mar 19, 12:55 pm, Michael Lang <mwl...@cybrains.net> wrote:
> I don't know if it makes any difference, but I actually first attempt at
> using the recursive select stuff to build my tree plugin in the
> "sequel_plus" gem, but found right off the bat that not all DBMS supports
> such fancy syntax, so I fell back to a safer implementation.
>
> Also, I started reading that linked article, but didn't get too far into it
> before getting distracted by real work and deadlines, so we may be talking
> about two different things with regards to trees and adjacency plugins...
>
> Michael

Nope, it's the same thing.

The plugin probably only works on PostgreSQL 8.4+, MSSQL 2005+, and
maybe a recent version of Firebird. Recursive common table
expressions are in a recent SQL standard, but not many databases
support them yet.

Jeremy

Simon Arnaud

unread,
Mar 23, 2010, 7:06:21 AM3/23/10
to seque...@googlegroups.com
I think it should ship with sequel, as an extension.
It is a great addition, and usefull in a lot of cases.

Could it be emulated on databases without recursion ?
I have something that is mostly this for SQLite, without a flexible
"to a given level", based on "Tree - All Ancestors and Descendents"
from the documentation.
Re-reading this section, it already talks about rcte it seems.

Simon

Jeremy Evans

unread,
Mar 23, 2010, 12:06:14 PM3/23/10
to sequel-talk

That section shows you how to get something similar without recursion,
but it doesn't perform nearly as well. And the plugin was originally
based on the rcte code at the bottom of the section. It just
generalizes it for you.

Jeremy

Michael Lang

unread,
Mar 23, 2010, 12:19:55 PM3/23/10
to seque...@googlegroups.com
As Jeremy said, the non-recursive version is a little slower, but I find it suitably fast for my needs for generating nested menus for websites (which won't have but 30 or 40 entries and 3 levels deep at most in practice).

If you need the tree functionality, install sequel_plus gem that I put together:

http://github.com/mwlang/sequel_plus

for more info and how to install and use.

Regards,

Michael

--
You received this message because you are subscribed to the Google Groups "sequel-talk" group.
To post to this group, send email to seque...@googlegroups.com.
To unsubscribe from this group, send email to sequel-talk...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sequel-talk?hl=en.




--
http://codeconnoisseur.org

Mike Luu

unread,
Mar 29, 2010, 2:52:28 PM3/29/10
to sequel-talk
shipped with Sequel please :)

Jeremy Evans

unread,
Mar 29, 2010, 5:15:27 PM3/29/10
to sequel-talk
On Mar 19, 11:21 am, Jeremy Evans <jeremyeva...@gmail.com> wrote:
> I'm posting this to the list for early comment as to whether people
> think this plugin should be shipped with Sequel, or whether it should
> be an external plugin (available as a separate gem, similar to
> sequel_validation_helpers_block).  If you have feelings either way,
> please post here.

Based on the feedback received here, I've decided to ship the plugin
with Sequel: http://github.com/jeremyevans/sequel/commit/4ca07d9336bc94643654839e932124a3a6807f49#diff-1

Jeremy

Reply all
Reply to author
Forward
0 new messages