Module path_search 

Searching paths on the graph index: SQL/PGQ’s quantified edges (-[e]->{1,3}, -[e]->*), path variables, selectors (ANY SHORTEST, ALL SHORTEST, SHORTEST k) and path modes (TRAIL, SIMPLE, ACYCLIC) (#297).

A fixed-length pattern is planned as joins (see super::pattern). A quantified edge is not: it is a PathSearchNode, a relation of paths that runs a breadth-first search on the edge table’s graph index, the index hop and shortest_path use, and joins to the nodes at its two ends like any edge. Its rows are one per path:

column	what
__start	the key of the path’s first node
__end	the key of its last node
__length	its number of edges (path_length(p))
__vertices	its nodes’ keys, first to last (vertices(p))
__edges	its edges’ rows in the edge table, from 0 (edges(p))
__element_id	nodes and edges alternating (element_id(p))

The last three are computed only when the query uses them.

A fixed-length edge next to a bound node is searched too, as one edge ({1,1}) from the nodes already reached (see super::pattern): each of its rows is one edge, in edge-row order, so the search’s rows are the join’s rows.

Targets

A search may be given its targets: the keys the last node can have, when a condition on it alone says so (b.id = 7, b.id IN (…)). It keeps only the paths that end at one, and a search with a selector stops as soon as every target has all its paths: ANY SHORTEST from one node to another looks no further than the target.

Which paths

The search runs from each start node: every node of the left end’s table that its conditions keep. A path of n edges is in the result when min <= n <= max and the path mode allows it. Without a selector, every such path is (a walk needs an upper bound, or it would be endless). With one, per pair of first and last node:

• ANY SHORTEST (and ANY): one shortest path;
• SHORTEST k (and ANY k): the k shortest paths;
• ALL SHORTEST: every path as short as the shortest.

Among paths of one length, a path comes before another when its first edge has a lower row in the edge table, or the same first edge and a lower second, and so on: ANY SHORTEST keeps the first. The search finds paths in that order, so the result does not depend on the run or the thread count. (An undirected edge is followed either way; a self-loop once.)

How

The search is breadth-first over (node, edges so far, up to min), so a shortest path of at least min edges is found even when it has to come back to a node it passed. Under WALK, a selector lets it stop extending a state once it has its k paths (or, for ALL SHORTEST, the paths as short as the first): any longer prefix makes a longer or later path. That holds for the other modes too when the lower bound is 0 or 1, the selector is ANY SHORTEST or ALL SHORTEST and the path is not an undirected TRAIL: a shortest walk between two nodes repeats no node, and one back to its start is a cycle. Otherwise the search lists every path the mode allows, up to MAX_PATHS.

Structs

PathColumns

Which path columns a node computes besides its ends and length.

PathSearchNode

A search on a graph’s index, as a logical plan node. Its inputs:

Search

What a search looks for.

Constants

EDGES

Its edges’ rows in the edge table.

ELEMENTS

Its nodes and edges, alternating.

END

Its last node.

FUNCTIONS

The path functions, and the column each reads.

LENGTH

Its number of edges.

MAX_PATHS

The most paths one search lists before it stops with an error.

START

The path’s first node.

VERTICES

Its nodes, first to last.

Functions

run

Run search from each of starts (keys of the graph’s id type, each once) on the index topology/ids; the rows of schema, and how many path prefixes the search extended. edge_row gives the edge table’s row of an edge of the index (see super::GraphIndex::edge_row). With targets, only the paths that end at one are kept, and a search with a selector stops once every target has its paths (see the module docs). With known_only, a start that is no node of the index has no path.

schema

The schema of a search’s rows, for node ids of id_type.