Toxic Elephant

Don't bury it in your back yard!

Materialized Path to Nested Set

Posted by matijs 13/12/2010 at 23h14

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>