Complexité d'une requête
Sous-jacent dans la discussion sur l'optimisation de requête est la question de la difficulté d'obtenir une certaine information. Nous rencontrons la notion de complexité. Depuis Kurt Gödel, nous savons qu'il est des propositions qui ne peuvent être ni démontrées ni réfutées, qu'il est des problèmes qui ne peuvent être résolus. Cette notion d'indécidabilité commence péniblement à arriver jusqu'au grand public. Ce même public ne voit dans le fait qu'une requête prend plus ou moins longtemps que des raisons purement techniques.
Évidemment, le temps de calcul dépend de la puissance du serveur, de la vitesse du disque ou de la qualité de l'optimiseur. Mais au-delà de tels aspects, il est des tâches qui demandent intrinsèquement plus de temps que d'autres. Par exemple, nous pouvons facilement afficher un graphe avec 100 noeuds ; ça ne prend que quelques fractions de secondes. Par contre, cela prendrait énormément de temps d'afficher un après l'autre tous les graphes possibles reliant ces 100 noeuds. Même parmi les problèmes dont la réponse est courte (par exemple, la réponse est oui ou non), il en est qui, bien que décidables, sont intrinsèquement bien plus complexes que d'autres ; il en est même que nous ne savons pas résoudre en temps raisonnable. Parfois, cette difficulté trouve même son utilité. Le système cryptographique RSA repose sur le fait que nous ne savons pas factoriser (en général) un très grand entier en nombres premiers, en un temps raisonnable et qu'il est donc très difficile de décrypter un message sans en connaître la clé secrète.
La complexité est un aspect particulièrement important pour le traitement de gros volumes de données. Pour une requête particulière, nous voulons savoir :
quel temps il faut pour la réaliser ? complexité en temps,
quel espace disque (ou quelle mémoire) est nécessaire ? complexité en espace.
Évidemment ces quantités dépendent de la taille de la base de données. Si la requête prend un temps t et que nous doublons la taille n de nos données, nous faut-il attendre le même temps (temps constant), le double de temps (temps linéaire en n), ou est-ce que le temps grandit de manière polynomiale (en nk où n est la taille des données) voire exponentielle (en kn) ? Ce n'est pas anodin : sur de gros volumes de données, une complexité en temps nk exigera une grosse puissance de calcul, et une complexité en kn sera rédhibitoire.
De nombreuses classes de complexité ont été étudiées. Intuitivement, une classe de complexité regroupe tous les problèmes qui peuvent être résolus sans dépasser certaines ressources disponibles, typiquement le temps ou l'espace. Par exemple, vous avez peut-être entendu parler de la classe P, temps polynomial. Il s'agit de l'ensemble des problèmes qu'il est possible de résoudre dans un temps nk où n est la taille des données et k un entier arbitraire. Au-delà de P, nous atteignons les temps NP (pour non-déterministe polynomial 4 ) et EXPTIME (temps exponentiel), des temps prohibitifs ? Pourtant, il faut relativiser. Les systèmes informatiques résolvent routinièrement des problèmes parmi les plus complexes de NP. Et, a contrario, pour 1.5 téraoctets de données, n3 est encore aujourd'hui hors d'atteinte, même en disposant de tous les ordinateurs de la planète.