Hi Jef, * Jef Driesen <[EMAIL PROTECTED]> [2007-04-06 11:20]: > Q1. Which is more efficient? Two simple queries or one self > join? > > I have seen two different types of queries to retrieve a tree. > The first one uses two very simple queries: > > SELECT lft, rgt FROM tree WHERE name = @name; > SELECT * FROM tree WHERE lft BETWEEN @lft AND @rgt ORDER BY lft ASC; > > The first query is only required to retrieve the lft and rgt > values of the node. The other type uses a self join (which I > assume is more expensive), but no extra query is required: > > SELECT node.* > FROM tree AS node, tree AS parent > WHERE node.lft BETWEEN parent.lft AND parent.rgt > AND parent.name = @name > ORDER BY node.lft; > > Which type of query is more efficient?
I’d say just measure it. Another way to write this, possibly cheaper than the full-monty join in your second query, is to join on a single-row subquery: SELECT child.* FROM tree AS child, (SELECT lft, rgt FROM tree WHERE name = @name) AS boundary WHERE child.lft BETWEEN boundary.lft AND boundary.rgt ORDER BY child.lft ASC; However, this could actually be a disimprovement. As always, if you guess at the performance of any piece of code, you are guaranteed to be wrong; profile, profile, profile and profile again. Personally, I prefer this variant over the join you showed simply because I find it much more obvious what’s going on. > Retrieving the path to a node is very similar: > > SELECT * FROM tree WHERE lft <= @lft AND rgt >= @rgt ORDER BY lft ASC; > > or > > SELECT parent.* > FROM tree AS node, tree AS parent > WHERE node.lft BETWEEN parent.lft AND parent.rgt > AND node.name = @name > ORDER BY parent.lft; Again, the same trivial transform could be applied. > Q3. How do I move a node (or subtree)? > > In the adjacency list model, this is extremely easy by pointing > the parent_id to another node. But I don't know how to do that > in the nested set model. This is pretty complex. I wrote a procedure once to move a single node: If the node should... -- ...become a sibling to the left of the target node: SELECT lft FROM categories WHERE name = @target_name -- ...become a sibling to the right of the target node: SELECT rgt + 1 FROM categories WHERE name = @target_name -- ...become the first child of the target node: SELECT lft + 1 FROM categories WHERE name = @target_name -- ...become the last child of the target node: SELECT rgt FROM categories WHERE name = @target_name Now you have your new `lft` value. With it, you can perform the desired update. First, you make room for the node at the target location: UPDATE tree SET rgt = rgt + 2 WHERE rgt >= @lft ORDER BY rgt DESC UPDATE tree SET lft = lft + 2 WHERE lft >= @lft ORDER BY lft DESC Note that I had to split this up in two separate queries because I have UNIQUE constraints on `lft` and `rgt` and MySQL failed half-way into the query if any one row failed the constraint; very annoying. The ORDER BY clauses are necessary to keep MySQL from tripping over itself. I assume that most other database engines would be able to check constraints only at the end of a transaction. After all, Celko writes this update as a single query with CASEs. Hopefully I’ll be able to do have the query that way on Postgres once I’m done with the migration. Anyway, after all that, you can finally move the desired node to the space at the target: UPDATE tree SET lft = @lft, rgt = @lft + 1 WHERE name = @source_name However, as it should be pretty obvious, this only moves a single node – the subtree below this node does not tag along for the journey. Due to the nature of nested sets, it becomes re-parented to the parent of the moved node. I have always meant to go back and change the queries as necessary to move an entire subtree, but I’ve yet to get around to it. Basically, what would be necessary is: • Change from a fixed amount of 2 when making room at the target location (which is enough to make room for a single node), to instead be the difference between the `lft` and `rgt` values of the source node. • Modify the WHERE clause and calculations in the final UPDATE so it moves an entire tree, not just a single node. It shouldn’t be hard, it just takes a bit of concentration to get all the cogs in the queries just so. Regards, -- Aristotle Pagaltzis // <http://plasmasturm.org/> ----------------------------------------------------------------------------- To unsubscribe, send email to [EMAIL PROTECTED] -----------------------------------------------------------------------------