Optimisation des requêtes dans les systèmes centralisés

Une fois que les chemins d'accès alternatifs pour le calcul d'une expression d'algèbre relationnelle sont dérivés, le chemin d'accès optimal est déterminé. Dans ce chapitre, nous examinerons l'optimisation des requêtes dans un système centralisé tandis que dans le prochain chapitre, nous étudierons l'optimisation des requêtes dans un système distribué.

Dans un système centralisé, le traitement des requêtes est effectué dans le but suivant -

• Minimisation du temps de réponse de la requête (temps nécessaire pour produire les résultats à la requête de l'utilisateur).

• Maximisez le débit du système (le nombre de demandes traitées dans un laps de temps donné).

• Réduisez la quantité de mémoire et de stockage requise pour le traitement.

• Augmentez le parallélisme.

Analyse et traduction des requêtes

Initialement, la requête SQL est analysée. Ensuite, il est analysé pour rechercher les erreurs syntaxiques et l'exactitude des types de données. Si la requête réussit cette étape, la requête est décomposée en blocs de requête plus petits. Chaque bloc est ensuite traduit en une expression d'algèbre relationnelle équivalente.

Étapes d'optimisation des requêtes

L'optimisation des requêtes implique trois étapes, à savoir la génération d'arborescence de requêtes, la génération de plan et la génération de code de plan de requête.

Step 1 − Query Tree Generation

Un arbre de requête est une structure de données arborescente représentant une expression d'algèbre relationnelle. Les tables de la requête sont représentées sous forme de nœuds feuilles. Les opérations d'algèbre relationnelle sont représentées comme les nœuds internes. La racine représente la requête dans son ensemble.

Pendant l'exécution, un nœud interne est exécuté chaque fois que ses tables d'opérandes sont disponibles. Le nœud est ensuite remplacé par la table de résultats. Ce processus se poursuit pour tous les nœuds internes jusqu'à ce que le nœud racine soit exécuté et remplacé par la table de résultats.

Par exemple, considérons les schémas suivants -

EMPLOYÉ

EmpID

EName

Un salaire

DépartementNon

Date d'adhésion

DÉPARTEMENT

DNo

DNom

Emplacement

Exemple 1

Considérons la requête comme suit.

$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$

L'arbre de requête correspondant sera -

Exemple 2

Considérons une autre requête impliquant une jointure.

$ \ pi_ {FRame, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $

Voici l'arborescence des requêtes pour la requête ci-dessus.

Step 2 − Query Plan Generation

Une fois l'arborescence de requêtes générée, un plan de requête est créé. Un plan de requête est une arborescence de requêtes étendue qui comprend des chemins d'accès pour toutes les opérations de l'arborescence de requêtes. Les chemins d'accès spécifient comment les opérations relationnelles dans l'arborescence doivent être effectuées. Par exemple, une opération de sélection peut avoir un chemin d'accès qui donne des détails sur l'utilisation de l'index d'arborescence B + pour la sélection.

En outre, un plan de requête indique également comment les tables intermédiaires doivent être passées d'un opérateur à l'autre, comment les tables temporaires doivent être utilisées et comment les opérations doivent être mises en pipeline / combinées.

Step 3− Code Generation

La génération de code est la dernière étape de l'optimisation des requêtes. Il s'agit de la forme exécutable de la requête, dont la forme dépend du type du système d'exploitation sous-jacent. Une fois le code de requête généré, le gestionnaire d'exécution l'exécute et produit les résultats.

Approches de l'optimisation des requêtes

Parmi les approches d'optimisation des requêtes, la recherche exhaustive et les algorithmes basés sur l'heuristique sont principalement utilisés.

Optimisation complète de la recherche

Dans ces techniques, pour une requête, tous les plans de requête possibles sont initialement générés, puis le meilleur plan est sélectionné. Bien que ces techniques fournissent la meilleure solution, leur complexité temporelle et spatiale est exponentielle en raison du grand espace de solution. Par exemple, technique de programmation dynamique.

Optimisation basée sur l'heuristique

L'optimisation heuristique utilise des approches d'optimisation basées sur des règles pour l'optimisation des requêtes. Ces algorithmes ont une complexité temporelle et spatiale polynomiale, qui est inférieure à la complexité exponentielle des algorithmes basés sur la recherche exhaustive. Cependant, ces algorithmes ne produisent pas nécessairement le meilleur plan de requête.

Certaines des règles heuristiques courantes sont -

• Effectuez des opérations de sélection et de projet avant les opérations de jointure. Cela se fait en déplaçant les opérations de sélection et de projet vers le bas de l'arborescence des requêtes. Cela réduit le nombre de tuples disponibles pour la jointure.

• Effectuez les opérations de sélection / projet les plus restrictives avant les autres opérations.

• Évitez les opérations croisées car elles se traduisent par des tables intermédiaires de très grande taille.