Quel est un moyen efficace de stocker et récupérer une structure imbriquée de profondeur arbitraire dans Postgres ?

Question

Dans mon application ruby-on-rails, j'ai des commentaires imbriqués qui peuvent être imbriqués à une longueur arbitraire.

J'ai essayé différentes façons de stocker cela :

Utiliser des auto-jointures :

belongs_to :parent, :class_name => 'Comment', :foreign_key => 'parent_id'
has_many :children, :class_name => 'Comment', :foreign_key => "parent_id"

Utiliser la gem ancestry

etc

Cependant, le problème est que peu importe ce que j'utilise, il y aura toujours un nombre linéaire de déclarations SQL. (1 déclaration pour récupérer tous les commentaires racine, puis 1 déclaration pour chaque enfant de la racine, puis 1 déclaration pour tous les enfants de cela, etc)

Y a-t-il un moyen plus efficace d'accomplir cela ?

Postgres 9.1, mais les solutions compatibles avec les versions antérieures sont préférées.

Answer 1

Vous pourriez rester avec votre colonne de pointeur parent_id et utiliser find_by_sql et une requête WITH RECURSIVE et laisser la base de données faire tout le travail en une seule fois. Quelque chose comme ceci :

comments = Comment.find_by_sql(%Q{
    with recursive tree(id) as (
        select c.id, c.column1, ...
        from comments c
        where c.id in (#{roots.join(',')})
        union all
        select c.id, c.column1, ...
        from comments c
        join tree on c.parent_id = tree.id
    )
    select id, column1, ...
    from tree
})

où roots serait un tableau Ruby contenant les id des nœuds racine qui vous intéressent. Cela vous donnera tous les nœuds dans les sous-arbres d'intérêt en tant qu'instances de Comment. J'ai utilisé des requêtes comme celle-ci dans le passé et WITH RECURSIVE était bien plus de deux fois plus rapide que votre technique itérative même avec des arbres peu profonds, je suppose que des arbres plus profonds verraient encore de meilleures accélérations.

La structure parent_id que vous utilisez est très pratique pour la plupart des choses et s'harmonise très bien avec la façon dont ActiveRecord veut fonctionner. De plus, rester avec votre structure actuelle signifie que vous pouvez laisser le reste de votre application intact.

WITH RECURSIVE est disponible dans PostgreSQL 8.4 et supérieur.

Answer 2

Jetez un œil à awesome_nested_set, je pense que vous allez l'adorer.

https://github.com/collectiveidea/awesome_nested_set

Answer 3

Il existe de nombreux articles qui discutent des options classiques (c'est-à-dire basées sur SQL de base). Par exemple, celui-ci est un résumé décent des options classiques et cet article traite de l'utilisation de requêtes récursives avec Rails.

Cependant, puisque vous utilisez Postgressql (et sinon commencez) vous avez la possibilité d'utiliser l'extension ltree qui crée des index spécifiquement adaptés aux structures en arbre. J'aurais utilisé ltree_hierarchy mais il s'avère que postgres ne supporte pas les tirets dans les libellés ltree, ce qui rend incompatible l'utilisation de uuid pour mes identifiants. J'ai opté pour la gem ancestry malgré le fait qu'elle n'utilise pas les fonctionnalités sympas (le seul autre choix réel en 2021 est awesome_nested_set, qui a une documentation sur "comment créer un index text_pattern_ops pour votre colonne postgresql".