Identification relative VS performance

Version imprimable

14/09/2012, 10h17
Kropernic

Identification relative VS performance

Bonjour,

Une petite question pour savoir que penser de l'identification relative d'un point de vue performance.

Histoire d'être bien sur la même longueur d'onde, voici ce qu'est l'identification relative pour moi.

Prenons un cas typique dont voici la règle de gestion :
Une personne peut posséder plusieurs numéro de téléphone et un numéro de téléphone est posséder par une seule personne.

Ce qui donnera comme MCD :
PERSONNE-0,n----POSSEDER----(1,1)-TELEPHONE

Au niveau des tables, il n'y a que les clefs primaire qui nous intéressent :
- une table T_PERSONNE_PRS avec la colonne PRS_ID INT IDENTITY(1,1) comme clef primaire.
- une table T_TELEPHONE_TEL avec les colonnes PRS_ID et TEL_ID comme clef primaire composée. Où la numérotation de TEL_ID recommence à 1 pour chaque valeur de PRS_ID.

Ce que j'en ai compris :
Au niveau des requêtes de sélection, cela sera plus performant car tous les numéros d'une même personne seront regroupé sur la même page de l'index cluster.
Au niveau des insertions, cela va immanquablement être moins performant car il faudra, à chaque insertion, réorganiser l'index (sauf si on insère un nouveau numéro pour la personne avec l'id maximal).

Du coup, que faut-il préférer ? Je ne suis pas assez versé dans l'administration et l'optimisation pour parvenir à juger de l'impact de ce genre de chose. C'est pourquoi je fais appel à vous.

Merci d'avance.
14/09/2012, 11h12
SQLpro

Toute clef primaire créé un index avec des statistiques derrières. Les statistiques ne sont disponibles que pour la première colonne d'un index composite. Dès lors que vous avez plusieurs colonnes dans un index l'optimisation est souvent moins bonne. C'est le cas avec cette problématique d'identification relative...
De plus les PK créée des index CLUSTERED dont la valeur est utilisée comme repère de ligne dans tous les index secondaires (NON CLUSTERED). Avec deux colonnes composant la clef d'index, ce repère est donc 2 fois plus gros et impacte tous les index....

Et comme vous l'avez remarqué, une clef primaire sémantique (donc index cluster) sera notablement plus fragmentée car :
- l'ordre n'est pas constant à l'insertion (défaut de monotonie)
- chaque update dans la clef impacte tous les index secondaires

Une solution consiste donc à avoir en sus de la clef primaire de type IDENTITY une clef alternative sur PRS_ID + NUM tel, et c'est probablement cet index qui sera utilisé pour récupérer un n° de téléphone dans les jointures !

A +
14/09/2012, 11h20
Kropernic

Merci beaucoup pour cet éclaircissement.
24/09/2012, 11h39
Serguei_TARASSOV

Kropernic,
Fais attention sur le point des index supplémentaires et les colonnes de données.
Si ta table d'association n'a pas des index (ou le petit nombre des index) mais contient les colonnes, il n'est pas évident d'avoir une clé supplémentaire auto-incrément.
Explication : dans ce cas t'a besoin d'un index composite supplémentaire sur les colonnes de références et toutes le requêtes qui font la sélection des colonnes hors cet index seront impactées en terme de perf (clustered key seek vs index seek + clustered key seek) ainsi que pour l'insertion (MAJ l'index supplémentaire).

Bonsoir,

Quelques remarques en passant.

Citation:

Envoyé par SQLpro

Toute clef primaire créé un index avec des statistiques derrières

Jusqu'ici pas de problème.

Citation:

Envoyé par SQLpro

Les statistiques ne sont disponibles que pour la première colonne d'un index composite.

Il serait temps que SQL Server tienne des stats sur la clé complète, à l’instar par exemple de DB2 qui procède ainsi depuis toujours, c'est-à-dire près de 30 ans.

Extrait du document IBM DATABASE 2, Release 1.0 Reference Summary SX23-3740-1 (1984) :

