Support ALL shortest path

[Dtenwolde]

Currently we only support ANY SHORTEST with the *. However, we also need to add support for ALL SHORTEST, which would return all the paths between A and B with the same shortest path length. Because this is ALL paths, it cannot work together with *, since that could lead to infinite results. Therefore, we will enforce this to only work on quantified path patterns. For instance, p = ALL SHORTEST MATCH (a:Person)-[k:Knows]->{1,3}(b:Person) or even just ALL SHORTEST MATCH (a:Person)-[k:Knows]->{1,3}(b:Person)

The current approach is to use WITH RECURSIVE internally, with this moved to a separate CTE. The RECURSIVE statement consists of two parts: 1. Non-recursive step, executed once as the first step. 2. Recursive step, executed until the resulting step is empty.

An advantage that DuckDB provides us is the fact that the result does not need to be monotonically increasing, i.e. we can filter out tuples that will not become the shortest path already during the recursive steps.

The current query that I am considering is:

CREATE TABLE person_knows_person (
Person1Id BIGINT,
Person2Id BIGINT,
creationDate TIMESTAMP
);
INSERT INTO person_knows_person (Person1Id, Person2Id, creationDate) VALUES
(1, 2, '2024-01-01 10:00:00'),
(2, 3, '2024-01-01 11:00:00'),
(1, 4, '2024-01-01 10:30:00'),
(4, 3, '2024-01-01 11:30:00');



WITH RECURSIVE AllShortestPaths AS (
    -- Non-recursive step: Start from the given Person1Id
    SELECT
        Person1Id,
        Person2Id,
        1 AS depth,  -- Start with depth 1
        ARRAY[Person1Id, Person2Id] AS path  -- Store the path as an array
    FROM Person_knows_person
    WHERE Person1Id = 1  -- Starting Person1Id

    UNION ALL

    -- Recursive step: Expand paths and group by Person2Id to retain shortest paths
    SELECT
        r.Person1Id,
        rt.Person2Id,
        MIN(r.depth + 1) AS depth,  -- Keep the minimum depth for each Person2Id
        list_append(r.path, rt.Person2Id) AS path  -- Extend the path
    FROM AllShortestPaths r
    JOIN Person_knows_person rt
        ON r.Person2Id = rt.Person1Id
    WHERE r.depth < 3  -- Limit depth to 3
    GROUP BY r.Person1Id, rt.Person2Id, r.path  -- Group by relevant columns
)

-- Final selection: Return all paths with details
SELECT DISTINCT
    path,
    depth
FROM AllShortestPaths
ORDER BY depth, path;

In this case, the starting point is node 1, but it could be that there are multiple nodes from which we wish to explore. In that case we use WHERE Person1Id IN (1,4) -- Starting Person1Id instead.