Relationship-type alternation [:A|B] scans all edge label tables instead of only the listed labels
- Dominant language
- C
- Stars
- 4.8k
- Forks
- 523
- Avg merge
- 1d 2h
- Merged PRs (30d)
- 9
Description
Splitting this out of the review discussion on #2468 so it can be tracked independently of that PR's merge.
### Summary
Relationship-type alternation (`[:A|B]`, added in #2468) is implemented as a post-filter over the generic edge parent table rather than as a scan restricted to the listed labels. The result is that `MATCH ()-[:A|B]->()` reads every edge label table in the graph, not just `A` and `B`.
### Mechanism
1. The parser action sets `rel->label` to `NULL` for an alternation pattern (the PR's own comment on `make_edge_label_alternation_qual` states this explicitly).
2. With a NULL label, `transform_cypher_edge` resolves the edge to `AG_DEFAULT_LABEL_EDGE` (`cypher_clause.c:5908`, `:5914`) and builds the `RangeVar` at `_ag_label_edge` (`cypher_clause.c:6021-6030`).
3. Every user-created edge label table inherits from `_ag_label_edge` (`label_commands.c:286-289`, applied at `:407`), and the `RangeVar` carries `inh = true` (`makeRangeVar` default, passed through at `cypher_clause.c:6033-6034`). Postgres therefore expands the scan across all edge label child tables.
4. The alternation is then narrowed by a synthetic qual of the form `ag_catalog._extract_label_id(.id) IN (id_A, id_B, ...)`.
Because step 4 is a function-wrapped expression over `id` rather than a predicate on a column Postgres can reason about, neither constraint exclusion nor partition pruning can eliminate the non-matching children. The non-matching tables are scanned and then discarded row by row.
### Impact
`[:A|B]` costs O(total edge labels in the graph) instead of O(2). On a graph with labels `A..E` the query touches all five tables; the gap widens linearly with edge-label cardinality. Graphs with many edge types — a common modeling style — pay the most.
This is a performance characteristic of the new feature, not a correctness bug: results are correct, only the plan is wider than necessary.
### Suggested direction
Build an Append/Union over the resolved labels' own `RangeVar`s, reusing the per-label lookup the single-label path already performs (`get_label_relation_name`, `cypher_clause.c:6023`), instead of falling through to the generic parent plus post-filter. That keeps the scan proportional to the number of labels actually named in the pattern.
An alternative worth considering is keeping the current structure but emitting a prunable predicate, so the planner can exclude children without the function wrapper.
### Notes
- Related review discussion: #2468. @jrgemignani raised a performance question on that PR (Jul 13) that points at this same behavior.
- Filing this does not by itself resolve the concern raised on #2468 — that review asked for either a fix or a scope-out accompanied by a benchmark quantifying the regression at realistic label counts. This issue tracks the underlying problem regardless of which path #2468 takes.
Contributor guide
Research direction
Start in cypher_clause.c at transform_cypher_edge, including get_label_relation_name and the RangeVar construction, then inspect inheritance setup in label_commands.c. Reproduce the plan for [:A|B] on a graph with several edge labels and compare it with the single-label path. Done means only the named label tables are scanned and benchmarks quantify the result at realistic label counts.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, postgresql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100