博客

在之前的两篇4store源码解析系列文章中，我们已经对单条triple的查询流程和细节处理进行了说明。在这一篇中，我们将对如何处理有嵌套关系的多条triple查询问题展开讨论，并进一步分析4store对这个问题的处理优化。

graph pattern解析和优化

如查询流程概述中所述，4store并不直接参与sparql语句的解析，而只对Rasqal库解析了后的graph结构进行分析。

要了解4store如何二次解析Rasqal对sparql查询语句的解析结果，我们首先需要了解Rasqa解析结果的具体形式。在Rasqal中，主要使用了graph pattern的概念，来组合解析结果中各个分支。我们可以将其理解成语法树中的一个节点，但这里的节点有很多类型，包括：Graph、Optional、Filter、Basic以及Union等。

• Basic类型节点只包含若干条triple，每个triple的返回结果之间做交（即MERGE）。
• Filter类型节点只包含一个表达式，表达式只使用其兄弟节点中涉及的变量值来计算。表达式是可以嵌套的，如?x < 10 && ?y != 0。最外层的表达式必要能返回BOOL类型的结果；返回TRUE表示符合表达式的条件，FALSE表示不符合；只有符合表达式条件的结果会被其父节点接受。
• GRAPH类型节点只包含若干个子节点，每个节点返回的结果间做交（即INNER_JOIN，同MERGE，仅在名称上有所区分）操作。
• Union类型的节点也只包含若干个子节点，但是每个子节点返回的结果间做并（即UNION）操作。
• Optional类型的节点，也只包含若干个子节点。其结果与其兄弟节点之间做半交（即LEFT_JOIN）操作，Optional节点下涉及的变量值对于其父节点而言是可选的。
• 其他类型，如MINUS类型、LET类型等暂不展开介绍。

可以看到，查询流程概述中graph pattern是非常简单的，只有一个Basic类型的节点。

下面，我们将引入了一个相对复杂的sparql查询语句来作为例子，针对分析有嵌套关系的多条triple查询问题。

实例分析

实例内容

测试数据依旧是foaf（friend of a friend）。SPARQL查询语句如下：

SPARQL

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/> 
SELECT ?name, ?page, ?nick 
WHERE { 
    ?x rdf:type foaf:Person .
    ?x foaf:name ?name . 
    {
        ?x foaf:homepage ?page 
    } UNION {
        ?x foaf:workplaceHomepage ?page
    } 
    OPTIONAL {
        ?x foaf:nick ?nick. 
        FILTER(
            strlen(?nick) < 5
        ) 
    } 
    FILTER regex(str(?page), "^http://www", "i") 
}

查询结果

这一次的查询结果返回了6条记录，具体如下：

count	?name	?page	?nick
0	“Jim Hendler”	http://www.cs.umd.edu/~hendler/
1	“Eric Miller”	http://www.w3.org/People/EM/	“em”
2	“Tim Berners-Lee”	http://www.w3.org/People/Berners-Lee/
3	“Bijan Parsia”	http://www.mindswap.org/~bparsia/
4	“Jan Grant”	http://www.ilrt.bris.ac.uk/about/staff/web_staff?search=cmjg	“jang”
5	“Dan Connolly”	http://www.w3.org/People/Connolly/	“DanC”

Rasqal Graph Pattern

