Optimisation de requête
Il existe une infinité d'expressions algébriques qui évaluent une même requête. Si elles sont syntaxiquement différentes, elles définissent la même question. D'un point de vue sémantique, elles sont équivalentes. Optimiser une requête consiste à la transformer en une autre qui donne les mêmes réponses, mais qui soit la moins coûteuse possible (typiquement en temps).
D'un point de vue pratique, il nous faut choisir un plan d'exécution, c'est-à-dire une expression algébrique avec des précisions sur l'algorithme à utiliser pour évaluer chacune des opérations. Un plan d'exécution, c'est quasiment un programme pour calculer la réponse.
Un premier problème est que l'espace de recherche, c'est-à-dire l'espace dans lequel nous voulons trouver le plan d'exécution, est gigantesque. Pour éviter de le parcourir entièrement, nous allons utiliser des heuristiques, c'est-à-dire des méthodes qui, si elles ne garantissent pas de trouver le plan optimal, donnent assez rapidement des plans satisfaisants. Ces heuristiques utilisent souvent des règles de bon sens comme : il faut réaliser les sélections le plus tôt possible.
L'autre difficulté est que pour choisir le plan le moins chronophage, l'optimiseur (c'est-à-dire le programme en charge de l'optimisation) doit être capable d'estimer le coût de chaque plan candidat et c'est une tâche complexe à laquelle le système ne peut se permettre d'accorder trop de ressources. Donc, l'optimiseur fait de son mieux. Et typiquement les optimiseurs de systèmes comme Oracle ou DB2 font des merveilles sur des requêtes simples. C'est bien moins glorieux pour les requêtes complexes, par exemple mettant en jeu des quantificateurs universels comme la question : quels sont les acteurs qui n'ont joué que dans des comédies ? Heureusement, en pratique, la plupart des questions posées par des applications utilisant des bases de données sont simples.