用大数据计算公共组成员资格的算法

Question

我需要编写一个程序来计算两个用户在同一组中的次数.用户按用户名和组ID分配.例如,使用输入(存储在文本文件中):

john 32
john 21
jim 21
jim 32
bob 32

我想要结果:

john-jim 2 
john-bob 1
jim-bob 1

这听起来微不足道.但问题是:我有1,800万组和30万用户.还有很多会员资格(我预计每个用户平均至少50个,可能更多).这意味着大量的数据和处理.

我写了5个不同的程序,没有一个能够减少数据量:它像PostgreSQL查询一样慢.耗尽内存消耗在Java工作内存中的Map中运行(第一个堆空间,在优化之后我得到了罕见的"超出GC开销限制").从Java连续写入数据库太慢(即使使用批处理查询进行优化).越来越绝望,我尝试了一些更奇特的东西,比如把所有的对都写成一个数组,然后对它们进行排序(O(n log(n)))然后将它们计算为peuàpeu.但仍有太多数据需要存储在内存中.

有关算法的任何想法吗？还是不可能？

Answer 1

RDBMS专门用于排序等操作.在数据库外部执行此操作几乎不会在性能上接近.用SQL做吧!

这将完成工作(简化更新):

SELECT t1.usr || '-' || t2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
WHERE  t2.usr > t1.usr   -- prevent dupes and get sorted pair
GROUP  BY t1.usr, t2.usr;

正如您所说,根据您拥有的重叠次数,这可能会产生大量的行.所以这永远不会快.

提出一个问题:产生数百万行没有人可以处理的目的是什么？你确定,这个操作从一开始就有意义吗？

为了让它更快,你可以..

• 升级! PostgreSQL 8.4现在已经过时了.特别是,PostgreSQL 9.2专注于大数据.你可以期待很多像这样的工作更好的性能.
  而且没有人应该运行8.4.0.仅出于安全原因,您也错过了很多错误修复.目前的释放点是8.4.17.我引用链接的网站:

我们始终建议所有用户运行最新的可用次要版本,以用于正在使用的主要版本.

• 使用integer作为用户的代理键,所以你只处理整数usr_grp.使表和索引更小并且处理更快.如果n:m table(usr_grp)的基数比表大得多usr,那么它应该更快,即使它意味着额外的连接.

SELECT u1.usr  || '-' || u2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
JOIN   usr u1 ON t1.usr_id = u1.usr_id
JOIN   usr u2 ON t2.usr_id = u2.usr_id
WHERE  t2.usr_id > t1.usr_id
GROUP  BY u1.usr_id, u2.usr_id;

• 创建一个多列索引(如果还没有).
  grp_id必须先来.为什么这很重要？

    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

• 把大量的RAM到你的机器并增加设置work_mem和shared_buffers.

测试用例

我根据他的测试用例报告了@OldCurmudgeon的数字,并在PostgreSQL中创建了一个类似的测试用例.

- > SQLfiddle演示.

在这个公共测试数据库中约250毫秒.
结果未订购(否ORDER BY),因为尚未指定.
相比2.5分钟,报告如下.因素600.