A. Pagaltzis wrote:
Hi Jef,
* Jef Driesen [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.
I know profiling is the only way to be 100% sure about performance. But
i was only asking some more general advice, since I have little
experience with sql(ite) an thus no idea what type of queries are more
expensive than others.
I'll test with your variant too.
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.
The fourth option is what I want.
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 noticed this too. But sqlite does not seem to support the ORDER BY
when doing an update.
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 need to be able to move the entire subtree for my application (e.g.
drag and drop in a treeview).
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.
I'm already working on a version to move an entire subtree and it's
almost finished. In the meantime, I also found an implementation for
postgres [1]. The math is a little different (because they move to the
first child of the target node, instead of the last child), but the idea
is the same. It also made me realize the math is different depending on
the direction of the move.
I also found another article [2] that has some pseudo code for moving a
subtree.
[1] http://archives.postgresql.org/pgsql-sql/2002-11/msg00355.php
[2] http://mrnaz.com/static/articles/trees_in_sql_tutorial/
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
