[spip-dev] [Spip-zone-commit] r20100 - in /_plugins_/_test_/sql_arbo: ./ base/ base/abstract_arbre.php

Dev
1

Oui, il est très clair dans mon esprit que la gestion des acces restreint doit passer par une gestion intervalaire a moyen terme car c'est bien plus efficace et rapide en terme de code.
Par ailleurs, l'implémentation actuelle d'acces retreint casse sur les gros sites lorsqu'on a beaucoup de rubriques visibles (ou restreintes, c'est selon)
pour cause de dépassement mémoire (la faute à un array qui stocke les id des rubriques en memoire).

Toutefois, cela suppose que les rubriques soient aussi implémentées de façon intervalaire (ce qui accélérerait notablement certains critères comme 'branche').
Les transactions n'étant pas disponibles pour mysql tout venant, je pencherai pour conserver une double implémentation :
- id_parent qui sert à pointer sur le parent, et resterait la référence
- bord_gauche, bord_droit, niveau, qui seraient utilisées par l'implémentation intervalaire.

Passer à ce mode de réprésentation ne casserait aucune compat, et permetrait de bénéficier des gains en perfos au prix de 3 champs supplémentaires (on peut en gagner un à terme en supprimant id_secteur).

Mais cela suppose in fine :
- que l'api gère le double système id_parent + bord_gauche/bord_droite/niveau
- l'id_parent reste la référence car manipulable un une requete sur un enregistrement
- avoir une fonction de reconstruction des bords gauche et droite par parcours de l'arbre
- avoir un critère "d'arbre douteux", qui sera testé dans la fonction 'propager_les_secteurs', qui peut reposer simplement sur quelques conditions simples testables en une requete unique :
  - max(bord_droite) = 2xN (le nombre de rubriques)
  - bord_droite>bord_gauche pour toutes les rubriques
  - somme(bord_gauche)+somme(bord_droite) = N.(N+1)/2
  - somme(bord_gauche^2)+somme(bord_droite^2) = (2.N + 1).(N+1) . N/6
si une incohérence est detectée, lancer la reconstruction des bords de chaque noeud, par parcourt de l'arbre

Avec une telle implémentation, il me semble que l'on couvre tous les besoins, sans casser la compat (raison pour laquelle je serais d'avis de maintenir le champ id_secteur dans un premier temps, en l'annonçant obsolete, le critère pouvant lui être remplacé par une condition sur les bords)

Cédric

2

S'lt

Oui, il est très clair dans mon esprit que la gestion des acces
restreint doit passer par une gestion intervalaire a moyen terme car
c'est bien plus efficace et rapide en terme de code.

Ouf rassuré :slight_smile:

Toutefois, cela suppose que les rubriques soient aussi implémentées
de façon intervalaire (ce qui accélérerait notablement certains
critères comme 'branche').

J'avais dans l'idée qu'on pourrait faire sauter à terme ce id_secteur.

La table spip_auteurs_rubriques serait du coup pas mal allégée, nous
n'aurions besoin de ne connaître que l'id_rubrique qui sert de noeud
principal les sous rubriques découlant naturellement de l'intervalle.

Les transactions n'étant pas disponibles pour mysql tout venant, je
pencherai pour conserver une double implémentation :
- id_parent qui sert à pointer sur le parent, et resterait la référence
- bord_gauche, bord_droit, niveau, qui seraient utilisées par
l'implémentation intervalaire.

Le test d'api va dans ce sens, les 2 approches sont complémentaires.
Pour le problème transactionnel de mysql, ta technique est pas mal.

Passer à ce mode de réprésentation ne casserait aucune compat, et
permetrait de bénéficier des gains en perfos au prix de 3 champs
supplémentaires (on peut en gagner un à terme en supprimant id_secteur).

On ajoute seulement 2 champs seulement bord_droit et bord_gauche. Mais
j'ai peut être zappé un truc, ce qui est bien possible vu que
j'explore et je dev dans le même temps.

Ahh tu parles d'un champ 'niveau' ? A priori pas besoin, on peut le
faire simplement à l'aide d'un count()

Mais cela suppose in fine :
- que l'api gère le double système id_parent + bord_gauche/
bord_droite/niveau

L'api ne supprime pas l'id_parent et de plus l'exploite pour faire les
insertions de noeuds

- l'id_parent reste la référence car manipulable un une requete sur
un enregistrement

ouaips

- avoir une fonction de reconstruction des bords gauche et droite par
parcours de l'arbre

Première fonction developpée dans l'api avec sql_arbre_convertir()

