Discussion :

[zeb_zed]

Bonjour à tous,

Je développe un site dont le système est plus au moins similaire à disqus (système de commentaires avec pagination des commentaires)

Schématiquement:
une table item (plusieurs millions)
une table user (plusieurs millions)
une table comments (plusieurs millions) <== c'est là que je m'interroge

(mon environnement : PostgreSQL 9.1 + JPA Hibernate)

Je me demandais quelle pouvait être la meilleurs manière de persister en DB les informations de l'arbre des commentaires.

D'après ce lien:
Models for hierarchical data
Il existe 4 manières différentes de faire :
1 - "adjacency liste" : le plus commun, chaque noeud contient l'id de son parent
2 - "path énumération" : les chemins matérialisés
3 - nested set : arbre par représentation intervallaire
4 - closure table
5 - recursive CTE

Pour le 1 : cela implique des sous requêtes complexes et non performantes
Pour le 2 : ca me semble bien mais je crains que les requêtes sur des path avec des like % soit couteux
pour le 3 : l'idée est bonne mais dès que tu ajoutes un nœud il faut recalculer tous les autres, je pense que c'est une mauvaise idée pour des tables volumineuses et dont les insertions sont fréquentes (je table sur des millions de rows)
pour le 4 : ça semble idéal mais il y a peu de retour utilisateur et c'est surtout l'auteur de ce pattern qui en fait l'éloge donc j'ai des doutes (d'autant que j'ai l'impression que cette technique peut devenir très consommatrice en terme d'espace disque si l'arborescence est profonde)
pour le 5 : je sais que PostgreSQL supporte ça mais je ne pense pas que ça s'interface facilement avec Hibernate.

Je sais que d'autres solutions dérivées du nested set existent mais je n'ai pas la compétence pour juger de leur intérêt dans mon cas (entre autre : Nested Intervals Tree Encoding with Continued Fractions qui semble bien mais assez complexe à mettre en œuvre)

Bref, je ne sais pas quelle solution choisir parmi les 4 (même si je penche pour la 2 et la 4)

N'importe laquelle des solutions pourrait aller mais je dois choisir celle qui assure les meilleurs performances (table énorme et sollicitations très fréquentes) et une bonne maintenabilité.

vos avis et retours d'expériences sont les bienvenus

Merci

[SQLpro]

de toutes la meilleure solution est généralement l'arbre intervallaire, spécialement si le classement arborescent ne varie pas au fil du temps (pas d'update concernant les bornes de l’intervalle.

Lisez les articles que j'ai écrit à ce sujet :
http://sqlpro.developpez.com/cours/arborescence/
http://blog.developpez.com/sqlpro/p8...allaire-proce/
http://blog.developpez.com/sqlpro/p7...dure-de-depla/
http://blog.developpez.com/sqlpro/p7...dure-de-derec/

A noter 1 et 5 reviennent au même...

A +

[zeb_zed]

Bonjour SQLpro,

Tes articles ont bien sur été le point de départ de ma réflexion

Cependant, malgré toutes les qualités des arbre intervallaires, je ne suis pas sur que c'est adapté dans mon cas (rappel: fort trafic et fort volume) car :
1 - j'ai des tables volumineuses (dès que tu ajoutes un nœud il faut recalculer tous les autres). De plus, je trouve qu'on perd le principe d'indépendance des rows du relationnel en recalculant les intervalles
2 - j'ai de nombreux accès concurrents (j'imagine que le recalcul des intervalles lors d'une insertion doit poser de nombreux verrous sur la base... pas glop)

[SQLpro]

Il faut être un peu plus malin... et ne pas oublier de penser...

1) le volume n'est pas important. J'ai mis en œuvre des arbres intervallaire testé au départ avec un millions de lignes et qui sont aujourd'hui sur plusieurs dizaines de millions. Plus l'arbre est profond et plus on est gagnant par rapport au modèle adjacent ou path
2) si tu as peur que la mise à jour soit bloquante, on peut au choix :
2.1) placer les composantes de l'arbre dans une table externe, et présenter une
vue
2.2) utiliser des intervalles décimaux qui ne propagent pas les updates. Cela s'apelle "Modélisation intervallaire par intercalage" (voir ma très ancienne présentation pour InterBase/FireBird : http://sqlpro.developpez.com/cours/borcon2003/)

A +

[zeb_zed]

Merci pour la qualité de ta réponse.

2.1) placer les composantes de l'arbre dans une table externe, et présenter une
vue

La perspective ne m'enchante guère... en tant que développeur java, j'ai tendance à effectuer la majorité du traitement coté applicatif et de ne pas laisser la base s'en charger, par manque de compétences dans ce domaine. J'ai aussi tendance à simplifier au maximum les choses et créer une vue pour résoudre un problème de mise à jour bloquante me parait un peu lourd à gérer.

2.2) utiliser des intervalles décimaux qui ne propagent pas les updates. Cela s'apelle "Modélisation intervallaire par intercalage" (voir ma très ancienne présentation pour InterBase/FireBird : http://sqlpro.developpez.com/cours/borcon2003/)

