MySQL Nested Set / Pre-order tree query

And while I am at it, here was the original suggestion I had before finding that nice approach using find_in_set() and group_concat().  It uses a technique discussed here:

http://jimlife.wordpress.com/2008/09/09/displaying-row-number-rownum-in-mysql/

Showing as it is actually less code if you are stuck with not being able to create a view.  Therefore, if you cannot create a view this may be an alternative.

/* get children */
select c.id, c.title, c.left_, c.right_,
c.`level`, p.id as parent
from category c
inner join category p
  on c.left_ between p.left_ and p.right_
  and c.right_ between p.left_ and p.right_
  and c.`level` = coalesce(p.`level`,0)+1
where p.id = 12
 
union
 
select id, title, left_, right_, `level`, parent
from (
 
/* get sub children */
select c.id, c.title, c.left_, c.right_, c.`level`,
 
/* emulate row_number() over() */
if(p.id = @lastparent, @rownum:=@rownum+1, @rownum:=1) as rank,
 
/* since using @lastparent in @rownum,
  have to set @lastparent 2nd;
  otherwise, p.id will always equal @lastparent in our if().
*/
@lastparent:=p.id as parent
 
from (select @rownum:=0, @lastparent:=null) r, category c
inner join category p
  on c.left_ between p.left_ and p.right_
  and c.right_ between p.left_ and p.right_
  and c.`level` = coalesce(p.`level`,0)+1
where exists (
  select 1
  from category c1
  inner join category p1
    on c1.left_ between p1.left_ and p1.right_
    and c1.right_ between p1.left_ and p1.right_
    and c1.`level` = coalesce(p1.`level`,0)+1
  where p1.id = 12 and c1.id = p.id
)
order by p.id
 
) derivedb
where rank <= 2

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:

Wow thanks.  It may take me a while to review this and test it out, but how do you feel this will perform on large data sets (large number of categories)?

It is harder to tell with small row set, but here is what I could gather.

All three of these solutions are pretty comparable:

(1) No View - Using @RowNum -- http:#25311936

5 rows fetched in 0.243s (0.0051s)

(2) No View - Using Find_In_Set() / Group_Concat() -- http:#25311853

5 rows fetched in 0.0032s (0.0065s)

(3) View - Using Find_In_Set() / Group_Concat() -- http:#25311853

5 rows fetched in 0.0033s (0.1200s)


#1 seems to be the faster of the three.  EXPLAIN plan for each is also pretty similar, but shows better for the #1 solution due to not requiring the extra inner query to get the group_concat() on parent category.  

With a little work, can probably modify the other no view solution to combine the join on category to determine parent/child with join to get children list of that parent.  For that matter, may be able to do ranking before storing in the view.

Can try for yourself using this as a helpful guide to tweaking / troubleshooting for performance:
3 Ways to Speed Up MySQL - http:viewArticle.jsp?aid=1250

The biggest key I found was to have an index on level column.


M-1

>>The biggest key I found was to have an index on level column.

That is with assumption that id is already indexed as primary key.

More efficient:
(no UNION, using view shown above)

select c.id, title, 
left_, right_,
level, parent
from vw_childcategories c
where parent = 12 or
(
 
/* handles sub children */
exists (select 1
   from vw_childcategories
   where parent = 12
   and id = c.parent)
 
and
 
/* handles X # of sub children */
find_in_set(c.id,
   (select group_concat(id) as children
    from vw_childcategories
    where parent = c.parent
    group by parent
  )) <= 2
 
)
order by parent, id
;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

Unfortunately I won't be able to use views.  I will review the non-review method unless you have a more optimized version of it?

Give me a second.  I updated data to have a larger number of records, so can better tell efficiency.  Will try with no view and post back.

Here you go:

select c.id, c.title, c.left_, c.right_,
c.`level`, p.id as parent
from category c
inner join category p
  on c.left_ between p.left_ and p.right_
  and c.right_ between p.left_ and p.right_
  and c.`level` = coalesce(p.`level`,0)+1
