Otimização de junção de intervalo

Uma junção por intervalo ocorre quando duas relações são unidas usando uma condição de ponto em intervalo ou de sobreposição de intervalos. O uso da otimização de junção de intervalo no Databricks Runtime pode melhorar significativamente o desempenho da consulta.

No Databricks SQL, Azure Databricks otimiza automaticamente as junções de intervalo sem nenhuma configuração manual. Você também pode ajustar manualmente as junções de intervalo usando dicas de junção ou configuração de sessão para todos os tipos de computação.

Junção de ponto em intervalo de intervalo

Uma junção de intervalo de ponto é uma junção cuja condição contém predicados que especificam que um valor de uma relação se encontra 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 por sobreposição de intervalos

Uma junção por sobreposição de intervalo é uma junção em que a condição contém predicados que definem 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:

• Possuem uma condição que pode ser interpretada como uma junção de intervalos de ponto ou 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), DATE ou TIMESTAMP.
• Todos os valores envolvidos na condição de junção por 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 uma junção de intervalo de pontos, um LEFT OUTER JOIN com valor de ponto à esquerda, ou RIGHT OUTER JOIN com valor de ponto à direita.
• Tenha um tamanho de compartimento, derivado automaticamente ou especificado manualmente.

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

Quando uma condição de junção inclui tanto uma condição de igualdade em uma coluna numérica quanto uma condição de intervalo, o otimizador pode aplicar agrupamento em faixas à coluna numérica da condição de igualdade, porque ela atende aos requisitos de tipo necessários para a otimização de junções por intervalo. Isso pode fazer com que a coluna de igualdade seja atribuída a compartimentos ou excluída da otimização, reduzindo o desempenho.

Para garantir que a otimização de junção de intervalo se aplique apenas à condição de intervalo pretendida, converta as colunas de igualdade numérica em STRING. Isso impede que sejam consideradas como colunas de condição de intervalo.

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 se aplica a outras colunas numéricas usadas como chaves de igualdade, como DATE, identificadores inteiros ou colunas de partição em cluster.

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 bin usando um hint de junção por intervalo na consulta ou definindo um parâmetro de configuração da sessão. No Databricks SQL, o tamanho do intervalo é determinado automaticamente quando a otimização automática de junção por intervalo está habilitada.

Otimização automática de junção por intervalo

No Databricks SQL, o Azure Databricks detecta automaticamente as junções por intervalo qualificadas e determina o tamanho ideal do compartimento por meio da amostragem da tabela de intervalos. Isso remove a necessidade de especificar manualmente um tamanho de compartimento por meio de dicas ou configuração de sessão.

A otimização automática de junção por intervalo é ativada por padrão no Databricks SQL. Para desabilitá-lo, defina a seguinte configuração:

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

Se você especificar um tamanho de bin por meio de uma dica de junção por intervalo ou por uma configuração de sessão, esse valor substitui o tamanho de bin determinado automaticamente.

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

Para habilitar a otimização de junção por intervalo em uma consulta SQL, use uma hint de junção por intervalo para especificar o tamanho do intervalo. A indicação deve conter o nome da relação de uma das relações unidas e o parâmetro numérico do tamanho do compartimento. O nome da relação pode ser uma tabela, uma visualizaçã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 adicionar uma dica de junção de intervalo em um dos DataFrames que foram unidos. Nesse caso, a dica contém apenas o parâmetro numérico de tamanho de 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 junção de faixa usando a configuração da sessão

Se você não quiser modificar a consulta, especifique o tamanho da lixeira 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 da lixeira

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

A conversão de cada coluna para DOUBLE antes da subtração garante que a consulta funcione, quer as colunas contenham valores numéricos, DATE ou TIMESTAMP.

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 percentil 99,9 dividido por 100, etc. 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, apenas 1% dos comprimentos dos intervalos de valor abrangerão mais de 11 compartimentos adjacentes.
• Se o valor no percentil de 99.9 for o tamanho do compartimento, somente 0,1% dos comprimentos de intervalos de valores abrangerão mais de 101 intervalos de compartimentos adjacentes.
• O mesmo pode ser repetido para os valores nos percentis 99,99 e 99,999, etc., 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 do tamanho da lixeira obtido dessa forma é apenas um ponto de partida para ajuste fino; os resultados reais podem depender da carga de trabalho específica.