La perspective évoquée dans ta présentation est très séduisante
Ça rejoint l'article "Nested Intervals Tree Encoding with Continued Fractions" qui explique la mise en œuvre de ce principe. A première vue, ça semble assez complexe à mettre en œuvre. Et le requétage étant plus long en flottant qu'avec des numériques, je me dis autant utiliser dans ce cas des chemins matérialisés qui ont les mêmes avantages que la Modélisation intervallaire par intercalage sans la complexité apparente.

Également, il est difficile de récupérer uniquement les enfants d'un noeud avec les nested set ou les chemins matérialisés alors que les "closure table" le permette.
J'ai l'impression que les "closure table" permettent autant voir plus de souplesse que les nested set. Le recalcul des rows des nested set nécessite un update sur chacun des noeuds, soit un lock sur chacun des noeuds. Les closures table ne nécessitent qu'un insert donc pas de lock sur les noeuds (je dis peut être des bêtises, je ne suis pas compétant dans le mécanisme des verrous)

quelle dilemme!

[SQLpro]

NON, non, non et non !!! Vous commettez de nombreuses fautes dans votre raisonnement !

...
La perspective ne m'enchante guère... en tant que développeur java, j'ai tendance à effectuer la majorité du traitement coté applicatif et de ne pas laisser la base s'en charger,

C'est la pire de choses pour les performances. D'un coté vous demandez un conseil sur les perf. De l'autre vous allez détruire tous les axes de performances possible. Lisez l'article que j'ai écrit au sujet du style de dev.
http://sqlpro.developpez.com/cours/b...s-epaisses.pdf
Si vous voulez des perf, me seule moyen est de mettre le maximum d'intelligence dans le base et le minimum du côté client; En effet un code client (donc itératif) n'est jamais optimisable dynamiquement, alors que c'est ce que pratiquent en permanence les bons SGBGDR du fait du code ensembliste, de l'indexation, de l'optimiseur et des contraintes !

par manque de compétences dans ce domaine. J'ai aussi tendance à simplifier au maximum les choses et créer une vue pour résoudre un problème de mise à jour bloquante me parait un peu lourd à gérer.

Manue de compétence, c'est hélas le point n°1 des mauvaises perf... quand on ne sait pas comment fonctionne un système quelconque il est impossible d'en tirer le meilleur partit !
De plus l'usage des vues est normalement impérative. Aucune application ne devrait attaquer directement les tables ! L'ensemble des vues et des routines (procédures, fonctions, déclencheurs...) con situant le MED (Modèle Externe de Données). Pensez simplement à ceci : que va t-il se passer une fois votre application écrite si il faut restructurer une table parce que les performance,ces ne sont pas bonnes ? Avec une vue, vous n'avez pas à récrire toute votre application. En utilisant un accès directe aux tables, vous êtes dans le merde....

La perspective évoquée dans ta présentation est très séduisante
Ça rejoint l'article "Nested Intervals Tree Encoding with Continued Fractions" qui explique la mise en œuvre de ce principe. A première vue, ça semble assez complexe à mettre en œuvre. Et le requétage étant plus long en flottant qu'avec des numériques,

Vous confondez entier et décimaux. En SQL il existe 3 types de nombres: les entiers (smallint, INT, BIGINT), les décimaux (DECIMAL, NUMEFRIC) et les réels (REAL, FLOAT). Vous ne devez surtout pas utiliser les réels car vous pourriez perdre définitivement certaines bornes du fait de l'imprécision des calculs en virgule flottante. C'est pourquoi SQL propose les décimaux qui ne sont pas entachés de ce problème

je me dis autant utiliser dans ce cas des chemins matérialisés qui ont les mêmes avantages que la Modélisation intervallaire par intercalage sans la complexité apparente.

Pas du tout !!!! Les performances d'une base de données relationnelle sont directement liées à la volumétrie et à la non redondance des informations. Avec ce modèle vous explosez les deux, à moins de trouver un moyen de compresser le path, comme le fait MS SQL Server depuis la version 2008 avec le type Hierarchyid (mais c'est toujours pas aussi bon que l'intervallaire).L

Également, il est difficile de récupérer uniquement les enfants d'un noeud avec les nested set ou les chemins matérialisés alors que les "closure table" le permette.
J'ai l'impression que les "closure table" permettent autant voir plus de souplesse que les nested set. Le recalcul des rows des nested set nécessite un update sur chacun des noeuds, soit un lock sur chacun des noeuds. Les closures table ne nécessitent qu'un insert donc pas de lock sur les noeuds (je dis peut être des bêtises, je ne suis pas compétant dans le mécanisme des verrous)

quelle dilemme!

Ne vous posez pas les problématique de verrouillage; C'est le SGBDR qui les gèrent au mieux en fonction notamment de :

• la granularité des informations à verrouiller
• de la nature de la transaction
• de la concurrence à l'instant t

le fait de déporter Les données intervallaire dans une table à part minimise encore plus ces verrous....

Le choix d'un bon SGBDR pour gérer cela est encore plus important. par exemple MySQL comme PostGreSQL ne sont pas réellement des SGBD relationnel dans le sens ou il ne sont pas capable de réaliser des traitements ensemblistes. Lisez l'article que j'ai écrit à ce sujet : http://blog.developpez.com/sqlpro/p1...d-relationn-1/
Pire, MySQL est farci de bug tous plus débiles les uns que les autres. A me lire : http://blog.developpez.com/sqlpro/p9...udre-aux-yeux/

A +