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

Диапазонное соединение возникает, когда два отношения соединяются с использованием условия «точка в интервале» или условия перекрытия интервалов. Использование оптимизации соединения диапазона в Databricks Runtime может значительно повысить производительность запросов.

В Databricks SQL Azure 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 со значением точки справа.
  • Имеет размер ячейки, автоматически производный или вручную указанный.

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

Если условие соединения включает как условие равенства для числового столбца, так и условия диапазона, оптимизатор может применить бинирование к числовой столбцу равенства, так как он соответствует требованиям типа для оптимизации соединения диапазона. Это может привести к тому, что столбец равенства будет отнесён к группам или исключён из оптимизации, что снизит производительность.

Чтобы оптимизация соединения по диапазону применялась только к нужному условию диапазона, приведите числовые столбцы, участвующие в условии равенства, к STRING. Это не позволяет рассматривать их как колонки с условиями диапазона.

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;

Тот же шаблон применяется к другим числовым столбцам, используемым в качестве ключей равенства, например DATE, целых идентификаторов или кластеризованных столбцов секций.

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

Размер ячейки — это числовой параметр настройки, который разделяет домен значений условия диапазона на несколько ячеек равного размера. Например, если размер ячейки 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 миллисекунд.

Размер бина можно указать с помощью подсказки range join в запросе или путем задания параметра конфигурации сеанса. В Databricks SQL размер бина определяется автоматически, когда включена автоматическая оптимизация соединения по диапазону.

Автоматическая оптимизация соединения по диапазону

В Databricks SQL Azure Databricks автоматически обнаруживает подходящие соединения по диапазону и определяет оптимальный размер ячейки на основе выборки из таблицы интервалов. Это устраняет необходимость вручную указывать размер бина с помощью подсказок или конфигурации сеанса.

В Databricks SQL по умолчанию включена автоматическая оптимизация соединения по диапазону. Чтобы отключить его, задайте следующую конфигурацию:

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

Если задать размер ячейки с помощью указания соединения диапазона или конфигурации сеанса, это значение переопределяет автоматически производный размер ячейки.

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

Чтобы включить оптимизацию соединения диапазона в 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
  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;

Перед вычитанием приведение каждого столбца к типу DOUBLE гарантирует, что запрос будет работать независимо от того, содержат ли столбцы числовые значения, значения DATE или TIMESTAMP.

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

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

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

  • Last updated on