Edit

SHORTEST_PATH (Transact-SQL)

  • Article

Applies to: SQL Server 2019 (15.x) and later Azure SQL Database Azure SQL Managed Instance

Specifies a search condition for a graph, which is searched recursively or repetitively. SHORTEST_PATH can be used inside MATCH with graph node and edge tables, in the SELECT statement.

Transact-SQL syntax conventions

Shortest path

The SHORTEST_PATH function lets you find:

  • A shortest path between two given nodes/entities
  • Single source shortest path(s).
  • Shortest path from multiple source nodes to multiple target nodes.

It takes an arbitrary length pattern as input and returns a shortest path that exists between two nodes. This function can only be used inside MATCH. The function returns only one shortest path between any two given nodes. If there exist, two or more shortest paths of the same length between any pair of source and destination node(s), the function returns only one path that was found first during traversal. An arbitrary length pattern can only be specified inside a SHORTEST_PATH function.

For complete syntax, refer to MATCH (SQL Graph).

FOR PATH

FOR PATH must be used with any node or edge table name in the FROM clause, which participates in an arbitrary length pattern. FOR PATH tells the engine that the node or edge table returns an ordered collection representing the list of nodes or edges found along the path traversed. The attributes from these tables can't be projected directly in the SELECT clause. To project attributes from these tables, graph path aggregate functions must be used.

Arbitrary length pattern

This pattern includes the nodes and edges that must be traversed repeatedly until either:

  • The desired node is reached.
  • The maximum number of iterations as specified in the pattern is met.

The following two pattern quantifiers are supported:

  • '+': Repeat the pattern 1 or more times. Terminate as soon as a shortest path is found.
  • {1,n}: Repeat the pattern 1 to n times. Terminate as soon as a shortest is found.

LAST_NODE

LAST_NODE() function allows chaining of two arbitrary length traversal patterns. It can be used in scenarios where:

  • More than one shortest path patterns are used in a query and one pattern begins at the LAST node of the previous pattern.
  • Two shortest path patterns merge at the same LAST_NODE().

Graph path order

Graph path order refers to the order of data in the output path. The output path order always starts at the nonrecursive part of the pattern followed by the nodes/edges that appear in the recursive part. The order in which the graph is traversed during query optimization/execution has nothing to do with the order printed in the output. Similarly, the direction of arrow in the recursive pattern also doesn't affect the graph path order.

Graph path aggregate functions

Since the nodes and edges involved in arbitrary length pattern return a collection (of node(s) and edge(s) traversed in that path), users can't project the attributes directly using the conventional tablename.attributename syntax. For queries where it's required to project attribute values from the intermediate node or edge tables, in the path traversed, use following graph path aggregate functions: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX and COUNT. The general syntax to use these aggregate functions in the SELECT clause is:

<GRAPH_PATH_AGGREGATE_FUNCTION>(<expression> , <separator>)  <order_clause>

    <order_clause> ::=
        { WITHIN GROUP (GRAPH PATH) }

    <GRAPH_PATH_AGGREGATE_FUNCTION> ::=
          STRING_AGG
        | LAST_VALUE
        | SUM
        | COUNT
        | AVG
         | MIN
        | MAX

STRING_AGG

The STRING_AGG function takes an expression and separator as input and returns a string. Users can use this function in the SELECT clause to project attributes from the intermediate nodes or edges in the path traversed.

LAST_VALUE

To project attributes from the last node of path traversed, LAST_VALUE aggregate function can be used. It's an error to provide edge table alias as an input to this function, only node table names or aliases can be used.

Last Node: The last node refers to the node that appears last in the path traversed, irrespective of the direction of arrow in the MATCH predicate. For example: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Here the last node in the path is the last visited P node.

In the MATCH(SHORTEST_PATH((n<-(e)-)+p)) pattern, the last node is the last N node visited.

SUM

This function returns the sum of provided node/edge attribute values or expression that appeared in the traversed path.

COUNT

This function returns the number of non-null values of the specified node/edge attribute in the path. The COUNT function doesn't support the * operator - attempted usage of * results in a syntax error.

{  COUNT( <expression> )  <order_clause>  }

AVG

Returns the average of provided node/edge attribute values or expression that appeared in the traversed path.

MIN

Returns the minimum value from the provided node/edge attribute values or expression that appeared in the traversed path.

MAX

Returns the maximum value from the provided node/edge attribute values or expression that appeared in the traversed path.

Remarks

  • The SHORTEST_PATH function can only be used inside MATCH.
  • The LAST_NODE function is only supported inside SHORTEST_PATH.
  • The SHORTEST_PATH function returns any one shortest path between nodes. It currently doesn't support returning all shortest paths between nodes; it also doesn't support returning all paths between nodes.
  • The SHORTEST_PATH implementation finds an unweighted shortest path.
  • In some cases, bad plans may be generated for queries with higher number of hops, which results in higher query execution times. Evaluate if query hints like OPTION (HASH JOIN) and / or OPTION (MAXDOP 1) help.

Examples

For the example queries shown here, we use the node and edge tables created in SQL Graph sample

A. Find shortest path between two people

In the following example, we find shortest path between Jacob and Alice. We need the Person node and friendOf edge created from SQL Graph sample.

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

B. Find shortest path from a given node to all other nodes in the graph.

The following example finds all the people that Jacob is connected to in the graph and the shortest path starting from Jacob to all those people.

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
AND Person1.name = 'Jacob'

C. Count the number of hops/levels traversed to go from one person to another in the graph.

The following example finds the shortest path between Jacob and Alice and prints the number of hops it takes to go from Jacob to Alice.

 SELECT PersonName, Friends, levels
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

D. Find people 1-3 hops away from a given person

The following example finds the shortest path between Jacob and all the people that Jacob is connected to in the graph one to three hops away from him.

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
AND Person1.name = 'Jacob'

E. Find people exactly two hops away from a given person

The following example finds the shortest path between Jacob and people who are exactly two hops away from him in the graph.

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
    AND Person1.name = 'Jacob'
) Q
WHERE Q.levels = 2

F. Find people 1-3 hops away from a given person, who also like a specific restaurant

The following example finds the shortest path between Jacob and all the people that he's connected to in the graph 1-3 hops away from him. The query also filters connected people by their liking a given restaurant. In the below sample, that LAST_NODE(Person2) returns the final node for each shortest path. The "last" Person node obtained from LAST_NODE can then be "chained" for further traversals to find the restaurant(s) that they like.

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
    Restaurant.name
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2,
    likes,
    Restaurant
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}) AND LAST_NODE(Person2)-(likes)->Restaurant )
AND Person1.name = 'Jacob'
AND Restaurant.name = 'Ginger and Spice'

G. Find the shortest path from a given node to all other nodes in the graph, excluding "loops"

The following example finds all the people that Alice is connected to in the graph and the shortest path starting from Alice to all those people. The example explicitly checks for "loops" where the start and the end node of the path happen to be the same.

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Alice'
) AS Q
WHERE Q.LastNode != 'Alice'

Next steps