Combinations SQL

[cvvergara]

On 3.1 these signatures were added

• pgr_Dijkstra(Combinations) [Closes #1359 Adding pgr_dijkstra(combinations) #1360]
• pgr_DijkstraCost(Combinations) [Add pgr_dijkstraCost combinations #1375]

Add the signature(s) of Combinations SQL for the following functions

From official functions:

aStar - Family of functions [#1732]

• pgr_astar(Combinations)
• pgr_astarCost(Combinations)

Bidirectional A* - Family of functions [#1774]

• pgr_bdAstar(Combinations)
• pgr_bdAstarCost(Combinations)

Bidirectional Dijkstra - Family of functions [#1775]

• pgr_bdDijkstra(Combinations)
• pgr_bdDijkstraCost(Combinations)

Flow - Family of functions [#1777]

• pgr_maxFlow(Combinations)
• pgr_boykovKolmogorov(Combinations)
• pgr_edmondsKarp(Combinations)
• pgr_pushRelabel(Combinations)
• pgr_edgeDisjointPaths(Combinations)

From proposed functions:

withPoints - Family of functions [#1649]

• pgr_withPoints(Combinations)
• pgr_withPointsCost(Combinations)

From experimental functions:

• pgr_bellmanFord(Combinations) [Bellman Ford - Combinations #1779]
• pgr_binaryBreadthFirstSearch(Combinations) [Binary Breadth First Search - Combinations #1783]
• pgr_dagShortestPath(Combinations) [DAG Shortest Path - Combinations #1793]
• pgr_edwardMoore(Combinations) [Edward Moore - Combinations #1794]

Flow - Family of functions [#1777]

• pgr_maxFlowMinCost(Combinations)
• pgr_maxFlowMinCost_Cost(Combinations)

[krashish8]

I think I should proceed sequentially. So, after completing withPoints, I'll go with aStar.

[krashish8]

For the flow family of functions, if the combinations query has:
6,1
8,3
12, 11
8,1
Then, the function aggregates the sources and the targets, removes the duplicates, and then it calculates the result for sources 6,8,12 and for targets 1,3,11.

[mahmsakr]

Congratulations for this excellent work ! The combinations SQL signature helped significantly reducing the runtime of our trajectory data generator.
In general Combinations SQL covers the semantics of one-to-one, one-to-many, many-to-one, and many-to-many. In addition, it allows for arbitrary pairs. This signature thus gives maximum flexibility for setting up the parameters.

The only draw back is that the combinations SQL is passed as a string. It thus cannot reuse results from the outer query. The following query, for example, will through an error:
WITH combinations(source, target) AS(
SELECT ...
)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM combinations',
FALSE
);
This query will through because combinations is not a database object. In order for this query to work, one has to store the CTE combinations as a database table:

CREATE TABLE combinations AS(
SELECT ...
);

SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM combinations',
FALSE
);

The database table combinations, was created only for the sake of being able to use the combinations SQL. After running the pgr_dijkstra query, this table remains as junk in the database. Clearly this is not the optimal solution.

A more flexible solution would be to invent a "combination nested array" signature, rather than the "combinations SQL" signature. The main difference is that the "combinations nested array" can be constructed in the outer query. Every sub array in the combinations nested array is a pair of source and target. Here is an example:

WITH pairs(source, target) AS(
SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) t
), combinations(combinations_array) AS(
SELECT ARRAY_AGG(ARRAY[source, target]) FROM pairs
)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
SELECT combinations_array FROM combinations,
FALSE
);

[cvvergara]

All our queries are passed as string. So the first example you wrote can be written like this.
Can be used like this.

SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'WITH combinations(source, target) AS(
  SELECT ...
  )
SELECT * FROM combinations',
FALSE
);

The nested array structure looks interesting, you might put that in another issue.
Right now we need to unify all the functions to the combinations signatures where we can, to keep the extension standarized.

[cvvergara]

@krashish8 Thanks for this hard work