Optimierung des Bereichsjoins

Ein Bereichsverbund liegt vor, wenn zwei Relationen unter Verwendung einer Punkt-in-Intervall- oder Intervallüberlappungsbedingung verknüpft werden. Die Verwendung der Optimierung für Bereichs-Joins in Databricks Runtime kann die Abfrageleistung erheblich verbessern.

In Databricks SQL optimiert Azure Databricks Bereichs-Joins automatisch, ohne dass eine manuelle Konfiguration erforderlich ist. Sie können Bereichs-Joins auch manuell mithilfe von Join-Hinweisen oder der Sitzungskonfiguration für alle Rechentypen optimieren.

Punkt im Intervallbereichs-Join

Ein Join eines Punkts mit einem Intervallbereich ist ein Join, dessen Bedingung Prädikate enthält, die festlegen, dass ein Wert aus einer Relation zwischen zwei Werten der anderen Relation 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:

• 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 die Werte ebenfalls dieselbe Skalierung und Genauigkeit aufweisen.
• 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.
• Eine Bin-Größe haben, die entweder automatisch abgeleitet oder manuell festgelegt wird.

Verknüpfungen mit numerischen Gleichheits- und Bereichsbedingungen

Wenn eine Verknüpfungsbedingung sowohl eine Gleichheitsbedingung für eine numerische Spalte als auch eine Bereichsbedingung enthält, kann der Optimierer die Binning auf die Spalte für die numerische Gleichheit anwenden, da sie die Typanforderungen für die Optimierung der Bereichsbeitritte erfüllt. Dies kann dazu führen, dass der Gleichheitsspalte Container zugewiesen oder von der Optimierung ausgeschlossen wird, wodurch die Leistung reduziert wird.

Um sicherzustellen, dass die Range-Join-Optimierung nur auf die beabsichtigte Bereichsbedingung angewendet wird, konvertieren Sie die numerischen Spalten in der Gleichheitsbedingung in STRING um. Dadurch kommen sie für die Berücksichtigung als Spalten für Bereichsbedingungen nicht in Betracht.

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;

Dasselbe Muster gilt auch für andere numerische Spalten, die als Gleichheitsschlüssel verwendet werden, wie z. B. DATE, Ganzzahlkennungen oder geclusterte Partitionsspalten.

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 Bins fallen, sollten als mögliche Join-Vergleiche 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.

Sie können die Bin-Größe angeben, indem Sie in der Abfrage einen Range-Join-Hinweis verwenden oder einen Sitzungskonfigurationsparameter festlegen. In Databricks SQL wird die Bin-Größe automatisch ermittelt, wenn die automatische Range-Join-Optimierung aktiviert ist.

Automatische Optimierung von Range-Joins

In Databricks SQL erkennt Azure Databricks automatisch geeignete Bereichs-Joins und ermittelt die optimale Bin-Größe durch Stichproben aus der Intervalltabelle. Dadurch wird die Notwendigkeit entfernt, eine Bin-Größe manuell durch Hinweise oder Sitzungskonfiguration anzugeben.

Die automatische Bereichsbeitrittsoptimierung ist in Databricks SQL standardmäßig aktiviert. Um sie zu deaktivieren, legen Sie die folgende Konfiguration fest:

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

Wenn Sie eine Bin-Größe über einen Bereichsbeitrittshinweis oder eine Sitzungskonfiguration angeben, überschreibt dieser Wert die automatisch abgeleitete Bin-Größe.

Aktivieren des Bereichsjoins mithilfe eines Bereichsjoinhinweises

Um die Range-Join-Optimierung in einer SQL-Abfrage zu aktivieren, verwenden Sie einen Range-Join-Hinweis, um die Bin-Größ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)

#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 den numerischen Parameter für die Bin-Größe.

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, geben Sie die Bin-Größe als Konfigurationsparameter an.

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.

Wählen Sie die Größe des Behälters aus.

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

Die Umwandlung jeder Spalte in DOUBLE vor der Subtraktion stellt sicher, dass die Abfrage unabhängig davon funktioniert, ob die Spalten numerische Werte, DATE- oder TIMESTAMP-Werte enthalten.

Als empfohlene Klassengröße bietet sich das Maximum aus dem Wert beim 90. Perzentil, dem durch 10 geteilten Wert beim 99. Perzentil oder dem durch 100 geteilten Wert beim 99,9. Perzentil usw. an. Die Begründung lautet:

• 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 beim 99,99. und 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 abgerufene Bin-Größenwert ist nur ein Ausgangspunkt für die Feinabstimmung. Die tatsächlichen Ergebnisse hängen möglicherweise von der jeweiligen Arbeitsauslastung ab.