## 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:

<typo:code lang=“sql”>
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
</typo:code>