Otimização de junção de intervalo

Uma junção de intervalo ocorre quando duas relações são unidas usando um ponto no intervalo ou uma condição de sobreposição de intervalo. O suporte à otimização de junção de intervalo no Databricks Runtime pode trazer melhorias imensas no desempenho da consulta, mas exige um ajuste manual cuidadoso.

O Databricks recomenda usar dicas de junção para junções de intervalo quando o desempenho é ruim.

Junção de intervalo de ponto no intervalo

Uma Junção de intervalo de ponto no intervalo é uma junção em que a condição contém predicados que especificam que um valor de uma relação está entre dois valores da outra relação. Por exemplo:

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

Junção de intervalo de sobreposição de intervalo

Uma junção de intervalo de sobreposição de intervalo é uma junção em que a condição contém predicados que especificam uma sobreposição de intervalos entre dois valores de cada relação. Por exemplo:

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

Otimização de junção de intervalo

A otimização da junção de intervalo é executada para junções que:

• Têm uma condição que possa ser interpretada como uma junção de intervalo de ponto no intervalo ou de sobreposição de intervalo.
• Todos os valores envolvidos na condição de junção de intervalo são de um tipo numérico (integral, ponto flutuante, decimal), DATE ou TIMESTAMP.
• Todos os valores envolvidos na condição de junção de intervalo são do mesmo tipo. No caso do tipo decimal, os valores também precisam ser da mesma escala e precisão.
• É um INNER JOIN ou, no caso da junção de intervalo de ponto no intervalo, um LEFT OUTER JOIN com valor de ponto no lado esquerdo, ou RIGHT OUTER JOIN com valor de ponto no lado direito.
• Têm um parâmetro de ajuste do tamanho do compartimento.

Tamanho do compartimento

O tamanho do compartimento é um parâmetro de ajuste numérico que divide o domínio de valores da condição de intervalo em vários compartimentos de tamanho igual. Por exemplo, com um tamanho de compartimento de 10, a otimização divide o domínio em compartimentos com intervalos de comprimento de 10. Se você tiver uma condição de ponto no intervalo de p BETWEEN start AND end, start for 8 e end for 22, esse intervalo de valores se sobreporá a três compartimentos de comprimento 10: o primeiro compartimento de 0 a 10, o segundo compartimento de 10 a 20 e o terceiro compartimento de 20 a 30. Somente os pontos que ficam dentro dos mesmos três compartimentos precisam ser considerados como possíveis correspondências de junção para esse intervalo. Por exemplo, se p for 32, poderá ser descartado como estando entre start de 8 e end de 22, pois está no compartimento de 30 a 40.

Você pode especificar o tamanho do compartimento usando uma dica de junção de intervalo na consulta ou definindo um parâmetro de configuração de sessão. A otimização de junção de intervalo será aplicada somente se você especificar manualmente o tamanho do compartimento. A seção Escolher o tamanho do compartimento descreve como escolher um tamanho de compartimento ideal.

Habilitar junção de intervalo usando uma dica de junção de intervalo

Para habilitar a otimização de junção de intervalo em uma consulta SQL, você pode usar uma dica de junção de intervalo para especificar o tamanho do compartimento. A dica deve conter o nome da relação de uma das relações unidas e o parâmetro de tamanho do compartimento numérico. O nome da relação pode ser uma tabela, uma exibição ou uma subconsulta.

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

Você também pode posicionar uma dica de junção de intervalo em um dos DataFrames unidos. Nesse caso, a dica contém apenas o parâmetro de tamanho de compartimento numérico.

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

Habilitar junção de intervalo usando a configuração de sessão

Se você não quiser modificar a consulta, poderá especificar o tamanho do compartimento como um parâmetro de configuração.

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

Esse parâmetro de configuração se aplica a qualquer junção com uma condição de intervalo. No entanto, um tamanho de compartimento diferente definido por meio de uma dica de junção de intervalo sempre substitui aquele definido por meio do parâmetro.

Escolher o tamanho do compartimento

A eficácia da otimização de junção de intervalo depende da escolha do tamanho de compartimento apropriado.

Um pequeno tamanho de compartimento resulta em um número maior de compartimentos, o que ajuda a filtrar as possíveis correspondências. No entanto, ele se torna ineficiente se o tamanho do compartimento for significativamente menor do que os intervalos de valores encontrados, e os intervalos de valores se sobrepõem a vários intervalos de compartimentos. Por exemplo, com uma condição p BETWEEN start AND end, em que start é 1 milhão e end é 1.999.999, e um tamanho de compartimento de 10, o intervalo de valor se sobrepõe a 100.000 compartimentos.

Se o comprimento do intervalo for razoavelmente uniforme e conhecido, recomendamos que você defina o tamanho do compartimento como o tamanho típico esperado do intervalo de valor. No entanto, se o comprimento do intervalo for variado e distorcido, será necessário encontrar um equilíbrio para definir um tamanho de compartimento que filtre os intervalos curtos com eficiência, ao mesmo tempo que impede que os intervalos longos se sobreponham a muitos compartimentos. Supondo uma tabela ranges, com intervalos entre as colunas start e end, você pode determinar percentuais diferentes do valor de comprimento do intervalo distorcido com a seguinte consulta:

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

Uma configuração recomendada de tamanho de compartimento seria o máximo do valor no 90º percentil, ou o valor no 99º percentil dividido por 10, ou o valor no 99,9 percentil dividido por 100 e assim por diante. A lógica é:

• Se o valor no 90º percentil for o tamanho do compartimento, somente 10% dos comprimentos de intervalo de valor serão maiores do que o intervalo de compartimento, portanto, inclua mais de dois intervalos de compartimento adjacentes.
• Se o valor no 99º percentil for o tamanho do compartimento, somente 1% dos comprimentos de intervalo de valor ocuparão mais de 11 intervalos de compartimento adjacentes.
• Se o valor no 99,9º percentil for o tamanho do compartimento, somente 0.1% dos comprimentos de intervalo de valor ocuparão mais de 101 intervalos de compartimento adjacentes.
• O mesmo pode ser repetido para os valores em 99,99º, 99,999° percentil e assim por diante, se necessário.

O método descrito limita a quantidade de intervalos de valores longos distorcidos que se sobrepõem a vários intervalos de compartimentos. O valor de tamanho de compartimento obtido dessa maneira é apenas um ponto de partida para o ajuste fino; os resultados reais podem depender da carga de trabalho específica.