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

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

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

В 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 значения в условии соединения диапазона.
  • Используйте значения того же типа в условии range join. Десятичные значения также должны иметь одинаковый масштаб и точность.
  • Используйте поддерживаемый тип соединения:
    • INNER JOIN, для любого range 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-й перцентиль длины интервалов. При таком размере не более 10% интервалов охватывают более двух бинов.
  • 99-й процентиль, делённый на 10. При таком размере максимум 1% интервалов охватывают более 11 бинов.
  • 99,9-й процентиль, разделённый на 100. При таком размере не более 0,1% интервалов охватывают более 101 бин.

Чтобы ограничить ещё более длинные интервалы, продолжайте этот шаблон с 99,99-м и 99,999-м процентилями. Используйте результат как отправную точку, а затем настройте размер бина под свою нагрузку.

  • Последнее обновление: