Docs: clarify VLE semantics and cost model

[gregfelice]

Summary

The variable-length edge (VLE) expansion algorithm used for patterns like [*1..3] exhibits O(n^k) time complexity because it does not perform cycle detection or deduplication during recursive expansion. On graphs with cycles (which are common in real-world data), this causes exponential path explosion.

Reproduction

Setup: 100K nodes with edges forming natural cycles.

-- VLE query: find all nodes reachable within 1-3 hops
SELECT * FROM cypher('benchmark', $$
  MATCH (n:Node {bench_id: 42})-[*1..3]->(m)
  RETURN count(m)
$$) AS (cnt agtype);

On graphs with cycles, the expansion visits the same nodes exponentially many times because UNION ALL semantics are used internally (no deduplication).

Performance Data

Benchmark W06 (variable-length edge traversal):

Approach	10K scale	100K scale
Cypher VLE (before SDK workaround)	~23ms	~23ms
Recursive CTE with UNION (dedup)	0.08ms	0.34ms

The SDK workaround uses a recursive CTE with UNION (not UNION ALL) which provides implicit cycle detection through set deduplication, preventing exponential blowup:

WITH RECURSIVE vle AS (
  SELECT e.end_id AS node_id, 1 AS depth
  FROM benchmark."EDGE" e
  WHERE e.start_id = (SELECT id FROM benchmark."Node" WHERE _bench_id = 42)
  UNION  -- implicit dedup = cycle detection
  SELECT e.end_id, v.depth + 1
  FROM vle v
  JOIN benchmark."EDGE" e ON e.start_id = v.node_id
  WHERE v.depth < 3
)
SELECT count(*) FROM vle WHERE depth >= 1;

Suggested Fix

Add a visited-node set to the VLE expansion in the executor. When expanding [*min..max], track which (node_id, depth) pairs have already been explored and skip duplicates. This is equivalent to using UNION instead of UNION ALL in the recursive expansion.

Environment

• PostgreSQL 18.2
• Apache AGE 1.7.0 (built from source, branch release/PG18/1.7.0)
• 32-core, 64GB RAM, Linux 6.17

[jrgemignani]

@gregfelice The following is from Opus, because it can explain it better than I, as it has been a while since I wrote the VLE.

Analysis of Issue #2349: VLE path expansion cycle detection claims

Summary

Issue #2349 claims that AGE's VLE (variable-length edge) expansion has O(n^k) complexity with "no cycle detection" and proposes adding a visited-node set. After a thorough review of the entire VLE implementation (src/backend/utils/adt/age_vle.c, 2692 lines), the claims are substantially incorrect. AGE's VLE already implements cycle prevention via edge-uniqueness enforcement — consistent with the openCypher specification. The performance concern is real but misdiagnosed.

---

How VLE Actually Works

The VLE implementation uses a DFS (depth-first search) with per-path edge-uniqueness enforcement, not unchecked recursive expansion.

Core data structures (age_vle.c lines 42–97):

• edge_state_hashtable — per-edge state tracking (100K initial hash buckets)
• edge_state_entry.used_in_path — boolean flag marking edges currently in the active DFS path
• dfs_path_stack — the current path being explored
• dfs_edge_stack — working stack of candidate edges
• dfs_vertex_stack — parent vertex tracking (used only for undirected traversal)

Cycle prevention operates at two levels:

1. In add_valid_vertex_edges() (lines 1206–1367): Before adding an edge to the exploration stack, the code checks ese->used_in_path. If the edge is already in the current path, it is skipped. For small paths (<10 edges), a fast linear scan via is_edge_in_path() is used before falling through to the hash lookup.

2. In dfs_find_a_path_between() and dfs_find_a_path_from() (lines 933–1176): When an edge is popped that has used_in_path == true, the algorithm recognizes it is backtracking — it pops the edge from the path stack, resets used_in_path = false, and continues to the next candidate. This is textbook DFS backtracking with edge-uniqueness.

