MySQL: nested set is slow?

I have a table that looks like this:

category

• category_id
• name
• category_seo_friendly_url
• left_id
• right_id

When I run a query like this, it take almost 1 second:

SELECT node.category_id                                       AS node_category_id,
       node.category_seo_friendly_url,
       node.name,
       ( COUNT(parent.category_id) - ( sub_tree.depth + 1 ) ) AS depth
FROM   category AS node,
       category AS parent,
       category AS sub_parent,
       (SELECT node.category_id,
               ( COUNT(parent.category_id) - 1 ) AS depth
        FROM   category AS node,
               category AS parent
        WHERE  node.left_id BETWEEN parent.left_id AND parent.right_id
               AND node.category_id = 2
        GROUP  BY node.category_id
        ORDER  BY node.left_id)AS sub_tree
WHERE  node.left_id BETWEEN parent.left_id AND parent.right_id
       AND node.left_id BETWEEN sub_parent.left_id AND sub_parent.right_id
       AND sub_parent.category_id = sub_tree.category_id
GROUP  BY node.category_id
HAVING depth > 0
       AND depth <= 1
ORDER  BY node.name ASC

When I do an EXPLAIN, I get the following:

id    select_type    table       type    possible_keys                         key       key_len    ref     rows    Extra
1     PRIMARY        <derived2>  system  NULL                   开发者_Python百科               NULL      NULL       NULL    1       Using temporary; Using filesort
1     PRIMARY        sub_parent  const   PRIMARY,category_id,left_id,right_id  PRIMARY   4          const   1     
1     PRIMARY        node        ALL     left_id                               NULL      NULL       NULL    748     Using where
1     PRIMARY        parent      ALL     left_id,right_id                      NULL      NULL       NULL    748     Range checked for each record (index map: 0x30)
2     DERIVED        node        const   PRIMARY,category_id,left_id           PRIMARY   4                  1     
2     DERIVED        parent      range   left_id,right_id                      left_id   5          NULL    17      Using where

Any idea what's going on? I can't afford this near 1 second execution time.

UPDATE:

-- phpMyAdmin SQL Dump
-- version 3.3.9
-- http://www.phpmyadmin.net
--
-- Host: localhost
-- Generation Time: Feb 16, 2011 at 10:58 PM
-- Server version: 5.0.91
-- PHP Version: 5.2.6
SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";

/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8 */;
--
-- Database: `foobar`
--
-- --------------------------------------------------------
--
-- Table structure for table `category`
--
CREATE TABLE IF NOT EXISTS `category`
  (
     `category_id`               INT(11) NOT NULL AUTO_INCREMENT,
     `name`                      CHAR(255) DEFAULT NULL,
     `category_seo_friendly_url` CHAR(255) DEFAULT NULL,
     `left_id`                   INT(11) DEFAULT '1',
     `right_id`                  INT(11) DEFAULT '2',
     PRIMARY KEY (`category_id`),
     UNIQUE KEY `seo_friendly_url_UNIQUE` (`category_seo_friendly_url`),
     KEY `category_id` (`category_id`),
     KEY `left_id` (`left_id`),
     KEY `right_id` (`right_id`)
  )
ENGINE=MyISAM
DEFAULT CHARSET=latin1
AUTO_INCREMENT=765; 

---

IME, MySQL does not do well at optimizing sub-queries - particularly it doesn't seem to manage push-predicates.

I am a little bit conmfused about what the query is actually intended to return - particularly the 'sub-parent'

You'd get some improvement by putting left_id and right_id into a single index.

While you'll also get some improvement by unrolling the query into a stored procedure, given that you seem to be traversing almost the entire dataset each time a better solution would be to denormalise the tree depth and store it as an attribute for each node. Indeed you seem to be traversing it at least twice in the outer query alone.

However I notice that at the end of the query:

HAVING depth > 0
   AND depth <= 1

Which surely is the same thing as

HAVING depth=1

Which then provides a very different way of optimizing the query (start by getting all the nodes where right=left+1 to find the nodes with no children and work up the way to check the category id).