- avoir un critère "d'arbre douteux", qui sera testé dans la fonction
'propager_les_secteurs', qui peut reposer simplement sur quelques
conditions simples testables en une requete unique :
        - max(bord_droite) = 2xN (le nombre de rubriques)
        - bord_droite>bord_gauche pour toutes les rubriques
        - somme(bord_gauche)+somme(bord_droite) = N.(N+1)/2
        - somme(bord_gauche^2)+somme(bord_droite^2) = (2.N + 1).(N+1) . N/6
si une incohérence est detectée, lancer la reconstruction des bords
de chaque noeud, par parcourt de l'arbre

La reconstruction ne peut se faire que si nous gardons la logique id_parent.
J'avais pas encore fait mes critère de validité de l'arbre. Merci

Avec une telle implémentation, il me semble que l'on couvre tous les
besoins, sans casser la compat (raison pour laquelle je serais d'avis
de maintenir le champ id_secteur dans un premier temps, en
l'annonçant obsolete, le critère pouvant lui être remplacé par une
condition sur les bords)

Deja faisons une api qui tienne la route :slight_smile:

L'idée c'est de garder ce qui fonctionne bien actuellement mais de
laisser la porte à d'autre développement complémentaires.

Par exemple on peut tout à fait garder le comportement actuellement
des mots clefs :
- en fusionnant groupes et mots
- les groupes deviennent des noeuds, les mots des feuilles
- avec un simple contrôle on peut bloquer la génération arborescente
par calcul du niveau

De là on peut ouvrir la porte à une arborescence plus fouillée sans
qu'on est à trifouiller dans la structure même des bases.

Pour ma part je vois bien :
Pour le core : la gestion actuelle des mots clef en intervallaire avec
les limitations actuelles

Pour les plugins :
- la gestion arborescente qui débriderai juste les niveaux et
permettrait d'affecter comme mot clef un groupe.

- la gestion technique avec sa propre interface.

Ainsi techniquement on mutualise et on ouvre la porte à des
développements parallèles.

Km

3

D'accord pour ce plan, sauf sur un point : il ne faut PAS, à mon avis,
virer id_secteur, ni la déclarer obsolète. Car c'est bien utile pour
ceux qui n'ont pas le temps de se plonger dans les arcanes
algorithmiques de la représentation intervallaire. Mais il faut écrire
quelque part que c'est une valeur calculée et redondante (tout comme
les intervalles), la valeur maîtresse étant id_parent (si j'ai bien
compris).

-- Fil

4

S'lt

D'accord pour ce plan, sauf sur un point : il ne faut PAS, à mon avis,
virer id_secteur, ni la déclarer obsolète. Car c'est bien utile pour
ceux qui n'ont pas le temps de se plonger dans les arcanes
algorithmiques de la représentation intervallaire.
Mais il faut écrire
quelque part que c'est une valeur calculée et redondante (tout comme
les intervalles),

J'avais dans l'idée de proposer une sql_arbre_get_racine() ?

la valeur maîtresse étant id_parent (si j'ai bien
compris).

L'idée c'est de ne connaître que l'id_objet qui nous intéresse. Comme
c'est le cas actuellement.
id_parent si c'est une insertion par rapport au parent ou l'id_enfant
si c'est une insertion par rapport à un enfant.

Hum est du coup le return de l'insertion serait l'id de l'objet inséré.

Les bordures restant à la discrétion de l'api.

5

la valeur maîtresse étant id_parent (si j'ai bien
compris).

L'idée c'est de ne connaître que l'id_objet qui nous intéresse. Comme
c'est le cas actuellement.
id_parent si c'est une insertion par rapport au parent ou l'id_enfant
si c'est une insertion par rapport à un enfant.

C'est quoi une insertion par rapport à un enfant ???

-Nicolas

6

C'est quoi une insertion par rapport à un enfant ???

Par exemple un nouveau parent. Je pensais aussi au cas d'insertion
d'un élément frère.

7

Pour le frère je vois bien, mais le nouveau parent d'un enfant, c'est forcément un parent qui existe déjà, donc c'est plus un changement de parent de l'enfant qu'une "insertion".

-Nicolas

8

S'lt

> Par exemple un nouveau parent. Je pensais aussi au cas d'insertion
> d'un élément frère.
Pour le frère je vois bien, mais le nouveau parent d'un enfant, c'est
forcément un parent qui existe déjà, donc c'est plus un changement de
parent de l'enfant qu'une "insertion".

Pas forcément, l'idée c'est qu'on peut inserer un noeud quelconque
n'importe où même si celui n'existe pas à l'origine.

Peut etre intéressant si on insere un nouveau niveau de mots de clef
ou de rubrique.

9

Par exemple un nouveau parent. Je pensais aussi au cas d'insertion
d'un élément frère.

