Otimização de junção de intervalo

Uma junção de intervalo une duas tabelas em uma condição que verifica se um valor está dentro de um intervalo, ou se dois intervalos se sobrepõem, em vez de verificar se dois valores são iguais. Por exemplo, uma consulta que corresponde cada evento do site à sessão do usuário em que ocorreu verifica se o carimbo de tempo do evento está entre o início e o fim da sessão. Uma consulta que encontre reuniões agendadas ao mesmo tempo verifica se dois intervalos de tempo se sobrepõem. A otimização de joins de intervalo no Databricks Runtime pode melhorar muito o desempenho dessas consultas.

Por causa disso, uma junção pode comparar vários pares de linhas que não podem corresponder. A otimização de junção de intervalo divide a faixa de valores em bins e compara apenas linhas que caem em bins sobrepostos. Veja Tamanho do bin.

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 intervalo de ponto no intervalo

Um ponto na junção de intervalo é uma junção em que a 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 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 de união por intervalo se aplica a junções que:

• Ter um ponto no intervalo ou uma condição de junção por sobreposição de intervalos.
• Use apenas números (integrais, de ponto flutuante ou decimais), os valores DATE ou TIMESTAMP, na condição de junção de intervalo.
• Use valores do mesmo tipo na condição de junção de intervalo. Valores decimais também devem ter a mesma escala e precisão.
• Use um tipo de junção compatível:
  • INNER JOIN, para qualquer junção de intervalo
  • LEFT OUTER JOIN com o valor de pontos no lado esquerdo, ou RIGHT OUTER JOIN com o valor de pontos no lado direito, apenas para junções de intervalo de ponto em intervalo
• Defina um tamanho de compartimento, seja 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.

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. Para um valor inferior a um segundo, use um valor fracionário. 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 de junção de intervalo na consulta ou definindo um parâmetro de configuração de sessão. No Databricks SQL, o tamanho do compartimento é 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 desativá-lo, configure esta configuração:

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

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

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

Observação

No terceiro exemplo, você deve inserir a dica em c. Isso ocorre porque as junções são associativas, portanto, a consulta é interpretada como (a JOIN b) JOIN c, e a dica em a se aplica à junção de a com b, e não à junção 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 posicionar uma dica de junção de intervalo em um dos DataFrames 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. Um tamanho pequeno de bin se torna ineficiente se intervalos de valor forem muito maiores que o tamanho do bin, fazendo com que intervalos se sobreponham a muitos bins. 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 bin de 10, o intervalo se sobrepõe a 100.000 bins.

Se o comprimento do intervalo for relativamente uniforme e conhecido, ajuste o tamanho do bin para o comprimento típico do intervalo. Para intervalos variados e assimétricos, escolha um tamanho de bin que filtre intervalos curtos de forma eficiente enquanto evita que intervalos longos se sobreponham a bins demais. Para uma tabela ranges com intervalos entre colunas start e end, determine percentis do comprimento do intervalo assimétrico com esta 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.

Defina o tamanho do bin como o maior destes valores:

• O percentil 90 dos comprimentos de intervalo. Com esse tamanho, no máximo 10% dos intervalos abrangem mais de 2 bins.
• O percentil 99 dividido por 10. Nesse tamanho, no máximo 1% de intervalos abrangem mais de 11 bins.
• O percentil de 99,9 dividido por 100. Nesse tamanho, no máximo 0,1% de intervalos abrangem mais de 101 bins.

Para limitar intervalos ainda mais longos, continue o padrão com os percentis 99,99º e 99,999º. Use o resultado como ponto de partida e ajuste o tamanho do compartimento para a sua carga de trabalho.