PostgreSQL 19 vs Memgraph: Comparing Graph Traversal Performance
With SQL/PGQ support, Postgres can now define property graphs over relational tables and query them with graph pattern syntax. For anyone working with connected data, that raises a fair question: how far can these new graph features go before the relational engine starts to show its limits?
We wanted to test that question directly, but keep the scope narrow. A broad PostgreSQL vs Memgraph benchmark would be too noisy to say much. So this comparison focuses on one graph workload where the execution model matters: exact hop reachability.
That keeps the benchmark small enough to reason about, but still useful for seeing what changes as traversal depth increases.
PostgreSQL 19 rings Graph Querying to SQL
PostgreSQL 19 adds support for SQL/PGQ, the SQL standard for property graph queries. SQL/PGQ lets users define a property graph over relational tables, then query that graph using graph pattern syntax through constructs such as GRAPH_TABLE and MATCH.
In practice, this means Postgres users can model existing relational tables as vertices and edges, then ask graph shaped questions without leaving SQL.
For teams already using PostgreSQL, this is valuable. Connected data often lives in relational tables: users, accounts, transactions, permissions, products, infrastructure records, and event logs. SQL/PGQ gives those teams a way to explore relationships inside Postgres.
But PostgreSQL is still a relational database. Its graph features add graph querying over relational data.
Whereas native graph databases like Memgraph starts from a different assumption: the graph is the primary data model.
That difference becomes important when the workload moves from shallow pattern matching to deeper traversal.
Memgraph Starts With the Graph
Memgraph is a native graph database built around the property graph model. Data is represented as nodes, relationships, labels, and properties, then queried using Cypher.
That makes it different from adding graph queries over an existing relational model. In Memgraph, relationships are not a layer on top of tables. They are part of the core data model the database stores and traverses.
This matters for applications where relationships are not just metadata, but the main thing being queried. Fraud detection, identity and access graphs, infrastructure dependency mapping, recommendations, GraphRAG retrieval, and agent memory all depend on moving across connected data.
Benchmark Setup
The benchmark uses the Pokec medium dataset to test exact N hop reachability from a single starting user. For each hop count from 1 to 5, both databases count the number of distinct users reachable through outbound friendship relationships.
This keeps the comparison focused on traversal depth rather than mixing in unrelated graph operations. The same dataset and hop range are used for both PostgreSQL 19 and Memgraph.
| Item | PostgreSQL 19 | Memgraph |
|---|---|---|
| Dataset | Pokec medium | Pokec medium |
| Dataset size | 100,000 vertices, 1,768,515 edges | 100,000 vertices, 1,768,515 edges |
| Query type | Exact N hop reachability | Exact N hop reachability |
| Query syntax | SQL/PGQ with GRAPH_TABLE and MATCH | Cypher with *BFS |
| Hop range | 1 to 5 | 1 to 5 |
| Timeout | 30 seconds | Completed all tested hops |
The setup uses Docker for both PostgreSQL 19 and Memgraph. The benchmark repo includes a load.sh script that loads the Pokec dataset into both engines.
For PostgreSQL, the script applies the SQL schema, loads the SQL dump, and creates the pokec property graph. For Memgraph, it loads the Cypher dump, creates indexes on :User and :User(id), and switches between analytical and transactional in memory modes during import.
The benchmark script uses a warmup run before timing and reports latency per engine along with the speedup ratio.
The full setup is documented in Memgraph’s best practices repository for anyone who wants to recreate the benchmark or inspect the scripts.
Benchmark Results
The key pattern does not the emerge in the first few hop result. At one hop, both engines are effectively in the same range because the query only expands to immediate neighbors.
The difference starts to matter as the traversal gets deeper. By four hops, PostgreSQL moved from milliseconds into seconds, while Memgraph stayed under 100 ms with a massive 11.5x speedup. At five hops, PostgreSQL hit the 30 second timeout, while Memgraph still completed the query in 259.15 ms.
That is the useful signal from this benchmark. SQL/PGQ makes graph shaped queries possible inside PostgreSQL, but deeper hop traversal exposes the cost of running graph workloads over a relational engine. Memgraph’s advantage appears when the query has to keep expanding through relationships rather than checking a shallow pattern.
Why Traversal Depth Matters
PostgreSQL 19’s SQL/PGQ support gives developers a graph query interface inside SQL. That is valuable for compatibility, convenience, and standards based graph querying over existing Postgres data.
But a graph query interface does not make the underlying database graph native.
In PostgreSQL, the graph is defined over relational tables. That works well when the graph query is shallow or when the main goal is to keep data inside Postgres. But deeper traversal puts pressure on the engine because each hop expands the search space.
Memgraph is built around the graph itself. Nodes and relationships are the main data model, and traversal is a core execution path. For exact hop reachability, the database is doing the kind of operation it was designed to do: follow relationships across the graph.
That is why the comparison changes with depth. At one hop, there is not much work to do. At four or five hops, the database has to keep expanding through the network. This is where graph native execution starts to matter.
Best Fit: PostgreSQL 19 SQL/PGQ vs Memgraph
The table below summarizes where each fits based on the role graph querying plays in your application.
| PostgreSQL 19 SQL/PGQ | Memgraph |
|---|---|
| Your connected data already lives in Postgres | The application depends on relationship-driven decisions |
| Graph queries are useful, but not the core workload | Queries need to follow paths across several connected steps |
| You need shallow relationship lookups or occasional graph analysis | Low-latency traversal matters for production workloads |
| You want to avoid adding another database just for graph analysis | You are building fraud, access control, infrastructure, recommendation, GraphRAG, or agent memory systems |
So the decision is less about whether PostgreSQL can now express graph queries. It can. The real question is whether graph traversal is occasional, or whether it is the workload your application depends on.
Final Takeaway
PostgreSQL 19’s SQL/PGQ support is an important step for graph querying in the SQL ecosystem. It gives Postgres users a standards based way to model and query their data without leaving their relational database.
But this benchmark shows the boundary between graph query support and graph native execution.
PostgreSQL 19 makes graph querying more accessible for SQL users. Memgraph is built for applications where graph traversal is the workload.
If your graph queries are shallow and your data already lives in PostgreSQL, SQL/PGQ may be enough. If your application depends on deep traversal, pathfinding, graph algorithms, or low latency multi-hop expansion, a native graph database is the stronger architecture.
To test this on your own workload, recreate the benchmark from the best practices repo or try the same kind of multi-hop traversal query in Memgraph against your graph data.
