Toxic Elephant

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>