crdv7 opened a new issue, #2484: URL: https://github.com/apache/age/issues/2484
**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: <img width="1200" height="750" alt="Image" src="https://github.com/user-attachments/assets/39d16c1e-b7bd-4382-a868-be4109ab2ea2"; /> 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. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
