Optimalisatie van range joins

Een range join vindt plaats wanneer twee relaties worden samengevoegd met behulp van een interval- of overlapvoorwaarde. De ondersteuning voor range join-optimalisatie in Databricks Runtime kan zorgen voor een exponentiële verbetering in queryprestaties, maar vereist zorgvuldige, handmatige fijn afstemming.

Databricks raadt aan om join hints te gebruiken voor range joins bij slechte prestaties.

Intervalbereikdeelname

Een point in interval range join is een join waarin de voorwaarde predicaten bevat die specificeren dat een waarde uit de ene relatie ligt tussen twee waarden van de andere relatie. Voorbeeld:

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

Interval overlapping bereik samenvoeging

Een koppeling van overlappende intervalbereiken is een koppeling waarin de conditie predicaten bevat die een overlapping van intervallen tussen twee waarden uit elke relatie bepalen. Voorbeeld:

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

Optimalisatie van range joins

De optimalisatie van bereikjoin wordt uitgevoerd voor joins die:

• Een voorwaarde hebben die kan worden geïnterpreteerd als een punt-in-interval of interval-overlappingsbereikdeelname.
• Alle waarden die betrokken zijn bij de voorwaarde voor bereikdeelname zijn van een numeriek type (integraal, drijvende komma, decimaal), DATEof TIMESTAMP.
• Alle waarden die betrokken zijn bij de bereikverbindingsvoorwaarde, zijn van hetzelfde type. In het geval van het decimale type moeten de waarden ook dezelfde schaal en precisie hebben.
• Het is een INNER JOIN, of in het geval van punt-in-intervalbereik-join, een LEFT OUTER JOIN met puntwaarde aan de linkerkant of RIGHT OUTER JOIN met puntwaarde aan de rechterkant.
• Een parameter voor het afstemmen van de grootte van de bin hebben.

Bakgrootte

De grootte van de bin is een numerieke afstemmingsparameter waarmee het waardendomein van de bereikvoorwaarde wordt gesplitst in meerdere bins met gelijke grootte. Met een bingrootte van 10 splitst de optimalisatie het domein bijvoorbeeld op in bins die intervallen van lengte 10 zijn. Als u een punt in bereikvoorwaarde hebt van p BETWEEN start AND enden start 8 is en end 22 is, overlapt dit waarde-interval met drie bins van lengte 10: de eerste bin van 0 tot 10, de tweede bin van 10 tot 20 en de derde bin van 20 tot 30. Alleen de punten die binnen dezelfde drie klassen vallen, moeten worden beschouwd als mogelijke koppelingen voor dat interval. Als p bijvoorbeeld 32 is, kan het worden uitgesloten als zijnde tussen start van 8 en end van 22, omdat het in de categorie van 30 tot 40 valt.

Notitie

• Voor DATE waarden wordt de waarde van de bin-grootte geïnterpreteerd als dagen. Een bin-groottewaarde van 7 vertegenwoordigt bijvoorbeeld een week.
• Voor TIMESTAMP waarden wordt de waarde van de bin-grootte geïnterpreteerd als seconden. Als een sub-seconde waarde is vereist, kunnen fractiewaarden worden gebruikt. Een bin-groottewaarde van 60 vertegenwoordigt bijvoorbeeld een minuut en een bin-groottewaarde van 0,1 vertegenwoordigt 100 milliseconden.

U kunt de grootte van de bin opgeven met behulp van een hint voor bereikdeelname in de query of door een sessieconfiguratieparameter in te stellen. De range join-optimalisatie wordt alleen toegepast als u handmatig de grootte van de bin opgeeft. In de sectie Kies de bingrootte staat beschreven hoe u een optimale bingrootte kunt kiezen.

Bereikdeelname inschakelen met behulp van een hint voor bereikdeelname

Als u de optimalisatie van bereikdeelname in een SQL-query wilt inschakelen, kunt u een hint voor bereikdeelname gebruiken om de grootte van de bin op te geven. De hint moet de relationele naam van een van de gekoppelde relaties en de parameter voor de grootte van de numerieke bin bevatten. De relatienaam kan een tabel, een weergave of een subquery zijn.

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)

Notitie

In het derde voorbeeld moet u de hint plaatsen opc. Dit komt doordat joins links associatief zijn, zodat de query wordt geïnterpreteerd als (a JOIN b) JOIN c, en de hint op a van toepassing is op de join van a met b en niet op de join met 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()
)

U kunt ook een range join-hint plaatsen op een van de gekoppelde DataFrames. In dat geval bevat de hint alleen de parameter voor de numerieke bin-grootte.

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

Range join inschakelen door sessieconfiguratie

Als u de query niet wilt wijzigen, kunt u de grootte van de bin opgeven als een configuratieparameter.

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

Deze configuratieparameter is van toepassing op elke join met een bereikvoorwaarde. Een andere bin-grootte die is ingesteld via een range join-hint overschrijft echter altijd diegene die via de parameter is ingesteld.

Kies de grootte van de bak

De effectiviteit van de bereikjoin-optimalisatie hangt af van het kiezen van de juiste bingrootte.

Een kleine bin-grootte resulteert in een groter aantal bins, wat helpt bij het filteren van de potentiële overeenkomsten. Het wordt echter inefficiënt als de bin-grootte aanzienlijk kleiner is dan de aangetroffen waardeintervallen en de waardeintervallen overlappen meerdere bin-intervallen . Met een voorwaarde p BETWEEN start AND end, waarbij start bijvoorbeeld 1.000.000 is en end 1.999.999 is en een bingrootte van 10, overlapt het waarde-interval met 100.000 bins.

Als de lengte van het interval redelijk uniform en bekend is, raden we u aan de bin-grootte in te stellen op de typische verwachte lengte van het waardeinterval. Als de lengte van het interval echter varieert en scheef is, moet een evenwicht worden gevonden om een bin-grootte in te stellen waarmee de korte intervallen efficiënt kunnen worden gefilterd, terwijl de lange intervallen te veel bins overlappen. Ervan uitgaande dat er een tabel ranges is, met intervallen tussen kolommen start en end, kunt u verschillende percentielen van de scheefgetrokken intervallengte bepalen met de volgende query:

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

Een aanbevolen instelling van bin-grootte is het maximum van de waarde op het 90e percentiel, of de waarde op het 99e percentiel gedeeld door 10, of de waarde op het 99,9e percentiel gedeeld door 100, enzovoort. De reden is:

• Als de waarde bij het 90e percentiel de grootte van de bin is, dan is slechts 10% van de waarde-interval lengtes langer dan het bin-interval, en overspannen ze meer dan 2 aangrenzende bin-intervallen.
• Als de waarde bij het 99e percentiel de bin-grootte is, is slechts 1% van de lengte van het waarde-interval langer dan 11 aangrenzende bin-intervallen.
• Als de waarde bij het 99,9e percentiel de bin-grootte is, beslaat slechts 0,1% van de lengte van het waardeinterval meer dan 101 aangrenzende bin-intervallen.
• Hetzelfde kan worden herhaald voor de waarden op het 99,99e, het 99,999e percentiel, enzovoort, indien nodig.

De beschreven methode beperkt de hoeveelheid scheefgetrokken lange waardeintervallen die meerdere bin-intervallen overlappen. De waarde van de bin-grootte die op deze manier is verkregen, is slechts een uitgangspunt voor het afstemmen; werkelijke resultaten kunnen afhankelijk zijn van de specifieke workload.