Graph VT Benchmarks¶
Compares CSR adjacency caching strategies against direct TVF access after edge mutations. Each chart plots performance against graph size (node count) on a log-log scale.
Methods¶
| Method | Description |
|---|---|
| TVF | No cache — scans edge table via SQL on every query |
| CSR | Persistent CSR cache; initial build from edge table |
| CSR — full rebuild | Persistent CSR cache; full edge-table re-scan when stale |
| CSR — incremental | Delta + merge; rebuilds all blocks (spread mutations) |
| CSR — blocked incremental | Delta + merge; rebuilds only affected blocks (concentrated mutations) |
Workloads¶
| Size | Nodes | Edges | Graph Model |
|---|---|---|---|
| xsmall | 500 | 2,000 | Erdos-Renyi |
| small | 1,000 | 5,000 | Erdos-Renyi |
| medium | 5,000 | 25,000 | Barabasi-Albert |
| large | 10,000 | 50,000 | Barabasi-Albert |
How Blocked CSR Works¶
The CSR is partitioned into blocks of 4,096 nodes. Each block is a separate row in the shadow table. When edges change, only blocks containing affected nodes are rewritten — unaffected blocks require zero I/O.
Algorithm Query Time¶
Degree Query Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.353,
0.541,
3.112,
5.795
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.263,
0.49,
2.738,
6.366
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.279,
0.506,
2.648,
5.729
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.325,
0.402,
2.782,
6.219
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "TVF (no cache)",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.773,
1.711,
16.219,
34.229
],
"marker": {
"color": "hsl(0, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(0, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "tvf",
"legendgrouptitle": {
"text": "TVF (no cache)"
}
}
],
"layout": {
"title": {
"text": "Degree Query Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Degree Computation (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Betweenness Query Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000
],
"y": [
20.299,
111.908,
4795.417
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000
],
"y": [
20.134,
110.522,
4780.993
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000
],
"y": [
20.4,
113.283,
4770.226
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000
],
"y": [
19.976,
111.552,
4786.653
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "TVF (no cache)",
"x": [
500,
1000,
5000
],
"y": [
20.223,
113.778,
4781.628
],
"marker": {
"color": "hsl(0, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(0, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "tvf",
"legendgrouptitle": {
"text": "TVF (no cache)"
}
}
],
"layout": {
"title": {
"text": "Betweenness Query Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Betweenness Computation (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Closeness Query Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000
],
"y": [
19.257,
105.313,
4710.078
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000
],
"y": [
19.011,
107.239,
4698.934
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000
],
"y": [
19.858,
105.476,
4696.496
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000
],
"y": [
19.604,
107.185,
4767.104
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "TVF (no cache)",
"x": [
500,
1000,
5000
],
"y": [
19.172,
107.798,
4702.905
],
"marker": {
"color": "hsl(0, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(0, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "tvf",
"legendgrouptitle": {
"text": "TVF (no cache)"
}
}
],
"layout": {
"title": {
"text": "Closeness Query Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Closeness Computation (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Leiden Query Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.746,
1.255,
22.294,
31.962
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.598,
1.344,
21.59,
33.928
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.641,
1.343,
21.963,
32.86
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.603,
1.281,
23.947,
33.514
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "TVF (no cache)",
"x": [
500,
1000,
5000,
10000
],
"y": [
1.019,
2.592,
35.818,
60.217
],
"marker": {
"color": "hsl(0, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(0, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "tvf",
"legendgrouptitle": {
"text": "TVF (no cache)"
}
}
],
"layout": {
"title": {
"text": "Leiden Query Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Leiden Computation (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Rebuild Performance¶
Rebuild Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
1.356,
1.461,
7.142,
13.759
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000,
10000
],
"y": [
1.827,
3.355,
28.071,
58.081
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
1.596,
1.373,
7.821,
18.292
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
}
],
"layout": {
"title": {
"text": "Rebuild Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Rebuild Time (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Build Performance¶
Initial CSR Build Time¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000,
10000
],
"y": [
2.968,
4.322,
28.909,
55.057
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
}
],
"layout": {
"title": {
"text": "Initial CSR Build Time"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Build Time (ms)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Storage¶
Shadow Table Disk Usage¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000,
10000
],
"y": [
98304.0,
188416.0,
1478656.0,
2916352.0
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
98304.0,
188416.0,
1486848.0,
2940928.0
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000,
10000
],
"y": [
98304.0,
188416.0,
1486848.0,
2940928.0
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
98304.0,
188416.0,
1486848.0,
2932736.0
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "TVF (no cache)",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.0,
0.0,
0.0,
0.0
],
"marker": {
"color": "hsl(0, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(0, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "tvf",
"legendgrouptitle": {
"text": "TVF (no cache)"
}
}
],
"layout": {
"title": {
"text": "Shadow Table Disk Usage"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Disk Usage (bytes)"
},
"type": "log"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}
Trigger Overhead¶
Trigger Overhead¶
{
"data": [
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.727,
1.215,
1.814,
1.771
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr",
"legendgrouptitle": {
"text": "CSR"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR blocked-incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.459,
1.251,
3.823,
2.802
],
"marker": {
"color": "hsl(270, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(270, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_blocked",
"legendgrouptitle": {
"text": "CSR blocked-incremental"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR full-rebuild",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.317,
1.338,
3.974,
3.521
],
"marker": {
"color": "hsl(30, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(30, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_full_rebuild",
"legendgrouptitle": {
"text": "CSR full-rebuild"
}
},
{
"type": "scatter",
"mode": "lines+markers",
"name": "CSR incremental",
"x": [
500,
1000,
5000,
10000
],
"y": [
0.47,
1.463,
3.881,
6.128
],
"marker": {
"color": "hsl(160, 75%, 45%)",
"size": 7
},
"line": {
"color": "hsl(160, 75%, 45%)",
"width": 2
},
"opacity": 0.6,
"legendgroup": "csr_incremental",
"legendgrouptitle": {
"text": "CSR incremental"
}
}
],
"layout": {
"title": {
"text": "Trigger Overhead"
},
"xaxis": {
"title": {
"text": "Graph Size (nodes)"
},
"type": "log"
},
"yaxis": {
"title": {
"text": "Overhead (ms)"
},
"type": "linear"
},
"template": "plotly_white",
"legend": {
"orientation": "v",
"yanchor": "top",
"y": 0.99,
"xanchor": "left",
"x": 1.02,
"groupclick": "togglegroup"
}
}
}