java - 用大数据统计普通组成员的算法

Question

我需要编写一个程序来计算两个用户在同一组中的次数。用户由用户名和组由 id 给出。例如，输入(存储在文本文件中):

john 32
john 21
jim 21
jim 32
bob 32

我想要结果:

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

这听起来微不足道。但问题是:我有 180 万个组和 300,000 个用户。还有很多成员(member)资格(我预计每个用户平均至少有 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 is rather outdated by now .特别是 PostgreSQL 9.2 将重点放在了大数据上。对于这样的工作，您可以期待很多更好的表现。
  而且没有人应该运行 8.4.0。仅出于安全原因，您也错过了很多错误修复。当前的小版本是 8.4.17。我引用链接的网站:

We always recommend that all users run the latest available minor release for whatever major version is in use.

• 使用 integer 作为用户的代理键，因此您只在 usr_grp 中处理整数。使表和索引更小，处理速度更快。如果 n:m 表 (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 必须在前。 Why does this matter?

    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

• 将大量内存放入您的机器并增加work_mem 的设置|和 shared_buffers .

测试用例

我取了数字 @OldCurmudgeon reported用于他的测试用例，并在 PostgreSQL 中创建了一个可比较的测试用例。

-> SQLfiddle demo.

~ 250 毫秒 在此公共(public)测试数据库中。
结果未排序(无 ORDER BY)，因为尚未指定。
与2.5 分钟 相比，reported below .因子 600。