THÈSE

THÈSE présentée à L’UNIVERSITÉ de VERSAILLES-SAINT-QUENTIN-EN-YVELINES pour obtenir le titre de DOCTEUR Spécialité INFORMATIQUE par Luc BOUGANIM Sujet de la thèse : ÉQUILIBRAGE DE CHARGE LORS DE L’EXÉCUTION DE REQUÊTES SUR DES ARCHITECTURES MULTIPROCESSEURS HYBRIDES Soutenue le 13 décembre 1996 devant le jury composé de M. Georges GARDARIN Président MM. André FLORY Rapporteurs Martin KERSTEN Claude DELOBEL Examinateurs Philippe PUCHERAL Patrick VALDURIEZà Anaenza et Taïna, à mes parents et mes beaux-parents... - i-- ii-Remerciements Cette thèse n’a qu’un auteur mais elle est le fruit de la collaboration et du travail de plusieurs personnes que je voudrais remercier chaleureusement: André Flory et Martin Kersten, pour avoir accepté la tache ingrate d’être rappor- teur de cette thèse. Merci pour la lecture attentive du premier manuscrit et pour les remarques qui ont permis de l’améliorer. Georges Gardarin, pour m’avoir accueilli dans son DEA, puis en thèse et enfin pour avoir présider le jury. Merci de ta confiance. Tu ne devais pas trop être en forme le jour de la soutenance car tu ne m’as pas trop torturé avec les questions. Je m’atten- dais au pire... Patrick Valduriez, coauteur de plusieurs publications et directeur de thèse. Merci de m’avoir suivi tout au long de ma thèse. Je pense avoir bien fait de choisir un sujet qui te tient à coeur: Le parallélisme Claude Delobel, pour m’avoir fait l’honneur d’assister à une présentation en privé. Je n’aurais, sans doute, plus jamais un tel pourcentage de professeurs experimentés (et attentif) dans mon auditoire. Cette soutenance privée, 10 jours avant la date finale m’aura permis de prendre du recul. Philippe Pucheral, pour avoir participer au jury de thèse et pour l’immense plaisir qu’il m’a fait, la veille de la thèse, en déclarant ‘ton état de l’art pourra, sans doute, me servir pour un cours’. Preuve qu’écrire une thèse est toujours utile. Merci pour tes en- couragements et pour ton amitié. Les personnes qui m’ont fais découvrir l’enseignement et m’ont permis d’enseigner: Michel Couprie, Frederic Voisin, Françoise Schlienger, Albin Morelle, Jean-Marc Sa- glio, Brigitte Safar. Vous m’avez témoigné votre confiance en me proposant des cours, td ou tp. J’espère ne pas vous avoir deçu. Les personnes du GDR Transaction animé par Philippe Pucheral et ceux du GDR Bases de données parallèles et réparties animé par Mr. Hameurlain. Merci de mainte- nir vivante cette ‘ouverture’ profitable à tous. Nos collègues d'outre-Atlantique, car ils aiment le vin français et l’ambiance du projet RODIN. Mike Franklin, pour les parties de petèque. Claude Mohan, qui à lui seul a épuisé tout les membres du projet. Alon Levy pour son humour légendaire. Sans oublier Louiqua Rachid, Tamer Oszu, Denis Shasha. Les ex-membres de l’équipe de recherche ‘bases de données avancées’ de BULL pour tout ce qu’ils m’ont appris et pour leur amitié. Alex, Benoit, Carla, Pascale, Patrick, merci d’avoir été présent du début à la fn de ma thèse. Sans oublier les grenoblois, Mau- ricio et Pascal. - iii-Les membres (et anciens membres) de l’equipe RODIN pour l’ambiance régnant dans le projet: Antony, le photographe. Claude, caviste. L’infatigable Dana (!!). Dimi et son parcours du thésard. Elisabeth, G.O. des séminaires Rodin. ‘Bonjour’ Eric Si- mon. Esther, ‘carioca da gema’. Florian, ‘shellman’. François et son saucisson récursif. Françoise, conseillère générale. Frederic, le dieu du PC. Hubert, le dictionnaire, merci de ton aide. L’incroyable JRO (!!). Laurent A., ramasseur de miettes. Laurent D., pas- sager d’Air India. Maja et ses gâteaux. L’antenne à Marcin. Marie-Joe et Barcelonne. Mikal, mon secrétaire particulier, Mokrane A. et Balaton. Mokrane B., et ses incroya- bles histoires. Olga et ses coups de poings. Les ‘inclassables’ pour qui on ne peut faire une ‘section’ mais qu’on voudrait re- mercier quand même. Jean-Paul Chieze, maître de la KSR1. Les membres du personnel administratif de l’INRIA, pour leur compréhension. Abdel Redouane, Christophe Masse, Paul Lebailly pour avoir fait l’effort de venir à ma soutenance. Enfin, je voudrais remercier mes parents, pour m’avoir toujours poussé vers les études, mes beaux-parents qui prenaient le relais à chaque veille de ‘deadline’, ma fem- me, Anaenza, pour sa patience. J’espère qu'un jour, je ne mentirais plus en disant ‘de- main j’aurais du temps libre’. Merci à mon tout petit bout de fille, Taïna, de me rappeler chaque soir qu’il faut que je ‘rentre à 7’. J’espère que ton futur petit frère ou petite soeur sera moins exigeant(e). Luc Bouganim - iv-Table des matières Chapitre I : Introduction .............................................1 1. Architectures matérielles ............................................... 1 2. Problématique .................................................................. 2 3. Contexte ............................................................................. 4 4. Principales contributions 4 5. Organisation de la thèse ................................................. 6 Chapitre II : Exécution parallèle de requêtes relationnelles.............................................9 1. Architectures matérielles ............................................... 10 1.1. Architectures à mémoire partagée ou shared-memory....... 11 1.2. Architecture distribuées ou shared-nothing (SN) ............... 12 1.3. Architectures à disques partagés ou shared disks .............. 13 1.4. Architecture à mémoire non uniforme ou NUMA ............. 14 1.5. Architectures hiérarchiques .................................................... 15 2. Formes de parallélisme. .................................................. 16 2.1. Modèle d’exécution fragmenté .............................................. 17 2.1.1. parallélisme intra-opérateur .......................................... 17 2.1.2. Parallélisme inter-opérateur 19 2.2. Modèle d’exécution non fragmenté........................................ 20 3. Opérateur de jointure : algorithme et parallélisation 21 3.1. Jointure par hachage mono-processeur ................................ 21 3.2. Jointure par hachage sur un modèle d’exécution fragmenté21 3.3. Jointure par hachage sur un modèle non fragmenté ......... 22 3.4. Jointure par hachage non bloquant (pipeline hash join) .... 23 4. Arbre d’opérateurs .......................................................... 24 5. Mesure de performances ................................................ 26 6. Problèmes liés à l’exécution parallèle ......................... 28 - v-6.1. Initialisation et mise en place du parallélisme ..................... 28 6.2. Contrôle de l’exécution parallèle ........................................... 29 6.3. Interférences et effets de convoi ............................................ 30 6.4. Le problème de la répartition de la charge de travail ........ 32 6.4.1. Répartition de charge intra-opérateur ......................... 33 6.4.2. Répartition de charge inter-opérateur 36 7. Quelques modèles d’exécution parallèle .................... 38 7.1. Gamma ...................................................................................... 38 7.2. PRISMA/DB ............................................................................. 41 7.3. Volcano 41 7.4. XPRS .......................................................................................... 45 8. Conclusion ........................................................................ 46 Chapitre III : Exécution parallèle et répartition de charge dans DBS3.....................................47 1. Introduction ...................................................................... 47 2. Le modèle d’exécution parallèle de DBS3 .................. 50 2.1. Plans d’exécution parallèles: le langage LERA-par............. 50 2.2. Mise en œuvre sur une architecture à mémoire partagée . 53 3. Analyse du modèle .......................................................... 55 4. Etude de performance ..................................................... 57 4.1. Plate-forme d’expérimentation .............................................. 58 4.1.1. Impact du modèle Allcache sur DBS3 ......................... 59 4.2. Base de tests .............................................................................. 60 4.3. Impact du data skew ............................................................... 62 4.4. Degré de parallélisme et répartition de charge ................... 63 4.5. Degré de fragmentation et répartition de charge ............... 65 4.5.1. Surcoûts d’un haut degré de fragmentation 65 4.5.2. Un haut degré de fragmentation pour un meilleur support du skew ...................................................................................... 66 5. Conclusion ........................................................................ 68 - vi-Chapitre IV : Exécution parallèle sur une architecture hiérarchique .......................71 1. Introduction ...................................................................... 71 2. Problématique .................................................................. 74 2.1. Système d’exécution ................................................................ 74 2.2. Plan d’exécution parallèle ....................................................... 75 2.3. Définition du problème ........................................................... 77 3. Le modèle d’exécution parallèle DP ............................ 77 3.1. Concepts .................................................................................... 78 3.2. Répartition de la charge .......................................................... 81 3.3. Exemple ..................................................................................... 83 4. Techniques d’implémentation ...................................... 84 5. Etude de performances ................................................... 87 5.1. Plate-forme d’expérimentation .............................................. 87 5.1.1. Configuratio