lkozeev opened a new pull request, #2515:
URL: https://github.com/apache/age/pull/2515
# VLE: cache edge/vertex classification and prune PATHS_BETWEEN via reverse
BFS
## Problem
`dfs_find_a_path_between()` (`PATHS_BETWEEN` / `shortestPath`-style
`[:REL*min..max]`,
both endpoints known) did this on every visit to a vertex, regardless of
prior visits:
- **Adjacency re-scanned across every edge label on every visit**, not just
the pattern's
— the graph context carries no label-based pre-filtering. For each edge in
that array,
two hashtable probes (`edge_table`, `edge_state_hashtable`) ran on every
visit, even
though `is_an_edge_match()`'s verdict was already memoized per edge. Cost:
`O(k · deg_total(v))` instead of `O(deg_total(v) + k · deg_match(v))`.
- **Edge endpoint re-resolved via hashtable lookup on every traversal
step**, though
`start_vertex_id`/`end_vertex_id` are fixed at edge-creation time.
- **No lower bound on remaining distance to target** — a branch that can't
reach it within
the hop budget was walked in full (`O(d^r)`) before backtracking, instead
of rejected in
`O(1)`.
No memory bound on any of the above — a pathological query could grow them
unbounded for
the duration of the call.
## Changes
1. Parser: pass a previously-bound target vertex through (was hardcoded
`NULL`) — required
for `PATHS_BETWEEN` classification to ever trigger.
2. Cache edge endpoints in `edge_state_entry` — resolved once, not per
traversal step.
3. Cache per-vertex relevant edges (`vertex_edge_cache`) — built once per
vertex, skips
non-matching-label edges on every later visit.
4. Reverse-BFS distance-to-target pruning for `PATHS_BETWEEN` — reject an
unreachable
branch in `O(1)`.
5–6. `edge_state_entry`: remove struct padding; bitpack 3 `bool`s into one
`uint8`.
7. GUC-bounded caches + clock eviction (`age.vle_*`); fails open under
pressure (never
wrong, only less pruning).
8. Bug fixes: pointer-vs-size `Assert`, wrong function names in error
messages.
No change in visible behavior is expected.
## Results
Env: AMD Ryzen 5 5500U (6c/12t), 16 GiB RAM, boost off,
governor=`performance`. PG18
`736d880` vs. vanilla PG18+AGE. SNB graph via `generate_graph.sql`
(`gsmall`=SF1,
`gmid`=SF10).
**`ShortestPath_hard`** — `MATCH path=(p1)-[:KNOWS*1..5]-(p2) ...
min(length(path))`
| Cluster | C/W | TPS before→after (×) | Latency before→after (×) | Peak mem
Δ |
|---|---|---|---|---|
| gsmall | 1/1 | 0.2→10.6 (53.2x) | 4,737→93.9ms (50.5x) | 83→89MB (+7%)
|
| gsmall | 6/6 | 1.22→62.8 (51.6x) | 4,752→94.8ms (50.1x) | 312→340MB
(+9%) |
| gsmall | 6/12 | 1.43→78.4 (54.7x) | 7,643→152.3ms (50.2x) | 558→650MB
(+16%) |
| gsmall | 8/16 | 1.45→77.4 (53.4x) | 9,964→204.6ms (48.7x) | 694→872MB
(+26%) |
| gmid | 1/1 | 0.2→21.1 (105.4x) | 4,749→47.2ms (100.7x) | 519→422MB
(−19%) |
| gmid | 6/6 | 1.08→105.3 (97.2x) | 5,227→56.8ms (92.1x) | 2,049→1,473MB
(−28%) |
| gmid | 6/12 | 1.33→128.0 (96.0x) | 8,264→93.1ms (88.7x) | 3,749→2,705MB
(−28%) |
| gmid | 8/16 | 1.3→126.2 (97.0x) | 11,004→121.4ms (87.7x)| 4,649→3,509MB
(−24%) |
**`Path`** — same pattern, `RETURN path LIMIT 1` (first match, no min
aggregation)
| Cluster | C/W | TPS before→after (×) | Latency before→after (×) | Peak mem
Δ |
|---|---|---|---|---|
| gsmall | 1/1 | 0.25→47.2 (188.7x) | 3,861→20.8ms (185.7x) | 84→103MB
(+23%) |
| gsmall | 6/6 | 1.23→246.3 (199.7x) | 4,613→24.1ms (191.5x) | 313→411MB
(+31%) |
| gsmall | 6/12 | 1.63→329.0 (201.4x) | 6,809→36.3ms (187.5x) | 565→721MB
(+28%) |
| gsmall | 8/16 | 1.63→314.7 (192.7x) | 9,003→49.9ms (180.3x) | 708→904MB
(+28%) |
| gmid | 1/1 | 0.22→23.6 (108.9x) | 4,545→42.1ms (107.9x) | 515→423MB
(−18%) |
| gmid | 6/6 | 1.08→111.5 (103.0x) | 5,181→53.6ms (96.7x) |
2,042→1,473MB (−28%) |
| gmid | 6/12 | 1.3→133.5 (102.7x) | 8,627→89.3ms (96.7x) |
3,742→2,699MB (−28%) |
| gmid | 8/16 | 1.15→129.4 (112.5x) | 12,028→121.4ms (99.1x)|
4,536→3,509MB (−23%) |
<img width="1189" height="490" alt="image"
src="https://github.com/user-attachments/assets/0d155285-ccfd-46f3-8cdc-d0993f1c4711";
/>
## Reproduce
```
psql -d postgres -f generate_graph.sql -v sf=1
pgbench -d postgres -f shortest_path.sql -c 12 -j 6 -T 60 -s 1 -n -P 1
pgbench -d postgres -f path.sql -c 12 -j 6 -T 60 -s 1 -n -P 1
```
## New GUCs
| GUC | Responsibility |
| --- | --- |
| `age.vle_edge_state_htab_initial_size` | Initial bucket count for the
`vle_edge_state` cache, default `16384` |
| `age.vle_vertex_edge_htab_initial_size` | Initial bucket count for the
`vertex_edge_cache`, default `1024` |
| `age.vle_edge_state_max_entries` | Soft cap on live entries in the
`vle_edge_state` cache before background eviction of unreferenced entries kicks
in, default `2000000` |
| `age.vle_vertex_edge_cache_max_entries` | Soft cap on live entries in the
`vertex_edge_cache` before background eviction of unreferenced entries kicks
in, default `200000` |
| `age.vle_vertex_edge_cache_max_kb` | Soft cap, in kilobytes, on the memory
`vertex_edge_cache` adjacency arrays, default `65536` |
| `age.vle_reverse_dist_max_entries` | Cap on the reverse-BFS distance table
used to prune PATHS_BETWEEN VLE queries, default `500000` |
| `age.vle_max_cached_contexts` | Maximum number of VLE_local_context
objects, default `5` |
| `age.vle_edge_state_eviction_enabled` | Enable clock-style eviction of
unreferenced entries in the `vle_edge_state` cache, default `true` |
## AI assistance
Used throughout; no clean split of responsibility is possible to state. All
code comments
were AI-generated.
--
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]
