代码之家 › 专栏 › 技术社区 › Abe Voelker

提高Postgres在多级自联接的类图查询中的性能(与Neo4j的比较)

neo4j postgresql sql

Abe Voelker · 技术社区 · 6 年前

其中一个 claims Neo4j makes in their marketing 关系数据库不擅长进行多级自连接查询:

我找到了 code repository 对应于索赔书,以及 translated it to 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   |

(这是一个例子 EXPLAIN ANALYZE of a depth 5 query )

我的问题是,有没有办法提高这些查询的性能,以满足或超过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秒( EXPLAIN ANALYZE )

1 回复 | 直到 6 年前

Vladimir Baranov 6 年前

我想从一开始就指出,比较关系数据库和非关系数据库并不是一对一比较。

当数据更新时,非关系数据库可能会维护一些额外的预计算结构。这会使更新速度稍慢,并需要更多磁盘空间。您使用的纯关系模式没有任何额外功能,这使得更新尽可能快,并将磁盘使用率保持在最低水平。

我将重点介绍如何使用给定的模式。

首先我要做一个综合指数

CREATE INDEX idx_user_friend_user_12 ON t_user_friend (user_1, user_2);

一个这样的指数就足够了。

然后,我们知道总共只有100万用户,所以最终结果不能超过100万。

5级查询最终生成31250万行(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 ,博士后不够聪明,做了一些不必要的事情。此外,它还对一些应用程序使用哈希聚合 选择不同的 ,这需要额外的排序。

因此,下一步的尝试是为每个步骤显式地使用带有适当索引的临时表。

此外,我还要定义 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;

作为显式临时表的额外好处,您可以测量每个额外级别所需的时间。