cakephp/cakephp — pull request #1193 by AD7six (2013-03-24 17:31:12+00:00)
Title: make tree recovery much, much simpler

After talking about how complex and slow recovering trees can be, I realised it could be massively simpler. Using one the the test methods as an example (which has 7 nodes)

With the new code, 22 queries are executed (with only single-field updates updates):

SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` IS NULL ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 1 WHERE `NumberTree`.`id` = 1
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 1 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 2 WHERE `NumberTree`.`id` = 2
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 2 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 3 WHERE `NumberTree`.`id` = 3
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 3 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 4 WHERE `NumberTree`.`id` = 3
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 5 WHERE `NumberTree`.`id` = 4
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 4 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 6 WHERE `NumberTree`.`id` = 4
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 7 WHERE `NumberTree`.`id` = 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 8 WHERE `NumberTree`.`id` = 5
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 5 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 9 WHERE `NumberTree`.`id` = 6
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 6 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 10 WHERE `NumberTree`.`id` = 6
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = 11 WHERE `NumberTree`.`id` = 7
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `parent_id` = 7 ORDER BY `id` ASC LIMIT 100
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 12 WHERE `NumberTree`.`id` = 7
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 13 WHERE `NumberTree`.`id` = 5
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = 14 WHERE `NumberTree`.`id` = 1

With the old, 84 (and there are mutiple updates affecting more than one row):

SELECT `NumberTree`.`id`, `NumberTree`.`name` FROM `test`.`number_trees` AS `NumberTree` LEFT JOIN `test`.`number_trees` AS `VerifyParent` ON (`NumberTree`.`parent_id` = `VerifyParent`.`id`) WHERE 1 = 1 AND ((NOT (`NumberTree`.`parent_id` IS NULL)) AND (`VerifyParent`.`id` IS NULL))
SELECT `NumberTree`.`id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 ORDER BY `lft` ASC
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 2
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 2
UPDATE `test`.`number_trees` SET `lft` = 1, `rght` = 2 WHERE `test`.`number_trees`.`id` = '2'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 1
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 1
UPDATE `test`.`number_trees` SET `lft` = 3, `rght` = 4 WHERE `test`.`number_trees`.`id` = '1'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 3
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 3
UPDATE `test`.`number_trees` SET `lft` = 5, `rght` = 6 WHERE `test`.`number_trees`.`id` = '3'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 4
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 4
UPDATE `test`.`number_trees` SET `lft` = 7, `rght` = 8 WHERE `test`.`number_trees`.`id` = '4'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 5
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 5
UPDATE `test`.`number_trees` SET `lft` = 9, `rght` = 10 WHERE `test`.`number_trees`.`id` = '5'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 6
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 6
UPDATE `test`.`number_trees` SET `lft` = 11, `rght` = 12 WHERE `test`.`number_trees`.`id` = '6'
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 7
SELECT COUNT(*) AS `count` FROM `test`.`number_trees` AS `NumberTree` WHERE `NumberTree`.`id` = 7
UPDATE `test`.`number_trees` SET `lft` = 13, `rght` = 14 WHERE `test`.`number_trees`.`id` = '7'
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 ORDER BY `lft` ASC
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 2 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 1 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 3
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 3
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 13 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 13 WHERE `NumberTree`.`rght` > 14
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 1 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 4
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 4
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 4 WHERE `NumberTree`.`lft` > 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 4 WHERE `NumberTree`.`rght` > 1
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 3 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 2 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 4 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 4 WHERE `NumberTree`.`rght` > 14
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 4 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 2 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 4 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 4 WHERE `NumberTree`.`rght` > 14
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 5 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 1 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 13
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 13
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 3 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 3 WHERE `NumberTree`.`rght` > 14
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 6 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 5 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 4 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 4 WHERE `NumberTree`.`rght` > 14
SELECT `NumberTree`.`id`, `NumberTree`.`parent_id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 7 LIMIT 1
SELECT MAX(`NumberTree`.`rght`) AS `rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 LIMIT 1
SELECT `NumberTree`.`id`, `NumberTree`.`lft`, `NumberTree`.`rght` FROM `test`.`number_trees` AS `NumberTree` WHERE 1 = 1 AND `NumberTree`.`id` = 5 LIMIT 1
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` + 14 WHERE `NumberTree`.`lft` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` + 14 WHERE `NumberTree`.`rght` BETWEEN 1 AND 2
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 2 WHERE `NumberTree`.`lft` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 2 WHERE `NumberTree`.`rght` BETWEEN 2 AND 12
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`lft` = `NumberTree`.`lft` - 4 WHERE `NumberTree`.`lft` > 14
UPDATE `test`.`number_trees` AS `NumberTree` SET `NumberTree`.`rght` = `NumberTree`.`rght` - 4 WHERE `NumberTree`.`rght` > 14

The only disadvantage I see to this approach is that the tree is invalid during recovery, and since it's recursive with incredibly deep trees it may fail (though, is is realistic to have a tree with e.g. more than 200 levels of nesting..?).

Thoughts?

cc @rchavik