search

chrisroberts / acts_as_sane_tree

Sane tree builder for ActiveRecord and PostgreSQL
http://chrisroberts.github.com/acts_as_sane_tree
53 stars 20 forks source link

Fix performance issue when getting descendants. #2

Open Gee-Bee opened 9 years ago

Gee-Bee commented 9 years ago

When building tree, database is hitted for each node, looking up its parent node. The culprit is here: https://github.com/chrisroberts/acts_as_sane_tree/blob/d7aa2dbce7f07801c3d30a9494ac0c5bb14d6086/lib/acts_as_sane_tree/singleton_methods.rb#L150-L151. My branch fixes this issue.

This is example output before:

pry(main)> PWD.nodes_and_descendants(to_depth: 2)                                                                                                                [88/1827]
  PWD Load (3.3ms)  SELECT "pwds".* FROM (WITH RECURSIVE crumbs AS (
          SELECT pwds.*, 0 AS depth FROM pwds WHERE parent_id IS NULL
          UNION ALL
          SELECT alias1.*, crumbs.depth + 1 FROM crumbs JOIN pwds alias1 on alias1.parent_id = crumbs.id
          WHERE crumbs.depth + 1 < 2
        ) SELECT * FROM crumbs) as pwds WHERE (pwds.depth >= 0) AND (pwds.depth + 1 < 4)
  PWD Load (0.4ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.4ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.4ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.6ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.2ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.2ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.4ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.9ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.4ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.5ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.3ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.2ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]
  PWD Load (0.2ms)  SELECT  "pwds".* FROM "pwds" WHERE "pwds"."id" = $1 LIMIT 1  [["id", 3]]

and after:

pry(main)> PWD.nodes_and_descendants(to_depth: 2)
  PWD Load (1.8ms)  SELECT "pwds".* FROM (WITH RECURSIVE crumbs AS (
          SELECT pwds.*, 0 AS depth FROM pwds WHERE parent_id IS NULL
          UNION ALL
          SELECT alias1.*, crumbs.depth + 1 FROM crumbs JOIN pwds alias1 on alias1.parent_id = crumbs.id
          WHERE crumbs.depth + 1 < 2
        ) SELECT * FROM crumbs) as pwds WHERE (pwds.depth >= 0) AND (pwds.depth + 1 < 4)