xml - 编写更高效的 xquery 代码(避免冗余迭代)

Question

这是我正在处理的问题的简化版本:我有一堆 xml 数据，这些数据对有关人的信息进行编码。每个人都由“id”属性唯一标识，但他们可能有多个名字。例如，在一份文件中，我可能会发现

<person id=1>Paul Mcartney</person>
<person id=2>Ringo Starr</person>

在另一个我可能会发现:

<person id=1>Sir Paul McCartney</person>
<person id=2>Richard Starkey</person>

我想使用 xquery 生成一个新文档，其中列出与给定 ID 关联的每个名称。即:

<person id=1>
    <name>Paul McCartney</name>
    <name>Sir Paul McCartney</name>
    <name>James Paul McCartney</name>
</person>
<person id=2>
    ...
</person>

我现在在 xquery 中这样做的方式是这样的(伪代码式):

let $ids := distinct-terms( [all the id attributes on people] )
for $id in $ids
    return <person id={$id}>
    {
    for $unique-name in distinct-values
            (
            for $name in ( [all names] )
            where $name/@id=$id
            return $name
            )
        return <name>{$unique-name}</name>
    }
    </person>

问题是这真的很慢。我想瓶颈是最内层的循环，它为每个 id 执行一次(其中大约有 1200 个)。我正在处理相当多的数据(300 MB，分布在大约 800 个 xml 文件中)，所以即使在内部循环中执行一次查询也需要大约 12 秒，这意味着重复它 1200 次将需要大约 4小时(这可能是乐观的 - 该过程到目前为止已经运行了 3 小时)。它不仅速度慢，而且会占用大量虚拟内存。我正在使用 Saxon，我必须将 Java 的最大堆大小设置为 10 GB(!)以避免出现内存不足错误，并且它当前使用 6 GB 的物理内存。

所以这就是我真正喜欢的方式(在 Pythonic 伪代码中):

persons = {}
for id in ids:
    person[id] = set()
for person in all_the_people_in_my_xml_document:
    persons[person.id].add(person.name)

在那里，我只是在线性时间内完成，只扫描了一次 xml 文档。现在，有没有办法在 xquery 中做类似的事情？当然如果我能想象的话，一个合理的编程语言应该能够做到(他不切实际地说道)。我想问题在于，与 Python 不同，xquery(据我所知)没有任何类似关联数组的东西。

有什么聪明的方法可以解决这个问题吗？如果做不到这一点，是否有比 xquery 更好的东西可以用来实现我的目标？因为实际上，我在这个相对简单的问题上投入的计算资源有点荒谬。

Answer 1

不幸的是，这是 XQuery 1.0 中的一个缺点

XQuery 1.1 将 group by 子句添加到语法中以解决此问题，您的问题将通过以下方式解决:

for $person in /person
let $id = $person/@id
group by $id
return  <people id="{$id}">{
          for $name in distinct-values($person)
          return <name>{$name}</name>
        }</people>

不幸的是，XQuery 1.1 并未得到广泛实现，因此目前您无法使用 group by 子句。

作为 XQSharp 的开发人员，我不能代表任何其他实现，但我们花了很多时间调整我们的优化器，以发现 XQuery 1.1 中常见的分组依据模式，并使用您指定的算法执行它们。

特别是以下版本的查询:

declare variable $people as element(person, xs:untyped)* external;

for $id in distinct-values($people/@id)
return <people id="{$id}">{
          for $person in $people
          where $person/@id = $id
          return <name>{$person}</name>
       }</people>

被发现为一个分组依据，如下面的查询计划所证明的那样:

library http://www.w3.org/2005/xpath-functions external;
library http://www.w3.org/2001/XMLSchema external;
declare variable $people external;

for $distinct-person in $people
let $id := http://www.w3.org/2005/xpath-functions:data($distinct-person/attribute::id)
group by
  $id
aggregate
  element {name} { fs:item-sequence-to-node-sequence($distinct-person) }
as
  $:temp:19
return
  element {person} { (attribute {id} { $id } , fs:item-sequence-to-node-sequence($:temp:19)) }

请注意，类型注释 as element(person, xs:untyped)* 是必需的，因为不知道节点是未类型化的(未根据模式验证)，查询处理器没有办法知道 $person/@id 的数据值中没有多项。 XQSharp 尚不支持每个节点可以有多个键的表达式分组。但是，在这种情况下，仍然会发现左外部联接，因此复杂度应该大致为 n log n，而不是您遇到的二次方。

不幸的是，虽然在组中的一组人周围添加不​​同的值(以过滤掉重复的名称)似乎阻止了 XQSharp 找到连接；这已被记录为错误。目前，这可以通过分两次执行查询来解决——按 ID 对名称进行分组，并删除重复的名称。

总而言之，XQuery 1.0 中没有更好的方法，但一些实现(例如 XQSharp)将能够有效地评估它。如有疑问，请检查查询计划。

要更详细地了解 XQSharp 执行的连接优化，请查看此 blog post .