How are nested set models traversed in MySQL?

Question

I'm reading this article and on the part with the query:

SELECT node.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

I'm wondering how is it travered? What happens step by step? I'm confused, please help.

Answer 1

Well, the database system could execute the query several different ways with the same result, but here's one way to understand what's going on:

Take 2 copies of the nested_category table, one named parent and the other named node. Find the row in parent named ELECTRONICS (the article you link to implies there's only one). The range parent.lft to parent.rgt gives any nodes with ELECTRONICS as an ancestor in the tree, at any depth.

Sorting by node.lft means you'll get the sub-nodes of ELECTRONICS along the left side of the sub-tree first, in an pre-order traversal.

It might be easier to walk through a simpler example to understand this: what if we choose TELEVISIONS instead of ELECTRONICS as the parent:

The 'parent' set has only 1 row, because of [parent.name = 'TELEVISIONS']:

{ name: "TELEVISIONS", lft: 2, rgt: 9 }

The 'node' set has the 4 rows that satisfy [node.lft between 2 and 9] because we can substitute the single lft/rgt values from parent:

{ name: "TELEVISIONS", lft: 2, rgt: 9 }
{ name: "TUBE",        lft: 3, rgt: 4 }
{ name: "LCD",         lft: 5, rgt: 6 }
{ name: "PLASMA",      lft: 7, rgt: 8 }

And, as you can see, the above 4 rows are alread sorted by "lft" values, so to satisfy the query, we just take the name values and we're done.