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

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

  •  9
  • Abe Voelker  · 技术社区  · 6 年前

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

    enter image description here

    我找到了 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 年前
        1
  •  8
  •   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;
    

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