PostgreSQL : 거대한 그래프를 저장하고 쿼리하기 위해 데이터베이스를 최적화하는 방법

Question

1GB RAM 및 Mac OS X 10.5.8이 장착 된 1.83GHz Intel Core Duo Mac Mini에 PostgreSQL 8.3을 실행하고 있습니다. 내 PostgreSQL 데이터베이스에 거대한 그래프가 저장되어 있습니다. 160 만 개의 노드와 3 천만 개의 에지로 구성됩니다.

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 
... 

은 그래서 아이디 Y에 나가는 링크 X ID 각 노드에 대한 저장과 같습니다처럼 내 데이터베이스 스키마입니다.

모든 나가는 링크를 검색하기위한 시간은 괜찮 :

=# 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 배 이상 느리지 만 수신의 결과 수 내가

,627,211,714,288,458,321를 통해 비트 맵 검색을 사용하지 포스트 그레스를 강제로 시도

=# 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가있는 노드에 대해 들어오는 모든 링크를 포함하는 세 번째 테이블을 생성해야합니까? 그러나 그것은 디스크 공간을 낭비하게 만듭니다. 하지만 SQL 데이터베이스에 익숙하지 않으므로 여기에 기본적인 것을 놓치고 있을까요?

Answer 1

나는 habe이 맞다고 생각합니다.

표를 채운 후에 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); 

을 당신이 임시 테이블을 클러스터 필요가 없습니다 , 그것은 물리적으로 바로 창조 될 것입니다. 하나의 쿼리에는 의미가 없지만 여러 쿼리에 연속적으로 도움이 될 수 있습니다.

Answer 2

나는 그것이 디스크상의 동일한 키 - 레코드의 "밀도"때문이라고 생각합니다. 동일한 id를 가진 레코드는 밀도가 높고 (즉, 블록 수가 적음) 저장되어 있고 링크가 동일한 레코드는 스파 스 (즉, 거대한 블록 수에 분산되어 있음)에 저장되어 있다고 생각합니다. 레코드를 ID 순서대로 삽입 한 경우이 상황이 발생할 수 있습니다.

가정 : 1. (id, link) = (1,1), (1,2), ..., (1,0) 1, 100), (2, 1) ... 및 3. 블록에 50 개의 레코드를 저장할 수 있습니다. (1, 1) ~ (1,50), (1,51) ~ (1,100) 및 (2, 1) ~ (3)의 블록으로 구성된다. 2, 50).

SELECT * FROM edges WHERE id=1 때 2 블록 (# 1, # 2) 만로드하고 스캔합니다. 반면에 SELECT * FROM edges WHERE link=1은 행 수가 동일하더라도 50 개의 블록 (# 1, # 3, # 5, ...)이 필요합니다.

Answer 3

디스크 관련 문제 인 것 같습니다. Postgres는 행이 표시되는지 여부를 확인하기 위해 색인 일치의 튜플을 읽어야합니다 (필요한 정보가 포함되어 있지 않기 때문에 색인에서 수행 할 수 없습니다).

삭제 된 행 및/또는 업데이트 된 행이 많으면 VACUUM ANALYZE (또는 간단히 ANALYZE)가 도움이됩니다. 먼저 실행하고 개선 사항이 있는지 확인하십시오.

CLUSTER도 도움이 될 수 있습니다. 귀하의 예제를 기반으로, 나는 link_idx를 클러스터 키로 사용한다고 말하고 싶습니다. "CLUSTER 가장자리 USING link_idx". ID 쿼리의 성능이 저하 될 수 있습니다 (ID 쿼리가 이미 디스크에서 정렬되어 있으므로 쿼리가 빠를 수도 있습니다). CLUSTER 후에 ANALYZE를 실행해야합니다.

다음 단계에는 메모리 매개 변수 조정, 메모리 추가 또는 더 빠른 디스크 하위 시스템 추가가 포함됩니다.

Answer 4

성능이 좋고 외래 키 제약없이 처리하거나 트리거를 사용하여 수동으로 구현할 수있는 경우 intarray 및 intagg 확장 모듈을 사용해보십시오. 에지 테이블 대신 노드 테이블에 outedges integer[] 열이 있어야합니다. 이렇게하면 테이블에 약 140MB가 추가되므로 모든 것이 메모리에 잘 맞을 것입니다. 역방향 조회의 경우, outedges 열에 GIN 색인을 작성하거나 (280MB 추가) 또는 inedges 열을 추가하십시오.

PostgreSQL은 꽤 높은 행 오버 헤드를 가지므로 순진 에지 테이블은 테이블의 경우 1G 공간을 생성하고 인덱스는 1.5입니다. 데이터 배열 크기를 감안할 때 정수 배열을 사용하여 관계를 저장하는 경우 대부분의 데이터 집합을 캐시에 저장할 수 있습니다. 이것은 어떤 조회든지 blazingly 빨리 할 것이다. 주어진 노드에 대해 어느 방향 으로든 에지를 얻기 위해 약 0.08ms의 검색 시간을 봅니다. 메모리에 모두 들어 맞지 않더라도 여전히 메모리가 차지하는 비중이 높고 캐시 위치가 훨씬 우수합니다.

Answer 5

www.neo4j.org에서이 작업을 시도해 보셨습니까? 이것은 그래프 데이터베이스에서 거의 중요하지 않으며 ms-range에서 usecase에 대한 성능을 제공해야합니다.