查询的执行#

一般来说，数据库具体如何执行查询被认为是具体实现的细节，用户不需要了解，理由是这样数据库会有更多的有优化查询计划的空间。然而在实际应用中的情况并非如此理想化：由于在复杂查询（尤其是多表连接查询）时数据库“优化”后的计划常常造成性能上的问题，用户常常需要通过各种方式限制数据库的这种自由度来使数据库按照用户的意图来执行查询，这个过程艰辛且令人痛苦。在图数据库中这个问题尤其突出，因为图查询包含大量多表连接。

对此问题，Cozo 采取了实用的态度，保证执行查询时的执行计划是 确定性的 ，即根据查询的文本本身就能断定查询如何被执行。这也意味着用户常常需要对数据本身有一定的了解，特别是需要知道应该如何写查询文本才能生成想要的查询执行计划。大家会发现，在查询文本复杂时，这种确定性，这种能够明确地操纵查询计划的能力，实际上会省去很多时间与精力。

析取范式#

查询文本编译的第一个步骤是将所有内联规则中由原子组成的逻辑表达式转化为析取范式：所有的否定都直接作用于底层的原子上，然后整个逻辑短句由有限个合取式的析取组成，这些合取式则只包含底层原子或底层原子的否定式。而后顶层析取式中的每个合取短句都成为独立的同一个内联规则下的正文。需要注意的是，转化后的查询文本可能会违反安全规则，即使文本本身看起来似乎没问题，比如：

::: rule[a, b] := rule1[a] or rule2[b]

在改写后这一条正文变成了两条正文，而在这两条正文中都未全部绑定包含头部所需要的所有变量，因此此查询是不安全的。

规则的分层#

下一步是将所有规则分为多个层次。首先将规则作为一个图中的节点，而当一条规则的正文中应用了其它的规则时，就画一条从这条规则到被应用规则的边。这些边中，满足以下任一条件的被标注为 断层边 ：

规则应用的原子处于被否定的位置；
被应用的规则不是当前规则本身，且被应用的规则含有任何聚合算符；
被应用的规则就是当前规则本身，被应用的规则含有聚合算符且该聚合算符不能做为半晶格算符执行；
规则或被应用的规则是固定规则；

接下来算出这个图中的强连通分量。如果某一个强连通分量中含有断层边，则此查询被认为无法分层，执行报错。

如果没有报错，则对强连通分量组成的图进行拓扑排序。排序后这些强连通分量会被进一步合并为层，这个合并满足以下条件：每层中所含有的规则间没有断层边，且每层中的规则只有到当前或之前层中规则的边，没有到之后层中规则的边。

通过这个步骤我们得到的层，在查询中会按照顺序依次执行。具体查询文本的分层可以通过 ::explain 系统操作来展示。

魔法集改写#

接下来，层中的规则会做为一个整体来进行 魔法集改写 。这个改写的目的是省去一些不必要的中间结果。例如在以下查询中

::: reachable[a, b] := link[a, n] reachable[a, b] := reachable[a, c], link[c, b] ?[r] := reachable[‘A’, r]

如果不进行改写就直接执行，完整的 reachable 表会被生成，而当我们返回最终结果是实际上仅用到了这个表中非常小的一部分，即 a == 'A' 的那部分。而改写后的规则则只会计算这需要的一部分，并保证输出的最终结果与改写前完全相同。改写的结果同样可以通过 ::explain 查询。

任何带有聚合算符的规则都不会被改写。

半朴素求值#

现在每层内要么含有单个的固定规则，要么含有改写过的若干个内联规则。单个的固定规则会按照其实现算法执行，而内联规则的集，当我们已经知道如何执行每条规则的正文时，从宏观上来说，则会依照半朴素求值算法执行。朴素求值算法是一个自下而上的算法：它以所有已知的事实出发，按照所给规则推导隐含的事实。由于规则间的递归关系，这个推导过程需要执行不定的次数，直到没有新事实被推导出为止，而半朴素求值法则在朴素求值法的基础上做了一些改进，通过代数性质省去了大量的推导过程。

备注

另一类求值法是自上而下的求值法：由需要证明的事实而不是给出的事实出发，逐步构建证明的步骤。自下而上求值法相比自上而下求值法而言具有许多优势，尤其是在一定情况下能保证算法不陷入死循环（自上而下不能）。其劣势在于自下而上法经常会生成不需要的事实，而魔法集改写的引入正好完美消除了这个劣势。

对原子排序#

现在我们来介绍内联规则的正文部分如何被执行。首先编译器会对原子进行重新排序，然后原子依次被执行。由于我们已经将正文都转写为了析取范式，现在每个原子只能是以下情况之一：

显性归一；
存储或内联表的应用；
表达式；
存储或内联表应用的否定。

上面给出的前两种情况可以生成新的绑定，而后两种不行。在重新排序时，前两种情况的原子原地不动，而后两种情况的原子会被安排在其所包含所有变量都已经绑定了的尽量早的位置。在重新排序之后，前两种情况就变成了关系代数的表的连接，用来连接的列就是其包含的已绑定的变量；而后两种情况就变成了关系代数中的过滤。改写的意义在于，过滤会被尽量早地执行，使得中间结果尽量地少。

在编写查询文本时，首要的目的就是减少中间结果的数量。一个几乎只有好处没有坏处的策略是，在连接多个表的时候，将能过滤掉更多行的表写在前面。

对原子求值#

接下来介绍能够生成新绑定的原子的求值方法。

在显性归一种，算符右边的表达式会被执行（此时其所含所有变量都已有绑定），然后结果会被连接到当前的表中，相当于函数式语言中的 map-cat 函数。

表的应用都与单个的表相关，而这些表都是以其键做字典排序来存储的树。因此，一个表的应用的算法复杂度取决于其已绑定的变量是否构成表键列的前缀。比如说，在下例中的应用

a_rule['A', 'B', c]

变量 c 未被绑定。这个查询中前两列已被绑定，且构成了前缀，所以系统可以直接在树上找到前缀对应的位置，因此此查询复杂度低，速度快。与此相对的，以下查询中

a_rule[a, 'B', 'C']

如果变量 a 未绑定，则系统必须遍历所有数据才能找出满足条件的行，因此复杂度高，速度慢。

在了解存储表应用的具体执行必须先了解存储表的结构。系统操作 ::explain 也可以显示一个查询中是否含有对某个表的遍历操作。

对正文求值时，行是以流式的方式生成的，也就是说前一个原子生成了一行后，就立刻开始连接下一个原子，而不等前一个原子生成其所有行。

早停法#

指定了查询选项 :limit 以后，在执行入口规则 ? 时系统会启用一个计数器来记录已经生成了多少满足查询条件的行，而由于流式的正文执行，当足够的行被生成后查询就会立刻停止。这就是 早停法 。此法仅对没有同时指定 :order 的查询中的内联规则奏效。