http://www.fsmwarden.com/developpez_...rd(DB2_V1).png
La colonne FULLKEYCARD permettait déjà de connaître les stats utiles, à une époque à laquelle Kropernic se souciait plus de son pouce et de son canard:bebe:que des index...

Citation:

Envoyé par SQLpro

Dès lors que vous avez plusieurs colonnes dans un index l'optimisation est souvent moins bonne.

Conséquence de ce qui précède, mais en l’occurrence, en quoi consiste très précisément l’optimisation ? Efficacité du regroupement des téléphones dans les pages de données ?

Citation:

Envoyé par SQLpro

C'est le cas avec cette problématique d'identification relative.

Peut-être, mais sous réserve d’avoir une explication claire de ce qu’on entend par optimisation. Pour le moment on est au niveau pifométrique.

Citation:

Envoyé par SQLpro

De plus les PK créée des index CLUSTERED

Je suppose que vous voulez dire que chaque clé primaire est dotée d’un index cluster. S’il en est ainsi, je dirais : sauf si on préfère qu’il en soit autrement. Exemple (qui ne sera pas mis en œuvre !) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 CREATE TABLE TELEPHONE ( PersonneId INTEGER NOT NULL , TelephoneId TINYINT NOT NULL , TelephoneNumero VARCHAR(24) NOT NULL , CONSTRAINT TEL_PK PRIMARY KEY NONCLUSTERED (PersonneId, TelephoneId) , CONSTRAINT TEL_PSN_PK FOREIGN KEY (PersonneId) REFERENCES PERSONNE ON DELETE CASCADE ) ; ALTER INDEX TEL_PK ON TELEPHONE REBUILD WITH (PAD_INDEX = ON, FILLFACTOR = 80) ; CREATE CLUSTERED INDEX TEL_NO_X ON TELEPHONE (TelephoneNumero) WITH (PAD_INDEX = ON, FILLFACTOR = 80) ;
=>
http://www.fsmwarden.com/developpez_...ster_Notel.png

Citation:

Envoyé par SQLpro

Avec deux colonnes composant la clef d'index, ce repère est donc 2 fois plus gros et impacte tous les index

Dans le cas de la table TELEPHONE il n’en est pas ainsi (comme le plus souvent dans le cas de l’identification relative). La colonne PersonneId mesure 4 octets et la colonne TelephoneId un seul octet (soit au plus 255 occurrences de téléphones par personne, ce qui dans le cas de Kropernic est plus que très largement suffisant). Si l’on n’utilise pas l’identification relative, l’identifiant TelephoneId devient absolu, mais son type est au moins celui de PersonneId, c'est-à-dire INTEGER dans l’exemple, ce qui représente 4 octets. Maintenant, je ne sache pas que 4 + 1 soit deux fois plus « gros » que 4.

Cela dit, si l’index cluster avait une clé composite avec des colonnes de type CHARACTER(N) avec N = gros, je ne dis pas. Mais on n’est absolument pas dans ce genre de scénario, Kropernic est quelqu’un de sérieux...

Citation:

Envoyé par SQLpro

l'ordre n'est pas constant à l'insertion (défaut de monotonie)

Si les ajouts des téléphones d’une personne se font aléatoirement, au fil des jours, c’est vrai, qu’il s’agisse de l’index primaire en cas d'identification relative ou de l’index secondaire en l’absence d’identification relative. En tout cas, lors des consultations :

En mode « Joe Transaction » (direct, léger), ça n’est pas un problème dans la mesure où l’on ne cherche pas à ramener tous les téléphones à chaque transaction. En mode « Jane Query » (direct, lourd) ou « Bill Batch », les performances pourraient être dégradées, mais heureusement, le DBA aura fait son travail de surveillance et déclenché en conséquence les réorganisations dans le but de prévenir la dégradation des performances. Par ailleurs, l’effet de monotonie ne se fait pas ressentir tant que le FILLFACTOR est choisi correctement (@Kropernic : j’espère que vous avez bien prévu ce paramétrage en ce qui concerne la table des gifts et les tables des stocks...)

