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]
-----------------------------------------------------------------------------
