我需要编写一个程序来计算两个用户在同一组中的次数。用户由用户名和组由 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 计数。但是在内存中存储的数据仍然太多。
关于执行此操作的算法有什么想法吗?还是不可能?
请您参考如下方法:
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 中创建了一个可比较的测试用例。
~ 250 毫秒 在此公共(public)测试数据库中。
结果未排序(无 ORDER BY
),因为尚未指定。
与2.5 分钟 相比,reported below .因子 600。