Otimização de associações de intervalos

Uma junção por intervalo ocorre quando duas relações são associadas com base numa condição de ponto-no-intervalo ou de sobreposição de intervalos. A utilização da otimização de range-join no Databricks Runtime pode melhorar significativamente o desempenho das consultas.

No Databricks SQL, o Azure Databricks otimiza automaticamente as uniões de intervalo sem qualquer configuração manual. Também pode ajustar manualmente as junções de intervalo utilizando sugestões de junção ou a configuração da sessão para todos os tipos de computação.

Ponto na junção de intervalo

Um ponto na junção de intervalos é um join cuja condição contém predicados que especificam que um valor de uma relação fica 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 intervalos sobrepostos

Uma junção de sobreposição de intervalos é uma junção 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 associações de intervalos

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

• Ter uma condição que possa ser interpretada como um ponto numa junção de intervalo ou numa sobreposição de intervalos.
• Todos os valores envolvidos na condição de junção de intervalo são de um tipo numérico (integral, ponto flutuante, decimal), DATEou TIMESTAMP.
• Todos os valores que participam na condição de junção de intervalo são do mesmo tipo. No caso do tipo decimal, os valores também devem ser da mesma escala e precisão.
• É um INNER JOIN, ou no caso de junção de intervalos, um LEFT OUTER JOIN com valor de ponto à esquerda, ou RIGHT OUTER JOIN com valor de ponto à direita.
• Ter um tamanho da caixa, seja derivado automaticamente ou especificado manualmente.

Junções com condições de igualdade numérica e de intervalo

Quando uma condição de junção inclui tanto uma condição de igualdade numa coluna numérica como uma condição de intervalo, o otimizador pode aplicar binning à coluna de igualdade numérica porque esta cumpre os requisitos de tipo para otimização de junção de intervalo. Isto pode fazer com que a coluna de igualdade seja atribuída a bins ou excluída da otimização, reduzindo o desempenho.

Para garantir que a otimização da junção de intervalo se aplica apenas à condição de intervalo pretendida, conjure as colunas de igualdade numérica para STRING. Isto exclui-as da consideração como colunas de condição de alcance.

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;

O mesmo padrão aplica-se a outras colunas numéricas usadas como chaves de igualdade, como DATEidentificadores de inteiros ou colunas de partição agrupadas.

Tamanho do intervalo

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 tiver uma condição de ponto no intervalo de p BETWEEN start AND end, e start for 8 e end for 22, esse intervalo de valores sobrepõe-se a três binários de comprimento 10 – o primeiro binário de 0 a 10, o segundo de 10 a 20, e o terceiro de 20 a 30. Apenas os pontos que se enquadram nos mesmos três compartimentos precisam ser considerados como possíveis partidas de junção para esse intervalo. Por exemplo, se p for 32, pode ser descartado como estando no intervalo entre start de 8 e end de 22, porque está no intervalo de 30 a 40.

Pode especificar o tamanho do bin usando uma dica de junta de intervalo na consulta ou definindo um parâmetro de configuração de sessão. No Databricks SQL, o tamanho do bin é automaticamente obtido quando a otimização automática da junção por intervalo está ativada.

Otimização automática da junção de alcances

No Databricks SQL, o Azure Databricks deteta automaticamente as uniões de intervalo qualificadas e deriva o tamanho ótimo do bin amostrando a tabela de intervalos. Isto elimina a necessidade de especificar manualmente o tamanho do bin através de dicas ou configuração da sessão.

A otimização automática de range join está ativada por defeito no Databricks SQL. Para o desativar, defina a seguinte configuração:

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

Se especificar o tamanho do bin através de uma sugestão de junção por intervalo ou da configuração da sessão, esse valor substitui o tamanho do bin derivado automaticamente.

Ativar junção de intervalo usando uma sugestão de junção de intervalo

Para ativar a otimização da junção por intervalo numa consulta SQL, use uma sugestão de junção por intervalo para especificar o tamanho do intervalo. A dica deve conter o nome da relação de uma das relações unidas e o parâmetro numérico bin size. O nome da relação pode ser uma tabela, um modo de 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 colocar uma dica de junção por intervalo em um dos DataFrames associados. Nesse caso, a dica contém apenas o parâmetro numérico do tamanho do compartimento.

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 a junção de intervalos usando a configuração da sessão

Se não quiseres modificar a consulta, especifica o tamanho do bin como um parâmetro de configuração.

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

Este parâmetro de configuração aplica-se a qualquer junção com uma condição de intervalo. No entanto, um tamanho de compartimento diferente configurado através de uma indicação de junção de intervalo sempre sobrepõe-se ao configurado através do parâmetro.

Escolha o tamanho da caixa

A eficácia da otimização da junção de gama depende da escolha do tamanho adequado do caixote.

Um tamanho pequeno do compartimento resulta em um número maior de compartimentos, o que ajuda a filtrar as possíveis correspondências. No entanto, torna-se ineficiente se o tamanho do compartimento for significativamente menor do que os intervalos de valores encontrados, e os intervalos de valor se sobrepuserem a vários intervalos de compartimento. Por exemplo, com uma condição p BETWEEN start AND end, onde 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 do compartimento para o comprimento esperado típico do intervalo de valores. No entanto, se o comprimento do intervalo é variável e enviesado, uma balança deve ser encontrada para definir um tamanho de compartimento que filtre os intervalos curtos de forma eficiente, evitando que os intervalos longos se sobreponham a muitos compartimentos. Supondo uma tabela ranges, com intervalos entre colunas start e end, você pode determinar percentis diferentes do valor de comprimento de intervalo distorcido com a seguinte consulta:

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;

Converter cada coluna em DOUBLE antes de subtrair garante que a consulta funcione, independentemente de as colunas serem valores numéricos, DATE ou TIMESTAMP.

Uma definiçã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, etc. A justificação é:

• Se o valor no percentil 90 for o tamanho do compartimento, apenas 10% dos comprimentos do intervalo de valor são maiores do que o intervalo do compartimento, portanto, abrangem mais de 2 intervalos de compartimento adjacentes.
• Se o valor no percentil 99 for o tamanho do compartimento, apenas 1% dos comprimentos do intervalo de valores abrangem mais de 11 intervalos adjacentes do compartimento.
• Se o valor no percentil 99,9 for o tamanho do compartimento, apenas 0,1% dos comprimentos do intervalo de valores abrangem mais de 101 intervalos de compartimento adjacentes.
• O mesmo pode ser repetido para os valores no 99,99º percentil, no 99,999º percentil, etc., se necessário.

O método descrito limita a quantidade de intervalos enviesados de valores longos que se sobrepõem a vários intervalos binários. O valor do tamanho da caixa obtido desta forma é apenas um ponto de partida para o ajuste fino; Os resultados reais podem depender da carga de trabalho específica.