optimization - PostgreSQL:如何优化我的数据库以存储和查询一个巨大的图形

Question

我在配备 1GB 内存和 Mac OS X 10.5.8 的 1.83 GHz Intel Core Duo Mac Mini 上运行 PostgreSQL 8.3。我在我的 PostgreSQL 数据库中存储了一个巨大的图表。它由 160 万个节点和 3000 万条边组成。我的数据库架构如下:

CREATE TABLE nodes (id INTEGER PRIMARY KEY,title VARCHAR(256));
CREATE TABLE edges (id INTEGER,link INTEGER,PRIMARY KEY (id,link));
CREATE INDEX id_idx ON edges (id);
CREATE INDEX link_idx ON edges (link);

表格边缘的数据看起来像

id link 
1  234
1  88865
1  6
2  365
2  12
...

因此它为每个具有 id x 的节点存储到 id y 的传出链接。

搜索所有外链的时间是可以的:

=# explain analyze select link from edges where id=4620;
                           QUERY PLAN                                                        
    ---------------------------------------------------------------------------------
     Index Scan using id_idx on edges  (cost=0.00..101.61 rows=3067 width=4) (actual time=135.507..157.982 rows=1052 loops=1)
       Index Cond: (id = 4620)
     Total runtime: 158.348 ms
    (3 rows)

但是，如果我搜索一个节点的传入链接，数据库会慢 100 多倍(尽管由此产生的传入链接数只比传出链接数高 5-10 倍):

=# explain analyze select id from edges where link=4620;
                         QUERY PLAN                                                           
----------------------------------------------------------------------------------
     Bitmap Heap Scan on edges  (cost=846.31..100697.48 rows=51016 width=4) (actual time=322.584..48983.478 rows=26887 loops=1)
       Recheck Cond: (link = 4620)
       ->  Bitmap Index Scan on link_idx  (cost=0.00..833.56 rows=51016 width=0) (actual time=298.132..298.132 rows=26887 loops=1)
             Index Cond: (link = 4620)
     Total runtime: 49001.936 ms
    (5 rows)

我试图强制 Postgres 不通过使用位图扫描

=# set enable_bitmapscan = false;

但是查询传入链接的速度并没有提高:

=# explain analyze select id from edges where link=1588;
                      QUERY PLAN                                                           
-------------------------------------------------------------------------------------------
 Index Scan using link_idx on edges  (cost=0.00..4467.63 rows=1143 width=4) (actual time=110.302..51275.822 rows=43629 loops=1)
   Index Cond: (link = 1588)
 Total runtime: 51300.041 ms
(3 rows)

我还将我的共享缓冲区从 24MB 增加到 512MB，但没有帮助。所以我想知道为什么我对传出和传入链接的查询显示出这种不对称行为？我选择的索引有问题吗？还是我应该更好地创建第三个表来保存 ID 为 x 的节点的所有传入链接？但这将是相当浪费磁盘空间。但是因为我是 SQL 数据库的新手，所以我可能在这里遗漏了一些基本的东西？

Answer 1

我猜这是因为磁盘上相同 key 记录的“密度”。 我认为具有相同 id 的记录存储在密集的(即，很少的 block )，而具有相同链接的记录存储在稀疏的(即，分布到大量的 block )。 如果按照id的顺序插入记录，就会出现这种情况。

假设: 1.有10,000条记录， 2. 它们按顺序存储，例如 (id, link) = (1, 1), (1, 2),..., (1, 100), (2, 1)..., and 3. 一个区 block 可以存储50条记录。

在上面的假设中， block #1~#3由记录(1, 1)~(1, 50)，(1, 51)~(1, 100)和(2, 1)~(2 , 50) 分别。

当您SELECT * FROM edges WHERE id=1 时，仅加载和扫描 2 个 block (#1、#2)。 另一方面，SELECT * FROM edges WHERE link=1 需要 50 个 block (#1、#3、#5、...)，即使行数相同也是如此。