where p.id = 12 /* get children */
or (
 
/* get sub children */
exists (
  select 1
  from category c1
  inner join category p1
    on c1.left_ between p1.left_ and p1.right_
    and c1.right_ between p1.left_ and p1.right_
    and c1.`level` = coalesce(p1.`level`,0)+1
  where p1.id = 12 and c1.id = p.id
)
 
and
 
/* filter X # of sub children */
find_in_set(c.id,
   (select group_concat(c1.id) as children
    from category c1
    inner join category p1
      on c1.left_ between p1.left_ and p1.right_
      and c1.right_ between p1.left_ and p1.right_
      and c1.`level` = coalesce(p1.`level`,0)+1
    where p1.id = p.id
    group by p1.id
  )) <= 2
 
)
order by parent, id
;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

You mentioned you had a larger data set to test on, what kind of numbers were we talking about?

Not huge, just more than 5 records so could see actual impact on EXPLAIN plan.  Think about 60 records.  This is more efficient based on how the indexes get used.  The indexes I have are on left_ and right_ together and both are integers.  Another index on primary key id.  And another on level which is an integer also.

I tested it out on a set of 2000 categories.

I have the same indexes mentioned.

But it is slow.  Showing rows 0 - 29 (103 total, Query took 3.1897 sec)

EXPLAIN says:
1        PRIMARY        p        ALL        PRIMARY        NULL        NULL        NULL        2023        Using where
1       PRIMARY       c       ALL       left_,level       NULL       NULL       NULL       1518       Range checked for each record (index map: 0x6)

The results look ok but is there anyway to order these so we get the category, then the subcategories, then the next main category, then the subcategories? and so on?

You can probably try some of the other approaches mentioned without views and see if any perform better for you.

For the sort, you will need something like:

order by if(p.id=12,c.id,p.id), c.level, c.id

The code below was the one I tried with the slow results.

select c.id, c.title, c.left_, c.right_,
c.`level`, p.id as parent
from category c
inner join category p
  on c.left_ between p.left_ and p.right_
  and c.right_ between p.left_ and p.right_
  and c.`level` = coalesce(p.`level`,0)+1
where p.id = 12 /* get children */
or (
 
/* get sub children */
exists (
  select 1
  from category c1
  inner join category p1
    on c1.left_ between p1.left_ and p1.right_
    and c1.right_ between p1.left_ and p1.right_
    and c1.`level` = coalesce(p1.`level`,0)+1
  where p1.id = 12 and c1.id = p.id
)
 
and
 
/* filter X # of sub children */
find_in_set(c.id,
   (select group_concat(c1.id) as children
    from category c1
    inner join category p1
      on c1.left_ between p1.left_ and p1.right_
      and c1.right_ between p1.left_ and p1.right_
      and c1.`level` = coalesce(p1.`level`,0)+1
    where p1.id = p.id
    group by p1.id
  )) <= 2
 
)
order by parent, id
;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

I understood that, so I was saying you could try some of the UNION variations to see if works better with your actual data.

Unfortunately I could not get any of these to return decent speeds.

3 seconds is not decent speed?  And the question was how to do this?  My providing extra work towards efficiency was bonus with all due respect.  You asked how this was possible.  The fastest method as I told you involved views.  I cannot control your not being able to create a view in your database.  Anyway, good luck -- optimizing is very difficult.  Doing some now myself, it is very tedious so all the best to you.

Regards,

Kevin

3 seconds is not a decent speed, no.

Especially when the query is used on a high traffic website on the home page.

Yes, the question was how to do this.  We simply assumed that the answer given would take into account speed.  I didn't think we had to ask for it to be a optimized query, I simply assumed this was obvious as it should be for -any- SQL query.

As far as not being able to use views, we simply said a single SQL query.  I figured it was obvious there as well, as we did not mention a "single SQL query with a view".

Thanks for your detailed answer and hard work so no disrespect, but it is still not what we need as its slow therefore making it applicable for what we need.

:) As I said good luck!