Un truc qui marche : pousser les sélections et les projections
Une heuristique très simple est d'exécuter au plus tôt les projections et sélections possibles, ce qu'on appelle "pousser les sélections et les projections". En effet, projection/sélection sont des réducteurs d'espace souvent radicaux :
Sélection
Relation R et critère de sélection de probabilité p%
O(σC(R)) = p * O(R)
Exercice : Calculer la taille du résultat pour 1 million de nuplets de taille 200 octets en moyenne, et p =2%
Projection
Relation R et passage de la taille moyenne de K à K'
O(πX (R)) = (K'/K) * O(R)
Exercice : Calculer si K' est de 6 octets
Remarque : C'est peut-être encore moins avec l'élimination de dupliquets
Pour les jointures, c'est le contraire
Relations R et S avec une probabilité de jointure p'
O(R â S) = p' * O(R) * O(S)
Dans le pire des cas, c'est O(R) * O(S)
Exercice : avec R ci-dessus, S de taille identique et p'=2%
Remarque : Peut être aussi réducteur si p' est très petit