Traitement des requêtes distribuées

Le traitement des requêtes distribuées évalue les requêtes sur des données réparties sur de nombreux nœuds, exploitant le parallélisme pour la rapidité et minimisant la communication réseau qui domine les coûts dans un environnement distribué.

Definition

Le traitement des requêtes distribuées est la décomposition, l'optimisation et l'exécution d'une requête sur des données situées sur plusieurs sites ou partitions, où le plan doit coordonner le travail entre les nœuds et minimiser à la fois le calcul et le transfert de données inter-nœuds.

Scope

Ce sujet couvre la manière dont les requêtes s'exécutent sur des données partitionnées et répliquées : les formes de parallélisme (partitionné, en pipeline et indépendant) ; les stratégies de jointure parallèles et distribuées telles que les jointures par repartitionnement et par diffusion ; les techniques de réduction de la communication telles que la semi-jointure ; et l'extension de l'optimisation basée sur les coûts pour tenir compte du transfert réseau et du placement des données. Il traite de la manière dont une requête logique est décomposée et planifiée sur les nœuds. Il exclut les décisions de placement des données et les protocoles de validation pour les transactions distribuées.

Core questions

• Quelles formes de parallélisme (partitionné, en pipeline, indépendant) un plan distribué peut-il exploiter ?
• Comment les jointures sont-elles exécutées lorsque les entrées sont partitionnées entre les nœuds ?
• Comment la semi-jointure réduit-elle la quantité de données expédiées entre les sites ?
• Comment l'optimisation change-t-elle lorsque le coût réseau devient dominant ?
• Comment le placement des données affecte-t-il le choix du plan le moins coûteux ?

Key concepts

• parallélisme partitionné
• parallélisme en pipeline
• parallélisme indépendant
• jointure par repartitionnement (mélange)
• jointure par diffusion
• réduction par semi-jointure
• coût de communication
• localisation des données

Key theories

Parallélisme dans l'exécution des requêtes

Les plans distribués exploitent le parallélisme partitionné (le même opérateur s'exécute sur des partitions de données disjointes), le parallélisme en pipeline (les opérateurs d'une chaîne s'exécutent concurremment) et le parallélisme indépendant (des sous-plans non liés s'exécutent simultanément) pour réduire le temps de réponse.

Jointures distribuées et parallèles

Les jointures sur des données partitionnées utilisent le repartitionnement (mélange des deux entrées par la clé de jointure) ou la diffusion d'une petite entrée à tous les nœuds ; le choix entre ces méthodes dépend de la taille des relations et du partitionnement existant.

Semi-jointure et minimisation de la communication

La semi-jointure réduit une relation aux seuls tuples qui peuvent correspondre avant de l'expédier sur le réseau, réduisant ainsi le coût de communication ; cette technique était centrale pour les premiers processeurs de requêtes distribuées tels que SDD-1.

Clinical relevance

Le traitement des requêtes distribuées permet aux systèmes analytiques de répondre à des requêtes sur des données bien plus volumineuses que ce qu'une seule machine pourrait contenir, et les techniques de minimisation du trafic réseau et de maximisation du parallélisme déterminent directement la vitesse des entrepôts de données et des moteurs de requêtes à grande échelle.

History

Le traitement des requêtes distribuées a été pionnier dans le système SDD-1 vers 1980, qui a introduit la réduction de la communication basée sur la semi-jointure. Les bases de données parallèles à architecture sans partage (shared-nothing) des années 1980 et 1990, étudiées par DeWitt et Gray, ont établi les jointures par repartitionnement et par diffusion ainsi que la taxonomie du parallélisme que les moteurs de requêtes distribuées modernes utilisent encore.

Key figures

• Philip Bernstein
• David DeWitt
• M. Tamer Özsu
• Patrick Valduriez

Seminal works

• bernstein1981
• dewitt1992
• ozsu2011

Frequently asked questions

Pourquoi le coût réseau est-il si important dans le traitement des requêtes distribuées ?

Dans une base de données distribuée, la ressource la plus lente et la plus sollicitée est généralement le réseau entre les nœuds. L'expédition de grands résultats intermédiaires entre les nœuds peut dominer le temps total de la requête, de sorte que les optimiseurs et les techniques telles que la semi-jointure se concentrent sur le transfert du moins de données possible, même au prix d'un calcul local supplémentaire.

Quand utilise-t-on une jointure par diffusion plutôt qu'une jointure par repartitionnement ?

Une jointure par diffusion envoie une copie d'une entrée à chaque nœud et est efficace lorsque cette entrée est petite. Une jointure par repartitionnement (mélange) redistribue les deux entrées par la clé de jointure entre les nœuds et est utilisée lorsque les deux relations sont grandes. L'optimiseur compare le coût de communication de la diffusion par rapport au repartitionnement pour faire son choix.