Jointure avec index

• Joint utilisant une table de hachage : on construit une table de hachage pour r₂ sur les attributs communs X. On parcourt r₁ et pour chaque tuple de r₁ (et sa valeur pour X), on va chercher dans la table de hachage les tuples de r₂ qui ont la même valeur pour X.
• Complexité : O(n_r1 + n_r2 ), pour autant que n_r2/nbVal(X,r₂) soit borné pour les attributs communs X.
• Joint en présence d’un index : Supposons que r₂ possède un index pour les attributs communs X. On parcourt r₁ et pour chaque tuple de r₁ (et sa valeur pour X), on va chercher dans r₂ les tuples qui ont la même valeur pour X.
• Complexité : O(n_r1 (1 + log(n_r2 ))), pour autant que n_r2/nbVal(X,r₂) soit borné pour les attributs communs X.