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