PostgreSQL: Cómo optimizar mi base de datos para almacenar y consultar un enorme gráfico

Question

Estoy ejecutando PostgreSQL 8.3 en un Intel Core Duo Mac Mini de 1,83 GHz con 1 GB de RAM y Mac OS X 10.5.8. Tengo un gran gráfico guardado en mi base de datos PostgreSQL. Consta de 1,6 millones de nodos y 30 millones de bordes. Mi esquema de base es como:

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

Los datos en los bordes de la mesa parece

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

Así que almacena para cada nodo con id x el enlace de salida de Identificación y.

El tiempo para buscar todos los enlaces salientes es aceptable:

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

Sin embargo, si la búsqueda de los enlaces entrantes a un nodo, la base de datos es más de 100 veces más lento (aunque el número resultante de entrantes enlaces es sólo 5-10 veces mayor que el número de enlaces salientes):

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

traté de forzar Postgres no utilizar una exploración de mapa de bits a través de

=# set enable_bitmapscan = false; 

pero la velocidad de la consulta para los enlaces entrantes no mejoró:

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

También he aumentado mis buffers compartidos desde 24 MB a 512 MB, pero no sirvió de nada. Entonces, me pregunto por qué mis consultas de enlaces salientes y entrantes muestran un comportamiento tan asimétrico. ¿Hay algún problema con mi elección de índices? ¿O debería crear una tercera tabla que contenga todos los enlaces entrantes para un nodo con id x? Pero eso sería un desperdicio de espacio en el disco. Pero dado que soy nuevo en las bases de datos SQL, quizás me esté perdiendo algo básico aquí.

Answer 1

Creo que habe tiene razón.

Puede verificar esto usando cluster link_idx on edges; analyze edges después de llenar la tabla. Ahora la segunda consulta debe ser rápida y la primera debe ser lenta.

Para tener ambas consultas rápido, tendrá que desnormalizarse usando una segunda tabla, como ha propuesto. Solo recuerde agrupar y analizar esta segunda tabla después de cargar sus datos, de modo que todos los egdes que se vinculan a un nodo se agrupen físicamente.

Si no va a consultar esta todo el tiempo y que no desea almacenar y copia de seguridad de esta segunda tabla a continuación, se pueden crear de forma temporal antes de consultar:

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

Usted no tiene que agruparse esta tabla temporal , ya que se ordenará físicamente desde la creación. No tiene sentido para una consulta, pero puede ayudar para varias consultas en una fila.

Answer 2

Supongo que es debido a la "densidad" de los mismos registros clave en el disco. Creo que los registros con el mismo ID se almacenan en densos (es decir, pocos) y aquellos con el mismo enlace se almacenan en escasos (es decir, distribuidos en un gran número de bloques). Si ha insertado registros en el orden de identificación, esta situación puede ocurrir.

Supongamos que: 1. hay 10.000 registros, 2. sino que están almacenados en el orden tal como (id, enlace) = (1, 1), (1, 2), ..., (1, 100), (2, 1) ... y 3. Se pueden almacenar 50 registros en un bloque.

En la suposición anterior, el bloque # 1 ~ # 3 consta de los registros (1, 1) ~ (1, 50), (1, 51) ~ (1, 100) y (2, 1) ~ (2, 50) respectivamente.

Cuando SELECT * FROM edges WHERE id=1, solo se carguen y escaneen 2 bloques (n. ° 1, n. ° 2). Por otro lado, SELECT * FROM edges WHERE link=1 requiere 50 bloques (# 1, # 3, # 5, ...), aunque el número de filas sea el mismo.

Answer 3

Parece que su problema está relacionado con el disco. Postgres tiene que leer las tuplas de las coincidencias de índice para ver si la fila es visible (esto no se puede hacer desde un índice ya que no contiene la información necesaria).

VACUUM ANALYZE (o simplemente ANALYZE) le ayudará si tiene muchas filas eliminadas y/o filas actualizadas. Ejecútelo primero y vea si obtiene alguna mejora.

CLUSTER también podría ayudar. De acuerdo con sus ejemplos, diría que usa link_idx como la clave del clúster. "CLUSTER bordes USANDO link_idx". Sin embargo, podría degradar el rendimiento de sus consultas de id. (Sus consultas de id podrían ser rápidas porque ya están ordenadas en el disco). Recuerde ejecutar ANALYZE después de CLUSTER.

Los próximos pasos incluyen ajustar los parámetros de memoria, agregar más memoria o agregar un subsistema de disco más rápido.

Answer 4

Si necesita un buen rendimiento y puede tratar sin restricciones de clave externa (o utilizar disparadores para implementarlos manualmente) pruebe los módulos de extensión intarray y intagg. En lugar de la tabla de bordes, tiene una columna outedges integer[] en la tabla de nodos. Esto agregará unos 140MB a la tabla, por lo que toda la información probablemente se ajuste a la memoria. Para las búsquedas inversas, cree un índice GIN en la columna outedges (para 280MB adicionales) o simplemente agregue una columna inedges.

Postgresql tiene una altura de fila muy alta por lo que la tabla de bordes ingenuos dará como resultado 1G de espacio solo para la tabla, + otro 1.5 para los índices. Dado el tamaño de su conjunto de datos, tiene muchas posibilidades de tener la mayor parte en caché si utiliza matrices de enteros para almacenar las relaciones. Esto hará que las búsquedas sean increíblemente rápidas. Veo unos tiempos de búsqueda de 0.08ms para obtener los bordes en cualquier dirección para un nodo dado. Incluso si no lo incluye todo en la memoria, todavía tendrá una fracción más grande en la memoria y una localidad de caché mucho mejor.

Answer 5

has intentado hacer esto en www.neo4j.org? Esto es casi trivial en una base de datos de gráficos y debería proporcionarle rendimiento en su uso en ms-range.