Afin de minimiser le traitement à l'intérieur du programme, ce dernier devait faire des transferts de tuples depuis différents serveurs et utiliser une requête MySQL pour faire la jointure et sortir les résultats. Pour ce billet, le but est de faire la requête ci-dessous, les deux tables concernées étant réparties horizontalement sur plusieurs serveurs (sans réplication).

SELECT * FROM Adresse a, Localite l 
WHERE a.idLocalite = l.idLocalite

Afin de pouvoir faire une jointure locale (sur le même serveur), les données des autres serveurs doivent être transférées dans une table locale (temporaire) afin de pouvoir laisser MySQL exécuter la requête.

Pour simplifier le problème, il y a N localités et K adresses par localités. Toutes ces données sont réparties équitablement sur 10 serveurs différents. Par exemple, la localité (1234,Sierre) se trouve sur le serveur 1 et chacun des serveurs contient K/10 adresses avec la clé idLocalite=1234.

L'idée est donc de transférer sur le serveur 1 toutes les adresses liées aux localités qu'il contient (il en a N/10) et d'exécuter la requête ci-dessus. Il suffit ensuite de faire de même avec les 9 autres serveurs et de combiner les résultats.

L'approche naïve consisterait à simplement récupérer toutes les adresses des autres serveurs. Le problème étant que le volume des données à transférer sera gros et donc lent. Afin de limiter au plus les tuples à copier, il suffit de les filtrer:

--récupération sur les serveurs 2 à 10
SELECT * FROM Adresse a
WHERE a.idLocalite IN (1230, 1231, 1232, 1233, 1234, ...)

Cela s'appelle un SemiJoin, qui offre déjà des possibilités intéressantes. Maintenant, en admettant qu'il y ait beaucoup d'identifiant, cela nécessitera beaucoup de temps à MySQL pour faire le tri. Par ailleurs, il faudra également communiquer cette requête qui sera très longue...

La version optimisée, le BloomJoin, utilise un BloomFilter. C'est simplement un tableau de bit (bitmap) qui va servir à faire ce tri de manière efficace. En gros, le but est d'implémenter l'algorithme suivant via MySQL:

Fonction Filtre(bitmap)
   Output = []
   Pour chaque tuple Adresse
      i = hash(idLocalite)
      Si bitmap[i] == 1
         Ajouter tuple dans Output
      Fin
   Fin
   Retourner Output

Il existe plusieurs algorithmes avec plusieurs fonctions de hash différentes, mais seule une sera utilisée ici. Le transfert et la jointure locale étant trivial, il reste la problématique de générer le bitmap sur le seveur ou doit être fait la jointure et le tri des données sur les autres serveurs.

Le choix d'une bonne fonction de hash est généralement crucial, toutefois l'exercice est laissé aux mathématiciens Pour l'exemple, la fonction ci-dessous suffira amplement:

(key*107 + 1009) mod 64

Cela permet de générer un nombre entre 0 et 63 (compris) et ainsi de crée facilement un bitmap:

--création du bitmap sur le serveur 1
SELECT BIT_OR(1 << ((l.idLocalite*107+1009) MOD 64) 
FROM Localite l

L'avantage est que cette requête est très rapide. Le gros inconvénient est qu'il n'y a que 64 bits disponibles, ce qui réduit à néant l'utilité du filtre dès qu'il y a trop de données (tous les bits seront à 1). Il faut donc une solution permettant de générer des bitmaps de taille arbitraire.

Une autre idée est d'utiliser une table temporaire ne contenant qu'une seule colonne qui fait office de compteur. Ensuite, la requête suivante permet de générer un bitmap utile (ici 3000):

SELECT
  GROUP_CONCAT(
    IF(x IN
      (SELECT (l.idLocalite*107+1009) MOD 3000
       FROM Localite l),
      '1',
      '0')
  SEPARATOR '')
FROM TMP_COUNTER

Outre le fait d'avoir à créer un table juste pour ça, MySQL n'aime pas vraiment les sous-requêtes et l'exemple ci-dessus est très lent... Toutefois, il existe une solution rapide et efficace, mais pour cela il faut "tricher" un peu avec les fonctionnalités MySQL.

--initialisation
SET @bf:=LPAD('',3000,'0'), @cn:=0;
 
--génération du bitmap
SELECT @cn:=@cn+1 AS cnt,
       @bf:=INSERT(@bf, x+1, 1, '1') AS bf FROM
(
  SELECT DISTINCT (l.idLocalite*107+1009) MOD 3000 AS x
  FROM Localite
) AS t
ORDER BY cnt DESC
LIMIT 1;

L'astuce est d'utiliser les variables de MySQL (précédées d'un '@'). A l'initialisation, la variable bf est initialisée avec 3000 zéro (fonction LPAD). Pour mettre les bits de sélection à 1, chaque idLocalite est hashé (le distinct est nécessaire car plusieurs idLocalite vont tomber sur le même nombre). Finalement, pour chaque résultat, le bit correspondant à la position du hash est remplacé par un 1.

Comme chaque ligne va altérer le bitmap (d'une ligne à une autre, seul un bit est changé), un compteur est utilisé pour ne retourner que la dernière ligne qui est le bitmap final ! Il ne reste plus qu'a l'utiliser sur les autres serveurs pour filtrer les tuples à transférer.

--filtre sur les serveurs 2 à 10
SELECT * FROM Adresse a
WHERE SUBSTRING(
            bitmap, 
            ((a.idLocalite*107+1009) MOD 3000)+1, 
            1) = '1'

Grâce à cette méthode, nous avons pu effectuer une requête avec de multiples jointures sur 10Go de données réparties entre 8 noeuds en moins de 10 minutes en utilisant un BloomFilter de 10'000 bits, ce qui constitue un très bon résultat