Toxic Elephant

Don't bury it in your back yard!

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>

Tags no comments no trackbacks

Comments

Comments are disabled