October 2009 Archives

I've had a need for some time now to have an ability to make recursive calls to an SQL database with out completely melting down my database server using literal recursion for SQL calls (namely, a for loop that does a select for EACH record I need to retrieve, easy to see how things would go up in flames.), and have played around with a few ideas.

There are nested sets, which are kind of cool, because they make a nice bridge between programming's want for trees/graphs, and SQLs stickler for their organized sets. It's a neat concept, having the immediate knowledge of what is to the left and right of a given "node", but this makes it KILLER to make inserts into. You have a whole ton of knowledge to gather before you even insert any data for a new record.

Adjacency lists are a bit like nested sets, but they pretty much keep track of the parent id as opposed to what's on each side of the node. They're fast, but once again, munging must be done before you can get correct/normalized results and good inserts.

Materialized paths are currently my favorite, but by no means are they the be all end all solution. Especially since different RDBMSes are better optimized for other such methods (Oracle's CONNECT BY, for instance). Materialized paths are pretty much just a path up to the node you are selecting of its parents. For instance:

1.2.1.1.3.5

would be the 5th child of the 3rd child of the 1st child of the 1st child of the 2nd child of the parent whose primary key is 1. It's pretty simple. Selecting from and inserting into with this is pretty easy as well.

DBIC::T::Recursive is probably going to, in one way or another, make use of each of these (maybe more, given there is likely going to be a -handle => $methodgoeshere where $methodgoeshere could be matpath, adjacency list, nested set, connect by, etc.), and will eventually be optimized per DBMS to suit the best type of recursion.

The best part, it will all be abstracted away and will Just Work. It's going to be a mighty project, but I'm looking forward to making more progress on it.

So, I recently finished (for certain values of "finished") my Google Summer of Code grant. It was very fun, stressful, and eye opening. I learned a LOT. A lot more than I could possibly encompass in a single (or infinite, really) blog post, and way more than the realm of computer hackery involves.

I remember starting the project, getting my SVN commit bit, svn co'ing the code, and going "Holy shit. I am in WAY over my head." But I kept at it. I was stubborn, and MOST important, asked incessant questions, probably much to the chagrin of my mentor and the very kind souls that held my hand through all of this.

I finally got my head wrapped around most of the code, and went, "hey! I kick ass! I'm contributing, I'm smart, I'm getting things done, I'm good enough, and gosh darn it people like me!." Then we got into stage two. The process preeeetty much started all over again. I had no idea where I was, I was writings tests for things I didn't quite understand, and did a great deal of staring at my computer screen. I wasn't, however, committing to the wrong places or fucking up the repo (as much) anymore! Progress was being made. Slow, but there.