Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SQL Anywhere 11.0.1 (中文) » SQL Anywhere 服务器 - SQL 的用法 » 查询处理 » 查询优化与执行 » [查询执行] 算法 » 算法类型

 

连接算法

SQL Anywhere 提供了多种不同的连接实现方法供查询优化程序进行选择。每个连接算法都有其具体特征,因此对于给定的查询和给定的执行环境而言,都会存在有的算法会比较适用而有的算法则不太适用的情况。

访问计划中连接的顺序与初始 SQL 语句中连接的顺序可能相符也可能不符;查询优化程序将负责以最低执行开销为前提为每个查询选择最佳连接策略。某些情况下,可能会为一些复杂语句使用查询重写优化,以增加或减少任何特定语句的计算连接数量。

以下是 SQL Anywhere 支持的三种连接算法,不过每种算法都具有其它变体:

  • 嵌套循环连接   最直接的算法为嵌套循环连接。对于左侧的每一行,都会基于连接条件对右侧进行扫描以查找匹配项。通常会通过索引来访问右侧的各行,以减少总执行开销。这种情况常常称为索引嵌套循环连接

    嵌套循环连接具有支持 LEFT OUTER 和 FULL OUTER 连接的变体。还可以将嵌套循环实现用于半连接(最常用于处理 EXISTS 子查询)。

    尽管计算不等式条件上的连接效率非常低,但无论连接条件的特征为何,都可以使用嵌套循环连接。

    使用嵌套循环 FULL OUTER 连接来计算任何大小的输入需要的开销都非常大,只有其它连接算法都不能使用时,查询优化程序才会选择使用这种算法。

  • 合并连接   合并连接依赖于将其两个输入按连接属性进行排序。连接条件必须至少包含一个相等谓语,查询优化程序才会选择此方法。基本算法就是直接合并两个输入:当两个连接属性的值不同时,算法会滚动到左侧或右侧(取决于哪一侧的值小)的下一行。当具有多个匹配项时,可能需要进行回溯。

    提供了合并连接变体以支持 LEFT OUTER 和 FULL OUTER 连接。FULL OUTER 连接的合并连接明显比嵌套循环连接更为高效。

    基本的合并连接算法还用于支持 SQL 集合运算符 EXCEPT 和 INTERSECT,尽管这些变体已在访问计划中显式命名为 EXCEPT 或 INTERSECT 算法。

  • 散列连接   散列连接是 SQL Anywhere 数据库服务器所支持的最通用的连接方法。简言之,散列连接算法会用两个输入中的较小输入建立内存中的散列表,然后读取较大的输入并探查内存中的散列表以查找匹配项。

    提供了散列连接变体以支持 LEFT OUTER 连接、FULL OUTER 连接、半连接和反半连接。此外,当使用递归 UNION 查询表达式时,SQL Anywhere 还支持用于递归 INNER 和 LEFT OUTER 连接的散列连接变体。

    可以并行执行散列内连接、左外连接、半连接和反半连接算法。

    如果由算法构建的内存中散列表不适合可用内存,则散列连接算法会将输入拆分成多个部分(对非常大的输入可能递归),然后单独对每个部分执行连接。如果没有足够的高速缓存来保存连接属性为特定值的所有行,则在可能的情况下,每个散列连接都会在第一次放弃中间结果后动态地切换到基于索引的嵌套循环策略,以避免用尽语句的内存消耗限额。

    还使用散列连接的变体来支持 SQL 查询表达式 EXCEPT 和 INTERSECT,尽管这些变体已在访问计划中显式命名为 EXCEPT 或 INTERSECT 算法。


HashJoin 算法(JH、JHSP、JHFO、JHAP、JHO、JHPO)
RecursiveHashJoin 算法 (JHR)
RecursiveLeftOuterHashJoin 算法 (JHRO)
HashSemijoin 算法 (JHS)
HashAntisemijoin 算法 (JHA)
MergeJoin 算法(JM、JMFO、JMO)
NestedLoopsJoin 算法(JNL、JNLFO、JNLO)
NestedLoopsSemijoin 算法 (JNLS)
NestedLoopsAntisemijoin 算法 (JNLA)