PostgreSQL：データベースを最適化して巨大なグラフを保存する方法

Question

私は1.83 GHzのIntel Core Duo Mac Miniに1GBのRAMとMac OS X 10.5.8の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 yに発信リンクX IDを持つノードごとに記憶するようになります。私のようなデータベーススキーマです。

すべての発信リンクを検索するための時間がOK：私は、ノードへの着信リンクを検索する場合は、データベースが100倍以上遅い

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

（受信の結果として得られる数であるが私は

を経由してビットマップスキャンを使用しないのPostgresを強制しようとした

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

：リンクは外部リンクの数）よりもわずか5〜10倍高いです0

が、着信リンクのクエリの速度が改善されなかった。

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

また、私は512メガバイトに24メガバイトから私の共有バッファを増加させたが、それは助けにはなりませんでした。だから私は発信と着信リンクのクエリがそのような非対称な振る舞いを示すのはなぜだろうか？インデックスの選択に何か問題がありますか？または、ID xのノードのすべての受信リンクを保持する3番目のテーブルを作成する方がよいでしょうか？しかし、それはかなりのディスク容量を浪費します。しかし、私はSQLデータベースを初めて使っているので、ここで何か基本的なものが欠けているかもしれません。

Answer 1

私はhabeが正しいと思います。

cluster link_idx on edges; analyze edgesを使用して確認することができます。これで、2番目のクエリは高速になり、最初は遅くなるはずです。

両方のクエリを高速にするには、提案したように、2番目のテーブルを使用して非正規化する必要があります。データをロードした後、この2番目のテーブルをクラスタ化して分析することを忘れないでください。ノードにリンクするすべての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); 

あなたはこの一時テーブルをクラスタ化する必要はありませんそれは創作の権利が物理的に秩序立っているからです。 1つのクエリでは意味をなさないが、連続して複数のクエリで役立つことができます。

Answer 2

私はそれがディスク上の同じキー・レコードの「密度」のためだと思います。 同じIDを持つレコードは密集した（すなわち、少数のブロック）に格納され、同じリンクを持つレコードはまばらな（すなわち、膨大な数のブロックに分散して）格納されていると思います。 idの順にレコードを挿入した場合、このような状況が発生する可能性があります。

仮定： 1. 10,000レコードがあります。 2.（id、link）=（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 3

問題はdisk-ioと関連しているようです。 Postgresは、行が可視かどうかを調べるために、インデックス一致のタプルを読み取る必要があります（これは、必要な情報が含まれていないため、インデックスからは実行できません）。

VACUUM ANALYZE（または単にANALYZE）は、削除された行や更新された行がたくさんある場合に役立ちます。最初に実行し、改善が得られたかどうかを確認してください。

CLUSTERもお手伝いします。あなたの例に基づいて、私はリンクキーとしてlink_idxを使うと言っています。 "CLUSTERエッジUSING link_idx"。ただし、idクエリのパフォーマンスが低下する可能性があります（idクエリはすでにディスク上でソートされているため、速くなる可能性があります）。 CLUSTERの後でANALYZEを実行することを忘れないでください。

次の手順には、メモリパラメータの微調整、メモリの追加、または高速なディスクサブシステムの追加が含まれます。

Answer 4

外的なキーの制約なしに（または手動で実装するためにトリガーを使用して）適切なパフォーマンスが必要な場合は、intarrayとintagg拡張モジュールを試してみてください。エッジテーブルの代わりに、ノードテーブルにoutedges integer[]という列があります。これにより、テーブルに約140MBが追加されるため、メモリ全体がまだまだフィットします。逆引き参照の場合は、アウトエッジ列にGINインデックスを作成するか（280MB追加）、または単にインジェッジ列を追加します。

PostgreSQLは非常に高いローオーバヘッドを持っているので、ナイーブなエッジテーブルはテーブルだけのために1Gのスペースをもたらし、インデックスのためにもう1つの1.5をもたらします。データセットのサイズを考えると、整数配列を使用してリレーションを格納すると、そのデータセットの大部分をキャッシュに入れることができます。これにより、どんな検索も驚くほど速くなります。私は所与のノードに対していずれかの方向にエッジを得るために約0.08msのルックアップ時間を見る。メモリにすべてが収まらない場合でも、メモリの占める割合は大きくなり、キャッシュのローカリティは向上します。

Answer 5

これをwww.neo4j.orgでやってみましたか？これは、グラフデータベースではほとんど問題にならず、msecageでの使用状況のパフォーマンスが得られるはずです。