Optimierung des Bereichsjoins

Ein Bereichs-Join verbindet zwei Tabellen unter einer Bedingung, die prüft, ob ein Wert innerhalb eines Bereichs liegt oder ob sich zwei Bereiche überschneiden, anstatt zu prüfen, ob zwei Werte gleich sind. Zum Beispiel prüft eine Abfrage, die jedes Website-Ereignis mit der Benutzersitzung abstimmt, in der es stattgefunden hat, ob der Zeitstempel des Ereignisses zwischen der Start- und Endzeit der Sitzung liegt. Eine Abfrage, die Meetings findet, die zur gleichen Zeit geplant sind, prüft, ob sich zwei Zeitbereiche überschneiden. Die Optimierung von Range-Joins in Databricks Runtime kann die Leistung dieser Abfragen erheblich verbessern.

Deshalb kann ein Join viele Paare von Zeilen vergleichen, die nicht übereinstimmen können. Die Bereichs-Join-Optimierung teilt den Wertebereich in Bins auf und vergleicht nur Zeilen, die in überlappenden Bins liegen. Siehe Bin Size.

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 Bereichs-Join-Optimierung gilt für Joins, die:

• Eine Join-Bedingung für Punkt-in-Intervall oder Intervallüberlappungsbereich.
• Verwenden Sie nur numerische (Integral-, Gleitkomma- oder Dezimalwerte), DATE oder TIMESTAMP Werte in der Range-Join-Bedingung.
• Verwenden Sie Werte desselben Typs in der Range Join-Bedingung. Dezimalwerte müssen ebenfalls die gleiche Skala und Präzision haben.
• Verwenden Sie einen unterstützten Join-Typ:
  • INNER JOIN, für jeden Range-Join
  • LEFT OUTER JOIN mit dem Punktwert auf der linken Seite oder RIGHT OUTER JOIN mit dem Punktwert auf der rechten Seite, nur für Point-in-Interval-Range-Joins
• Legen Sie eine Bin-Größe fest, 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 es zu deaktivieren, legen Sie diese Konfigurationseinstellung 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 Relationsname ist eine Tabelle, eine Ansicht oder eine Unteranfrage.

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. Eine kleine Bin-Größe wird ineffizient, wenn die Wertintervalle viel größer sind als die Bin-Größe, wodurch Intervalle viele Bins überlappen. Zum Beispiel überschneidet sich bei einer Bedingung p BETWEEN start AND end, wobei start 1.000.000 und end 1.999.999 ist, und einer Bin-Größe von 10 das Intervall mit 100.000 Bins.

Wenn die Intervalllänge relativ gleichmäßig und bekannt ist, setzen Sie die Bin-Größe auf die typische Intervalllänge. Für variierende, schiefe Intervalle wählen Sie eine Bin-Größe, die kurze Intervalle effizient filtert und gleichzeitig verhindert, dass lange Intervalle zu viele Bins überlappen. Für eine Tabelle ranges mit Intervallen zwischen den Spalten end und start bestimmen Sie Perzentile der schiefen Intervalllänge mit dieser Abfrage:

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.

Setze die Bin-Größe auf die größte dieser Werte:

• Das 90. Perzentil der Intervalllängen. Bei dieser Größe spannen höchstens 10 % der Intervalle mehr als 2 Klassen.
• Das 99. Perzentil geteilt durch 10. Bei dieser Größe spannen höchstens 1 % der Intervalle mehr als 11 Klassen.
• Das 99,9. Perzentil, geteilt durch 100. Bei dieser Größe spannen höchstens 0,1 % der Intervalle mehr als 101 Bins.

Um noch längere Intervalle abzudecken, setzen Sie das Muster mit den Perzentilwerten 99,99 und 99,999 fort. Nutze das Ergebnis als Ausgangspunkt und passe dann die Bin-Größe für deine Arbeitsbelastung an.