Otimização de junção de intervalo

Uma joinde intervalo ocorre quando duas relações são joinusando um ponto no intervalo ou condição de sobreposição de intervalo. O suporte à otimização de join de intervalo no Databricks Runtime pode trazer melhorias de ordens de magnitude no desempenho query , mas requer um ajuste manual cuidadoso.

Ponto na junção de intervalo de intervalo

Um ponto na joinde intervalo de intervalo é uma join na qual 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 faixa de sobreposição de intervalo

Uma joinintervalo de sobreposição de intervalo é uma join na qual 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 join de intervalo é realizada para join que:

  • Tem uma condição que pode ser interpretada como um ponto no intervalo ou join de intervalo de sobreposição de intervalo.

  • Todos os valores envolvidos na condição join de intervalo são de tipo numérico (integral, ponto flutuante, decimal), DATE ou TIMESTAMP.

  • Todos os valores envolvidos na condição join de intervalo são do mesmo tipo. No caso do tipo decimal, os valores também precisam ter a mesma escala e precisão.

  • É um INNER JOIN, ou no caso de ponto na join de intervalo de intervalo, um LEFT OUTER JOIN com valor de ponto no lado esquerdo ou RIGHT OUTER JOIN com valor de ponto no lado direito.

  • Tenha um parâmetro de ajuste do tamanho do compartimento.

tamanho da caixa

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 que são intervalos de comprimento 10. Se você tiver um ponto na condição de intervalo de p BETWEEN start AND end, e start for 8 e end for 22, esse intervalo de valor se sobrepõe a três compartimentos de comprimento 10 – o primeiro compartimento de 0 a 10, o segundo compartimento de 10 a 20, e a terceira caixa de 20 a 30. Apenas os pontos que se enquadram nas mesmas três caixas precisam ser considerados como possíveis correspondências join para esse intervalo. Por exemplo, se p for 32, pode ser descartado como estando entre start de 8 e end de 22, porque cai na caixa de 30 a 40.

Observação

  • Para valores DATE , o valor do tamanho do compartimento é interpretado como dias. Por exemplo, um valor de tamanho de compartimento de 7 representa uma semana.

  • Para valores TIMESTAMP , o valor do tamanho do compartimento é interpretado como segundos. Se for necessário um valor de subsegundos, podem ser usados valores fracionários. Por exemplo, um valor de tamanho de compartimento de 60 representa um minuto e um valor de tamanho de compartimento de 0,1 representa 100 milissegundos.

Você pode especificar o tamanho do compartimento usando uma dica join intervalo na query ou definindo um parâmetro de configuração de sessão. A otimização join de intervalo é aplicada somente se você especificar manualmente o tamanho da caixa. 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 join intervalo em uma query SQL, você pode usar uma dica join 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 numérico de tamanho da caixa. O nome da relação pode ser uma tabela, uma view 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)

Observação

No terceiro exemplo, você deve colocar a dica em c. Isso ocorre porque join são associativas à esquerda, portanto, a query é interpretada como (a JOIN b) JOIN c e a dica em a se aplica à join de a com b e não à join com 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()
)

Você também pode colocar uma dica join de intervalo em um dos DataFrames ed join . Nesse caso, a dica contém apenas o parâmetro numérico de tamanho da caixa.

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 configuração de sessão

Se você não deseja modificar a query, pode especificar o tamanho do bin como um parâmetro de configuração.

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

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

Escolha o tamanho da caixa

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

Um tamanho de compartimento pequeno resulta em um número maior de compartimentos, o que ajuda na filtragem de possíveis correspondências. No entanto, torna-se ineficiente se o tamanho da caixa for significativamente menor do que os intervalos de valor encontrados e os intervalos de valor se sobrepõem a vários intervalos de caixa . Por exemplo, com uma condição p BETWEEN start AND end, em que start é 1.000.000 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 bastante uniforme e conhecido, recomendamos que você defina o tamanho da caixa para o comprimento típico esperado do intervalo de valores. No entanto, se o comprimento do intervalo estiver variando e distorcido, um equilíbrio deve ser encontrado para definir um tamanho de compartimento que filtre os intervalos curtos com eficiência, evitando que os intervalos longos se sobreponham a muitos compartimentos. Assumindo uma tabela ranges, com intervalos que estão entre as colunas start e end, você pode determinar diferentes percentis do valor de comprimento de intervalo distorcido com a seguinte query:

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 do tamanho da caixa 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 justificativa é:

  • Se o valor no 90º percentil for o tamanho do bin, apenas 10% dos comprimentos do intervalo de valor são maiores do que o intervalo do bin, portanto abrangem mais de 2 intervalos de bin adjacentes.

  • Se o valor no 99º percentil for o tamanho do bin, apenas 1% dos comprimentos do intervalo de valor abrangem mais de 11 intervalos de bin adjacentes.

  • Se o valor no percentil 99,9 for o tamanho do bin, apenas 0,1% dos comprimentos do intervalo de valor abrangem mais de 101 intervalos de bin adjacentes.

  • O mesmo pode ser repetido para os valores no percentil 99,99, 99,999 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 categorias. O valor do tamanho do compartimento obtido dessa maneira é apenas um ponto de partida para o ajuste fino; os resultados reais podem depender da carga de trabalho específica.