Skip to content

Avoid redundant entity lookups in writable Cypher clauses #2484

Description

@crdv7

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 added a unique id index
to vertex labels and start_id/end_id indexes to edge labels. PR
#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:

MATCH (n:Person)
SET n.updated = true
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:

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
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
using a 2,000,000-vertex DELETE workload.

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

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.
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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions