Optimisation des jointures de plage

  • Article

Une jointure de plage se produit lorsque deux relations sont jointes à l’aide d’un point dans une condition de chevauchement d’intervalle ou d’intervalle. La prise en charge de l’optimisation de jointure de plage dans Databricks Runtime peut apporter des améliorations de l’amplitude des performances des requêtes, mais nécessite un réglage manuel minutieux.

Point dans la jointure de plage d’intervalles

Un point dans la jointure de plage d’intervalles est une jointure dans laquelle 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 de plage de chevauchement d’intervalle

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 de jointure de plage est effectuée pour les jointures qui :

  • Ont une condition qui peut être interprétée comme un point dans un intervalle ou une jointure de plage de chevauchement d’intervalle.
  • Toutes les valeurs impliquées dans la condition de jointure de la plage sont d’un type numérique (intégral, virgule flottante, décimal), DATE ou TIMESTAMP.
  • Toutes les valeurs impliquées dans la condition de jointure de plage sont du même type. Dans le cas du type décimal, les valeurs doivent également être de la même portée et de la même précision.
  • Il s’agit d’un INNER JOIN ou, dans le cas d’une jointure de plage d’intervalles, d’un LEFT OUTER JOIN avec une valeur de point sur le côté gauche ou RIGHT OUTER JOIN avec une valeur de point située à droite.
  • Avoir un paramètre de réglage de la taille de la classe.

Taille de la classe

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 classe de 10, l’optimisation fractionne le domaine en classes dont l’intervalle est égal à 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 jointure possibles pour cet intervalle. Par exemple, si p a la valeur 32, il peut être exclu de la valeur entre start 8 et end et 22, car il se trouve dans l’emplacement de 30 à 40.

Notes

  • Pour les valeurs DATE, la valeur de la taille de la classe est interprétée comme des jours. Par exemple, une valeur de taille de classe de 7 représente une semaine.
  • Pour les valeurs TIMESTAMP, la valeur de la taille de la classe est interprétée comme des secondes. Si une deuxième valeur est requise, des valeurs fractionnaires peuvent être utilisées. Par exemple, une valeur de taille de classe de 60 représente une minute et une valeur de taille de classe de 0,1 représente 100 millisecondes.

Vous pouvez spécifier la taille de la classe à l’aide d’un indicateur de jointure de plage dans la requête ou en définissant un paramètre de configuration de session. L’optimisation de jointure de plage est appliquée uniquement si vous spécifiez manuellement la taille de la classe. La section Choisir la taille de la classe décrit comment choisir une taille de classe optimale.

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, vous pouvez utiliser un indicateur de jointure de plage pour spécifier la taille de la classe. Le conseil doit contenir le nom de relation de l’une des relations jointes et le paramètre de taille de classe numérique. Le nom de la relation peut être 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)

Notes

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 l’indicateur 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 placer un indicateur de jointure de plage sur l’un des DataFrames joints. Dans ce cas, l’indicateur contient uniquement le paramètre taille de la classe 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, vous pouvez spécifier la taille de la classe 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 classe définie par le biais d’un indicateur de jointure de plage remplace toujours celle définie par le paramètre.

Choisir la taille de la classe

L’efficacité de l’optimisation de jointure de plage dépend du choix de la taille de classe appropriée.

Une petite taille de classe entraîne un plus grand nombre de classes, ce qui permet de filtrer les correspondances potentielles. Toutefois, cela devient inefficace si la taille de la classe est beaucoup plus petite que les intervalles de valeur rencontrés, et les intervalles de valeur chevauchent plusieurs intervalles de classe. Par exemple, avec une condition p BETWEEN start AND end, où start est 1 million et end est 1 999 999, et une taille de classe de 10, l’intervalle de valeur chevauche les classes 100 000.

Si la longueur de l’intervalle est relativement uniforme et connue, nous vous recommandons de définir la taille de l’emplacement sur la longueur normale attendue de l’intervalle de valeur. Toutefois, si la longueur de l’intervalle est variable et inclinée, un équilibre doit être trouvé pour définir une taille de classe qui filtre efficacement les intervalles courts, tout en empêchant les intervalles longs de chevaucher trop de classes. En supposant une table ranges, avec des intervalles entre les colonnes start et end, vous pouvez déterminer différents centiles de la valeur de la longueur d’intervalle décalée avec la requête suivante :

SELECT APPROX_PERCENTILE(CAST(end - start AS DOUBLE), ARRAY(0.5, 0.9, 0.99, 0.999, 0.9999)) FROM ranges

Un paramètre recommandé pour la taille de la class est le maximum de la valeur au 90e centile, ou la valeur au 99e centile divisée par 10, ou la valeur au 99,9e centile divisée par 100, etc. Le raisonnement est le suivant :

  • Si la valeur au 90e centile correspond à la taille de la classe, seuls 10 % des longueurs de valeur sont plus longues que l’intervalle de l’intervalle de la classe. Par conséquent, elles couvrent plus de 2 intervalles de classes adjacents.
  • Si la valeur au 99e centile est la taille de la classe, seul 1 % des longueurs d’intervalle de valeur s’étendent sur plus de 11 intervalles de classe adjacents.
  • Si la valeur au 99,9e centile est la taille de la classe, seul 0,1 % des longueurs d’intervalle de valeur s’étendent sur plus de 101 intervalles de classe adjacents.
  • La même opération peut être répétée pour les valeurs au 99,99e, le 99,999e centile, et ainsi de suite, si nécessaire.

La méthode décrite limite la quantité d’intervalles de valeurs longues inclinés qui chevauchent plusieurs intervalles de classe. La valeur de taille de la classe obtenue de cette façon n’est qu’un point de départ pour affiner le réglage. Les résultats réels peuvent dépendre de la charge de travail spécifique.