Pour le frère je vois bien, mais le nouveau parent d'un enfant, c'est
forcément un parent qui existe déjà, donc c'est plus un changement de
parent de l'enfant qu'une "insertion".

Pas forcément, l'idée c'est qu'on peut inserer un noeud quelconque
n'importe où même si celui n'existe pas à l'origine.

Il faut dans ce cas que ce nouveau parent soit lui-même enfant que quelque chose alors.

Et de toute façon on reste dans de l'arborescence, si j'ai bien compris, on ne part pas en réseau...

-Nicolas

10

je voulais dire virer le champ, mais le remplacer par un critere calcule {id_secteur} qui fait la meme chose.

11

je voulais dire virer le champ

ça gêne pas si on le laisse, et ça permet de ne pas pêter les scripts
qui font l'effort de le renseigner

, mais le remplacer par un critere calcule
{id_secteur} qui fait la meme chose.

dans les squelettes oui, mais pas pour le reste

-- Fil

12

cedric.morin@yterium.com a écrit :

Oui, il est très clair dans mon esprit que la gestion des acces restreint doit passer par une gestion intervalaire a moyen terme car c'est bien plus efficace et rapide en terme de code.
Par ailleurs, l'implémentation actuelle d'acces retreint casse sur les gros sites lorsqu'on a beaucoup de rubriques visibles (ou restreintes, c'est selon)
pour cause de dépassement mémoire (la faute à un array qui stocke les id des rubriques en memoire).
  
m'est avis qu'il faut creuser un peu, parce que ca m'étonnerait franchement que ca soit ce tableau d'id qui fasse exploser la memoire... ou alors le nombre de rubriques se compte en milliers sur ton gros site ?

13

Le 21 avr. 08 à 15:50, Stephane a écrit :

cedric.morin@yterium.com a écrit :

Oui, il est très clair dans mon esprit que la gestion des acces
restreint doit passer par une gestion intervalaire a moyen terme car
c'est bien plus efficace et rapide en terme de code.
Par ailleurs, l'implémentation actuelle d'acces retreint casse sur
les gros sites lorsqu'on a beaucoup de rubriques visibles (ou
restreintes, c'est selon)
pour cause de dépassement mémoire (la faute à un array qui stocke les
id des rubriques en memoire).

m'est avis qu'il faut creuser un peu, parce que ca m'étonnerait
franchement que ca soit ce tableau d'id qui fasse exploser la memoire...
ou alors le nombre de rubriques se compte en milliers sur ton gros site ?

le cas de debordement etait sur les articles, et oui, ils se comptent par milliers, et les rubriques etaient aussi assez nombreuses
Cédric

14

Cédric MORIN a écrit :

Le 21 avr. 08 à 15:50, Stephane a écrit :

cedric.morin@yterium.com a écrit :

Oui, il est très clair dans mon esprit que la gestion des acces
restreint doit passer par une gestion intervalaire a moyen terme car
c'est bien plus efficace et rapide en terme de code.
Par ailleurs, l'implémentation actuelle d'acces retreint casse sur
les gros sites lorsqu'on a beaucoup de rubriques visibles (ou
restreintes, c'est selon)
pour cause de dépassement mémoire (la faute à un array qui stocke les
id des rubriques en memoire).

m'est avis qu'il faut creuser un peu, parce que ca m'étonnerait
franchement que ca soit ce tableau d'id qui fasse exploser la memoire...
ou alors le nombre de rubriques se compte en milliers sur ton gros site ?

le cas de debordement etait sur les articles,

ah oui, la, les articles, ca peut quelques centaines de millier et la ca commence à faire lourd.
mais si tu dois gérer des droits d'accès differents sur les articles d'une meme rubrique (ce que je m'interdis pour eviter justement ce genre de soucis), le plus efficace c'est les "Control Access Lists".
c'est l'idée d'accès groupe si j'ai bien compris.
bref, de toutes facons, charger l'ensemble des droits sur les articles, c'est pas raisonnable.

et oui, ils se comptent par milliers, et les rubriques etaient aussi assez nombreuses

Mais sur les rubriques, en ne notant que la ou il y a des droits déclaré, mais en descendant les branches (le comportement natif de spip), c'est jamais énorme (moi j'y colle en plus des droits).
Et puis meme si tu te trimbales pour quelques utilisateurs un tableau de quelques milliers d'id, c'est pas ca qui fera exploser la mémoire (meme si ca y contribue).
Après pour les appels à autorisation, c'est quand meme bien plus efficace d'avoir le tableau sous la main dès le premier appel.

Enfin, je dis ca, c'est peut etre mon utilisation qui est particulière.