Materialized Path to Nested Set
Posted by matijs 13/12/2010 at 23h14
On twitter, @clemensk asks:
Hey SQL experts, is it somehow possible in pure (My)SQL to extract a nested set from a table full of paths (think: Category 1 > Category 2)?
To do this, you need to do two things: Extract the names of the nodes, and
calculate values for lft and rgt. Here’s my take on the latter part:
Finding the left and right values basically corresponds to traversing a number of boundaries. For each enclosing set, we traverse its boundary once, and for each neighboring set, we traverse its boundary twice. Therefore:
- We must count the enclosing sets:
SUBSTRING(this.path, 1, LENGTH(other.path)) = other.path. Each counts as one, including the current node itself. - We must count the neighboring sets:
other.path < this.path AND SUBSTRING(this.path, 1, LENGTH(other.path)) <> other.path
This will give us the value for lft.
For rgt, it’s almost the same:
- We must count the enclosing sets:
SUBSTRING(this.path, 1, LENGTH(other.path)) = other.path. Each counts as one, including the current node itself. - We must count the neighboring sets, but this is more complicated, as the
ordering is not entirely alphabetical:
SUBSTRING(other.path, 1, LENGTH(this.path) > this.path - Finally, we have to subtract from the maximum value of
rgt(which is twice the number of nodes) and add 1 to take care of off-by-one errors.
And here is the resulting query:
SELECT
( SELECT COUNT(*)
FROM paths b
WHERE SUBSTRING(a.path, 1, LENGTH(b.path)) = b.path ) +
( SELECT COUNT(*)
FROM paths b
WHERE SUBSTRING(a.path, 1, LENGTH(b.path)) <> b.path
AND b.path < a.path ) * 2 AS lft,
( SELECT COUNT(*) FROM paths ) * 2 -
( SELECT COUNT(*)
FROM paths b
WHERE SUBSTRING(a.path, 1, LENGTH(b.path)) = b.path ) -
( SELECT COUNT(*)
FROM paths b
WHERE SUBSTRING(b.path, 1, LENGTH(a.path)) > a.path) * 2 + 1 AS rgt,
a.path
FROM paths a 
