mysql - 在 SQL 中有效地加入间隔范围

Question

假设我有如下两个表(数据取自 SO post ):

表d1:

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

表d2:

 x pos
 a   2
 a   3
 b   3
 b  12
 c  20
 d  52
 e  10

两个表中的第一行都是列标题。我想提取 d2 中的所有行，其中列 x 与 d1 匹配并且 pos1 落在 (包括边界值)d1 的start 和end 列。也就是说，我想要这样的结果:

 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

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

是否有任何其他有效的查询优化(例如:使用 interval trees )或其他可以有效处理 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) 上尝试一个独特的...)