Re: Extracting Parent Model from Nested Sets Model

From: Flavio Botelho <nuncanada_at_ig.com.br>
Date: 22 Jan 2003 09:44:23 -0800
Message-ID: <de0df942.0301220944.5458caf1_at_posting.google.com>

One of our programmers (mikespub from Xaraya) did some tests and this is what he found:
"

1) parent-child approach :
SELECT xar_cid,xar_name,xar_left
FROM xar_categories
WHERE xar_parent=$parent
"

*** MY COMMENT ***
We´re using celko´s model, but with an extra column for parent_id for now because of performance reasons... So this is what he called parent-child approach...
*** MY COMMENT ***
"

2) celko approach (?) :
SELECT
children.xar_cid,children.xar_name,children.xar_left,children.xar_right, COUNT(parents.xar_cid) as indent
  FROM xar_categories AS parents, xar_categories AS children  WHERE children.xar_left BETWEEN $left AND $right    AND parents.xar_left BETWEEN $left - 1 AND $right    AND children.xar_left BETWEEN parents.xar_left AND parents.xar_right

   AND children.xar_cid != parents.xar_cid GROUP BY children.xar_cid
HAVING indent = 1
"

• MY COMMENT *** Arght... I didnt inform him what was your recommended query:
  "SELECT B.part AS boss, P.part
  FROM Frammis AS P LEFT OUTER JOIN Frammis AS B ON B.lft
  • (SELECT MAX(lft) FROM Frammis AS S WHERE P.lft > S.lft AND P.lft < S.rgt);
    "
    But anyways that cannot be implemented into MySQL, because it still doesnt have sub-select support.. (Alhough we can emulate it in php, performance would go to hell)... Btw, i dont know why the MySQL guys didnt do it yet, it seems a no-brainer thing to add for me (Probably it is difficult, it is just me that is not aware of the difficulties)...
• MY COMMENT ***

"

3) nuncanada approach :
SELECT _at_next_brother:=$left;

SELECT _at_next_brother:=

CASE WHEN xar_left = _at_next_brother
     THEN xar_right+1
     ELSE _at_next_brother

END AS next_brother, xar_cid, xar_name, xar_left, xar_right FROM xar_categories
WHERE xar_left >= $left AND xar_right <=$right HAVING next_brother = xar_right+1

(with $left = the xar_left of the parent + 1 and $right = the xar_right of the parent - 1)

I'm not sure if the Celko approach is his recommended one, but anyway, here's what I got when doing 1000 x SELECT for some different categories in my 3-level DMOZ extract :

---

cat | subcats | directchild | parent | Celko | nuncanada |

---

  A  |       4 |           4 |   2 sec |     2 sec |    22 sec |
  B  |     625 |          40 |   2 sec |   290 sec |    23 sec |
  C  |    6923 |          18 |   2 sec |32.000 sec |    30 sec |
----------------------------------------------------------------

[I had to extrapolate the Celko results based on a smaller number of queries, of course]
"

Everything in quotes is from mikespub... Maybe you can help me figure out, why in case A we have such a big extra baggage in the query, 22 secs? Is it because of having 2 SELECTS in the same query?

Thanks for everything,
Nuncanada Received on Wed Jan 22 2003 - 18:44:23 CET