3. Upper bound enforcement: Both DFS functions check get_stack_size(path_stack) < vlelctx->uidx before expanding deeper. A pattern like [*1..3] is strictly bounded at depth 3.

---

Point-by-Point Response to Issue Claims

Claim	Verdict	Explanation
"No cycle detection"	False	Edge-uniqueness is enforced via used_in_path flag + hash table. No edge can appear twice in any single path.
"O(n^k) complexity"	Misleading	Bounded by C(E,k) (edges choose k), not n^k. For bounded VLE like [*1..3], total work is O(E · d²) where d is average degree.
"UNION ALL semantics internally"	Incorrect	VLE is a custom DFS implemented as a PG Set-Returning Function (SRF). It does not use recursive CTEs.
"Visits same nodes exponentially"	Partially true	Vertices CAN be revisited via different edges — this is correct per the openCypher specification, which mandates edge-isomorphism (no repeated edges), not vertex-isomorphism (no repeated vertices).
"Fix: add visited-node set"	Would break semantics	Tracking visited nodes would change VLE from edge-unique to vertex-unique traversal, violating openCypher edge-isomorphism rules and producing incorrect results for queries that need all edge-unique paths.

---

The Benchmark Comparison Is Invalid

The issue compares VLE (~23ms) against a recursive CTE with UNION (~0.08ms), but these compute fundamentally different things:

• VLE returns all edge-unique paths — each as a full path object with vertices, edges, and properties. A MATCH (n)-[*1..3]->(m) RETURN count(m) enumerates every distinct path.
• Recursive CTE with UNION returns only reachable node IDs with deduplication. It collapses all paths to the same node into one row.

These are not equivalent operations. The CTE answers "which nodes are reachable?" while VLE answers "what are all the paths?" The performance difference reflects the algorithmic difference in output cardinality, not a bug.

---

The Legitimate Performance Concern

While the diagnosis is wrong, the underlying concern is valid: VLE can be expensive on dense cyclic graphs because edge-unique path enumeration is inherently combinatorial. On a graph where vertex V has high in/out degree and participates in many cycles, VLE will enumerate all edge-unique paths through V — visiting V many times via different edges. This is correct behavior, but expensive.

The test graph in AGE's own regression suite (regress/sql/cypher_vle.sql) demonstrates this: a 5-vertex graph with self-loops and back-edges produces 7,092 undirected paths with [*1..∞]. This is the expected combinatorial output for edge-unique enumeration over a cycle-rich topology.

Additionally, when the upper bound is omitted ([*] or [*1..]), VLE sets uidx_infinite = true and the only termination guarantee is edge-uniqueness depletion. On a graph with |E| edges, the maximum path length is |E|, making the worst case O(|E|!) — factorial. This is a genuine scalability risk.

---

Correct Characterization

AGE's VLE implements edge-isomorphic DFS path enumeration as required by the openCypher specification. The complexity for bounded patterns [*min..max] is polynomial in graph size. For unbounded patterns, it is exponential in the worst case — but this is inherent to the problem of enumerating all edge-unique paths, not a missing optimization.

What the reporter actually wants is vertex-unique reachability (BFS), which is a different operation than what VLE provides. The appropriate solutions would be:

• Implementing shortestPath() / allShortestPaths() using BFS (not yet available in AGE)
• Adding an optional vertex-unique traversal mode for reachability queries where full path enumeration is not needed
• Adding a configurable safety depth cap (GUC) for unbounded VLE to prevent runaway queries on dense graphs

[gregfelice]

@jrgemignani — thank you for the thorough analysis. You're right on the substance, and I was wrong on several points. Three corrections accepted:

