How to rebuild Issue nested set tree

Added by @ go2null almost 3 years ago

I had a case with the issue tree (quite large - over 50,000 issues) being corrupted. I tried the rebuild function, but it didn't completely fix it, although it took over 12 hours to run.

[9] pry(main)> Issue.update_all(root_id: nil, lft: nil, rgt: nil)
[9] pry(main)> Issue.rebuild!

Also tried, but no different.

[9] pry(main)> Issue.update_all(root_id: nil, lft: nil, rgt: nil)
[9] pry(main)> Issue.rebuild!(false)

Found this on Redmine forums and adapted for issues. It ran in 1/2-hour and worked. It is written for MySQL, but should be easily adaptable to other databases.

-- http://www.redmine.org/issues/3722#note-4

DROP PROCEDURE IF EXISTS recalculateNestedSet;
DROP PROCEDURE IF EXISTS recalculateNestedSet_recurse;

DELIMITER //

CREATE PROCEDURE recalculateNestedSet()
BEGIN
    -- ensure root_id is correct for roots. Do it quickly here.
    UPDATE issues SET root_id = id WHERE parent_id IS NULL;

    -- MySQL didn't/doesn't allowed OUT or INOUT parameters
    SET @left_value = 1;

    -- now do recusion
    CALL recalculateNestedSet_recurse(NULL, NULL);
END
//

CREATE PROCEDURE recalculateNestedSet_recurse(root INTEGER, parent INTEGER)
BEGIN
    DECLARE done             INTEGER DEFAULT 0;
    DECLARE node             INTEGER;
    DECLARE roots     CURSOR FOR SELECT id FROM issues WHERE parent_id IS NULL  ORDER BY id;
    DECLARE children  CURSOR FOR SELECT id FROM issues WHERE parent_id = parent ORDER BY id;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

    -- MySQL setting - allow up to 10 stored procedure recursions. Default is 0.
    SET max_sp_recursion_depth = 10;

    -- this is bypassed on first run
    IF parent IS NOT NULL THEN
        UPDATE issues SET root_id = root, lft = @left_value WHERE id = parent;
        SET @left_value = @left_value + 1;
    END IF;

    OPEN roots;
    OPEN children;

    -- for 1st run, and for root nodes
    IF parent IS NULL THEN
        FETCH roots INTO node;
        REPEAT
        IF node IS NOT NULL THEN
            CALL recalculateNestedSet_recurse(node, node);
            SET @left_value = @left_value + 1;
        END IF;
        FETCH roots INTO node;
        UNTIL done END REPEAT;
    ELSE
        FETCH children INTO node;
        REPEAT
        IF node IS NOT NULL THEN
            CALL recalculateNestedSet_recurse(root, node);
            SET @left_value = @left_value + 1;
        END IF;
        FETCH children INTO node;
        UNTIL done END REPEAT;
END IF;
UPDATE issues set rgt = @left_value where id = parent;

CLOSE roots;
CLOSE children;
END
//
DELIMITER ;

CALL recalculateNestedSet;

Environment:
  Redmine version                2.6.0.stable
  Ruby version                   1.9.3-p484 (2013-11-22) [x86_64-linux]
  Rails version                  3.2.19
  Environment                    production
  Database adapter               Mysql2
SCM:
  Subversion                     1.6.17
  Git                            1.7.10.4
  Filesystem                     
Redmine plugins:
  redmine_custom_workflows       0.0.4
  redmine_exception_handler      1.0.0
  redmine_importer               1.2.2
  redmine_issue_checklist        2.0.5
  redmine_plugin_views_revisions 0.0.1

Replies (5)

RE: How to rebuild Issue nested set tree - Added by @ go2null over 2 years ago

I've created a GitHub repo for Redmine helper Scripts, and included this script.

RE: How to rebuild Issue nested set tree - Added by Hans Ginzel over 2 years ago

Based on Swinging From Tree to Tree Using CTEs by Adam Machanic I used in PostgreSQL

-- CREATE EXTENSION ltree;

-- build hierarchical id, level
-- http://www.postgresql.org/docs/current/static/queries-with.html
-- http://www.postgresql.org/docs/current/static/ltree.html
DROP TABLE IF EXISTS tmp_Issues;
CREATE TABLE tmp_Issues AS
WITH RECURSIVE t AS (
 SELECT    1 AS Level, text2ltree(CAST(i.Id AS text)) AS Path, i.Id, i.Parent_Id --, Subject
 FROM    Issues    AS i
 WHERE    i.Parent_Id IS NULL
     AND i.Project_Id = 1
UNION ALL
 SELECT    t.Level+1, t.Path||LPAD(CAST(i.Id AS text),3,'0'), i.Id, i.Parent_Id --, Subject
 FROM    t
     JOIN Issues    AS i    ON t.Id = i.Parent_Id
)
SELECT    Row_Number() OVER (ORDER BY Path) AS R, Level, Path, Parent_Id, Id --, Subject
FROM    t
ORDER    BY Path
WITH    DATA;

-- Ensure root_id is correct for roots. Do it quickly here. ToDo: Set Root_Id for siblings.
UPDATE Issues SET Root_Id = Id WHERE Parent_Id IS NULL AND Project_Id=1;

-- http://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/swinging-from-tree-to-tree-using-ctes-part-1-adjacency-to-nested-sets.aspx
UPDATE    Issues AS i
SET    Lft = nst.Lft,
    Rgt = nst.Rgt