Citation:

Envoyé par SQLpro

chaque update dans la clef impacte tous les index secondaires

Dans le cas de Kropernic (sauf s’il n’a pas suivi mes conseils), la valeur d’une clé primaire est invariante et dépourvue de toute signification, donc en l'occurrence aucun update en vue.

Citation:

Envoyé par SQLpro

Une solution consiste donc à avoir en sus de la clef primaire de type IDENTITY une clef alternative sur PRS_ID + NUM tel, et c'est probablement cet index qui sera utilisé pour récupérer un n° de téléphone dans les jointures !

Hum... Avec un seul index (utilisation de l’identification relative), les jointures se passent très bien, mais elles sont plus coûteuses avec votre index secondaire (voir les schémas en annexe ci-dessous). Si l’on vous suivait, on aurait désormais deux index sur les bras au lieu d’un seul, avec un surcoût important en I/O c'est-à-dire en accès aux disques tant en lecture qu’en écriture (je sais : tout est dans le cache, avec la nouvelle technologie de disques Tartempion on va dix fois plus vite, le temps de verrouillage est réduit d’autant, etc.) : pour ma part, je passe volontiers cet index supplémentaire au fil du rasoir d’Ockham et j’en resterai à l’identification relative.

Cela dit, je ne généralise pas et ne prétends pas avoir raison à tout coup, l’expérience m’a appris à être prudent et ne pas me fier à ma seule intuition ou à mes habitudes : Vérité en deçà des Pyrénées, erreur au-delà... Mais il y a une chose dont je suis sûr : c’est sur la base d’un prototypage des performances sérieux que c’est telle solution qu’il faut retenir plutôt qu’une autre, résultats chiffrés en main pour une appréciation objective.

En tout cas, vu les coûts I/O (cf. annexe ci-dessous), je ne m’engage pas trop en disant que Kropernic peut conserver sans problème l’identification relative :

PERSONNE-0,n----POSSEDER----(1,1)--TELEPHONE
En effet, pour accéder à une page de données, le nombre d’I/O est égal à H + 1, tandis que sans identification relative, le coût est égal à H’ + 1 + H’’ ; par ailleurs l’index primaire n’est pas obèse (les clés mesurent 5 octets, on a vu pire), la clé primaire n’est jamais modifiée, etc.

Mais si un prototypage des performances montrait que malgré tout c’est l’autre solution qui était à retenir, au nom de l’indépendance physique (8e des 12 règles de Codd), c’est sous le capot que les transformations s’effectueraient, de façon transparente.

Annexe. Coût I/O (accès aux disques)

1) Avec utilisation de l’identification relative

Suite à réorganisation de la table TELEPHONE, la situation est synthétisée dans la figure ci-dessous. Soit H la hauteur de l’arbre, c'est-à-dire le nombre de niveaux de l’index cluster (sans les données) : le coût pour accéder à un numéro de téléphone de la personne 12345 est égal au plus à H+1 I/O. Par exemple pour donner un ordre de grandeur — observé avec DB2 for z/OS, à ajuster évidemment dans le cas de SQL Server —, H = 2 pour moins de 85 000 téléphones, et H = 3 pour moins de 25 000 000. On peut voir venir.

http://www.fsmwarden.com/developpez_...otel_IdRel.png

A supposer qu’une personne ait moins de 256 téléphones (du fait de l’utilisation du type Tinyint pour la colonne TelephoneId, cf. l’instruction CREATE TABLE ci-dessus), le coût d’une requête pour récupérer tous les téléphones d’une personne est égal au coût de la récupération d’un de ses téléphones en particulier (+ 1 I/O disons si les téléphones sont à cheval sur deux pages).

2) Sans utilisation de l’identification relative

