最短路径规划

此页面包含一个示例,说明如何使用 shortestPath() 函数规划查询。

在 Cypher® 中规划最短路径可能会根据需要评估的谓词导致不同的查询计划。在内部,如果谓词可以在搜索路径时进行评估,Neo4j 将使用快速双向广度优先搜索算法。因此,当路径上存在通用谓词时,此快速算法总是能确定返回正确答案;例如,在搜索所有节点都具有 Person 标签的最短路径,或没有节点具有 name 属性的最短路径时。

如果谓词需要在判断路径是否有效之前检查整个路径,则此快速算法无法用于查找最短路径,Neo4j 可能不得不求助于使用较慢的穷举深度优先搜索算法来查找路径。这意味着,对于带有非通用谓词的最短路径查询,其查询计划将包含一个备用方案,即在快速算法未成功时运行穷举搜索来查找路径。例如,根据数据情况,对于带有存在谓词的最短路径查询(例如要求至少一个节点包含属性 name='Kevin Bacon'),快速算法可能无法找到答案。在这种情况下,Neo4j 将回退到使用穷举搜索来枚举所有路径并可能返回答案。

这两种算法的运行时间可能相差几个数量级,因此确保对时间关键型查询使用快速方法至关重要。

当规划穷举搜索时,它仍然只在快速算法未能找到任何匹配路径时才执行。快速算法总是首先执行,因为它即使在规划时无法保证,也可能找到一条有效路径。

请注意,在某些情况下,回退到穷举搜索可能会非常耗时;例如当两个节点之间没有最短路径时。因此,在这些情况下,建议将 cypher.forbid_exhaustive_shortestpath 设置为 true,如操作手册 → 配置设置中所述。

最短路径 — 快速算法

示例 1. 使用快速算法评估的查询

此查询可以使用快速算法进行评估 — 因为在评估之前不需要查看整个路径的谓词。

查询
PROFILE
MATCH
  (KevinB:Person {name: 'Kevin Bacon'}),
  (Al:Person {name: 'Al Pacino'}),
  p = shortestPath((KevinB)-[:ACTED_IN*]-(Al))
WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL)
RETURN p
查询计划
Planner COST

Runtime PIPELINED

Runtime version 2025.05

Batch size 128

+---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| Operator            | Details                                                                                        | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline      |
+---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +ProduceResults     | p                                                                                              |              2 |    1 |       0 |                |                    1/0 |     0.252 |               |
| |                   +------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+               |
| +ShortestPath       | p = (KevinB)-[anon_0:ACTED_IN*]-(Al) WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL) |              2 |    1 |      23 |           1688 |                        |           | In Pipeline 1 |
| |                   +------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +MultiNodeIndexSeek | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0,                                    |              2 |    1 |       4 |            120 |                    1/1 |     0.916 | In Pipeline 0 |
|                     | RANGE INDEX Al:Person(name) WHERE name = $autostring_1                                         |                |      |         |                |                        |           |               |
+---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+

Total database accesses: 27, total allocated memory: 1752

最短路径 — 路径上的附加谓词检查

WHERE 子句中用于最短路径模式的谓词在决定最短匹配路径之前进行评估。

示例 2. 考虑使用穷举搜索作为备用方案
查询
MATCH
  (KevinB:Person {name: 'Kevin Bacon'}),
  (Al:Person {name: 'Al Pacino'}),
  p = shortestPath((KevinB)-[*]-(Al))
WHERE length(p) > 1
RETURN p

此查询与上面的查询不同,它需要检查整个路径是否遵循谓词,然后才能知道它是否有效,因此查询计划也将包含回退到较慢的穷举搜索算法。

查询计划
Planner COST

Runtime PIPELINED

Runtime version 2025.05

Batch size 1024