FROM    (
 SELECT
    Id,
    Path,
    Level,
    R,
    (R * 2) - Level AS Lft,
    (R * 2) - Level + (
  SELECT    COUNT(*) * 2
  FROM    tmp_Issues    AS sub
  WHERE    sub.Path <@ i.Path
    ) - 1 AS Rgt
 FROM    tmp_Issues    AS i
 --ORDER    BY R;
)    AS nst    -- Nested set tree
WHERE    i.Id = nst.Id
    AND i.Project_Id = 1;

DROP TABLE IF EXISTS tmp_Issues;

-- vi: set ts=8 sw=8 nowrap:

PS: I am sorry, code reendering here does not properly work with tab stop (usually) default to 8 chars.

RE: How to rebuild Issue nested set tree - Added by Frederico Camara over 2 years ago

I used Bash to rebuild the projects nested tree, it's easy to convert, probably takes much longer to process but gives better control and preview:

Bash converting:

# SQL command to fetch necessary fields, output it to text archive "tree" 
SELECT id, parent_id, name FROM projects;

# Make a list "id|parentid|name" and sort by name
cat tree |
  cut -d "|" -f 2-4 |
  sed 's/^ *//;s/ *| */|/g' |
  sort -t "|" -k 3,3 > list

# Creates the parenthood chain on second field
while IFS="|" read i p o
do
  l=$p
  while [[ "$p" != "NULL" ]]
  do
    p=$(grep -w "^$p" list | cut -d "|" -f 2)
    l="$l,$p" 
  done
  echo "$i|$l|$o" 
done < list > listpar

# Creates left and right on 4th and 5th fields for interaction 0
let left=0
while IFS="|" read i l o
do
  let dif=$(grep "\b$i,NULL|" listpar | wc -l)*2+1
  let right=++left+dif
  echo "$i|$l|$o|$left|$right" 
  let left=right
done <<< "$(grep "|NULL|" listpar)" > i0

# The same for following interactions
n=0
while [ -s i$n ]
do
  while IFS="|" read i l nil left nil
  do
    grep "|$i,$l|" listpar |
    while IFS="|" read i l o
    do
      let dif=$(grep "\b$i,$l|" listpar | wc -l)*2+1
      let right=++left+dif
      echo "$i|$l|$o|$left|$right" 
      let left=right
    done
  done < i$n > i$((++n))
done

# Show concatenated
cat i*|sort -t"|" -k 4n

# SQL commands
while IFS="|" read id nil nil left right
do
  echo "UPDATE projects SET lft=$left, rgt=$right WHERE id=$id;" 
done <<< "$(cat i*)" 

RE: How to rebuild Issue nested set tree - Added by Felix Bünemann 4 months ago

Here's a fixed and improved version of the rebuild script for postgres posted by Hans Ginzel:

-- CREATE EXTENSION ltree;

BEGIN;
-- Lock issues for updates for the duration of the transaction.
-- Comment this out, if you need to allow issue updates while the rebuild is running,
-- but this could cause new or moved issues with wrong lft / rgt nodes.
LOCK TABLE issues IN EXCLUSIVE MODE;

-- build hierarchical id, level
-- http://www.postgresql.org/docs/current/static/queries-with.html
-- http://www.postgresql.org/docs/current/static/ltree.html
CREATE TEMP TABLE tmp_issues ON COMMIT DROP AS
WITH RECURSIVE t AS (
  SELECT 1 AS level, text2ltree(lpad(i.id::text, length((select max(id) from issues)::text), '0')) AS path, i.id, i.parent_id --, subject
  FROM issues AS i
  WHERE i.parent_id IS NULL
  UNION ALL
  SELECT t.level + 1, t.path || lpad(i.id::text, length((select max(id) from issues)::text), '0'), i.id, i.parent_id --, subject
  FROM t
  JOIN issues AS i ON t.id = i.parent_id
)
SELECT row_number() OVER (ORDER BY path) AS rownum, level, path, parent_id, id --, subject
FROM t
ORDER BY path
WITH DATA;

CREATE UNIQUE INDEX tmp_issues_id_idx ON tmp_issues (id);
CREATE INDEX tmp_issues_path_gist_idx ON tmp_issues USING GIST (path);
ANALYZE tmp_issues;

-- http://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/swinging-from-tree-to-tree-using-ctes-part-1-adjacency-to-nested-sets.aspx
UPDATE issues AS i
SET lft = nst.lft,
    rgt = nst.rgt
FROM (
  SELECT
    id,
    path,
    level,
    rownum,
    (rownum * 2) - level AS lft,
    (rownum * 2) - level + (
      SELECT count(*) * 2
      FROM tmp_issues AS sub
      WHERE sub.path <@ ti.path
    ) - 1 AS rgt
  FROM tmp_issues AS ti
  -- ORDER BY rownum
) AS nst -- nested set tree
WHERE i.id = nst.id;
COMMIT;

ANALYZE issues;

-- DROP EXTENSION ltree;

This script ran for around 5 minutes on a busy production db with around 65000 issues. The same update on the staging db with 37000 issues took 90 seconds.

If you have a large number of issues you should consider running the query when the system is not used or remove the LOCK TABLE statement, which has a chance of corrupting the lft / rgt nodes due to concurrent updates while the script is running.

RE: How to rebuild Issue nested set tree - Added by Guillermo ML 2 months ago

@ go2null -> thanks for your MySQL script, we still have an old 1.0.1.stable instance and the Issue_tree.rebuild! failed (don't know why) but your script worked like a charm. We only had to increment the max_sp_recursion_depth parameter.

(1-5/5)