范围联接优化

当两个关系基于点落在区间内或区间重叠条件进行联接时，就会发生 范围联接。 在 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的区间内。

可以通过在查询中使用范围联接提示或设置会话配置参数来指定箱大小。 在 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)

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

使用会话配置启用范围连接

如果不想修改查询，请将 bin 大小指定为配置参数。

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 个百分位数等的值。

上述方法限制了与多个箱间隔重叠的扭曲长值间隔的数量。 以这种方式获取的箱大小值只是微调的起点;实际结果可能取决于特定的工作负荷。