Optimierung des Bereichsjoins

  • Artikel

Ein Bereichsjoin tritt auf, wenn zwei Beziehungen mithilfe eines Punkts im Intervall oder einer Intervallüberlappungsbedingung verbunden werden. Die Unterstützung der Optimierung des Bereichsjoins in Databricks Runtime kann zu einer deutlichen Verbesserung der Abfrageleistung führen, erfordert jedoch eine sorgfältige manuelle Einstellung.

Punkt-im-Intervall-Bereichsjoin

Ein Punkt-im-Intervall-Bereichsjoin ist ein Join, bei dem die Bedingung Prädikate enthält, die angeben, dass ein Wert aus einer Beziehung zwischen zwei Werten aus der anderen Beziehung liegt. Beispiele:

-- 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;

Intervallüberlappungs-Bereichsjoin

Ein Intervallüberlappungs-Bereichsjoin ist ein Join, bei dem die Bedingung Prädikate enthält, die eine Überlappung von Intervallen zwischen zwei Werten aus den einzelnen Beziehungen angeben. Beispiele:

-- 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;

Optimierung des Bereichsjoins

Die Optimierung des Bereichsjoins wird für Joins ausgeführt, die folgende Bedingungen erfüllen:

  • Sie haben eine Bedingung, die als Punkt im Intervall oder als Intervallüberlappungs-Bereichsjoin interpretiert werden kann.
  • Alle Werte, die an der Bereichsjoinbedingung beteiligt sind, sind von numerischem Typ (integral, Gleitkomma, dezimal), DATE oder TIMESTAMP.
  • Alle Werte, die an der Bereichsjoinbedingung beteiligt sind, sind vom gleichen Typ. Im Fall des Dezimaltyps müssen auch Skala und Genauigkeit der Werte identisch sein.
  • Es handelt sich um einen INNER JOIN, oder im Falle eines Punkt-im-Intervall-Bereichsjoins um einen LEFT OUTER JOIN mit Punktwert auf der linken Seite, oder einen RIGHT OUTER JOIN mit Punktwert auf der rechten Seite.
  • Sie haben einen Parameter für die Optimierung der Bingröße.

Bingröße

Die Bingröße ist ein numerischer Optimierungsparameter, der die Wertedomäne der Bereichsbedingung in mehrere Bins gleicher Größe aufteilt. Bei einer Bingröße von 10 teilt die Optimierung die Domäne beispielsweise in Intervalle der Länge 10 auf. Wenn Sie eine Punkt-im-Bereich-Bedingung von p BETWEEN start AND end haben und start 8 und end 22 ist, überschneidet sich dieses Wertintervall mit drei Bins der Länge 10 – der erste Bin von 0 bis 10, der zweite Bin von 10 bis 20 und der dritte Bin von 20 bis 30. Nur die Punkte, die in dieselben drei Intervalle fallen, müssen als mögliche Joinübereinstimmungen für dieses Intervall betrachtet werden. Wenn z. B. p 32 ist, kann ausgeschlossen werden, dass es zwischen start von 8 und end von 22 liegt, da es zwischen 30 und 40 liegt.

Hinweis

  • Für DATE-Werte wird der Wert der Bingröße als Tage interpretiert. Beispielsweise stellt der Bingrößenwert 7 eine Woche dar.
  • Für TIMESTAMP-Werte wird der Wert der Bingröße in Sekunden interpretiert. Wenn ein Wert von unter einer Sekunde erforderlich ist, können Bruchwerte verwendet werden. Beispielsweise stellt ein Bingrößenwert von 60 eine Minute dar, und ein Bingrößenwert von 0,1 stellt 100 Millisekunden dar.

Sie können die Bingröße entweder mithilfe eines Bereichsjoinhinweises in der Abfrage oder durch Festlegen eines Sitzungskonfigurationsparameters angeben. Die Bereichsjoinoptimierung wird nur angewendet, wenn Sie die Bingröße manuell angeben. Im Abschnitt Auswählen der Bingröße wird beschrieben, wie Sie eine optimale Bingröße auswählen.

Aktivieren des Bereichsjoins mithilfe eines Bereichsjoinhinweises

Um die Optimierung des Bereichsjoins in einer SQL-Abfrage zu aktivieren, können Sie einen Bereichsjoinhinweis verwenden, um die Bingröße anzugeben. Der Hinweis muss den Beziehungsnamen einer der verknüpften Beziehungen und die numerische Bingröße als Parameter enthalten. Der Name der Beziehung kann eine Tabelle, eine Sicht oder eine Unterabfrage sein.

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)

Hinweis

Im dritten Beispiel müssen Sie den Hinweis auf c platzieren. Dies liegt daran, dass Joins linksassoziativ sind, sodass die Abfrage als (a JOIN b) JOIN c interpretiert wird und der Hinweis auf a für den Join von a mit b und nicht für den Join mit c gilt.

#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()
)

Sie können auch einen Bereichsjoinhinweis in einem der verknüpften DataFrames platzieren. In diesem Fall enthält der Hinweis nur die numerische Bingröße als Parameter.

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")

Aktivieren des Bereichsjoins mithilfe der Sitzungskonfiguration

Wenn Sie die Abfrage nicht ändern möchten, können Sie die Bingröße als Konfigurationsparameter angeben.

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

Dieser Konfigurationsparameter gilt für jeden Join mit einer Bereichsbedingung. Eine andere Bingröße, die durch einen Bereichsjoinhinweis festgelegt wird, überschreibt jedoch immer den durch den Parameter festgelegten Wert.

Auswählen der Bin-Größe

Die Effektivität der Optimierung des Bereichsjoins hängt von der Auswahl der geeigneten Bingröße ab.

Eine kleine Bingröße führt zu einer größeren Anzahl von Bins, was bei der Filterung potenzieller Übereinstimmungen hilft. Es wird jedoch ineffizient, wenn die Bingröße erheblich kleiner als die gefundenen Wertintervalle ist und die Wertintervalle mehrere Binintervalle überlappen. Bei einer p BETWEEN start AND end-Bedingung mit start von 1.000.000 und end von 1.999.999 und einer Bingröße von 10 überschneidet sich das Wertintervall beispielsweise mit 100.000 Bins.

Wenn die Länge des Intervalls relativ einheitlich und bekannt ist, sollten Sie die Bingröße auf die typische erwartete Länge des Wertintervalls setzen. Wenn die Länge des Intervalls jedoch variiert und verzerrt ist, muss ein Ausgleich gefunden werden, um eine Bingröße festzulegen, die die kurzen Intervalle effizient filtert, während verhindert wird, dass die langen Intervalle zu viele Bins überlappen. Unter der Annahme einer Tabelle ranges mit Intervallen zwischen den Spalten start und end können Sie mit der folgenden Abfrage verschiedene Perzentile des Werts für die Länge des verzerrten Intervalls bestimmen:

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

Eine empfohlene Einstellung der Bingröße wäre das Maximum des Werts im 90. Perzentil, oder der Wert im 99. Perzentil dividiert durch 10, oder der Wert im 99,9. Perzentil dividiert durch 100 und so weiter. Die Gründe dafür sind:

  • Wenn der Wert im 90. Perzentil die Bingröße ist, sind nur 10 % der Längen des Wertintervalls länger als das Binintervall, sodass mehr als 2 angrenzende Binintervalle umfasst werden.
  • Wenn der Wert im 99. Perzentil die Bingröße ist, umfasst nur 1 % der Wertintervalllängen mehr als 11 angrenzende Binintervalle.
  • Wenn der Wert im 99,9. Perzentil die Bingröße ist, umfasst nur 0,1 % der Wertintervalllängen mehr als 101 angrenzende Binintervalle.
  • Dasselbe kann bei Bedarf für die Werte im 99,99., 99,999. Perzentil usw. wiederholt werden.

Die beschriebene Methode schränkt die Menge der Intervalle mit verzerrten Längenwerten ein, die mehrere Binintervalle überlappen. Der auf diese Weise ermittelte Wert für die Bingröße ist nur ein Ausgangspunkt für die Feinabstimmung. Die tatsächlichen Ergebnisse können von der spezifischen Workload abhängen.