sql - 提高多级自连接的类图查询的 Postgres 性能(与 Neo4j 比较)
问题描述
Neo4j 在其营销中提出的一项声明是关系数据库不擅长进行多级自联接查询:
我找到了与该声明所来自的书相对应的代码存储库,并将其翻译为 Postgres:
CREATE TABLE t_user (
id bigserial PRIMARY KEY,
name text NOT NULL
);
CREATE TABLE t_user_friend (
id bigserial PRIMARY KEY,
user_1 bigint NOT NULL REFERENCES t_user,
user_2 bigint NOT NULL REFERENCES t_user
);
CREATE INDEX idx_user_friend_user_1 ON t_user_friend (user_1);
CREATE INDEX idx_user_friend_user_2 ON t_user_friend (user_2);
/* Create 1M users, each getting a random 10-character name */
INSERT INTO t_user (id, name)
SELECT x.id, substr(md5(random()::text), 0, 10)
FROM generate_series(1,1000000) AS x(id);
/* For each user, create 50 random friendships for a total of 50M friendship records */
INSERT INTO t_user_friend (user_1, user_2)
SELECT g1.x AS user_1, (1 + (random() * 999999)) :: int AS user_2
FROM generate_series(1, 1000000) as g1(x), generate_series(1, 50) as g2(y);
这些是 Neo4j 正在比较的不同深度的查询:
/* Depth 2 */
SELECT
COUNT(DISTINCT f2.user_2) AS cnt
FROM
t_user_friend f1
INNER JOIN
t_user_friend f2
ON f1.user_2 = f2.user_1
WHERE
f1.user_1 = 1;
/* Depth 3 */
SELECT
COUNT(DISTINCT f3.user_2) AS cnt
FROM
t_user_friend f1
INNER JOIN
t_user_friend f2
ON f1.user_2 = f2.user_1
INNER JOIN
t_user_friend f3
ON f2.user_2 = f3.user_1
WHERE
f1.user_1 = 1;
/* Depth 4 */
SELECT
COUNT(DISTINCT f4.user_2) AS cnt
FROM
t_user_friend f1
INNER JOIN
t_user_friend f2
ON f1.user_2 = f2.user_1
INNER JOIN
t_user_friend f3
ON f2.user_2 = f3.user_1
INNER JOIN
t_user_friend f4
ON f3.user_2 = f4.user_1
WHERE
f1.user_1 = 1;
/* Depth 5 */
SELECT
COUNT(DISTINCT f5.user_2) AS cnt
FROM
t_user_friend f1
INNER JOIN
t_user_friend f2
ON f1.user_2 = f2.user_1
INNER JOIN
t_user_friend f3
ON f2.user_2 = f3.user_1
INNER JOIN
t_user_friend f4
ON f3.user_2 = f4.user_1
INNER JOIN
t_user_friend f5
ON f4.user_2 = f5.user_1
WHERE
f1.user_1 = 1;
我大致能够重现这本书声称的结果,获得了针对 100 万用户、5000 万友谊的这些执行时间:
| Depth | Count(*) | Time (s) |
|-------|----------|----------|
| 2 | 2497 | 0.067 |
| 3 | 117301 | 0.118 |
| 4 | 997246 | 8.409 |
| 5 | 999999 | 214.56 |
(这是深度 5 查询的解释分析)
我的问题是,有没有办法提高这些查询的性能,以达到或超过 Neo4j 在深度 5 时约 2 秒的执行时间?
我尝试使用此递归 CTE:
WITH RECURSIVE chain(user_2, depth) AS (
SELECT t.user_2, 1 as depth
FROM t_user_friend t
WHERE t.user_1 = 1
UNION
SELECT t.user_2, c.depth + 1 as depth
FROM t_user_friend t, chain c
WHERE t.user_1 = c.user_2
AND depth < 4
)
SELECT COUNT(*)
FROM (SELECT DISTINCT user_2 FROM chain) AS temp;
但是它仍然很慢,深度 4 需要 5 秒,深度 5 需要 48 秒(解释分析)
解决方案
我想从一开始就指出,比较关系数据库和非关系数据库并不是同类比较。
随着数据的更新,非关系数据库很可能会维护一些额外的预先计算的结构。这会使更新速度变慢,并且需要更多的磁盘空间。您使用的纯关系模式没有任何额外内容,这使得更新尽可能快并将磁盘使用量降至最低。
我将重点介绍使用给定模式可以做什么。
起初我会做一个综合索引
CREATE INDEX idx_user_friend_user_12 ON t_user_friend (user_1, user_2);
一个这样的索引就足够了。
那么,我们知道总共只有100万用户,所以最终结果不能超过100万。
5 级查询最终生成 312.5M 行 (50*50*50*50*50)。这远远超过最大可能的结果,这意味着有很多重复。
因此,我会尝试在流程的早期实现中间结果并消除重复。
我们知道 Postgres 实现了 CTE,所以我会尝试使用它。
像这样的东西:
WITH
CTE12
AS
(
SELECT
DISTINCT f2.user_2
FROM
t_user_friend f1
INNER JOIN t_user_friend f2 ON f1.user_2 = f2.user_1
WHERE
f1.user_1 = 1
)
,CTE3
AS
(
SELECT
DISTINCT f3.user_2
FROM
CTE12
INNER JOIN t_user_friend f3 ON CTE12.user_2 = f3.user_1
)
,CTE4
AS
(
SELECT
DISTINCT f4.user_2
FROM
CTE3
INNER JOIN t_user_friend f4 ON CTE3.user_2 = f4.user_1
)
SELECT
COUNT(DISTINCT f5.user_2) AS cnt
FROM
CTE4
INNER JOIN t_user_friend f5 ON CTE4.user_2 = f5.user_1
;
很SELECT DISTINCT
可能需要排序,这将允许使用合并连接。
据我从上面https://explain.depesz.com/s/Sjov查询的执行计划中了解到,Postgres 不够聪明并且做了一些不必要的排序。此外,它对 some 使用哈希聚合SELECT DISTINCT
,这需要额外的排序。
因此,下一次尝试是为每个步骤显式使用具有适当索引的临时表。
另外,我将idx_user_friend_user_12
索引定义为唯一的。它可能会为优化器提供额外的提示。
看看下面的表现会很有趣。
CREATE TABLE temp12
(
user_2 bigint NOT NULL PRIMARY KEY
);
CREATE TABLE temp3
(
user_2 bigint NOT NULL PRIMARY KEY
);
CREATE TABLE temp4
(
user_2 bigint NOT NULL PRIMARY KEY
);
INSERT INTO temp12(user_2)
SELECT
DISTINCT f2.user_2
FROM
t_user_friend f1
INNER JOIN t_user_friend f2 ON f1.user_2 = f2.user_1
WHERE
f1.user_1 = 1
;
INSERT INTO temp3(user_2)
SELECT
DISTINCT f3.user_2
FROM
temp12
INNER JOIN t_user_friend f3 ON temp12.user_2 = f3.user_1
;
INSERT INTO temp4(user_2)
SELECT
DISTINCT f4.user_2
FROM
temp3
INNER JOIN t_user_friend f4 ON temp3.user_2 = f4.user_1
;
SELECT
COUNT(DISTINCT f5.user_2) AS cnt
FROM
temp4
INNER JOIN t_user_friend f5 ON temp4.user_2 = f5.user_1
;
DROP TABLE temp12;
DROP TABLE temp3;
DROP TABLE temp4;
作为显式临时表的额外好处,您可以测量每个额外级别需要多少时间。
推荐阅读
- javascript - 我的后端代码在发出发布请求时抛出了 500 个错误,这是怎么回事?
- tensorflow - 如何解决“AttributeError:模块'google.protobuf.descriptor'没有属性'_internal_create_key”?
- c++ - 是否可以在 C++ 中基于给定标识符创建基类的新实例,反之亦然
- javascript - 根据矩阵B的排序对矩阵A进行排序
- javascript - 有没有办法在查询构建器的“with”子句中添加计数?
- three.js - 在组件内部的Aframe中导入threejs代码
- php - Laravel 发送带有降价的电子邮件不记录
- mysql - 使用 Inner Join/Group_Concat 更新两个表之间的 Inner Join 返回子查询错误
- angular - 无法在角度中设置未定义的属性?
- c++ - 如何在 Xcode 中定义 DOBJC_OLD_DISPATCH_PROTOTYPES?