apache / apache/age

Avoid redundant entity lookups in writable Cypher clauses

Open
#2,484 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
C
Stars
4.8k
Forks
523
Avg merge
1d 2h
Merged PRs (30d)
9

Description

**Is your feature request related to a problem? Please describe.**

Writable Cypher clauses such as `SET`, `REMOVE`, and `DELETE` re-locate the
backing tuple of every graph entity even though the preceding `MATCH` has
already read that tuple in the same statement.

PR [#2117](https://github.com/apache/age/pull/2117) added a unique `id` index
to vertex labels and `start_id`/`end_id` indexes to edge labels. PR
[#2351](https://github.com/apache/age/pull/2351) made entity lookup use an
`id` index when available. For `M` writes against a label containing `N`
entities, repeating that B-tree lookup adds `O(M log N)` lookup work. A
validated CTID hint addresses the heap tuple directly, making the expected
lookup cost `O(1)` per entity and `O(M)` overall, aside from normal MVCC and
buffer-access costs.

Edge labels have a more expensive fallback. Their default `start_id` and
`end_id` indexes cannot resolve an edge by graphid, so without a user-created
`id` index each lookup can scan `O(N)` rows. This adds `O(MN)` lookup work and
can approach `O(N²)` for a batch that writes the whole label.

For a vertex label, the following clauses repeat the default `id` B-tree
lookup for every matched vertex:

```cypher
MATCH (n:Person)
SET n.updated = true
```

```cypher
MATCH (n:Person)
DELETE n
```

For an edge label without a user-created `id` index, the writable lookup in
the following query can instead perform a sequential scan for every matched
edge:

```cypher
MATCH ()-[r:KNOWS]->()
WITH r
REMOVE r.temporary_property
```

In each case, `MATCH` already knows the tuple's physical location. The
writable executor discards that information and resolves the entity again by
graphid.

**Describe the solution you'd like**

Carry the tuple `ctid` as an internal, hidden lookup hint from `MATCH` to
downstream writable clauses.

This follows the same principle as PostgreSQL's own `UPDATE` and `DELETE`
execution: carry the target tuple's physical row identity into the write
executor instead of resolving the row again through a logical-key index.
Because [`ctid`](https://www.postgresql.org/docs/current/ddl-system-columns.html)
identifies a tuple version's physical location, it enables an expected
`O(1)` direct heap fetch and avoids another B-tree descent.

AGE's writable clauses can carry this information internally from the matched
row to the write executor without exposing it in query results. The CTID
would remain only a hint: the executor must validate snapshot visibility and
graphid identity, then fall back to the existing graphid lookup when the hint
is missing or stale. Graphid remains the logical entity identity, and
read-only queries remain unchanged.

**Describe alternatives you've considered**

1. **Keep the current graphid lookup design.** This requires no planner
changes, but repeats an `id` B-tree lookup for every entity already read by
`MATCH` and falls back to repeated sequential scans when no suitable index
exists.
2. **Redesign writable Cypher clauses around PostgreSQL
`ModifyTable`-style execution.** This could carry native row identity into
PostgreSQL's update/delete machinery, but would require a much broader
parser, planner, and executor change to preserve dynamic graph labels,
chained Cypher clauses, `MERGE`, alias/path projection, RLS, and Cypher
result semantics.

Using a validated hidden CTID hint keeps the optimization local to writable
custom scans while preserving graphid as the logical entity identity. It
captures the main row-location benefit without requiring that architectural
rewrite.

**Additional context**

I profiled the current implementation at commit
[`801417404978823bd8732452c3f7959017584785`](https://github.com/apache/age/commit/801417404978823bd8732452c3f7959017584785)
using a 2,000,000-vertex `DELETE` workload.

The baseline flame graph contains repeated B-tree work below
`process_delete_list()`:

```text
process_delete_list
index_getnext_slot
index_getnext_tid
btgettuple
_bt_first
_bt_search
```

Stacks containing `process_delete_list;index_getnext_slot` account for 14.21%
of sampled CPU cycles. This is the graphid lookup repeated after `MATCH` has
already located each vertex.

- Baseline flame graph:

Image

I also measured current edge-label scaling without an `id` index using the
workload reproduced by
[repro_edge_set_no_id_index.sql](https://github.com/user-attachments/files/30529509/repro_edge_set_no_id_index.sql).
The script creates an edge label with only the default `start_id` and `end_id`
indexes, loads the requested number of edges, and runs `SET` on every edge.

The following results use that workload without a user-created `id` index.
Each value is the median of five measured runs after one unreported warm-up:

| Edges | Median time | Growth from 10,000 edges |
|---:|---:|---:|
| 10,000 | 860.594 ms | 1.00x |
| 20,000 | 3.260 s | 3.79x |
| 100,000 | 81.856 s | 95.12x |

Increasing the label from 10,000 to 100,000 edges increases elapsed time by
95.12x for a 10x increase in data, consistent with repeated per-edge
sequential lookup approaching quadratic scaling. `REMOVE` uses the same
shared update lookup path, but was not separately measured in this edge
workload.

I plan to submit a pull request implementing this validated hidden-CTID
lookup while preserving the existing graphid lookup as a fallback.

Contributor guide

Open the contributing guide

Research direction

Start at the writable lookup path around process_delete_list() and reproduce the edge-label behavior with repro_edge_set_no_id_index.sql. Trace how MATCH results reach SET, REMOVE, and DELETE, then verify that a validated hidden CTID hint avoids redundant lookup while preserving graphid fallback and run the existing relevant tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, postgresql
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.