Optimalisatie van range joins

Een range join voegt twee tabellen samen onder een voorwaarde die controleert of een waarde binnen een bereik valt, of dat twee ranges overlappen, in plaats van te controleren of twee waarden gelijk zijn. Bijvoorbeeld, een query die elk website-event koppelt aan de gebruikerssessie waarin het plaatsvond, controleert of de tijdstempel van het evenement tussen de begin- en eindtijd van de sessie valt. Een zoekopdracht die vergaderingen vindt die op hetzelfde tijdstip gepland staan, controleert of twee tijdsbereiken overlappen. De optimalisatie van range-joins in Databricks Runtime kan de prestaties van deze query's aanzienlijk verbeteren.

Hierdoor kan een join veel paren rijen vergelijken die niet kunnen overeenkomen. De optimalisatie van de range join splitst het bereik van waarden op in bins en vergelijkt alleen rijen die in overlappende bins vallen. Zie Bin size.

In Databricks SQL optimaliseert Azure Databricks automatisch bereik-joins zonder enige handmatige configuratie. U kunt range-joins ook handmatig afstemmen met join-hints of sessieconfiguratie voor alle rekentypen.

Intervalbereikdeelname

Een punt-in-intervalbereik-join is een join waarbij de voorwaarde predicaten bevat die aangeven dat een waarde van de ene relatie tussen twee waarden van de andere relatie valt. 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 de range join geldt voor joins die:

  • Gebruik een range-joinvoorwaarde met een punt in een interval of overlappende intervallen.
  • Gebruik alleen numerieke (geheel getal, floating-point of decimaal), DATE, of TIMESTAMP waarden in de bereikjoin-conditie.
  • Gebruik waarden van hetzelfde type in de range join-conditie. Decimale waarden moeten ook dezelfde schaal en precisie hebben.
  • Gebruik een ondersteund join-type:
    • INNER JOIN, voor elke range join
    • LEFT OUTER JOIN met de puntwaarde aan de linkerkant, of RIGHT OUTER JOIN met de puntwaarde aan de rechterkant, alleen voor point-in-intervalbereik-joins
  • Gebruik een bingrootte, automatisch afgeleid of handmatig gespecificeerd.

Joins met numerieke gelijkheids- en bereikvoorwaarden

Wanneer een joinvoorwaarde zowel een gelijkheidsvoorwaarde op een numerieke kolom als een bereikvoorwaarde bevat, kan de optimizer binning toepassen op de kolom voor numerieke gelijkheid, omdat deze voldoet aan de typevereisten voor bereikdeelnameoptimalisatie. Dit kan ertoe leiden dat de gelijkheidskolom aan bakken wordt toegewezen of van de optimalisatie wordt uitgesloten, waardoor de prestaties afnemen.

Om ervoor te zorgen dat de optimalisatie voor bereikjoins alleen van toepassing is op de beoogde bereikvoorwaarde, converteert u de kolommen in de numerieke gelijkheidsvoorwaarde naar STRING. Hiermee worden ze uitgesloten van overwegingen als kolommen met bereikvoorwaardes.

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;

Hetzelfde patroon geldt voor andere numerieke kolommen die als gelijkheidssleutels worden gebruikt, zoals DATE, integer-id's of geclusterde partitiekolommen.

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. Voor een waarde kleiner dan één seconde gebruik je een fractiewaarde. 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. In Databricks SQL wordt de bingrootte automatisch bepaald wanneer automatische optimalisatie van bereik-joins is ingeschakeld.

Optimalisatie van automatische bereikdeelname

In Databricks SQL detecteert Azure Databricks automatisch geschikte bereik-joins en bepaalt het de optimale bingrootte door een steekproef van de intervallentabel te nemen. Hierdoor hoeft u geen bin-grootte handmatig op te geven via hints of sessieconfiguratie.

Automatische optimalisatie van bereikdeelname is standaard ingeschakeld in Databricks SQL. Om het uit te schakelen, stel je deze configuratie in:

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

Als u een bin-grootte opgeeft via een range join-hint of sessieconfiguratie, heeft die waarde voorrang op de automatisch afgeleide bin-grootte.

Bereikdeelname inschakelen met behulp van een hint voor bereikdeelname

Als u de optimalisatie van bereikdeelname in een SQL-query wilt inschakelen, gebruikt u een hint voor bereikdeelname 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 is een tabel, een view of een subquery.

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, geeft u de grootte van de bin op 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. Een kleine bin-grootte wordt inefficiënt als waardeintervallen veel groter zijn dan de bin-grootte, waardoor intervallen veel bins overlappen. Bijvoorbeeld, met een conditie p BETWEEN start AND end waarbij start 1.000.000 is en end 1.999.999, en een bin-grootte van 10, overlapt het interval met 100.000 bins.

Als de intervallengte redelijk uniform en bekend is, stel dan de klassebreedte in op de typische intervallengte. Voor variërende, scheef verdeelde intervallen kies je een bin-grootte die korte intervallen efficiënt filtert terwijl lange intervallen niet te veel bins overlappen. Voor een tabel ranges met intervallen tussen kolommen start en end, bepaal percentielen van de scheef verdeelde intervallengte met deze query:

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;

Door elke kolom naar DOUBLE te casten voordat u ze van elkaar aftrekt, zorgt u ervoor dat de query werkt, ongeacht of de kolommen numerieke waarden, DATE-waarden of TIMESTAMP-waarden bevatten.

Stel de bingrootte in op de grootste van deze waarden:

  • Het 90e percentiel van de intervallengtes. Bij deze grootte beslaan maximaal 10% van de intervallen meer dan 2 klassen.
  • Het 99e percentiel gedeeld door 10. Bij deze grootte beslaan maximaal 1% van de intervallen meer dan 11 klassen.
  • Het 99,9e percentiel gedeeld door 100. Bij deze grootte beslaan maximaal 0,1% intervallen meer dan 101 bins.

Om nog langere intervallen te beperken, zet het patroon voort met de 99,99e en 99,999e percentielen. Gebruik het resultaat als uitgangspunt en stem vervolgens de bin-grootte af op je werklast.

  • Laatst bijgewerkt om