Оптимизация соединения по диапазону

Диапазонное соединение происходит, когда два отношения соединяются, используя точку в интервале или условие перекрывания интервалов. Поддержка оптимизации объединения по диапазонам в Databricks Runtime может привести к повышению производительности при обработке запросов, но потребует тщательной настройки вручную.

Databricks рекомендует использовать подсказки соединения для соединений диапазона при низкой производительности.

Соединение по диапазону с использованием точки в интервале

Объединение по точке в диапазоне интервала — это объединение, при котором условие содержит предикаты, указывающие, что значение из одного отношения расположено между двумя значениями из другого отношения. Например:

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

Объединение по пересечению диапазонов интервала

Объединение по диапазонам при перекрывании интервала — это объединение, при котором условие содержит предикаты, указывающие перекрывание интервалов между двумя значениями из каждого отношения. Например:

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

Оптимизация соединения по диапазону

Оптимизация диапазонного объединения выполняется для объединений, которые:

• Имеют условие, которое может быть интерпретировано как соединение по диапазону в результате наличия точки внутри интервала или диапазона с перекрытием интервалов.
• Все значения, участвующие в условии объединения по диапазонам, имеют числовой тип (целочисленный, с плавающей запятой, десятичный), DATE или TIMESTAMP.
• Все значения, участвующие в условии объединения по диапазонам, имеют один и тот же тип. При десятичном типе значения также должны иметь одинаковый масштаб и точность.
• Это — INNER JOIN, или, в случае объединения точек в диапазоне, LEFT OUTER JOIN со значением точки слева или RIGHT OUTER JOIN со значением точки справа.
• Имеет параметр настройки размера корзины.

Размер корзины

Размер ячейки — это числовой параметр настройки, который разделяет домен значений условия диапазона на несколько ячеек равного размера. Например, если размер ячейки 10, оптимизация разделяет домен на ячейки, которые имеют интервалы длиной 10. Если у вас есть точка в условии диапазона p BETWEEN start AND end, значение start равно 8, а значение end равно 22, этот интервал перекрывается с тремя ячейками длиной 10 – первая ячейка имеет размер от 0 до 10, вторая — от 10 до 20 и третья — от 20 до 30. Только точки, попадающие в те же три ячейки, должны рассматриваться как возможные совпадения при соединении в этом интервале. Например, если p равно 32, то его можно исключить из диапазона между start значением 8 и end значением 22, так как оно попадает в интервал от 30 до 40.

Примечание.

• Для значений DATE значение размера ячейки интерпретируется как количество дней. Например, значение размера ячейки, равное 7, представляет неделю.
• Для значений TIMESTAMP значение размера ячейки интерпретируется как количество секунд. Если требуется значение в долях секунды, можно использовать дробные значения. Например, значение размера ячейки 60 представляет минуту, а значение размера ячейки 0,1 — 100 миллисекунд.

Размер ячейки можно указать либо с помощью указания по объединению по диапазонам в запросе, либо путем настройки параметра конфигурации сеанса. Оптимизация объединения по диапазонам применяется только в том случае, если вы вручную укажете размер ячейки. Раздел Выбор размера ячейки описывает, как выбрать оптимальный размер ячейки.

Включение объединения по диапазонам с помощью указания по объединению по диапазонам

Чтобы включить оптимизацию объединения по диапазонам в SQL-запросе, можно использовать указание по объединению по диапазонам, чтобы указать размер ячейки. Указание должно содержать имя отношения одного из объединяемых отношений и числовой параметр размера ячейки. Имя отношения может быть таблицей, представлением или вложенным запросом.

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)

Примечание.

В третьем примере необходимо поместить указание в c. Это связано с тем, что операции объединения остаются ассоциативными, поэтому запрос интерпретируется как (a JOIN b) JOIN c, а указание a применяется к объединению a с b, а не к объединению с 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()
)

Также можно разместить указание объединения по диапазонам в одном из объединяемых кадров данных. В этом случае указание содержит только числовой параметр размера ячейки.

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

Активировать диапазонное объединение через настройку сеанса

Если вы не хотите изменять запрос, можно указать размер корзины в качестве параметра конфигурации.

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

Этот параметр конфигурации применяется к любому объединению с условием диапазона. Однако другой размер корзины, заданный с помощью подсказки для объединения по диапазону, всегда переопределяет тот, который задан параметром.

Выберите размер корзины

Эффективность оптимизации объединения по диапазонам зависит от выбора подходящего размера ячейки.

Небольшой размер ячейки приводит к увеличению количества ячеек, что помогает более эффективно фильтровать возможные совпадения. Однако это становится неэффективным, если размер контейнера значительно меньше интервалов значений и если интервалы значений перекрывают несколько интервалов контейнеров. Например, при условииp BETWEEN start AND end, где значение start равно 1 000 000, значение end равно 1 999 999, а размер ячейки равен 10, интервал значений перекрывается с ячейками 100 000.

Если длина интервала является однородной и известной, рекомендуется задать для ячейки размер, равный стандартной ожидаемой длине интервала значений. Тем не менее, если длина интервала изменяется и отклоняется, необходимо найти баланс, чтобы задать размер ячейки, который эффективно фильтрует короткие интервалы, не позволяя длинному интервалу перекрывать слишком много ячеек. Предполагая, что таблица ranges с интервалами в диапазоне между столбцами start и end, вы можете определить разные процентили для значения длины интервала с отклонением, используя следующий запрос:

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

Рекомендуемой настройкой размера ячейки является максимальное значение на 90-м или на 99-м процентиле, поделенное на 10, или значение на 99,9 процентиле, поделенное на 100 и т. д. Вывод следующий:

• Если значение на 90-м процентиле равно размеру ячейки, то только 10% значений длины интервала между значениями будут длиннее, чем интервал ячеек, поэтому они охватывают более двух смежных интервалов ячеек.
• Если значение на 99-м процентиле равно размеру ячейки, только 1% значений длины интервала значений будут охватывать более 11 смежных интервалов ячеек.
• Если значение на 99,9-м процентиле равно размеру корзины, только 0,1% длин интервалов будут охватывать более 101 смежных интервалов корзин.
• ту же процедуру при необходимости можно повторить для значений на 99,99-м, 99,999-м процентиле и т. д.

Описанный метод ограничивает количество длинных интервалов значений с отклонениями, которые перекрывают несколько интервалов ячеек. Значение размера ячейки, полученное таким способом, является отправной точкой для тонкой настройки; фактические результаты могут зависеть от конкретной рабочей нагрузки.