1

我对 mongodb 比较陌生,到目前为止,我还没有解决我之前用 SQL 后端解决的问题的方法。

问题本身很简单:我在数据库中保存了大量任意长度的有序单词序列,例如:

Sequence #0: [ "word1", "word34", "word56", …, "word_66" ]
Sequence #1: [ "word45", "word2", "word334", "word45", …, "word_668" ] 
...

在数据库序列中,同一个词可能会出现不止一次。

给定一个像 ["word2", "word334"] 这样的输入单词序列,我想检索所有包含输入单词的数据库序列,它们的顺序与给定的相同。唯一的特殊性是:输入的单词之间最多可以有一个单词。因此,例如,序列 ["a", "a", "b", "c"] 将匹配输入 ["a", "c"],"b" 是“跳过的单词”在这种情况下。假设在执行任何搜索之前,所有序列都已使用任何数据模型写入数据库;只有查询是感兴趣的。

使用 SQL,这个问题很容易通过对规范化表的单个查询来解决。但我想用 mongoDb 解决同样的问题。

首先,我尝试完全复制 mongoDb 中的表,就像我在 SQL 中一样。我想我会在我去的时候用 mongo 查询语言调整查询。这效果不太好,因为我发现无法在同一个 find() 中比较来自同一个集合的两个文档——(这是模拟某种 JOIN 的幼稚尝试)。

接下来,我尝试在“序列”文档中将序列词分组到一个数组中,并确保所有必要的信息都在同一个文档中可用。使用 aggregate() 管道,我尝试查看是否无法“链接”几个 $match 阶段。在 $match 阶段我能做的最好的事情是过滤其中包含所有输入单词的序列(使用 $all),但我不能再进一步了,因为我永远找不到 mongoDb 的方式来表达“比较位置文档数组中的一个单词到同一个文档数组中另一个单词的位置”(显然,您不能将字段放在查询比较运算符的右侧,即使来自同一个文档)。

然后我虽然可以编写一个javascript函数来计算一个文档的解决方案并在$match之后的$where阶段调用它。这种方法也没有成功,因为我找不到将输入序列(数组变量)传递给 $where 子句的方法。我什至尝试根据输入手动组合查询字符串,以便它只包含解析的常量以在之后运行它,但无济于事(显然,$where 不喜欢将局部变量作为参数传递,并且不像数组常量)。我尝试将功能上传到服务器,以防万一,但我也没有运气,限制似乎或多或少相同。

在这一点上,我能看到的唯一可行的方法是将所有序列单词放在一个大字符串中,并使用 $regex 运算符来执行匹配。这会有点难看,因为可能存在“跳过的单词”,并且因为正则表达式而非常慢,而且因为在这种情况下永远无法使用索引。我没有尝试成熟的 mapReduce 管道,但乍一看它似乎只是对 aggregate() 的扩展,因此可能同样不适合解决这个问题。

我已经浏览了几次文档,并没有发现任何其他可以帮助我的“特殊功能”或概念。有 MongoDB 建模知识的人可以推动我采用一些有效的方法吗?什么可能是一个对 mongoDb 友好的数据模型?我不是在寻找与这个特定问题相关的设计大纲那样多的代码。谢谢。

4

1 回答 1

0

我终于解决了这个问题,尽管我不确定我的解决方案有多优化(我将进行一些自动化测试以确定它的速度/可扩展性)。

因为 mongoDb 不能在同一个查询中比较两个单独的文档(可能是为了确保查询可以并行化),所以很难仅依靠它的查询“语言”来计算任何类型的连接属性。就我而言,我的结构相当于一个简单的 DAG。因此,我没有使用指示其位置的索引来存储序列的各个节点(单词)(并让查询语言像 SQL 中那样通过索引的间隔检查来推断连接性),而是使用边缘作为基本文档,即:word_i(起始节点)连接到 word_j(结束节点)。在这个边缘文档中,我添加了序列 ID 以及订购信息。要创建数据库集合,由于我可以在匹配之间跳过一个单词,因此我最多需要为每个起始单词添加两条边。

给定输入序列,我首先使用具有几个阶段的聚合器:

阶段 1:当我想搜索一个输入序列(例如:["word_a", "word_b", "word_c"])时,我首先四舍五入 ($match) 所有与输入推断相匹配的数据库边序列,在这种情况下:("word_a"->"word_b") 和 ("word_b"->"word_c")。当然,这会检索到误报,因为我无法表示只要有匹配项,“word_b”在两条边中都是相同的确切实例,而且我不能确保同一条边不会匹配两次另一个边缘根本不匹配的序列,我也会得到匹配太少的序列。

第 2 阶段:我按序列 id 和起始词索引对结果进行排序。

第 3 阶段:我按序列 _id 对先前的结果进行分组。阶段 2 中的排序将边缘按出现的顺序排列在序列中。同时,我 $addToSet 一个集合中的所有开始节点,以及另一个集合中的结束节点。我还 $sum 每组中匹配边的数量。

第 4 阶段:我 $match 删除所有不包含足够边以匹配输入的组(这会删除不包含我想要的所有边的序列)。

阶段 5,6,7,8:我的下一个目标是确保我想要的所有单词都被考虑在内,所以我计算了阶段 3 中计算的每个集合中的元素数量($unwind the set,然后一个 $group 与一个 $sum : 1 在一个计数字段)。

第 9 阶段:我 $match 以仅保留与从输入序列派生的相同单词集基数相同的边缘。(这与我第一次尝试解决方案失败的“$all”实现了或多或少相同的目标)。

第 10 阶段:我 $project 为下一步总结所有字段。

我唯一无法在聚合器中计算的是边之间的连通性:我不知道边的结束节点是否与下边的开始节​​点匹配。但是因为匹配序列的集合现在减少到最小,并且所有边都按序列中出现的顺序排序,所以我可以在 Javascript 中快速传递以仅保留所需边连续出现的序列(由跳字容差约束)。我会尝试将所有内容都塞进聚合器中,但不幸的是 $where 似乎在那里不起作用。

无论如何,这似乎足够快,而且速度似乎相当恒定,无论输入长度如何(在随机生成的样本数据库上),并且在 javascript 中花费的时间可以忽略不计。正如预期的那样,边缘表增长了很多,但是使用 mongo,我希望这不应该是一个问题。当然,我也不能轻易更改单词跳过约束值(例如更改为 2),因为这需要修改主集合。

结论:虽然可能有更快更好的解决方案,但通过这项工作,我对 mongoDb 有了更多的了解。我希望 mongo 团队最终将加强他们的“单文档评估语言集”,以涵盖其他不会破坏其并行模型的方便运算符,例如用于数组的 $size、$removeFromSet,在右侧有字段运算符,对数组值的测试,更多的算术运算符,如 $sqrt 等......

于 2013-10-27T03:54:12.103 回答