title: Nested set model optimization
body: <p>I have a website that contains ~100K pages (200-300 concurrent users). Each page has his own record in mysql InnoDB table - <em>page</em>:</p>
  
  <pre><code>page_id
  page_parent
  left_id
  right_id
  page_subject
  page_children
  page_depth
  ....
  </code></pre>
  
  <p>As you can see I use nested set model to display hierarchy of pages, etc etc.. Everything seems to be fine except performance of INSERT, UPDATE and DELETE statement. Moving page from one parent to another is extremely slow and sometimes takes ~30 sec (!!)</p>
  
  <pre><code> CREATE PROCEDURE `PAGE_MOVE`(IN `pageSrc` INT, IN `pageDst` INT)
      LANGUAGE SQL
      NOT DETERMINISTIC
      CONTAINS SQL
      SQL SECURITY DEFINER
      COMMENT ''
  BEGIN
      DECLARE srcLeftId INT;
      DECLARE srcRightId INT;
      DECLARE dstLeftId INT;
      DECLARE dstRightId INT;
      DECLARE width INT;
  
      SELECT left_id, right_id, right_id - left_id + 1
      INTO srcLeftId, srcRightId, width
      FROM page
      WHERE page_id = pageSrc;
  
      IF pageDst &gt; 0 THEN
          SELECT left_id, right_id
          INTO dstLeftId, dstRightId
          FROM page
          WHERE page_id = pageDst;
      ELSE
          SELECT MAX(right_id) INTO dstLeftId FROM page WHERE page_parent = 0;
          SET dstRightId = dstLeftId + 1;
      END IF;
  
      IF dstLeftId &gt; 0 THEN
  
          UPDATE page SET page_children = page_children - (width / 2)
          WHERE left_id &lt; srcLeftId AND right_id &gt; srcRightId;
  
          UPDATE page SET page_children = page_children + (width / 2)
          WHERE left_id &lt;= dstLeftId AND right_id &gt;= dstRightId;
  
          /**
           * Set nagative values to left_id and right_id (temporary)
           */
          UPDATE page
          SET left_id = -left_id, right_id = -right_id
          WHERE left_id &gt;= srcLeftId AND right_id &lt;= srcRightId;
  
          UPDATE page SET left_id = left_id - width WHERE left_id &gt; srcLeftId;
          UPDATE page SET right_id = right_id - width WHERE right_id &gt; srcRightId;
  
          UPDATE page SET left_id = left_id + width
          WHERE left_id &gt;= IF(dstRightId &gt; srcRightId, dstRightId - width, dstRightId);
  
          UPDATE page SET right_id = right_id + width
          WHERE right_id &gt;= IF(dstRightId &gt; srcRightId, dstRightId - width, dstRightId);
  
          SET @diff = IF(dstRightId &gt; srcRightId, dstRightId - srcRightId -1, dstRightId - srcRightId - 1 + width);
  
          UPDATE page
          SET left_id = -left_id + @diff,
               right_id = -right_id + @diff
          WHERE left_id &lt;= -srcLeftId AND right_id &gt;= -srcRightId;
          /**
           * Set parent_id and page_depth
           */
          UPDATE page SET page_parent = pageDst, page_depth = GET_PAGE_DEPTH(page_id) WHERE page_id = pageSrc;
  
          /**
           * Update page_depth in children's nodes
           */
          IF width &gt; 2 THEN
  
              SELECT left_id, right_id
              INTO srcLeftId, srcRightId
              FROM page
              WHERE page_id = pageSrc;
  
              UPDATE page
              SET page_depth = GET_PAGE_DEPTH(page_id)
              WHERE left_id &gt;= srcLeftId AND right_id &lt;= srcRightId;      
          END IF;
  
  
      END IF;
  END
  </code></pre>
  
  <p>How could I optimize this procedure? Or maybe question should be: What is the alternative of using nested set model? </p>
  
  <p>Function GET_PAGE_DEPTH():</p>
  
  <pre><code>CREATE FUNCTION `GET_PAGE_DEPTH`(`pageId` MEDIUMINT UNSIGNED)
      RETURNS smallint(6)
      LANGUAGE SQL
      DETERMINISTIC
      READS SQL DATA
      SQL SECURITY DEFINER
      COMMENT ''
  BEGIN
      RETURN (
          SELECT COUNT(*) -1 AS depth
          FROM page AS parent
          INNER JOIN page AS node ON node.page_id = pageId
          WHERE node.left_id BETWEEN parent.left_id AND parent.right_id
      );
  END
  </code></pre>
  
  <p>Hardware: Quad Core Q6600 (4x 2.40+ GHz), 4GB RAM</p>
  
  <p>Thanks for any advice! </p>
  
  <p>EDITED:</p>
  
  <p>Table page looks like this:</p>
  
  <pre><code>CREATE TABLE `page` (
    `page_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `page_parent` int(10) unsigned DEFAULT NULL,
    `left_id` int(11) NOT NULL,
    `right_id` int(11) NOT NULL,
    `page_module` smallint(5) unsigned NOT NULL,
    `page_connector` smallint(5) unsigned NOT NULL,
    `page_subject` varchar(255) NOT NULL,
    `page_title` varchar(255) DEFAULT NULL,
    `page_path` varchar(255) NOT NULL,
    `page_text` int(10) unsigned DEFAULT NULL,
    `page_children` mediumint(8) unsigned NOT NULL,
    `page_depth` smallint(5) unsigned NOT NULL DEFAULT '0',
    `page_content` tinyint(3) unsigned NOT NULL,
    `page_publish` tinyint(1) unsigned NOT NULL DEFAULT '1',
    `page_published` datetime DEFAULT NULL,
    `page_unpublished` datetime DEFAULT NULL,
    `page_time` int(10) unsigned NOT NULL,
    `page_edit_time` int(10) unsigned NOT NULL,
    `page_delete` tinyint(1) unsigned NOT NULL DEFAULT '0',
    `page_richtext` tinyint(1) unsigned NOT NULL DEFAULT '0',
    `page_cache` tinyint(1) unsigned NOT NULL DEFAULT '1',
    `page_template` varchar(255) NOT NULL,
    PRIMARY KEY (`page_id`),
    KEY `page_parent` (`page_parent`),
    KEY `left_id` (`left_id`),
    KEY `right_id` (`right_id`),
    KEY `page_depth` (`page_depth`),
    KEY `page_path` (`page_path`),
    KEY `page_connector` (`page_connector`),
    KEY `page_text` (`page_text`)
  ) ENGINE=InnoDB  DEFAULT CHARSET=utf8;
  </code></pre>