PostgreSQL:如何优化我的数据库以存储和查询大图

Question

我在1.83 GHz Intel Core Duo Mac Mini上运行PostgreSQL 8.3,内存为1GB,Mac OS X 10.5.8.我在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不要使用Bitmap Scan via

=# 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

我想这是因为磁盘上同密钥记录的"密度".我认为具有相同id的记录存储在密集(即,少数块)中,并且具有相同链接的记录存储在稀疏(即,分布到大量块)中.如果您按id的顺序插入记录,则可能发生这种情况.

假设:1,有10000条记录,2它们存储的顺序,如(ID,路段)=(1,1),(1,2),...,(1,100),( 2,1)......,和3. 50个记录可以存储在一个块中.

在上面的假设中,块#1~#3由记录(1,1)〜(1,50),(1,51)〜(1,100)和(2,1)〜(2,50)组成.分别.

当您SELECT * FROM edges WHERE id=1,只需要加载和扫描2个块(#1,#2).另一方面,SELECT * FROM edges WHERE link=1即使行数相同,也需要50个块(#1,#3,#5,...).

Answer 2

我认为哈贝是对的。

cluster link_idx on edges; analyze edges您可以在填写表格后使用来检查这一点。现在第二个查询应该很快，第一个查询应该很慢。

为了快速执行这两个查询，您必须按照您的建议使用第二个表来进行非规范化。只需记住在加载数据后对第二个表进行聚类和分析，以便链接到节点的所有egdes都将被物理分组。

如果您不会一直查询该表，并且不想存储和备份第二个表，那么您可以在查询之前临时创建它：

create temporary table egdes_backwards
  as select link, id from edges order by link, id;
create index edges_backwards_link_idx on edges_backwards(link);

您不必对该临时表进行集群，因为它将在创建时进行物理排序。它对于一个查询没有意义，但对于连续的多个查询有帮助。