{"id":85165,"date":"2019-09-11T14:35:45","date_gmt":"2019-09-11T14:35:45","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=85165"},"modified":"2021-06-03T16:48:18","modified_gmt":"2021-06-03T16:48:18","slug":"sql-server-2019-graph-database-and-shortest_path","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/sql-server-2019-graph-database-and-shortest_path\/","title":{"rendered":"SQL Server 2019 Graph Database and SHORTEST_PATH"},"content":{"rendered":"

My crystal ball seems to be working again: The new addition to SQL Server 2019, shortest_path<\/code>, was the subject of many of the technical sessions I delivered as one of the missing features of SQL Server Graph Database.<\/p>\n

I will use an example that is similar to the first article<\/a> I wrote on this topic. You can create the database and tables needed for this article using this script<\/a>. Maybe you would also like to read the previous blog post<\/a> about some recent improvements in Graph Databases.<\/p>\n

Since the data is essentially a graph, a solution to visually show the results is helpful. An application like Gephi to can be used to view the graph. (You can download this application here<\/a>.) To use Gephi with SQL Server, make sure that the TCP\/IP protocol and mixed authentication are enabled. The app only supports SQL authentication, so you will need a SQL Server login to connect.<\/p>\n

Using Gephi<\/h2>\n

Follow these steps to view the graph in Gephi.<\/p>\n

    \n
  • After opening Gephi, select New Project<\/em> on the Welcome<\/em> screen<\/li>\n
  • On the File<\/em> menu, select Import Database->Edge List. <\/em>This will open the Database settings <\/em>screen.<\/li>\n<\/ul>\n

    \"A<\/p>\n

      \n
    • In the Configuration Name<\/em> field, create a name for the configuration, such as SQLServer2019.<\/em><\/li>\n
    • In the Driver<\/em> field, select SQL Server.<\/em><\/li>\n
    • In the Host<\/em> field, insert the machine\/instance name of your SQL Server<\/li>\n
    • In the Port<\/em> field, enter the port used, typically 1433. If you\u2019re not sure, look for the port number in the SQL Server Configuration Manager program.<\/li>\n
    • In the Database<\/em> field, insert the name of the database which contains the graph tables which is probably GraphDemo<\/em> if you have been following along<\/li>\n
    • In the Username<\/em> field, enter the username of a SQL Server login with SELECT<\/em> permission to the tables in the GraphDemo database.<\/li>\n
    • In the Password<\/em> field, insert the password for the SQL login.<\/li>\n<\/ul>\n

      In addition to the configuration required to connect to SQL Server, the Database settings<\/em> screen also requires two queries: One to retrieve the list of nodes from the server and another to retrieve the list of edges from the server. I\u2019ll explain those queries next.<\/p>\n

      The screen itself contains information at the top of the dialog about the columns the queries need to return, and it’s important to notice these columns are case sensitive.<\/p>\n

      The nodes table in SQL Server has the pseudo-column $node_id<\/code>, which is a JSON column. A good option is to extract the id from the JSON and use the MemberName<\/code> as the label for the node. The query will look like this:<\/p>\n

      SELECT\u00a0Json_value($node_id,\u00a0'$.id')\u00a0AS\u00a0id,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0membername\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0AS\u00a0label\u00a0\r\nFROM\u00a0\u00a0\u00a0forummembers\u00a0<\/pre>\n
      The edge query has also to extract the id from\u00a0 $to_node<\/code> and $from_node<\/code>,<\/strong> but besides that, you need to filter the nodes returned, because the nodes table from the previous article has a relation between two members and between members and messages. For this example, return only the relation between two members. Here is the query:<\/p>\n
      SELECT\u00a0Json_value($from_id,\u00a0'$.id')\u00a0AS\u00a0source,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Json_value($to_id,\u00a0'$.id')\u00a0\u00a0\u00a0AS\u00a0target\u00a0\r\nFROM\u00a0\u00a0\u00a0likes\u00a0\r\nWHERE\u00a0Json_value($from_id,\u00a0'$.table')\u00a0=\u00a0'ForumMembers'\u00a0\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0AND\u00a0Json_value($to_id,\u00a0'$.table')\u00a0=\u00a0'ForumMembers'\u00a0<\/pre>\n
      It’s important to note that the source and target id’s in the edge query need to match with the ids in the node query. There are some additional columns that could be used, but for this example, you\u2019ll only need these.<\/p>\n
      The final configuration will look similar to the following image:<\/p>\n
      <\/p>\n
      After you click OK<\/em>, the next window, Import Report<\/em>, involves many details but they will not be covered in this article. What’s important here is the number of nodes and edges found, confirming that the queries are correct. However, there is only a single step to be done on this screen:<\/p>\n
      Select the option Append to existing workspace<\/em>.<\/p>\n
      \"A<\/p>\n
      After this first screen, you will see the Workspace1<\/em> and Preview<\/em> tabs and Preview Settings<\/em> window. It\u2019s time to build the graph.<\/p>\n
      \"A<\/p>\n
      Click on the Refresh<\/em> button inside the Preview Settings<\/em> pane. This will result in an image similar to the one below. Note that yours may look different, but in the next step, you can verify that the nodes are connected correctly.<\/p>\n
      \"A<\/p>\n
      Improve this graph just a bit by making these changes in the Preview Settings<\/em> tab.<\/p>\n
        \n
      • Change the Opacity<\/em> property to 0 under Nodes<\/em>.<\/li>\n
      • Mark the Show Labels<\/em> property under Node Labels.<\/em><\/li>\n
      • Change the Outline opacity<\/em> under Node Labels<\/em> to 0<\/li>\n<\/ul>\n
        After clicking refresh, the graph will change to something like the image below:<\/p>\n
        \"A<\/p>\n
        As you may notice, even a simple graph with a small amount of data can be quite complex to identify information such as the shortest path between two nodes in the graph. That’s why you need a tool to calculate this, and SQL Server 2019 can make this kind of calculation.<\/p>\n
        Calculating the Path<\/h2>\n
        When you think about a function to calculate the shortest path between two points, you may think that it will be a simple function. To make this calculation work, however, you need way more than a simple function. You must establish paths among the graph data. The data has many paths, and each one has many nodes with a beginning and an end. Each path is a group of nodes, in some ways like the group by function.<\/p>\n
        One similarity, for example, is that you can’t read the column directly from the path. You need to apply aggregation functions to the set of nodes that are part of the path to read the information.<\/p>\n
        The syntax to build this query resembles the GROUP BY<\/code> clause, requiring you to use aggregate functions to make calculations on every (shortest) path of nodes, getting grouped results.<\/p>\n
        To make this simpler, start to build the query over the model piece by piece. First, the From<\/code> clause<\/p>\n
        FROM\u00a0\r\n\u00a0\u00a0\u00a0\u00a0ForumMembers\u00a0P1,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0ForumMembers\u00a0FOR\u00a0PATH\u00a0as\u00a0P2,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0Likes\u00a0FOR\u00a0PATH\u00a0as\u00a0IPO<\/pre>\n
        The FOR<\/code> PATH<\/code> expression in the edge and node tables indicates these tables will be used to calculate paths, a grouping, in other words. Over the columns of these particular tables you can only apply aggregation functions; you can’t retrieve the columns directly.<\/p>\n
        You may have noticed the node table appears twice in the query, one using the FOR<\/code> PATH<\/code> and another without using the FOR<\/code> PATH<\/code>. Since you can’t retrieve columns directly from the FOR<\/code> PATH<\/code> tables, you can include the nodes table twice to retrieve individual values of the node columns, usually for the start node of the path.<\/p>\n
        Now analyse the list of columns and expressions in the SELECT<\/code> list:<\/p>\n
        SELECT\u00a0\r\n\u00a0\u00a0\u00a0\u00a0P1.MemberID,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0P1.MemberName,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0STRING_AGG(P2.MemberName,\r\n        '->')\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0AS\u00a0[MemberName],\u00a0\r\n\u00a0\u00a0\u00a0\u00a0LAST_VALUE(P2.MemberName)\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0\r\n        AS\u00a0FinalMemberName,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0COUNT(P2.MemberId)\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0AS\u00a0Levels<\/pre>\n
        The first two columns come from the P1 table, which is not marked as FOR<\/code> PATH<\/code>. The MemberID<\/em> and MemberName<\/em> columns are from the first node of the path. The WHERE<\/code> clause will also expose this.<\/p>\n
        The other three expressions use aggregate functions. They use the following functions:<\/p>\n
        Count<\/code>:<\/strong> is a well know aggregate function<\/p>\n
        STRING_AGG<\/code>:<\/strong> was introduced in a recent version of SQL Server and can be used to concatenate string values<\/p>\n
        LAST_VALUE<\/code>:<\/strong> is a windowing function, but it can be used with any kind of aggregation, including a graph path.<\/p>\n
        Besides each aggregation function, you have the WITHIN<\/code> GROUP<\/code> (GRAPH PATH)<\/code> statement, a special statement created for the grouping generated by the shortest_path<\/code> function.<\/p>\n
        Finally, here\u2019s the WHERE<\/code> clause:<\/p>\n
        WHERE\u00a0MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+))<\/pre>\n
        It’s like a regular MATCH<\/code> clause that you already know about, but using the new function, SHORTEST_PATH<\/code>. The first table, which is not part of the grouping, is related to the edge and node tables, which is part of the grouping. The edge and second node tables appear between parenthesis. The SHORTEST_PATH<\/code> function understands this as an instruction to use recursion, creating the groups.<\/p>\n
        The ‘+<\/code>‘ symbol indicates that you would like information about the entire path between each member of P1 and P2, without limiting the number of hops<\/p>\n
        Here\u2019s the final query:<\/p>\n
        SELECT\u00a0\r\n\u00a0\u00a0\u00a0\u00a0P1.MemberID,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0P1.MemberName,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0STRING_AGG(P2.MemberName,\r\n       '->')\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0AS\u00a0[MemberName],\u00a0\r\n\u00a0\u00a0\u00a0\u00a0LAST_VALUE(P2.MemberName)\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0\r\n       AS\u00a0FinalMemberName,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0COUNT(P2.MemberId)\u00a0WITHIN\u00a0GROUP\u00a0(GRAPH\u00a0PATH)\u00a0AS\u00a0Levels\u00a0\r\n\u00a0\u00a0FROM\u00a0\r\n\u00a0\u00a0\u00a0\u00a0ForumMembers\u00a0P1,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0ForumMembers\u00a0FOR\u00a0PATH\u00a0as\u00a0P2,\u00a0\r\n\u00a0\u00a0\u00a0\u00a0Likes\u00a0FOR\u00a0PATH\u00a0as\u00a0IPO\u00a0\r\n\u00a0\u00a0WHERE\u00a0MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+));<\/pre>\n
        The image below gives an idea of the result. You have the information about the first member of the path, you have the entire path (not including the first member) created by the function STRING_AGG<\/code>, you have the last name of the path created by the LAST_VALUE<\/code> function, and you also have the number of levels in the path, created by the function COUNT<\/code><\/p>\n
        <\/p>\n
        You may be wondering about how Carl connects to Carl. This image shows the path:<\/p>\n
        <\/p>\n
        Performance<\/h2>\n
        The execution plan is big. There is no doubt that you will need to take care when using it in large environments. The full execution plan doesn’t fit here, but you may notice by the piece below that the plan makes extensive use of tempdb<\/code>.<\/p>\n
        You may notice the following details in the execution plan:<\/p>\n
          \n
        • It starts with the edge table<\/li>\n
        • It creates three temporary tables from the edge table. You will see many table operations in the plan, but checking the names, you will notice there are only three<\/li>\n<\/ul>\n
          \"A<\/p>\n
            \n
          • It joins one of the temporary tables with the edge table, the nodes table and a second temporary table, aggregating the result and inserting in the temporary tables<\/li>\n
          • It has a Sequence<\/code> operator, which then is joined with the node table to get the results<\/li>\n<\/ul>\n
            \"A<\/p>\n
            Filtering<\/h2>\n
            By adding one more predicate, you can view just the paths starting from one forum member:<\/p>\n
            SELECT \r\n   P1.MemberID, \r\n   P1.MemberName,\r\n   STRING_AGG(P2.MemberName,'->') WITHIN GROUP \r\n       (GRAPH PATH) AS [MemberName],\r\n   LAST_VALUE(P2.MemberName) WITHIN GROUP (GRAPH PATH) \r\n        AS FinalMemberName,\r\n   COUNT(P2.MemberId) WITHIN GROUP (GRAPH PATH) AS Levels\r\nFROM ForumMembers P1,\r\n\t ForumMembers FOR PATH as P2,\r\n\t Likes FOR PATH as IPO\r\nWHERE MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+))\r\n\t  AND p1.MemberID=7;<\/pre>\n
            \"A<\/p>\n
            The execution plan changes. You may notice the following:<\/p>\n
              \n
            • The sequence is still the middle of the execution plan<\/li>\n
            • The plan starts by the node, not the edge<\/li>\n
            • After the sequence, the Query Optimizer is able to use an index for one of the nodes<\/li>\n<\/ul>\n
              \"A<\/p>\n
                \n
              • There is a fourth temporary table, called Source<\/em><\/li>\n
              • The number of paths before the sequence increases<\/li>\n<\/ul>\n
                \"A<\/p>\n
                If you would like to see only the path between Jonh<\/em> and Steve<\/em>, you may be surprised that you have to separate the query into a CTE or subquery and filter the results. One reason is that a windowing function cannot be directly filtered. The MATCH<\/code> statement doesn\u2019t offer a solution either, you can\u2019t filter by a P2 field, for example, because it\u2019s marked as FOR<\/code> PATH<\/code>.<\/p>\n
                WITH qry AS (\r\n  SELECT \r\n   P1.MemberID, \r\n   P1.MemberName,\r\n   STRING_AGG(P2.MemberName,'->') WITHIN GROUP (GRAPH PATH) \r\n     AS [Path],\r\n   LAST_VALUE(P2.MemberName) WITHIN GROUP (GRAPH PATH) \r\n     AS FinalMemberName,\r\n   COUNT(P2.MemberId) WITHIN GROUP (GRAPH PATH) AS Levels\r\n  FROM\r\n   ForumMembers P1,\r\n   ForumMembers FOR PATH as P2,\r\n   Likes FOR PATH as IPO\r\n  WHERE MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+))\r\n   and p1.MemberID=7)\r\nSELECT * FROM qry \r\nWHERE FinalMemberName='Steve';<\/pre>\n
                It’s not difficult to predict: The query plan is bad. You are calculating the path from Jonh<\/em> to all other members and only after this does the filter kick in to get the path between Jonh<\/em> and Steve<\/em>. In the image below you may notice the filter for Steve<\/em> only after the sequence, after calculating all the paths from Jonh<\/em><\/p>\n
                \"A<\/p>\n
                You may have already noticed the + symbol in the Match<\/code> clause. It means you allow an unlimited number of hops. However, you can use a slightly different syntax to find all the forum members that are, for example, up to two hops away from others:<\/p>\n
                SELECT \r\n   P1.MemberID, \r\n   P1.MemberName,\r\n   STRING_AGG(P2.MemberName,'->') WITHIN GROUP (GRAPH PATH) \r\n      AS [MemberName],\r\n   LAST_VALUE(P2.MemberName) WITHIN GROUP (GRAPH PATH) \r\n      AS FinalMemberName,\r\n   COUNT(P2.MemberId) WITHIN GROUP (GRAPH PATH) AS Levels\r\nFROM\r\n   ForumMembers P1,\r\n   ForumMembers FOR PATH as P2,\r\n   Likes FOR PATH as IPO\r\nWHERE MATCH(SHORTEST_PATH(P1(-(IPO)->P2){1,2}));<\/pre>\n
                However, the start needs always to be 1. If you want to see the people that are an exact number of hops from other, once again you will need to filter the result of the query:<\/p>\n
                WITH qry as\r\n(\r\n  SELECT \r\n   P1.MemberID, \r\n   P1.MemberName,\r\n   STRING_AGG(P2.MemberName,'->') WITHIN GROUP (GRAPH PATH) AS [path],\r\n   LAST_VALUE(P2.MemberName) WITHIN GROUP (GRAPH PATH) AS FinalMemberName,\r\n   COUNT(P2.MemberId) WITHIN GROUP (GRAPH PATH) AS Levels\r\n  FROM\r\n   ForumMembers P1,\r\n   ForumMembers FOR PATH as P2,\r\n   Likes FOR PATH as IPO\r\n  WHERE MATCH(SHORTEST_PATH(P1(-(IPO)->P2){1,2}))\r\n\t)\r\nSELECT * FROM qry WHERE levels=2;<\/pre>\n
                The shortest_path<\/code> function is a great new feature for the SQL Server<\/strong> graph database, but being unable to filter the end node or the exact number of hops without performing the entire calculation and only then filter the result is still a problem for query performance.<\/p>\n
                Indexing<\/h2>\n
                You can create indexes on the pseudo-columns of the edge and nodes. Considering the execution plans you saw, you can create the following clustered index for the edge:<\/p>\n
                CREATE CLUSTERED INDEX indLikes ON likes($from_id,$to_id);<\/pre>\n
                For the nodes, on the other hand, the index didn’t help so much. If you create a clustered index, it will result in a scan operation. If you create a non-clustered index, you would need to include all the columns involved in the operation. It may sound a bit strange, but one of the columns is the graph_id<\/code>. There is no pseudo-column for the graph_id<\/code> in the nodes table. There is one function to retrieve the graph_id, GRAPH_ID_FROM_NODE_ID, <\/code> but you can’t use this function to create a computed column. This instruction bellow, for example, will fail:<\/p>\n
                ALTER TABLE forumMembers ADD graph_id \r\nAS (GRAPH_ID_FROM_NODE_ID($node_id))\r\nPERSISTED;<\/pre>\n
                On the other hand, for the queries where you are filtering for the start member, a non-clustered index on the member id helps:<\/p>\n
                CREATE NONCLUSTERED INDEX indMembers ON ForumMembers(memberid);<\/pre>\n
                There is not much news about the more complex situations filtering by levels or end node: It’s an additional filter after all the calculations of shortest_path.<\/code><\/p>\n
                Conclusion<\/h2>\n
                The function shortest_path<\/code> is an excellent addition to the graph database features; however, the two limitations it has may create heavy queries in the environment:<\/p>\n
                  \n
                • You can’t specify an end node.<\/li>\n
                • You can’t specify a start number of hops which would allow selecting an exact number of hops with same start and end.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
                  With SQL Server 2019 on the way, it\u2019s time to begin learning about all the new features. In this article, Dennes Torres demonstrates how to use the new SHORTEST_PATH function that is part of the Graph Database feature. …<\/p>\n","protected":false},"author":50808,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143531],"tags":[95509],"coauthors":[6810],"class_list":["post-85165","post","type-post","status-publish","format-standard","hentry","category-featured","category-t-sql-programming-sql-server","tag-standardize"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/85165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/50808"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=85165"}],"version-history":[{"count":10,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/85165\/revisions"}],"predecessor-version":[{"id":85360,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/85165\/revisions\/85360"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=85165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=85165"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=85165"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=85165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}