|
Le coût d’une opération de tri-fusion et de jointure est généralement décomposé en coût de tri et coût de fusion. Le facteur dominant est généralement le tri. Décomposons-le :
1. Coût de tri :
* Algorithme : En règle générale, les bases de données utilisent un tri par fusion externe. Cela est dû au fait que les relations jointes sont souvent trop étendues pour tenir dans la mémoire.
* Coût d'E/S (facteur dominant) :
* Le tri par fusion externe implique plusieurs passages dans les données.
* Nombre de passes : Le nombre de passes dépend de la taille des relations et de la quantité de mémoire disponible (le « buffer »). Disons que nous avons :
* `B` =Nombre de blocs (pages) dans la relation.
* `M` =Nombre de blocs mémoire disponibles (taille du tampon).
* Le nombre de passes est d'environ « log_M(B) » ou légèrement supérieur si vous voulez être extrêmement précis.
* Coût d'E/S par passe : Chaque passe lit et écrit la relation entière, cela coûte donc « 2B » d'opérations d'E/S (B pour la lecture et B pour l'écriture).
* Coût total d'E/S pour le tri : `2B * nombre de passes =2B * log_M(B)`. Plus en détail, le coût de tri pour chaque relation « R » et « S » est :
* Trier(R) =2 * `B(R)` * logM (`B(R)`) (où `B(R)` est le nombre de blocs pour la relation R)
* Tri(S) =2 * `B(S)` * logM (`B(S)`) (où `B(S)` est le nombre de blocs pour la relation S)
* Coût du processeur : Bien que le tri soit principalement lié aux E/S, il existe un coût CPU associé à la comparaison des tuples, à la fusion des exécutions triées, etc. Ce coût est généralement inférieur au coût des E/S et est souvent ignoré dans les modèles de coûts simplifiés.
2. Coût de fusion :
* Coût d'E/S : Une fois les relations triées, la phase de fusion nécessite de lire une fois chaque bloc des deux relations triées.
* `B(R) + B(S)` (où `B(R)` et `B(S)` sont le nombre de blocs pour les relations R et S, respectivement)
* Coût du processeur : Le coût CPU de la comparaison des tuples pendant la phase de fusion est relativement faible par rapport aux coûts de tri et d'E/S.
Coût total :
Le coût total de la jointure tri-fusion correspond à peu près à la somme des coûts de tri et du coût de fusion :
Coût ≈ 2 * B(R) * logM (B(R)) + 2 * B(S) * logM (B(S)) + B(R) + B(S)
Coût simplifié (approximation commune) :
Si le coût du tri domine (ce qui est généralement le cas), une approximation simplifiée est :
Coût ≈ 2 * B(R) * logM (B(R)) + 2 * B(S) * logM (B(S))
Considérations importantes :
* Mémoire (M) : La quantité de mémoire disponible a un impact significatif sur le nombre de passes requises pour le tri. Plus de mémoire signifie moins de passes et un coût moindre.
* Données pré-triées : Si l'une ou l'autre relation est *déjà* triée sur la clé de jointure, vous pouvez ignorer l'étape de tri pour cette relation. Cela réduit considérablement le coût. Le coût devient le coût de tri uniquement de la relation non triée plus le coût de fusion.
* Doublons : Si les clés de jointure contiennent des doublons, la phase de fusion peut être plus complexe, nécessitant potentiellement des E/S et un processeur supplémentaires. La formule suppose que la gestion des doublons est incorporée dans chaque lecture d'un bloc.
* Taille du bloc : La taille du bloc (taille de la page) affecte le nombre de blocs dans une relation.
* Modèle de coût : La formule exacte utilisée pour l'estimation des coûts varie selon les systèmes de bases de données. Certains peuvent inclure le coût du processeur de manière plus explicite, les temps de recherche du disque, etc. Il s'agit d'un modèle simplifié permettant de comprendre les coûts relatifs.
* Jointure par hachage ou jointure par tri-fusion : Dans de nombreux cas, la jointure par hachage est plus efficace que la jointure par tri-fusion, en particulier lorsque l'une des relations tient entièrement en mémoire. Cependant, la jointure par tri et fusion peut être plus efficace lorsque les données sont déjà triées ou lorsque les données ne sont pas réparties de manière uniforme.
* Approches hybrides : Certaines bases de données utilisent des approches hybrides qui combinent les aspects de la jointure par hachage et de la jointure par tri-fusion.
* Performances réelles : Ce sont des coûts théoriques. Les performances réelles peuvent être affectées par des facteurs tels que les performances des E/S du disque, la vitesse du processeur, la simultanéité et le réglage de la base de données.
Exemple :
Disons :
* `B(R) =1000` blocs
* `B(S) =500` blocs
* `M =100` blocs de mémoire
Alors:
* journal100 (1000) ≈ 1,5
* journal100 (500) ≈ 1,35
Coût estimé ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500
≈ 3000 + 1350 + 1500
≈ 5850 opérations d’E/S.
Il ne s'agit que d'une estimation, et le coût réel dans un système de base de données réel pourrait être différent. La comparaison relative est que le coût de tri est supérieur au coût de fusion.
En résumé, le coût de la jointure par tri-fusion est dominé par le coût d’E/S du tri des relations. Le nombre de passes nécessaires au tri dépend de la taille des relations et de la quantité de mémoire disponible. Réduire la taille des relations (par exemple, via un filtrage ou une projection) ou augmenter la mémoire disponible peut améliorer considérablement les performances.
|
