Поделиться через

Оптимизация объединения по диапазонам

  • Статья

Объединение по диапазонам происходит, когда два отношения объединяются с помощью точки в интервале или условия перекрывания интервалов. Поддержка оптимизации объединения по диапазонам в 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-м процентиле и т. д.

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