1. Cycle prevention exists. edge_state_entry.used_in_path + is_edge_in_path() enforce edge-uniqueness on every DFS step. I mischaracterized this as "no cycle detection" when it's actually edge-isomorphism per the openCypher spec.
2. A visited-node set would break semantics. Swapping edge-isomorphism for vertex-isomorphism would silently drop valid paths and violate the spec. Not the right fix.
3. The benchmark is apples-to-oranges. Full path enumeration vs. deduplicated reachability answer different questions; the runtime delta reflects cardinality, not a bug.

That leaves one narrower concern from the original issue that I'd like to keep on the table, framed correctly this time:

Unbounded VLE ([*], [*1..]) has no safety cap. With uidx_infinite = true, termination relies solely on edge-uniqueness depletion, so worst case on a dense graph is O(|E|!). This is inherent to edge-unique path enumeration — not fixable by algorithm change — but it is a foot-gun with no guard rail. Two concrete, non-invasive improvements:

• A GUC (e.g. age.vle_max_depth, default unlimited or a large sentinel) that errors out when an unbounded traversal exceeds the cap. Opt-in safety for production workloads without changing semantics for anyone who doesn't set it.
• Doc note in the VLE / variable-length relationship section clarifying edge-isomorphism vs. vertex-isomorphism and the unbounded-depth cost model, so future users don't file the same misdiagnosis I did.

The "BFS-backed reachability / shortestPath" angle you mentioned lives in #2350 — happy to treat that as the separate work item it really is.

If the narrowed scope (GUC + docs) is agreeable I'll retitle this issue accordingly and submit a PR. Otherwise happy to close and re-file.

[jrgemignani]

@gregfelice I don't see the need for a max depth parameter. What if the path is max depth + 1? Who defines max depth? If a user wants to opt into some early termination, they only need to add an endpoint.

As for an addition to the documentation,... if you would like to add that, that is fine. But, I don't think we need a max depth parameter.

[gregfelice]

Fair call — dropping the GUC.

For the docs addition, I'll add a design-note comment block at the top of src/backend/utils/adt/age_vle.c explaining:

• Semantics — edge-isomorphism (openCypher-mandated): no repeated edges per path, vertices may recur. Small triangle example showing why a visited-node optimization would be spec-incorrect.
• Cost model — bounded [*min..max] is polynomial in graph size (bounded by C(E, max)); unbounded [*] / [*1..] is combinatorial in the worst case on cycle-rich graphs.
• Implementation pointer — one-liner noting that cycle prevention is enforced via edge_state_entry.used_in_path + the DFS backtracking in dfs_find_a_path_*(), so future readers can find it.

No code changes, no new tests. Will retitle this issue to "Docs: clarify VLE semantics and cost model" and submit the PR shortly. If you'd prefer the note in age_vle.h instead, or want a user-facing doc in age-website too, happy to adjust.

[jrgemignani]

@gregfelice -

For the docs addition, I'll add a design-note comment block at the top of src/backend/utils/adt/age_vle.c explaining:

Please hold off for a few days on that. I'm waiting on my PR for the VLE to be merged and it has a lot of changes. You'd likely need to rebase after that one. See #2376

[jrgemignani]

@gregfelice If you want to attempt shortest path,... BFS could be good, if the tree isn't too broad. DFS being a problem if it is deep. BFS would need to be built from the ground up, though. DFS is already there - tradeoffs.

It would be possible to use the VLE DFS code by setting progressively larger endpoints,...

MATCH p=()-[*0..1]->()
MATCH p=()-[*1..2]->()
MATCH p=()-[*2..3]->()
...
MATCH p=()-[*i..n]->()

That would allow reusing the VLE code. Just food for thought, though.

[jrgemignani]

VLE PR is now merged, so go ahead with any doc changes that you feel are necessary :)

[gregfelice]

Retitled to reflect the narrowed scope. PR #2413 adds the in-source design-note comment block to age_vle.c (edge-isomorphism semantics, bounded vs unbounded cost model, pointer to used_in_path / dfs_find_a_path_* / is_edge_in_path enforcement). No code change, no GUC, no tests. Cassert installcheck green (33/33).