4

我和朋友有一张桌子，id, u1, u2关于< 500,000单个 mysql 服务器上的条目

我想看看他们是否有共同的朋友userA。userB

做起来更快吗

select u2 from friends where u1 = userA and u2 IN (select u2 from friends where u1 = userB)

而不是在图上（在一台服务器上）运行最短路径算法？

像LinkedIn和Facebook这样的大型网络用来处理这个问题的标准方法是什么？

谢谢！

4

5 回答 5

2

如果表friends同时被u1和u2索引，那么SQL查询就是取2个子集的交集，速度相当快。这是因为索引已经完成。如果你在内存中进行计算，时间取决于你是否有预建索引：如果有，你会更快，因为没有数据库连接开销。如果索引包含在计算时间中，并且数据库已预热（内存中的所有数据），您可能会丢失。

我说的是索引，而不是最短路径算法，因为最短路径算法计算的数据比你需要的多。

于 2012-09-15T19:19:20.207 回答
2

在 MySQL 中，您编写的查询将比任何其他查找此信息的方式慢。也许比单独询问每个人要慢。您的查询：

select u2
from friends
where u1 = userA and
      u2 IN (select u2 from friends where u1 = userB)

在 IN 子句中有一个子查询。MySQL 评估遇到的每一行的查询。更好的写法是：

select u2
from friends
where u1 = userA and
      exists (select 1 from friends where u1 = userB limit 1)

如果您的数据都适合一台服务器并适合内存，那么优化的 MySQL 查询的性能应该没问题。LinkedIn 和 FaceBook 等网站正在处理无数问题——不断更新网络、大量数据、不同类型的链接等等。您的简单示例不能代表他们在做什么。但是，他们的许多分析将 Hadoop 或 Hadoop 与关系数据库结合使用。

于 2012-09-15T19:23:33.310 回答
2

在图形数据库中，您可以在gremlin中将查询编写为：

g.V('username','userB').out('friend').retain(g.V('username','userA').out('friend').gather)

大多数图形数据库应该快速执行此操作。

如果您使用 Titan，您还可以利用 Titan 按排序顺序维护相邻顶点，这意味着您只需对数据进行一次迭代即可计算两个好友列表的交集，而无需创建额外的数据结构。这可能会比 MySQL 更快，如果平均朋友数量很大，则速度会更快。

于 2012-11-19T23:32:04.837 回答
0

您确实必须尝试一下并根据自己的数据进行比较。看看cassovary、flockdb、neo4j 等

就个人而言，我会在内存中进行，因为您没有那么多条目。例如，尝试使用快速位操作 (AND) 的 BitSet。

于 2012-09-15T19:18:53.827 回答
0

这是使用简单的二级连接的另一种方法inner join：

select fA.u2 
from friends fA 
inner join friends fB on
           fA.u2 = fB.u2 
where fA.u1 = userA and
      fB.u1 = userB

这与多对多类型查询的方法相同。您不需要为该级别的关系使用最短路径。

如果您想寻找更大程度的关系，那么您应该查看邻接列表，但使用 MySQL 实现它并不容易。在该设置中需要真正注意一些问题：

  • 不相交的图（可以通过在子图上维护传递闭包来处理，并在需要时合并它们），
  • 有向图与无向图，
  • 数据分布（另一个答案提到hadoop是一种加速处理的方法，但它需要一个好的分区方案）

仅举几例。

于 2012-11-19T16:43:14.667 回答