SET @search_num:='2';
SELECT
--    ch.`level` AS lvl,
    If(@pr<>ch.`parent_id`,
      Greatest(@array:=REPLACE(@array, @prc, ''),
        @prc:=Concat(',',ch.`parent_id`,','),
        @pr:=ch.`parent_id`),
      @pr) AS parent,
    Greatest(ch.`id`,
		  If(Locate(@prc, @array) > 0,
        @array:=Concat(@array, Concat(',',ch.`id`,',')),
        '')
    ) AS childs
  FROM (
        SELECT @prc:=@array:=Concat(',',@pr:=@search_num,',')
      ) AS dummy,
      `catalog` AS ch -- FORCE INDEX (`PRIMARY`) # if present other index!
  WHERE Locate(Concat(',',ch.`parent_id`,','), @array) > 0;

/* 0 rows affected, 50 rows found. Duration for 2 queries: 0,000 sec. */

/* 0 rows affected, 1 274 rows found. Duration for 5 queries: 0,109 sec. */

SET group_concat_max_len = 65533;
SET @branch = '2';
SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Find_in_set(c.`parent_id`, @branch)
    AND NOT Find_in_set(c.`id`, @branch)
  ORDER BY `branch` DESC LIMIT 1
/* 0 rows affected, 1 rows found. Duration for 2 queries: 0,078 sec. */

SET @branch = '2';
SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Locate(Concat(',', c.`parent_id`), Concat(',', @branch))
    AND NOT Locate(Concat(',', c.`id`), Concat(',', @branch))
  ORDER BY `branch` DESC LIMIT 1
/* 0 rows affected, 1 rows found. Duration for 2 queries: 0,156 sec. */

SELECT
  ch.`id` AS child, ch.`parent_id` AS parent, ch.`level` AS level
  , @array := CONCAT(@array, CONCAT(',',ch.`id`,',')) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree1` AS ch  FORCE INDEX (level)
WHERE
  LOCATE(CONCAT(',',ch.`parent_id`,','), @array) > 0
;
--# индекс: `level` (`level`,`parent_id`,`id`) лучше делать единственным и первичным ключом таблицы
--# тогда можно не прибивать гвоздями...
--# В этом случае надо забыть про автоинтремент, требующий собственного отдельного индекса...

TABLE cat (
 id        INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
 parentID  INT UNSIGNED NOT NULL,
 catName   CHAR(50) NOT NULL
)

TABLE cat_relations (
 id        INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
 parentID  INT UNSIGNED NOT NULL,
 childID   INT UNSIGNED NOT NULL,
 UNIQUE KEY rel (parentID,childID)
)

INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM    (
           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID
       ) AS aa

INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM    (
           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID
       ) AS aa

           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID

INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM (все потомки ноды2)  AS aa