database - 为什么 Indexed Nested-Loop Join 仅适用于 equi-join 或 natural join？

Question

索引嵌套循环连接:

对于外层关系R中的每个元组tr，使用索引在S中查找满足与元组tr的连接条件的元组

一些资料提到“Indexed Nested-Loop Join”只适用于equi-join或natural join，并且索引在内部关系的join属性上可用

SELECT *
FROM tableA as a
JOIN tableB as b
ON a.col1 > b.col1;

假设我们在 b.col1 上有一个索引。

为什么 Indexed Nested-Loop Join 不适用于这种情况？

Answer 1

您正在引用数据库系统概念 (c) Silberschatz、Korth 和 Sudarshan 的幻灯片。

我们希望 DBMS 计算连接。有很多特殊情况，它可以用不同的方式来做。这些可能涉及是否有索引、选择条件等。

该书所称的特定技术在某些情况下有效:

Indexed Nested-Loop Join

If an index is available on the inner loop's join attribute and join is an equi-join or natural join

答案是，因为你的查询不符合条件。它不是等值连接(即 ON 或 WHERE a.col1 = b.col1)或自然连接(USING (col1) 或 NATURAL JOIN)。

至于为什么不满足这些条件意味着不使用该技术，那是因为它不起作用和/或其他一些技术更好。你给出了技术:

For each tuple tr in the outer relation r, use the index to look up tuples in s that satisfy the join condition with tuple tr

如果是不等式，你不能在索引中“查找”；您有搜索 索引。不是这个方法。