español - Buscando la consulta Neo4J Cypher para rutas largas pero(casi) únicas

neo4j tutorial

Question

Tenemos una base de datos Neo4J que representa un proceso evolutivo con aproximadamente 100K nodos y 200K relaciones. Los nodos son individuos en generaciones, y los bordes representan relaciones entre padres e hijos. El objetivo principal es poder tomar uno o nodos de interés en la generación final y explorar su historia evolutiva (más o menos, "¿cómo llegamos aquí?").

La primera consulta "obvia" para encontrar todos sus antepasados ​​no funciona porque hay demasiados antepasados ​​y rutas posibles a través de ese espacio:

match (a)-[:PARENT_OF*]->(c {is_interesting: true}) 
return distinct a;

Así que hemos preprocesado los datos de modo que algunos bordes estén marcados como "especiales", de modo que casi todos los nodos tienen como máximo un borde principal "especial", aunque en ocasiones ambos bordes principales están marcados como "especiales". Mi esperanza, entonces, era que esta consulta generaría (eficientemente) el camino (casi) único a lo largo de los bordes "especiales":

match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

Esto, sin embargo, sigue siendo muy lento.

Esto es frustrante porque "como ser humano", la lógica es simple: comience desde el pequeño número de nodos "interesantes" (a menudo 1, nunca más de unas pocas docenas), y persiga a lo largo de los bordes "especiales" casi siempre únicos. Suponiendo un número muy bajo de nodos con dos padres "especiales", esto debería ser algo así como O (N) donde N es el número de generaciones atrás en el tiempo.

En Neo4J, sin embargo, retroceder 25 pasos desde un nodo "interesante" único donde cada paso es único, sin embargo, toma 30 segundos, y una vez que hay una sola bifurcación (donde ambos padres son "especiales") empeora mucho más rápido que un función de pasos. 28 pasos (que nos llevan a la primera bifurcación) demoran 2 minutos, 30 (cuando todavía hay una sola bifurcación) tardan 6 minutos, y ni siquiera he pensado en probar los 100 pasos completos hasta el comienzo de la simulación.

Algunos trabajos similares del año pasado parecieron tener un mejor rendimiento, pero utilizamos una variedad de etiquetas de borde (por ejemplo, (a)-[:SPECIAL_PARENT_OF*]->(c) así como (a)-[:PARENT_OF*]->(c) ) en lugar de usar campos de datos en los bordes. ¿No es una buena idea consultar los valores del campo de relación? Tenemos bastantes valores diferentes vinculados a una relación en este modelo (algunos booleanos, algunos numéricos) y esperábamos / asumíamos que podíamos usarlos para limitar de manera eficiente las búsquedas, pero tal vez ese no era realmente el caso.

Las sugerencias sobre cómo ajustar nuestro modelo o consultas serían muy apreciadas.

Actualización Debería haber mencionado, todo esto es con Neo4J 2.1.7. Voy a probar 2.2 con la sugerencia de Brian Underwood e informaré.

Answer 1

Después de explorar cosas con las herramientas de creación de perfiles en Neo4J 2.2 (gracias a Brian Underwood por la sugerencia) está bastante claro que (por el momento) Neo4J no realiza ninguna actividad de filtrado previo en el borde, lo que lleva a desagradables explosiones combinatorias con largos trayectos .

Por ejemplo, la consulta original:

match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

encuentra todos los caminos de aa c y luego elimina los que tienen bordes que no son special . Dado que hay muchos millones de caminos de aa c , esto es totalmente inviable.

Si, en cambio, agrego un borde IS_SPECIAL donde haya un borde PARENT_OF que PARENT_OF {special: true} , las consultas se vuelven realmente rápidas, lo que me permite retrasar unas 100 generaciones en menos de un segundo.

Esta consulta crea todos los bordes nuevos:

match (a)-[r:PARENT_OF {special: true}]->(b) 
create (a)-[:IS_SPECIAL]->(b);

y toma menos de un segundo para agregar 91K relaciones en nuestro gráfico.

Entonces

match (c {is_interesting: true}) 
with c 
match (a)-[:IS_SPECIAL*]->(c) 
return distinct a;

toma menos de un segundo para encontrar los 112 nodos a lo largo de la ruta "especial" de un nodo de destino único c . Coincidir c primero y limitar el conjunto de nodos with c parece ser también importante, ya que Neo4J tampoco parece filtrar previamente las propiedades del nodo, y si hay varios nodos objetivo "interesantes" las cosas se vuelven mucho más lentas.

Answer 2

He tenido un poco de suerte al especificar un límite en la longitud de la ruta. Entonces, si sabes que nunca son más de 30 saltos, podrías intentarlo:

MATCH (c {is_interesting: true})
WITH c
MATCH (a)-[:PARENT_OF*1..30]->c 
RETURN DISTINCT a

Además, ¿hay un índice en la propiedad is_interesting ? Eso también podría causar lentitud, seguro.

¿Qué versión de Neo4j estás usando? Si está utilizando o si actualiza a la versión 2.2.0, puede utilizar las nuevas herramientas de creación de perfiles de consultas:

http://neo4j.com/docs/2.2.0/how-do-i-profile-a-query.html

Además, si los usa en la consola web, obtendrá un buen árbol gráfico (término técnico) que muestra cada paso.