La situation devient la suivante, dans laquelle on peut considérer que H’’ = H’ + 1, bien que la clé primaire mesure 4 octets cette fois-ci au lieu de 5 (par comparaison avec les chiffres précédents qui valent pour H, à peu de choses près (toujours avec DB2) H’ = 2 pour moins de 97 000 téléphones, et H’ = 3 pour moins de 30 000 000).

http://www.fsmwarden.com/developpez_...otel_IdAbs.png

03/10/2012, 12h09
Waldar

Belle réponse fsmel, comme d'habitude, mais n'y a-t-il pas une erreur dans la bataille car il me semble que la traduction du MCD vers le MPD est erronée :

Citation:

Envoyé par Kropernic

Une personne peut posséder plusieurs numéros de téléphone et un numéro de téléphone est possédé par une seule personne.

Ce qui donnera comme MCD :
PERSONNE-0,n----POSSEDER----(1,1)-TELEPHONE

Au niveau des tables, il n'y a que les clefs primaire qui nous intéressent :
- une table T_PERSONNE_PRS avec la colonne PRS_ID INT IDENTITY(1,1) comme clef primaire.
- une table T_TELEPHONE_TEL avec les colonnes PRS_ID et TEL_ID comme clef primaire composée. Où la numérotation de TEL_ID recommence à 1 pour chaque valeur de PRS_ID.

Rien à dire sur la table T_PERSONNE_PRS, mais sur la table T_TELEPHONE_TEL j'aurai écrit :
- une table T_TELEPHONE_TEL avec la colonne TEL_ID INT IDENTITY(1,1) comme clef primaire, et la colonne PRS_ID comme clef étrangère indexée référençant T_PERSONNE_PRS.PRS_ID.

Bonjour Waldar et merci à vous.

Citation:

Envoyé par Waldar

il me semble que la traduction du MCD vers le MPD est erronée

En fait, elle est juste... On est ici dans le mode de représentation propre à PowerAMC et l’instruction CREATE TABLE ci-dessous est celle qui a été fournie par l’AGL :
Code:

1 2 3 4 5 6 7 8 CREATE TABLE TELEPHONE ( PersonneId INTEGER NOT NULL , TelephoneId TINYINT NOT NULL , TelephoneNumero VARCHAR(24) NOT NULL , CONSTRAINT TEL_PK PRIMARY KEY (PersonneId, TelephoneId) , CONSTRAINT TEL_PSN_PK FOREIGN KEY (PersonneId) REFERENCES PERSONNE ON DELETE CASCADE ) ;
Instruction qui comporte donc la clé composite (PersonneId, TelephoneId). Notez aussi la clause CASCADE confirmant que TELEPHONE n’est jamais qu’une propriété multivaluée de PERSONNE.
Cette clé composite est la conséquence de l’utilisation de l’identification relative, symbolisée dans le cas de PowerAMC par la mise entre parenthèses de la cardinalité 1,1 :

[PERSONNE]----0,n----(POSSEDER)----(1,1)----[TELEPHONE]
Si on ôte les parenthèses :

[PERSONNE]----0,n----(POSSEDER)---- 1,1----[TELEPHONE]
Alors l’identification est absolue et PowerAMC produit l’instruction suivante :
Code:

1 2 3 4 5 6 7 8 CREATE TABLE TELEPHONE ( PersonneId INTEGER NOT NULL , TelephoneId TINYINT NOT NULL , TelephoneNumero VARCHAR(24) NOT NULL , CONSTRAINT TEL_PK PRIMARY KEY (TelephoneId) , CONSTRAINT TEL_PSN_PK FOREIGN KEY (PersonneId) REFERENCES PERSONNE ON DELETE NO ACTION ) ;
En l’occurrence et conceptuellement parlant, TELEPHONE est élevée au rang d’entité-type forte, faisant qu’on ne peut pas supprimer une personne ayant un téléphone (en tout cas au niveau sémantique, ce que l’on confirme au plan technique avec la clause NO ACTION), ce qui dans le cas de l’univers de Kropernic ne vaut pas puisqu’on y considère un téléphone comme une banale propriété (multivaluée) de la personne.

