Optimisation des jointures de plage

Une jointure par intervalles relie deux tables sous une condition qui vérifie si une valeur se trouve dans une plage, ou si deux plages se chevauchent, au lieu de vérifier si deux valeurs sont égales. Par exemple, une requête qui associe chaque événement web à la session utilisateur où il s’est produit vérifie si l’horodatage de l’événement se situe entre les heures de début et de fin de la session. Une requête qui trouve des réunions programmées en même temps vérifie si deux plages horaires se chevauchent. L’optimisation des jointures de plage dans Databricks Runtime peut grandement améliorer les performances de ces requêtes.

À cause de cela, une jointure peut comparer plusieurs paires de lignes qui ne correspondent pas. L’optimisation des jointures de plage divise la plage de valeurs en compartiments et ne compare que les lignes qui se trouvent dans des compartiments qui se chevauchent. Voir Taille du compartiment.

Dans Databricks SQL, Azure Databricks optimise automatiquement les jointures de plage sans configuration manuelle. Vous pouvez également paramétrer manuellement les jointures de plage à l’aide d’indicateurs de jointure ou de la configuration de session pour tous les types de calcul.

Point dans la jointure de plage d’intervalles

Une jointure de plage d’intervalles point-dans-intervalle est une jointure dont la condition contient des prédicats spécifiant qu’une valeur d’une relation est comprise entre deux valeurs de l’autre relation. Par exemple :

-- using BETWEEN expressions
SELECT *
FROM points JOIN ranges ON points.p BETWEEN ranges.start and ranges.end;

-- using inequality expressions
SELECT *
FROM points JOIN ranges ON points.p >= ranges.start AND points.p < ranges.end;

-- with fixed length interval
SELECT *
FROM points JOIN ranges ON points.p >= ranges.start AND points.p < ranges.start + 100;

-- join two sets of point values within a fixed distance from each other
SELECT *
FROM points1 p1 JOIN points2 p2 ON p1.p >= p2.p - 10 AND p1.p <= p2.p + 10;

-- a range condition together with other join conditions
SELECT *
FROM points, ranges
WHERE points.symbol = ranges.symbol
  AND points.p >= ranges.start
  AND points.p < ranges.end;

Jointure par chevauchement de plages d'intervalles

Une jointure de plage de chevauchement d’intervalle est une jointure dans laquelle la condition contient des prédicats qui spécifient un chevauchement d’intervalles entre deux valeurs de chaque relation. Par exemple :

-- overlap of [r1.start, r1.end] with [r2.start, r2.end]
SELECT *
FROM r1 JOIN r2 ON r1.start < r2.end AND r2.start < r1.end;

-- overlap of fixed length intervals
SELECT *
FROM r1 JOIN r2 ON r1.start < r2.start + 100 AND r2.start < r1.start + 100;

-- a range condition together with other join conditions
SELECT *
FROM r1 JOIN r2 ON r1.symbol = r2.symbol
  AND r1.start <= r2.end
  AND r1.end >= r2.start;

Optimisation des jointures de plage

L’optimisation des jointures par plage s’applique aux jointures qui :

  • Une jointure avec un point dans l’intervalle ou une condition de jointure par chevauchement d’intervalles.
  • Utilisez uniquement des valeurs numériques (intégrales, en virgule flottante ou décimales), DATE, ou TIMESTAMP dans la condition de jointure de plage.
  • Utilisez des valeurs du même type dans la condition de jointure de plage. Les valeurs décimales doivent également avoir la même échelle et la même précision.
  • Utilisez un type de jointure pris en charge :
    • INNER JOIN, pour toute jointure de plage
    • LEFT OUTER JOIN avec la valeur en points à gauche, ou RIGHT OUTER JOIN avec la valeur en points à droite, uniquement pour les jointures de plage d’intervalles pour les points
  • Définissez une taille de bac, soit dérivée automatiquement, soit spécifiée manuellement.

Jointures avec des conditions d’égalité numérique et de plage de valeurs

Lorsqu’une condition de jointure comprend à la fois une condition d’égalité sur une colonne numérique et une condition d’intervalle, l’optimiseur peut appliquer un regroupement en classes à la colonne numérique de la condition d’égalité, car elle répond aux exigences de type pour l’optimisation des jointures par intervalle. Cela peut entraîner l’affectation de la colonne d’égalité à des compartiments ou son exclusion de l’optimisation, ce qui réduit les performances.

