使用 Postgresql 高效地（递归地）查找朋友的朋友

Question

目标：用户提交他们的通讯录，然后应用程序根据他们的电话号码查找用户之间的联系。类似于“6次握手”的想法（https://en.wikipedia.org/wiki/Six_degrees_of_separation）。

问题：使这个查询性能接近实时。当用户提交他的电话号码并获得其他电话的完整列表时，他可能知道。普通列表 - 没有连接（图形顶点等），但完整，没有分页（这里要求是因为原始目标更复杂）。

问题：是否有可能使用纯关系数据库实现接近实时的性能，而无需图形数据库（Neo4j 等）、图形扩展（bitnine agensgraph）或工作流重新设计？任何非规范化都是可能的，但据我所知，它无济于事。

鉴于：

test=# select * from connections;
 user_phone | friend_phone
------------+--------------
          1 |            2
          1 |            3
          1 |            4
          2 |            6
          2 |            7
          2 |            8
          8 |           10
          8 |           11
          8 |           12
         20 |           30
         40 |           50
         60 |           70

我希望使用电话 === 1 的用户收到以下连接：

 friend_phone
--------------
            2
            3
            4
            6
            7
            8
           10
           11
           12
(9 rows)

估计真实世界的连接数真的很困难。但我至少在测试：

• 10,000 个用户（电话号码）
• 每个用户被随机分配了 50-1000 个与其他用户的伪随机连接
• 这导致了大约 1,000,000 个连接

如果一般情况下无法实现这一点（使用一些棘手的 ORDER BY 或子查询等） - 例如应该考虑哪些指标来理解：

对于 1,000,000 个连接，您需要 128GB RAM 实例才能获得 2 秒的响应时间

和

对于 100,000,000 个连接，您需要 1TB RAM 实例才能获得 5 秒的响应时间

?

PS 我尝试了子查询、CTE、JOIN，但最终我发现 WITH RECURSIVE 是最明确的方式，它的结果时间与其他方法相同。

这是表：

CREATE TABLE connections (
  user_phone bigint NOT NULL,
  friend_phone bigint NOT NULL
);

这就是我播种数据的方式：

INSERT INTO connections(user_phone, friend_phone) (
  SELECT generate_series AS user_phone, generate_series(1, (random()*5000)::int) AS friend_phone from generate_series(1, 500) ORDER BY user_phone
);

我创建了一些索引：

test=# \d connections
               Table "public.connections"
    Column    |  Type  | Collation | Nullable | Default
--------------+--------+-----------+----------+---------
 user_phone   | bigint |           | not null |
 friend_phone | bigint |           | not null |
Indexes:
    "connections_user_phone_friend_phone_idx" UNIQUE, btree (user_phone, friend_phone)
    "connections_friend_phone_idx" btree (friend_phone)
    "connections_friend_phone_user_phone_idx" btree (friend_phone, user_phone)
    "connections_user_phone_idx" btree (user_phone)

我期望friend_phones.count >>> user_phones.count，所以索引connections(friend_phones, user_phones)似乎是最合适的，但我在测试期间创建了所有 4 个索引。

已生成 2270852 条连接记录。然后我运行这个查询：

WITH RECURSIVE p AS (
    SELECT friend_phone FROM connections WHERE connections.user_phone = 1
    
    UNION

    SELECT friends.friend_phone FROM connections AS friends JOIN p ON friends.user_phone = p.friend_phone
  )
SELECT COUNT(friend_phone) FROM p;

它返回 5002 条记录并执行大约 3 秒。EXPLAIN ANALYZE如下所示：

                                                                                      QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=3111105.00..3111105.01 rows=1 width=8) (actual time=3151.781..3151.781 rows=1 loops=1)
   CTE p
     ->  Recursive Union  (cost=0.43..2146207.20 rows=42884347 width=8) (actual time=0.060..3148.294 rows=5002 loops=1)
           ->  Index Scan using connections_user_phone_idx on connections  (cost=0.43..3003.69 rows=4617 width=8) (actual time=0.055..2.024 rows=4137 loops=1)
                 Index Cond: (user_phone = 1)
           ->  Merge Join  (cost=4500.77..128551.66 rows=4287973 width=8) (actual time=768.577..1359.598 rows=635428 loops=2)
                 Merge Cond: (friends.user_phone = p_1.friend_phone)
                 ->  Index Scan using connections_user_phone_idx on connections friends  (cost=0.43..54054.59 rows=2270852 width=16) (actual time=0.013..793.467 rows=1722262 loops=2)
                 ->  Sort  (cost=4500.34..4615.77 rows=46170 width=8) (actual time=0.765..74.850 rows=637677 loops=2)
                       Sort Key: p_1.friend_phone
                       Sort Method: quicksort  Memory: 65kB
                       ->  WorkTable Scan on p p_1  (cost=0.00..923.40 rows=46170 width=8) (actual time=0.001..0.314 rows=2501 loops=2)
   ->  CTE Scan on p  (cost=0.00..857686.94 rows=42884347 width=8) (actual time=0.062..3150.755 rows=5002 loops=1)
 Planning Time: 0.409 ms
 Execution Time: 3152.412 ms
(15 rows)

我觉得我遗漏了一些东西，因为即使需要许多循环，对于每个用户来说，它也是有限数量的连接，这远小于连接总数（在上面的示例中 - 5000 个用户连接对2,2M 连接总数 ~ 0,25%)。也许某些特定的索引类型？也许还有一些我不知道的技巧？

提前感谢您阅读这么大的问题:)

PPS，使用 Postgres 12 和下一个 postgresql.conf：

# DB Version: 12
# OS Type: mac
# DB Type: web
# Total Memory (RAM): 16 GB
# CPUs num: 8
# Data Storage: ssd

max_connections = 200
shared_buffers = 4GB
effective_cache_size = 12GB
maintenance_work_mem = 1GB
checkpoint_completion_target = 0.7
wal_buffers = 16MB
default_statistics_target = 100
random_page_cost = 1.1
work_mem = 5242kB
min_wal_size = 1GB
max_wal_size = 4GB
max_worker_processes = 8
max_parallel_workers_per_gather = 4
max_parallel_workers = 8
max_parallel_maintenance_workers = 4

Answer 1

只需查看解释计划，我们就会发现优化器的估计完全脱离网格：

• 排序节点估计有 46170 行，而实际有 637677 行
• 索引扫描估计为 2270852 行，而实际有 1722262 行

等等。

vacuum analyze因此，我认为在制定新计划之前，您需要与餐桌上的人脉和朋友建立联系。

也许，它只会有一点帮助，但我们需要先解决这个问题，然后再尝试了解正在发生的事情以及如何在您的上下文中优化该查询。