Explication détaillée de la connexion de hachage de base de données (nouvelle fonctionnalité de MySQL)

Vue d'ensemble

Pendant longtemps, le seul algorithme que MySQL utilisait pour effectuer des jointures était l'algorithme de boucle imbriquée ), mais l'algorithme de boucle imbriquée est très inefficace dans certains scénarios, ce qui est également un problème pour lequel MySQL a été critiqué.

Avec la sortie de MySQL 8.0.18, MySQL Server peut utiliser la jointure par hachage. Cet article présentera brièvement comment implémenter la jointure par hachage et verra comment cela fonctionne dans MySQL, quand l'utiliser et quels sont les avantages. restrictions.

Apprentissage recommandé : Tutoriel MySQL

Introduction à la jointure par hachage

Qu'est-ce qu'une jointure par hachage ?

Hash join est un algorithme de jointure utilisé dans les bases de données relationnelles et ne peut être utilisé que pour des jointures avec des conditions de jointure égales (sur a.b = c.b). Il est généralement plus efficace que l'algorithme de boucle imbriquée (sauf lorsque l'extrémité de la sonde est très, très petite), surtout si aucun index n'est atteint.

Pour faire simple, l'algorithme de connexion de hachage consiste d'abord à charger une petite table dans la table de hachage mémoire, puis à parcourir les données de la grande table, à faire correspondre les données qualifiées dans la table de hachage ligne par ligne, et renvoyez-le au client.

(La table de hachage n'est qu'un exemple, pour comprendre, la clé du hachage réel est la valeur de la connexion, et la valeur est la liste chaînée des lignes de données )

Habituellement, le hachage La connexion est divisée en deux phases, la phase de construction et la phase de sonde. Dans la phase de construction, la table appropriée est d'abord sélectionnée comme « entrée de construction », la table de hachage est construite, puis les enregistrements d'une autre table « d'entrée de détection » sont parcourus afin de détecter la table de hachage pour trouver les enregistrements qui répondent aux conditions de connexion.

L'image ci-dessus est un exemple pour interroger la province correspondant à la ville. Nous supposons que city est l'entrée de construction. Pendant la phase de construction, le serveur crée une table de hachage de ville, parcourt la table de ville et place les lignes dans la table de hachage dans l'ordre. La clé est hash(province_id) et la valeur est la. ligne de ville correspondante. `

Pendant la phase de sonde, le serveur commence à lire les lignes à partir de l'entrée de la sonde (province). Pour chaque ligne, la table de hachage est interrogée pour rechercher les lignes correspondantes en utilisant la valeur hash(province.province_id) comme clé de recherche.

C'est-à-dire que si toutes les entrées de construction peuvent être chargées en mémoire, chaque ligne de détection n'est analysée qu'une seule fois et une recherche à temps constant peut être utilisée pour trouver des lignes correspondantes entre les deux entrées.

Que dois-je faire s'il y a trop de données qui ne peuvent pas être mises en mémoire ?

Le chargement de toutes les entrées de build en mémoire est sans aucun doute le plus efficace, mais dans certains cas, la mémoire n'est pas suffisante pour charger la table entière en mémoire, elle doit donc être traitée par lots.

Il existe deux méthodes courantes :

Chargement en mémoire par lots pour le traitement

1. La lecture de la mémoire maximale peut être effectuée. Créez une table de hachage pour accueillir les enregistrements, construisez l'entrée et générez une table de hachage

2. Parcourez l'entrée de détection et effectuez une détection complète de cette partie de la table de hachage ; 3. Nettoyez la table de hachage et redémarrez. Continuez ce processus jusqu'à ce que tout le traitement soit terminé.

Cette méthode entraînera l'analyse de l'intégralité de la table d'entrée de détection plusieurs fois.

Traitement d'écriture dans le fichier

1. Lorsque la mémoire est épuisée pendant la phase de table de hachage de construction, le serveur écrira l'entrée de construction restante sur plusieurs disques dans de petits fichiers. , tous les petits blocs de fichiers peuvent être lus en mémoire après le calcul et une table de hachage est créée (pour éviter les blocs de fichiers trop volumineux qui ne peuvent pas être chargés en mémoire ultérieurement et doivent être à nouveau séparés

2). Dans la phase de détection, en raison de La ligne de détection peut correspondre à une ligne de l'entrée de construction écrite sur le disque, donc l'entrée de détection doit également être écrite sur le disque

3. le fichier de bloc est lu à partir du disque et chargé en mémoire Dans la table de hachage, lisez le fichier de bloc de réponse à partir de l'entrée de détection et détectez l'élément correspondant

Après le traitement, passez à la paire de fichiers de bloc suivante ; tout le traitement est terminé.

Implémentation de jointure de hachage dans MySQL