Pour garantir que l’optimisation de jointure de plage s’applique uniquement à la condition de plage prévue, convertissez les colonnes d’égalité numérique en STRING. Cela les exclut de la prise en compte en tant que colonnes de condition d’intervalle.

SELECT /*+ RANGE_JOIN(reference, 3306084) */
    reference.*, position.*
FROM position
INNER JOIN reference
    ON CAST(position.parent_index AS STRING) = CAST(reference.parent_index AS STRING)
    AND position.child_index BETWEEN reference.min_child_index AND reference.max_child_index;

Le même modèle s’applique à d’autres colonnes numériques utilisées comme clés d’égalité, telles que DATEles identificateurs entiers ou les colonnes de partition en cluster.

Taille du compartiment

La taille de la classe est un paramètre de réglage numérique qui divise le domaine des valeurs de la condition de plage en plusieurs classes de même taille. Par exemple, avec une taille de compartiment de 10, l'optimisation divise le domaine en compartiments avec des intervalles de longueur 10. Si vous avez un point dans la condition de plage de p BETWEEN start AND end, que start est égal à 8 et end est égal à 22, cet intervalle de valeur chevauche trois classes de longueur 10 : la première classe de 0 à 10, la deuxième de 10 à 20 et la troisième de 20 à 30. Seuls les points qui se trouvent dans les trois mêmes classes doivent être considérés comme des correspondances de fusion possibles pour cet intervalle. Par exemple, si p a la valeur 32, il peut être exclu comme tombant entre start 8 et end 22, car il se situe dans la plage de 30 à 40.

Note

  • Pour les valeurs DATE, la taille du bac est interprétée comme des jours. Par exemple, une valeur de taille du compartiment de 7 représente une semaine.
  • Pour les valeurs TIMESTAMP, la valeur de la taille du compartiment est interprétée en secondes. Pour une valeur inférieure à une seconde, on utilise une valeur fractionnaire. Par exemple, une valeur de taille de compartiment de 60 représente une minute, tandis qu'une valeur de taille de compartiment de 0,1 représente 100 millisecondes.

Vous pouvez spécifier la taille de la corbeille à l’aide d’un indicateur de jointure de plage dans la requête ou en définissant un paramètre de configuration de session. Dans Databricks SQL, la taille de compartiment est déterminée automatiquement lorsque l’optimisation automatique des jointures de plage est activée.

Optimisation automatique des jointures sur intervalle

Dans Databricks SQL, Azure Databricks détecte automatiquement les jointures de plage éligibles et détermine la taille de compartiment optimale en échantillonnant la table d’intervalles. Cela supprime la nécessité de spécifier manuellement une taille de bac par le biais d’indicateurs ou de configuration de session.

L’optimisation de jointure de plage automatique est activée par défaut dans Databricks SQL. Pour le désactiver, configurez cette configuration :

SET spark.databricks.optimizer.autoRangeJoin.enabled = false;

Si vous spécifiez une taille de compartiment par le biais d’un indicateur de jointure de plage ou d’une configuration de session, cette valeur remplace la taille de compartiment dérivée automatiquement.

Activer la jointure de plage à l’aide d’un indicateur de jointure de plage

Pour activer l’optimisation de jointure de plage dans une requête SQL, utilisez un indicateur de jointure de plage pour spécifier la taille de la corbeille. L'indication doit contenir le nom de relation de l'une des relations jointes et le paramètre de taille de compartiment numérique. Le nom de la relation est une table, une vue ou une sous-requête.

SELECT /*+ RANGE_JOIN(points, 10) */ *
FROM points JOIN ranges ON points.p >= ranges.start AND points.p < ranges.end;

SELECT /*+ RANGE_JOIN(r1, 0.1) */ *
FROM (SELECT * FROM ranges WHERE ranges.amount < 100) r1, ranges r2
WHERE r1.start < r2.start + 100 AND r2.start < r1.start + 100;

SELECT /*+ RANGE_JOIN(c, 500) */ *
FROM a
  JOIN b ON (a.b_key = b.id)
  JOIN c ON (a.ts BETWEEN c.start_time AND c.end_time)

Note

Dans le troisième exemple, vous devez placer le conseil sur c. Cela est dû au fait que les jointures sont associatives à gauche, de sorte que la requête est interprétée comme (a JOIN b) JOIN c, et la suggestion sur a s’applique à la jointure de a avec b, et non à la jointure avec c.

