apache / apache/age

Relationship-type alternation [:A|B] scans all edge label tables instead of only the listed labels

Open
#2,479 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.