在 SQL 中有效地连接间隔范围

Question

假设我有两个表如下（数据取自这篇SO post）：

桌子d1：

 x start end
 a     1   3
 b     5  11
 c    19  22
 d    30  39
 e     7  25

桌子d2：

两个表中的第一行都是列标题。我想提取d2列x与d1和列匹配pos1并落在其中（包括边界值）d1的所有行。也就是说，我想要的结果是：startend

 x pos start  end
 a   2     1    3
 a   3     1    3
 c  20    19   22
 e  10     7   25

到目前为止我看到的这样做的方式是：

SELECT * FROM d1 JOIN d2 USING (x) WHERE pos BETWEEN start AND end

但我不清楚的是，这个操作是否尽可能高效地完成（即内部优化）。例如，恕我直言，首先计算整个连接并不是真正的可扩展方法（就速度和内存而言）。

是否有任何其他有效的查询优化（例如：使用区间树）或其他可以在 SQL 中有效处理范围（同样，在速度和内存方面）的算法可供我使用？如果使用 SQLite、PostgreSQL、mySQL 等都没关系。

在 SQL 中执行此操作最有效的方法是什么？

非常感谢。

Answer 1

不确定这一切在内部是如何运作的，但根据具体情况，我建议使用一张表来“推出” d1 中的所有值，然后加入该值。这样，查询引擎可以“准确”地查明正确的记录，而不必查找与正在查找的值相匹配的边界组合。

例如

x value
a  1
a  2
a  3
b  5
b  6
b  7
b  8
b  9
b 10
b 11
c 19 etc..

给定值列 (**) 上的索引，这应该比连接原始 d1 表上的 BETWEEN start AND end 快得多。

当然，每次对 d1 进行更改时，您也需要调整推出的表（触发器？）。如果这种情况经常发生，您将花费比最初获得的时间更多的时间来更新已推出的表！此外，如果某些间隔非常大，这可能会很快占用相当多的（磁盘）空间；而且，这假设我们不需要寻找非整数（例如，如果我们寻找值 3.14 该怎么办？）

（您可以考虑在这里尝试在 (value, x) 上尝试一种独特的方法...）