PostgreSQL 19 vs Memgraph: Comparing Graph Traversal Performance

Get a demoGet started

Back to blog

Neo4j and comparisons

PostgreSQL 19 vs Memgraph: Comparing Graph Traversal Performance<br>By Sabika Tasneem<br>6 min readJuly 8, 2026

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.

ItemPostgreSQL 19MemgraphDatasetPokec mediumPokec mediumDataset size100,000 vertices, 1,768,515 edges100,000 vertices, 1,768,515 edgesQuery typeExact N hop reachabilityExact N hop reachabilityQuery syntaxSQL/PGQ with GRAPH_TABLE and MATCHCypher with *BFSHop range1 to 51 to 5Timeout30 secondsCompleted all tested hops<br>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...