Pour l’anecdote, les autres AGL ont chacun leur façon de représenter l’identification relative mais produisent tous l’instruction CREATE TABLE ci-dessus :

WinDesign :

[PERSONNE]----0,n----(POSSEDER)---- 1,1 (R)----[TELEPHONE]

Open ModelSphere :

[PERSONNE]----0,n----(POSSEDER)---- 1, 1----[TELEPHONE]

Pour sa part, UML est sémantiquement encore plus précis, grâce à la relation de composition :

[PERSONNE]◄►-1,1--------------------- 0,N----[TELEPHONE]

Etc.

Merci Waldar de votre visite ;)

15/10/2012, 01h08
fsmrel

Pour complément d’information.

Citation:

Envoyé par SQLpro

Les PK créée des index CLUSTERED dont la valeur est utilisée comme repère de ligne dans tous les index secondaires (NON CLUSTERED).

Il me semblait avoir déjà rencontré cette façon de procéder qui consiste à brancher un ou plusieurs autres index sur un index cluster. Cela me trottait dans la tête, j’ai donc fouillé dans mes archives, et la lumière fut !

Dans les années soixante-dix, j’avais monté et dispensé des cours sur la méthode d’accès VSAM (Virtual Storage Access Method) d’IBM. A cette époque, VSAM permettait (et permet toujours !) de gérer plusieurs types de fichiers, dont les KSDS (Key Sequenced Data Sets), fichiers dont les données sont accessibles au moyen de clés (d’où le terme « Key ») ou séquentiellement, dans l’ordre de celles-ci (d’où le qualificatif « Sequenced »). Un KSDS est un arbre B+ (« B » pour Balanced tree, arbre équilibré (feuilles toutes à la même « distance » de la racine) et « + » pour symboliser le chaînage séquentiel des feuilles de l’arbre, donc des clés).

Un KSDS est fondamentalement composé d’un espace (ficher) de données d’une part et d’un espace index d’autre part : clés et pointeurs pour accéder aux enregistrements de données. Incidemment, une clé est mono-attribut et n’est pas modifiable (à l’instar de l’identifiant au sens de Merise 1re génération, qui à l’époque n’était du reste pas née...)

Par leur réunion, l’espace de données du KSDS et l’espace index associé constituent un CLUSTER.

Pour reprendre l’exemple des bovins cher à CinePhil, on accède par READ aux données du bovin Zaza, de clé '1234567' (ci-dessous, l’instruction MVC est l’équivalent en assembleur IBM/370 de l’instruction SET de T-SQL) :

http://www.fsmwarden.com/developpez_...DS_Cluster.png

Tiens, tiens ! Abstraction faite du langage d’accès aux données (SQL d’un côté, assembleur IBM/370 de l’autre), voilà une organisation et une terminologie quadragénaires rappelant quelque chose de plus récent... :

http://www.fsmwarden.com/developpez_...SQL_Server.png

La ressemblance est encore plus frappante quand on utilise des clés alternatives (à partir de 1975 avec VSAM) :

http://www.fsmwarden.com/developpez_...SQL_Server.png

Comme dans le cas de SQL Server, l’accès aux données à partir d’une clé alternative (« secondaire ») se fait systématiquement via l’index cluster/prime.

Par comparaison (même si comparaison n’est pas raison), les fichiers hébergeant les tables DB2 ne sont pas du type KSDS : les parents de DB2 n’ont pas réutilisé les facilités sophistiquées fournies par la maison mère IBM, et pour des raisons très vraisemblablement de performance, ils ont développé une technologie spécifique (qui utilise le minimum minimorum de VSAM, à savoir des fichiers de type LDS (Linear Data Set), bruts de décoffrage, mais il n’y a pas lieu ici d’entrer dans les détails). Avec DB2 un index quel qu'il soit est directement branché sur les données, jamais sur l’index cluster (prime index), voir ce message (Figure B) et celui-là (et ceux qui le suivent).