Rasqal解析上述查询语句之后，得到的graph pattern如下：

 graph pattern[0] Group( over 4 graph patterns[
        graph pattern[1] Basic(over 2 triples[
            triple(variable(x), uri<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>, uri<http://xmlns.com/foaf/0.1/Person>) ,
            triple(variable(x), uri<http://xmlns.com/foaf/0.1/name>, variable(name))
        ]) ,
        graph pattern[2] Union( over 2 graph patterns[
            graph pattern[3] Basic( over 1 triple[
                triple(variable(x), uri<http://xmlns.com/foaf/0.1/homepage>, variable(page))
            ]) ,
            graph pattern[4] Basic( over 1 triple[
                triple(variable(x), uri<http://xmlns.com/foaf/0.1/workplaceHomepage>, variable(page))
            ])
        ]) ,
        graph pattern[5] Optional( over 1 graph pattern[
            graph pattern[6] Group( over 2 graph patterns[
                graph pattern[7] Basic( over 1 triple[
                    triple(variable(x), uri<http://xmlns.com/foaf/0.1/nick>, variable(nick))
                ]) ,
                graph pattern[8] Filter(
                    expr(
                        op lt(
                            expr(
                                op strlen(
                                    expr(variable(nick))
                                )
                            ), 
                            expr(
                                integer(5)
                            )
                        )
                    )
                )
            ])
        ]) ,
        graph pattern[9] Filter(
            expr(
                op regex(
                    expr(
                        op str(
                            expr(variable(page))
                        )
                    ), 
                    expr(
                        string("^http://www")
                    ), 
                    expr(
                        string("i")
                    )
                )
            )
        )
    ]
)

为了方便大家阅读，我们将Rasqal解析的graph pattern用下面这张图来表示。

其中，T和C对应于上文中的triple和expression，它们有如下对应关系：

• T0：triple(variable(x), urihttp://www.w3.org/1999/02/22-rdf-syntax-ns#type, urihttp://xmlns.com/foaf/0.1/Person)
• T1：triple(variable(x), urihttp://xmlns.com/foaf/0.1/name, variable(name))
• T2：triple(variable(x), urihttp://xmlns.com/foaf/0.1/homepage, variable(page))
• T3：triple(variable(x), urihttp://xmlns.com/foaf/0.1/workplaceHomepage, variable(page))
• T4：triple(variable(x), urihttp://xmlns.com/foaf/0.1/nick, variable(nick))
• C0：expr(op lt(expr(op strlen(expr(variable(nick)))), expr(integer(5))))
• C1：expr(op regex(expr(op str(expr(variable(page)))), expr(string(“^http://www”)), expr(string(“i”))))

在我们熟悉Rasqal graph pattern的解析结果之后，再去理解4store的二次解析就比较容易了。

graph pattern解析

4store中使用了一个100行左右的函数，来递归解析这个树状结构的 graph pattern。这个递归函数在每访问一个节点时，主要做了如下几件事：

1. 判断节点的类型，来设定执行到这个节点时的要进行交并操作类型（INNER_JOIN、LEFT_JOIN、UNION或者MINUS）；
2. 若节点是Filter类型的，则将其之下的表达式直接保存到当前节点的位置；
3. 将这个节点中包含的triple进行保存，并同时保存其中涉及的变量。若发现当前保存的变量在之前已经被保存过，则需要设置一个标记位，表明之后在执行triple时这个变量的值是需要取出来的（因为这个变量被多条triple依赖）；
4. 继续递归访问每个子节点。

二次解析grpah pattern之后，我们将得到了一个新的树状图。这里，4store不在称节点为graph pattern，而是block。graph pattern节点之下的内容都是单一的，要么都是节点，要么都是表达式，要么都是triple。block则不然，可以同时包含节点，表达式以及triple。与Rasqal类似，block也是有不同类型的，只是不再有Graph、Basic以及Filter类型。在4store中，节点的类型表示的是当执行完当前节点的所有triple查询语句之后，需要跟以前的查询结果做哪种类型的操作，从来合成一份新的查询结果。

回到上面那个sparql查询例子，我们对Rasqal graph pattern进行二次解析之后可以得到如下所示的新graph pattern。

细心的读者可能还注意到，UINION类型的节点数量和位置都发生了变化，但是关于UINION操作的细节我们将留到下一篇来说明。

有了这样一个graph pattern，其实我们顺着block的数值升序来执行triple查询和结果合并，就已经能够得到结果了。新的graph pattern看似更加紧凑，其实与之前的是同构的，与输入的sparql直接对应。对于Rasqal而言，其节点类型的设计决定了它只能有这样一种结构；但store的block是更加灵活的，在获得同样执行结果的前提下，我们还有很多简单结构可以使用。

树状结构压缩

首先，为什么要树状结构压缩？它能减少与服务端的通讯请求量么？

树状结构压缩是不能减少通讯请求量的，基本上有几条triple语句就意味着有几次通讯请求。这里用了基本，实际有一种特例的优化方案，是我们下一节中马上要提到的。但那种优化方案，与这里的压缩没有直接关系。树状结构压缩后的最直接效果是看上去的结构会更加简单，但其效果并局限在看上去这么简单。简单的结构，就意味节点少了，层次少了，那么也就意味着可以用较少的数据合并操作。树状结构压缩的主要目的就是减少客户端的处理复杂度。

树状结构压缩的逻辑非常简单。只要满足一下两种情况的节点都是可以压缩的：

1. 节点类型是INNER_JOIN, 当前节点没有表达式
2. 节点类型是INNER_JOIN，父节点没有表达式且父节点没有triple

每找到一个符合条件的节点，就可以将其下的表达式、triple以及子节点全部转移到父节点中。将所有满足条件节点都压缩了，就完成了整个树状结构压缩。

需要注意的是，这个节点必须也不能受LET关键字的约束（LET是4store也支持的一个实验性sparql关键字，不是现行标准中的关键字）。

针对上面这个例子，我们可以看到具体的压缩步骤如下：

有了上述树状压缩结构之后，4store就实际形成了一套执行计划。关于执行计划这部分的内容，我们会在下一篇中展开。

triple的查询优化

除了树状图结构的压缩可以用来优化sparql的查询外，还有没有的查询优化可能呢？

一般的关系数据库中，SQL语句就有一个非常重要的优化：表查询的顺序。

树状结构压缩的目的是减少结果合并的次数，而这里的triple查询优化的就是为了减少单次查询的复杂度同时提高结果合并的效率。triple查询优化主要通过调整triple查询的顺序与合并同类的triple查询来完成。

下面我们将通过两个例子来具体展开讨论。

triple重排

下面这个例子的内容很简单，其Rasqal解析得到的graph pattern只有一个节点，4store再进行二次解析之后依旧是只有一个节点其无需展开树状图结构压缩。这个节点之下，有两条triple语句需要执行，我们不妨定义?x foaf:name ?name .为T0，?x foaf:nick "em“.为T1。

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?name
WHERE {
    ?x foaf:name ?name .
    ?x foaf:nick "em“. 
}

在默认情况下，4store按照T0、T1的顺序执行的（但这显然不是最优的）。

先执行T0时，按照查询处理细节这一篇中的关于服务端的triple查询处理逻辑的说明，会先根据P得到一个ptree_s，然后遍历这棵tree的所有节点，并访问每个节点指向的ptable入口下的所有[M, O]值，收集所有[S, O]作为结果返回。然后，执行T1时，会使用P和O已知，查询其他中的逻辑，根据P得到一个ptree_o，然后在根据O得到ptable的入口，遍历入口指向的[M, S]列表，返回其中S值相符的结果。执行T1的代价是可以接受的，但T0的开销很有可能是非常大的。

如果我们先执行T1，那么还是可以使用O访问ptree_o，然后返回ptable指向列表中的所有S。然后执行T0，也是访问ptree_s，但是这一次不需要再去遍历整个ptree，而是使用之前获取的S中的值，逐个访问每个ptable的入口，返回入口指向的所有O。

4store会对一个block内的所有triple进行排序，而排序的原则十分简单:

    /* roughly sort into order:
     *   const subject and predicate
     *   const predicate and object
     *   const subject
     *   const object
     *   const graph
     *   const predicate
     *   all variable
     */

除此之外，还会根据实际上一次获取的变量值数量，来估计每一条triple可能返回的结果数量，选择当前可能返回结果较少的那条triple来执行。需要注意的是，变量值对应的rid数量，是会随着triple查询不断变化的，为了更加准确评估剩余每条triple查询的复杂度，triple重排在每次triple查询前都做一次。

合并查询

triple重排是在策略上对查询进行了优化，接下来要说的合并查询则是在查询实现上进行优化。

我们还是先来看一个例子，这个例子与triple重排中使用的十分相似，只是多了第三条triple，不妨设定?x foaf:homepage <http://purl.org/net/eric/>为T2。

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?name
WHERE {
    ?x foaf:name ?name .
    ?x foaf:nick "em“. 
    ?x foaf:homepage <http://purl.org/net/eric/>
}

那么多了T2之后，在查询上会有什么区别呢？当然，我们首先还是要进行triple重排的，变成按照T1、T2、T0的顺序执行triple。我们新加了T2，肯定是要参与到triple合并中的。对比T0和T1，显然是应该选择T1作为T2的合并对象，因为至少T1和T2在查询形式上是一致的。

接下来，我们就来具体看一下triple合并是怎么被处理的。T1和T2合并之后，就可以按照(P1, O1)和(P1, O1)查询，被表示成了([P1, P2], [O1, O2])，并加上一个特殊的消息头，发送到服务端。服务端收到这条特殊消息时，会按照如下步骤进行处理：

1. 根据每个[P, O]，查询到对应ptree_o指向的ptable入口，并记录到一个入口数组L。
2. 根据每个入口指向的[M, S]列表的大小，从小到大对L进行排序
3. 查询L的第一个入口L[0]，然后将列表中的所有S返回，记为T
4. 访问L的下一个入口，检查每个S是否在集合T中；若S在集合T中，则将其放入集合U
5. 执行T = U, U = {}的集合操作
6. 回到4继续执行，直至L已全部访问

经过上述步骤，我们就可以得到与T1和T2分开执行，然后合并结果一样的最终结果了。

最后我们还有两个问题：1. 为什么要执行triple合并，这个优化有什么效果呢？2. 怎样triple符合合并的条件，是一定要已知P和O么？已知P和S行不行？

triple合并查询的优势

在分析优势前，我们先将triple分开执行时的情况说明一下。不妨继续拿上面这个例子来说明，在我们执行完T0之后，我们就已经得到了x变量的一个集合，不妨设为U0。然后开始执行T1，向服务端发送(U0, P1, O1)。T1在服务端执行的时候，会遵循”P和O已知，查询其他“的逻辑进行查找，然后得到了x变量的新结果集合，不妨设为U1。最后执行T2，向服务端发送(U1, P2, O2)，得到x最终的结果集合，不妨设为U2。在triple合并查询时，则只会向服务端发送一次(U0, [P1, P2], [O1, O2])的查询请求，而直接返回U2。

合并查询的优势主要体现在两个方面：

1. 节省网络传输的开销。在不合并的情况，每一次的triple查询结果都必须先返回给客户端，然后客户端再将同样的内容传回给服务端作为下一次查询的条件。在合并查询之后只需要返回查询最终的合并结果即可，就能省去2(N-1)次的网络数据传输（假定合并了N条triple）。
2. 提高查询结果合并的效率。在triple重排之后，对于客户端而言T1和T2是完全等价的，因为它不知道对应于(P1, O1)和(P1, O1)分别有多少个[M, S]对。因此客户端无法判断是应该先执行T1还是先执行T2，只能顺序执行下去。但triple合并时，在服务端可以很容易获取到每个条件下的候选集大小，从而决定查询的先后顺序。

这里不妨举个例子，假如有三条triple是Ta、Tb和Tc，它们单次查询可以分别得到1000、500和100条查询结果。而它们结果集合两两合并之后分别可以得到如下数量的子结果：

	Ta	Tb	Tc
Ta	1000	200	50
Tb	200	500	25
Tc	50	25	100

这三条triple全部合并之后的结果的数量是10条。

那么他们按照不同顺序执行，在查询结果的合并时的计算开销如下所示：

	第一次合并	第二次合并	合计
TaTbTc/TbTaTc	1000 * 500	200 * 100	520,000
TaTcTb/TcTaTb	1000 * 100	50 * 100	105,000
TbTcTa/TcTbTa	200 * 100	25 * 1000	45,000

显然，使用TbTcTa或TcTbTa的顺序来执行triple更加高效。当我们采用triple合并时，可以非常很轻松的获取到每个triple执行后的结果数量，从而选择TcTbTa这种高效的查询顺序。

triple合并查询的条件

从理论上来说，只要涉及的是同样的变量，那么它应该都是能够合并的。但是在4store中，只对查询同一个S，且P和O确定的情况进行了triple查询优化。从笔者的角度来看，这个优化至少是可以推广到查询同一个O，且P和S确定的情况的（4store也保留支持这个优化的代码与接口，只是没有最终被使用）。但是对于只已知P的情况，就留给读者们去考虑这样优化的价值到底如何。

conjuctive条件查询的异同

关于 conjuctive条件请回顾查询处理细节。乍看之下，T1和T2合并之后，跟我们之前提到的conjuctive条件的情况非常相似的：

• conjuctive查询的条件是(?S, [P1, P2], [O1, O2])或([S1, s2], [P1, P2], O)，其发送到服务端的消息除了消息头有所不同外，其他格式是完全相同的。
• conjuctive查询在处理时，也是类似的。将上述的(?S, [P1, P2], [O1, O2])拆解成(?S, P1, O1)和(?S, P2, O2)来执行

但是两者其实是完全没有联系的，它们的本质区别在于：

• 一个block内的triple查询之间的是交的关系，triple查询结果是需要进行JOIN合并的，选择triple返回值中变量值相同的部分来作为合并后的查询结果
• conjuctive条件是针对一条triple的情况的特殊执行方式。如果你将这条triple拆开成N条“子triple”，那么这些”子triple“间是并的关系，”子triple“的查询结果是需要进行UNION合并的