PostgreSQL: Come ottimizzare il mio database per l'archiviazione e l'interrogazione di un enorme grafico

Question

Io corro PostgreSQL 8.3 su un 1,83 GHz Intel Core Duo Mac Mini con 1GB di RAM e Mac OS X 10.5.8. Ho conservato un enorme grafico nel mio database PostgreSQL. Consiste di 1,6 milioni di nodi e 30 milioni di spigoli. Il mio schema del database è simile:

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); 

I dati nella tabella i bordi assomiglia

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

Quindi memorizza per ogni nodo con id x il link in uscita per id y.

Il tempo per la ricerca tutti i link in uscita è ok:

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

Tuttavia, se cerco per i collegamenti in entrata a un nodo, il database è più di 100 volte più lento (anche se il numero risultante di entrata link è il solo 5-10 volte superiore al numero di link in uscita):

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

ho cercato di forzare Postgres non utilizzare una scansione bitmap tramite

=# set enable_bitmapscan = false; 

ma la velocità della query per i link in entrata non è migliorata:

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

ho anche aumentato il mio buffer condivisi da 24MB a 512MB, ma non ha aiutato. Quindi mi chiedo perché le mie query per i link in uscita e in entrata mostrano un comportamento asimmetrico simile? C'è qualcosa di sbagliato nella mia scelta di indici? O dovrei creare meglio una terza tabella contenente tutti i link in entrata per un nodo con id x? Ma sarebbe uno spreco di spazio su disco. Ma dato che sono nuovo nei database SQL forse mi manca qualcosa di base qui?

Answer 1

penso habe è giusto.

È possibile controllare questo utilizzando cluster link_idx on edges; analyze edges dopo aver riempito la tabella. Ora la seconda query dovrebbe essere veloce e la prima dovrebbe essere lenta.

Per avere entrambe le query velocemente è necessario denormalizzare utilizzando una seconda tabella, come da lei proposto. Ricorda di raggruppare e analizzare questa seconda tabella dopo aver caricato i dati, quindi tutti gli URL che collegano a un nodo verranno raggruppati fisicamente.

Se non vuoi interrogare questo tutto il tempo e non si desidera memorizzare e il backup questo secondo tavolo allora si può creare temporaneamente prima interrogazione:

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); 

Non è necessario a raggrupparsi questa tabella temporanea , poiché sarà fisicamente ordinato proprio sulla creazione. Non ha senso per una query, ma può aiutare per diverse query di fila.

Answer 2

Credo che sia a causa di una “densità” delle stesse-chiave record sul disco. Penso che i record con lo stesso id siano memorizzati in denso (cioè pochi numero di blocchi) e quelli con lo stesso collegamento siano memorizzati in file sparsi (cioè distribuiti in un numero enorme di blocchi). Se sono stati inseriti record nell'ordine di id, questa situazione può verificarsi.

Presuppone che: 1. ci sono 10.000 record, 2. sono memorizzati nell'ordine come (id, link) = (1, 1), (1, 2), ..., (1, 100), (2, 1) ... e 3. 50 record possono essere memorizzati in un blocco.

Nell'assunzione sopra riportata, il blocco # 1 ~ # 3 è costituito dai record (1, 1) ~ (1, 50), (1, 51) ~ (1, 100) e (2, 1) ~ (2, 50) rispettivamente.

Quando si SELECT * FROM edges WHERE id=1, solo 2 blocchi (n. 1, n. 2) devono essere caricati e scansionati. D'altra parte, richiede SELECT * FROM edges WHERE link=1 50 blocchi (# 1, # 3, # 5, ...), anche se il numero di righe è stesso.

Answer 3

Il tuo problema sembra essere disk-io correlato. Postgres deve leggere le tuple delle corrispondenze dell'indice per vedere se la riga è visibile o meno (questo non può essere fatto da un indice in quanto non contiene le informazioni necessarie).

VACUUM ANALYZE (o semplicemente ANALYZE) è di aiuto se si dispone di molte righe eliminate e/o righe aggiornate. Esegui prima e vedi se ottieni qualche miglioramento.

CLUSTER potrebbe anche aiutare. In base ai tuoi esempi, direi usando link_idx come chiave di cluster. "Bordi CLUSTER UTILIZZO link_idx". Potrebbe tuttavia peggiorare le prestazioni delle tue query ID (le tue query di identificazione potrebbero essere veloci perché sono già ordinate su disco). Ricordarsi di eseguire ANALYZE dopo CLUSTER.

I passaggi successivi includono la regolazione fine dei parametri di memoria, l'aggiunta di ulteriore memoria o l'aggiunta di un sottosistema di dischi più veloce.

Answer 4

Se sono necessarie buone prestazioni e possono gestire senza vincoli di chiave esterna (o utilizzare trigger per implementarle manualmente), provare i moduli di estensione intarray e intagg. Al posto della tabella dei bordi è presente una colonna outedges integer[] nella tabella dei nodi. Ciò aggiungerà circa 140MB alla tabella, quindi l'intera cosa probabilmente si adatterà ancora alla memoria. Per le ricerche inverse, creare un indice GIN sulla colonna delle fughe (per ulteriori 280 MB) o aggiungere semplicemente una colonna inedite.

Postgresql ha un overhead di riga piuttosto elevato, quindi la tabella dei bordi ingenua risulterà in 1G di spazio per il solo tavolo, + un altro 1,5 per gli indici. Data la dimensione del set di dati, si ha una buona possibilità di avere la maggior parte di esso nella cache se si utilizzano array di interi per memorizzare le relazioni. Questo renderà tutte le ricerche incredibilmente veloci. Vedo circa 0,08 ms di tempo di ricerca per ottenere bordi in entrambe le direzioni per un dato nodo. Anche se non si adatta tutto in memoria, si avrà ancora una frazione maggiore nella memoria e molto meglio la localizzazione della cache.

Answer 5

avete provato a fare questo in www.neo4j.org? Questo è quasi banale in un database grafico e dovrebbe darti prestazioni sul tuo caso in serie ms.