MySQL sélectionnera la plus petite des deux entrées comme entrée de construction (calculée en octets), et lorsqu'il y a suffisamment de mémoire dans certains Dans certains cas, l'entrée de construction est chargée dans la mémoire pour traitement, et si cela ne suffit pas, elle est traitée par écriture dans un fichier.

Vous pouvez utiliser la variable système join_buffer_size pour contrôler l'utilisation de la mémoire des connexions de hachage. La mémoire utilisée par les connexions de hachage ne peut pas dépasser cette quantité. Lorsque cette quantité est dépassée, MySQL utilisera les fichiers pour le traitement.

L'exécution peut échouer si la mémoire dépasse join_buffer_size et les fichiers dépassent open_files_limit.

Vous pouvez utiliser les deux solutions suivantes :

● Augmentez join_buffer_size pour éviter le débordement de jointure de hachage sur le disque

● Augmentez open_files_limit

Dans quelles circonstances MySQL utilisera-t-il des jointures par hachage ?

Dans MySQL version 8.0.18, si les tables sont jointes ensemble en utilisant une ou plusieurs conditions de jointure égales et qu'aucun index n'est disponible pour la condition de jointure, une jointure par hachage sera utilisée. MySQL préfère utiliser les recherches d'index pour prendre en charge les boucles imbriquées si un index est disponible.

Par défaut, MySQL utilisera des jointures de hachage autant que possible, qui peuvent être activées ou désactivées des deux manières suivantes :

● Définir des variables globales ou de session (hash_join = on ou hash_join = off

SET optimizer_switch="hash_join=off";

● Utilisez des astuces (HASH_JOIN ou NO_HASH_JOIN).

Nous utiliserons la requête suivante comme exemple :

EXPLAIN FORMAT = tree
SELECT
  city.name AS city_name,
  province.name AS province_name
FROM
  city
  JOIN province
    ON city.province_id = province.province_id;

Le résultat est :

| -> Inner hash join (city.province_id = province.province_id)  (cost=1333.82 rows=1329)
    -> Table scan on city  (cost=0.14 rows=391)
    -> Hash
        -> Table scan on province  (cost=3.65 rows=34)

Les jointures de hachage peuvent également être utilisées dans plusieurs requêtes de jointure, à condition qu'il y ait une équijointure, vous pouvez utiliser une connexion de hachage.

Par exemple, la requête suivante :

EXPLAIN FORMAT= TREE
SELECT
  city.name AS city_name,
  province.name AS province_name,
  country.name AS country_name
FROM
  city
  JOIN province
    ON city.province_id = province.province_id
    AND city.id < 50
  JOIN country
    ON province.province_id = country.id

Le résultat est :

| -> Inner hash join (city.province_id = country.id)  (cost=23.27 rows=2)
    -> Filter: (city.id < 50)  (cost=5.32 rows=5)
        -> Index range scan on city using PRIMARY  (cost=5.32 rows=49)
    -> Hash
        -> Inner hash join (province.province_id = country.id)  (cost=4.00 rows=3)
            -> Table scan on province  (cost=0.59 rows=34)
            -> Hash
                -> Table scan on country  (cost=0.35 rows=1)

La connexion de hachage est également applicable au "produit cartésien", c'est-à-dire qu'aucune condition de requête n'est spécifiée , comme suit :

EXPLAIN FORMAT= TREE
SELECT
  *
FROM
  city
  JOIN province;

Le résultat est :

| -> Inner hash join  (cost=1333.82 rows=13294)
    -> Table scan on city  (cost=1.17 rows=391)
    -> Hash
        -> Table scan on province  (cost=3.65 rows=34)

Dans quelles circonstances MySQL n'utilisera-t-il pas les jointures de hachage ?

1. Actuellement, la jointure par hachage MySQL ne prend en charge que les jointures internes, les semi-jointures et les jointures externes sont toujours exécutées à l'aide de boucles imbriquées par blocs.

2. Si l'index est disponible, MySQL préférera utiliser la recherche d'index pour prendre en charge les boucles imbriquées ;

3 Lorsqu'il n'y a pas de requête équivalente, les boucles imbriquées seront utilisées.

est le suivant :

EXPLAIN FORMAT=TREE
SELECT
  *
FROM
  city
  JOIN province
    ON city.province_id < province.province_id;

Le résultat est :

| <not executable by iterator executor>

Comment vérifier si l'exécution de l'instruction utilise une connexion de hachage ?

EXPLAIN FORMAT= TREE peut être utilisé dans MySQL 8.0.16 et les versions ultérieures. TREE fournit une sortie arborescente et décrit le traitement des requêtes avec plus de précision que le format d'affichage traditionnel. format de l’utilisation de connexion attendue.

De plus, vous pouvez également utiliser EXPLAIN ANALYZE pour afficher les informations de connexion de hachage.

---

Ce qui précède est basé sur le serveur de communauté MySQL 8.0.18.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!