phpmysqlsqlmaterialized-path-pattern

Selecting based on path in mysql


I have a column id, a column parent and a column path that is a materialized path.

It looks like

1  | \N | 1  
2  | 1  | 1/2  
3  | 2  | 1/2/3  
4  | 3  | 1/2/3/4  
5  | 3  | 1/2/3/5  
6  | 2  | 1/2/6  
7  | 6  | 1/2/6/7  
8  | 2  | 1/2/8  
9  | 1  | 1/9  
10 | 9  | 1/9/10  
11 | 10 | 1/9/10/11  
12 | 11 | 1/9/10/11/12  
13 | 11 | 1/9/10/11/13  
14 | 11 | 1/9/10/11/14  
15 | 14 | 1/9/10/11/14/15  
16 | 14 | 1/9/10/11/14/16  
17 | 14 | 1/9/10/11/14/17  
18 | 10 | 1/9/10/18  
19 | \N | 19  
20 | 19 | 19\20  
21 | 19 | 19\21

I need to do some queries based off this table.

The queries I need to do are


Select all children of id 9

SELECT * FROM `tester` WHERE 'path' LIKE '%/9/%';  

Would work fine, Until you replace the ID with 1 or 19 as there is no / at the beginning.

SELECT * FROM `tester` WHERE 'path' LIKE '%1/%';

would select all rows where a number ends in 1, so, 1, 11, 21, 31, 211 etc

SELECT * FROM `tester` WHERE 'path' LIKE '1/%';

would work correctly for either rows 1 or 19

So SELECT * FROMtesterWHERE 'path' LIKE '1/%' OR 'path' LIKE '%/1/%';
Is the best I can come up with, any suggestions?


Select Direct children of 9 but not sub-children
For this Select * fromtesterwhere 'parent' = 9; will work fine.


select an aggregate count of 9's children, x levels deep.

So I want to end up with either one row of level1, level2, level3, ... levelx or x rows, representing the different levels,

Let us pretend x is 3 for this example The rows from this example would be 9, 8, 6 (the 4th level if we requested it would be 3)

Any Ideas?

Edit

#select count of children of specific node(5) down to a maximum of three levels, do no include the parent
SELECT COUNT(child.id) children, 
LENGTH(REPLACE(child.path, parent.path, '')) - LENGTH(REPLACE(REPLACE(child.path, parent.path, ''), '/', '')) AS LEVEL
FROM `tester` child JOIN `tester` parent ON child.path LIKE CONCAT(parent.path,'%') 
WHERE parent.id  =5 
GROUP BY LEVEL HAVING LEVEL <= 3 AND LEVEL > 0;


**select 9's children's id's down to x levels, with the level relative to 9,

So again for this example we will use 3 as x.

We are looking to get back

10 | 1
11 | 2
18 | 2
12 | 3
13 | 3
14 | 3 

Again I am at a complete loss as to how to do this.

Edit:

#select all information, and relative level from parent of children of specific node(5) down to a maximum of three levels, do no include the parent
SELECT child.*, 
LENGTH(REPLACE(child.path, parent.path, '')) - LENGTH(REPLACE(REPLACE(child.path, parent.path, ''), '/', '')) AS LEVEL
FROM `tester` child JOIN `tester` parent ON child.path LIKE CONCAT(parent.path,'%') 
WHERE parent.id  =9 
GROUP BY id HAVING LEVEL <= 3 AND LEVEL > 0;

Solution

  • Just to give you a heads up, these solutions are based on string comparisons, are not optimized & cannot use indexes. you should consider normalizing your tables differently. (See Managing Hierarchical Data in MySQL)

    Regarding some of the questions:


    Select all children of id 9:

    Since the Path column does not include the leading & trailing slashes, you need to concatenate them to the path:

    SELECT * 
    FROM tester
    WHERE CONCAT('/', path, '/') LIKE '%/9/%';
    

    select an aggregate count of 9's children, x levels deep:

    We need to group by the number of slashes in the path, minus the number of slashes in the parent path:

    SELECT (LENGTH(c.Path) - LENGTH(REPLACE(c.Path, '/', '')))
        - (LENGTH(p.Path) - LENGTH(REPLACE(p.Path, '/', ''))) AS Level,
        COUNT(*)
    FROM tester c
        JOIN tester p ON c.Parent = p.ID
    WHERE CONCAT('/', path, '/') LIKE '%/9/%';
    GROUP BY 1
    

    For simplicity i used the query above to show all the levels, If you want to limit x levels deep, use the WHERE predicate from the query below.


    select 9's children's id's down to x levels, with the level relative to 9:

    We search the Path column up to a x number of levels, while taking the parents level into consideration:

    SELECT c.*
    FROM tester c
        JOIN tester p ON c.Parent = p.ID
    WHERE CONCAT(
        '/',
        SUBSTRING_INDEX(
            Path, 
            '/', 
            (LENGTH(p.Path) - LENGTH(REPLACE(p.Path, '/', ''))) + 4
        ),
    '/') LIKE '%/9/%'
    

    The steps we are taking:

    1. We need to find out how deep the parent is, we can find that by counting the slashes in the parent's path. (LENGTH(p.Path) - LENGTH(REPLACE(p.Path, '/', '')))
    2. We need to add 1 to that number, since a path with 1 slash is 2 levels deep.
    3. We add the x number of desired levels.
    4. Grab the path column up to the level total, (Use the SUBSTRING_INDEX function).
    5. Add the leading and trailing slash.
    6. Search the final string for 9.