Understanding Doctrine’s NestedSet feature

August 30, 2008 – 8:53 pm Tags: ,

The Doctrine library comes with a feature called nested set, which makes saving trees in a database easy. However, it’s quite easy to accidentally cause a lot of extra unneeded queries if not being careful.

Here are some pointers to keep in mind while working with the nested set, and some example queries to make understanding it easier.

The general idea

Doctrine’s way of doing nested sets may at first seem confusing – what are the lft, rgt and level values and how do they relate to each other? Understanding the way lft, rgt and level works will allow you to understand how the tree actually works.

Fetching child rows

Typically, you might write something along the lines of..

<?php foreach($row->getChildren() as $child): ?>
  <b><?= $child->name; ?>
  <?php foreach($child->getChildren() as $childChild): ?>
      <?= $childChild->id; ?>
  <?php endforeach; ?>
<?php endforeach; ?>

That’s very bad! getChildren method always hits the database, so the above could generate many unneeded queries.

Doctrine’s tree nodes do contain a method called getDescedants, which can be used to fetch all descedants up to a specific depth. Always use this instead of getChildren if you need more than a single level of children fetched.

What if you wanted to find all the child rows of two (or more) rows?

Finding all child rows of a specific row is simple:

All rows, which have a higher lft, a lower rgt and a higher level value are children of the row in question.

For example, if we have a row with lft = 10, rgt = 20 and level = 1, the following query would fetch the next two levels of children of the row:

SELECT * FROM example WHERE lft > 10 AND rgt < 20 AND level > 1 AND level < 4

Finding children of two rows would be similarily simple, just modify the where clause to (lft > 10 AND rgt < 20) OR (lft > 40 AND rgt < 50). If the two rows are actually siblings, you can simply do lft > 10 AND rgt < 50.

Fetching parent rows

Just like with getChildren, getParent will only fetch one parent, and will always query the DB. Use getAncestors instead if you need more than one level.

Seeing how child rows have higher lft and lower rgt, parent rows have the opposite: lower lft and higher rgt

Fetching all parents of a row with lft = 10, rgt = 20 and level = 4:

SELECT * FROM example WHERE lft < 10 AND rgt > 20 AND level < 4

For fetching multiple row’s parents can be done in a similar fashion as multiple row’s children.

Pros and cons

getDescedants and getAncestors have a small problem: Their results won’t appear in a “proper” tree structure – if you loop over them, you will have to manually look at level and other values to check if the rows are on different levels. This could be simplified by writing a class which forms a proper tree out of the Doctrine_Collection object.

The SQL queries also have similar problems. You will have to manually confirm the correct order and level of the rows returned. Whether or not these are things you can live with would depend on your application, but understanding how things work behind the scenes is always useful.

Share this:
  1. 7 Responses to “Understanding Doctrine’s NestedSet feature”

  2. Hi,

    I’m Guilherme Blanco (http://www.doctrine-project.com/contributor/guilhermeblanco), one of the core developers of Doctrine.

    There’s a proposed patch (I wrote and suggested it) that will be incorporated in 1.0.1 (minor version not correctly defined) that will map a collection into a tree hierarchy.

    If you want to use it by now, here is the pastebin: http://pastebin.com/f2368a2ff

    Right now the patch only works when you hydrate_array the results, and does not work with a Doctrine_Collection.
    That’s the reason why my patch hasn’t been applied yet.

    So, go ahead and play with it. It’ll help you a lot with your nested loop. =)


    By Guilherme Blanco on Sep 2, 2008

  3. Nice. Something like that would indeed be useful for looping and such.

    I had actually made a class of my own which turns nestedset collections into tree structures… but it’s kinda tailor made for the project, so it would need quite some mods to make it more generic.

    By Jani Hartikainen on Sep 2, 2008

  4. Is there a way to use paging with doctrine’s nested set?

    By Sven on Jun 29, 2009

  5. Can we get a usage guide for code provided by Guilherme Blanco.

    By Kwasi on Sep 13, 2009

  6. getDescedants needs to be changed to getDescendants

    By Matt Alexander on Sep 12, 2010

  7. Hi Guilherme Blanco,
    The link which you provided is really more use fulled for me.

    Thanks a lot,

    By Ravinder Reddy on Nov 2, 2011

  1. 1 Trackback(s)

  2. Jan 22, 2009: Doctrine vs. Propel | CodeUtopia

Post a Comment

You can use some HTML (a, em, strong, etc.). If you want to post code, use <pre lang="PHP">code here</pre> (you can replace PHP with the language you are posting)