#create minute table
minutes = spark.createDataFrame(
    [(0, 60), (60, 120)],
    "minute_start: int, minute_end: int"
)

#create events table
events = spark.createDataFrame(
    [(12, 33), (0, 120), (33, 72), (65, 178)],
    "event_start: int, event_end: int"
)

#Range_Join with "hint" on the from table
(events.hint("range_join", 60)
  .join(minutes,
    on=[events.event_start < minutes.minute_end,
    minutes.minute_start < events.event_end])
  .orderBy(events.event_start,
    events.event_end,
    minutes.minute_start)
  .show()
)

#Range_Join with "hint" on the join table
(events.join(minutes.hint("range_join", 60),
  on=[events.event_start < minutes.minute_end,
    minutes.minute_start < events.event_end])
  .orderBy(events.event_start,
    events.event_end,
    minutes.minute_start)
  .show()
)

Vous pouvez également ajouter un indicateur de jointure par plage à l'un des DataFrames jointe. Dans ce cas, l’indice contient uniquement le paramètre de taille du compartiment numérique.

val df1 = spark.table("ranges").as("left")
val df2 = spark.table("ranges").as("right")

val joined = df1.hint("range_join", 10)
  .join(df2, $"left.type" === $"right.type" &&
     $"left.end" > $"right.start" &&
     $"left.start" < $"right.end")

val joined2 = df1
  .join(df2.hint("range_join", 0.5), $"left.type" === $"right.type" &&
     $"left.end" > $"right.start" &&
     $"left.start" < $"right.end")

Activer la jointure de plage à l’aide de la configuration de session

Si vous ne souhaitez pas modifier la requête, spécifiez la taille de la corbeille en tant que paramètre de configuration.

SET spark.databricks.optimizer.rangeJoin.binSize=5

Ce paramètre de configuration s’applique à toute jointure avec une condition de plage. Toutefois, une autre taille de bin définie par le biais d'un indice de jointure de plage remplace toujours celle définie par le paramètre.

Choisir la taille du bac

L’efficacité de l’optimisation de la jointure par intervalle dépend du choix de la taille de l'intervalle appropriée.

Une petite taille de compartiment entraîne un plus grand nombre de compartiments, ce qui permet de filtrer les correspondances potentielles. Une petite taille de bac devient inefficace si les intervalles de valeur sont beaucoup plus grands que la taille du bac, ce qui fait que les intervalles chevauchent de nombreux compartiments. Par exemple, avec une condition p BETWEEN start AND end où start est 1 000 000 et end est 1 999 999, et une taille de bac de 10, l’intervalle chevauche 100 000 compartiments.

Si la longueur de l’intervalle est assez uniforme et connue, définissez la taille du compartiment sur la longueur typique de l’intervalle. Pour des intervalles asymétriques variables, choisissez une taille de bin qui filtre efficacement les intervalles courts tout en empêchant les intervalles longs de se chevaucher trop de bins. Pour un tableau ranges avec des intervalles entre colonnes start et end, déterminez les percentiles de la longueur d’intervalle asymétrique avec cette requête :

SELECT
  map_from_arrays(
    ARRAY(0.5, 0.9, 0.99, 0.999, 0.9999),
    APPROX_PERCENTILE(
      end::DOUBLE - start::DOUBLE,
      ARRAY(0.5, 0.9, 0.99, 0.999, 0.9999)
    )
  ) AS bin_sizes
FROM
  ranges;

Le transtypage de chaque colonne en DOUBLE avant la soustraction garantit que la requête fonctionne, que les colonnes contiennent des valeurs numériques, DATE ou TIMESTAMP.

Réglez la taille du bac à la plus grande de ces valeurs :

  • Le 90e centile des longueurs des intervalles. À cette taille, au maximum 10% d’intervalles couvrent plus de 2 classes.
  • Le 99e centile divisé par 10. À cette taille, au maximum 1 % d’intervalles couvrent plus de 11 classes.
  • Le 99,9e centile divisé par 100. À cette taille, au maximum 0,1 % des intervalles couvrent plus de 101 compartiments.

Pour couvrir des intervalles encore plus longs, poursuivez le schéma avec les 99,99e et 99,999e percentiles. Utilisez le résultat comme point de départ, puis ajustez la taille des intervalles selon votre charge de travail.

  • Dernière mise à jour :