+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| Operator                 | Details                                                     | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline            |
+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults          | p                                                           |              1 |    1 |       0 |                |                        |           |                     |
| |                        +-------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| +AntiConditionalApply    |                                                             |              1 |    1 |       0 |          41464 |                    0/0 |     0.332 | Fused in Pipeline 6 |
| |\                       +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Top                   | anon_1 ASC LIMIT 1                                          |              2 |    0 |       0 |           4280 |                    0/0 |     0.000 | In Pipeline 5       |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Projection            | length(p) AS anon_1                                         |           7966 |    0 |       0 |                |                        |           |                     |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| | +Filter                | length(p) > $autoint_2                                      |           7966 |    0 |       0 |                |                        |           |                     |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| | +Projection            | (KevinB)-[anon_0*]-(Al) AS p                                |          26554 |    0 |       0 |                |                        |           |                     |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| | +VarLengthExpand(Into) | (KevinB)-[anon_0*]-(Al)                                     |          26554 |    0 |       0 |                |                        |           |                     |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| | +Argument              | KevinB, Al                                                  |              2 |    0 |       0 |              0 |                    0/0 |     0.000 | Fused in Pipeline 4 |
| |                        +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +Apply                   |                                                             |              2 |    1 |       0 |                |                    0/0 |     0.026 |                     |
| |\                       +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Optional              | KevinB, Al                                                  |              2 |    1 |       0 |           4840 |                    0/0 |     0.134 | In Pipeline 3       |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +ShortestPath          | p = (KevinB)-[anon_0*]-(Al) WHERE length(p) > $autoint_2    |              1 |    1 |       1 |           1760 |                        |           | In Pipeline 2       |
| | |                      +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Argument              | KevinB, Al                                                  |              2 |    1 |       0 |          24680 |                    0/0 |     0.056 | In Pipeline 1       |
| |                        +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +MultiNodeIndexSeek      | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0, |              2 |    1 |       4 |            120 |                    2/0 |     0.644 | In Pipeline 0       |
|                          | RANGE INDEX Al:Person(name) WHERE name = $autostring_1      |                |      |         |                |                        |           |                     |
+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+

Total database accesses: 5, total allocated memory: 50152

更大的穷举查询计划的工作方式是使用 Apply/Optional 来确保当快速算法未找到任何结果时,生成一个 null 结果,而不是简单地停止结果流。在此之上,规划器将发出一个 AntiConditionalApply,如果路径变量指向 null 而不是路径,则将运行穷举搜索。

在以下情况下,执行计划中将出现 ErrorPlan 运算符:

  • dbms.cypher.forbid_exhaustive_shortestpath 设置为 true

  • 快速算法无法找到最短路径。

示例 3. 防止使用穷举搜索作为备用方案
查询
MATCH
  (KevinB:Person {name: 'Kevin Bacon'}),
  (Al:Person {name: 'Al Pacino'}),
  p = shortestPath((KevinB)-[*]-(Al))
WITH p
WHERE length(p) > 1
RETURN p

此查询与上面的查询一样,需要检查整个路径是否遵循谓词,然后才能知道它是否有效。然而,包含 WITH 子句意味着查询计划将不包含回退到较慢的穷举搜索算法。相反,快速算法找到的任何路径将随后被过滤,这可能导致没有返回任何答案。

查询计划
Planner COST

Runtime PIPELINED

Runtime version 2025.05

Batch size 128

+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| Operator            | Details                                                     | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline      |
+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +ProduceResults     | p                                                           |              1 |    1 |       0 |                |                    1/0 |     0.353 |               |
| |                   +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+               |
| +Filter             | length(p) > $autoint_2                                      |              1 |    1 |       0 |                |                    0/0 |     0.255 |               |
| |                   +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+               |
| +ShortestPath       | p = (KevinB)-[anon_0*]-(Al)                                 |              2 |    1 |       1 |           1760 |                        |           | In Pipeline 1 |
| |                   +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +MultiNodeIndexSeek | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0, |              2 |    1 |       4 |            120 |                    2/0 |     0.371 | In Pipeline 0 |
|                     | RANGE INDEX Al:Person(name) WHERE name = $autostring_1      |                |      |         |                |                        |           |               |
+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+

Total database accesses: 5, total allocated memory: 1824
© . All rights reserved.