5 ms·

It's inherently slower because of the explosion in join table size as your depth increases and the slowness of using b-tree indexes instead of direct pointers t

It's inherently slower because of the explosion in join table size as your depth increases and the slowness of using b-tree indexes instead of direct pointers to neighbor nodes ("index-free adjacency") or the newer sparse matrix transforms (GraphBLAS) that graph databases use. What kind of database sizes have you used in your SQL Server experience? The linked StackOverflow question uses Postgres with 1M records, 50M relationships, and does index the join key columns. Maybe I'll have to replicate it on SQL Server in case there's some secret sauce but I'm highly skeptical.

benkrug 7y ago
Here's a super-basic test using MySQL CTEs w/1.6M nodes and 30M edges that I did a few years ago - https://intertubes.wordpress.com/2017/11/28/benchmarketing-neo4j-and-mysql/ https://intertubes.wordpress.com/2017/11/28/benchmarketing-n...
- taffer 7y ago
  There is also this [1] paper claiming that > [...] solutions using relational database technology [...] can offer performance superior to that of the dedicated graph databases. [1] https://event.cwi.nl/grades2013/07-welc.pdf https://event.cwi.nl/grades2013/07-welc.pdf
  - AndrewBowman 7y ago
    Note that this is an old paper. They are using Neo4j 1.8.2 for this (and the community version at that), which was released in February of 2013. Neo4j is at 3.5.9 currently, with 4.0 on the horizon, so there have been 2 major releases, nearly 3, since the paper, and dozens of minor releases and patch releases. I'm sure Oracle has been making improvements as well (all of the authors are from Oracle), so in any case the paper itself is too outdated to be useful.
    - taffer 7y ago
      The benchmark [1] that Neo4j uses in its advertising [2] is from 2014, so not much newer either. [1]: https://github.com/opencredo/neo4j-in-action https://github.com/opencredo/neo4j-in-action [2]: https://neo4j.com/business-edge/connected-data-cripples-relational-performance/ https://neo4j.com/business-edge/connected-data-cripples-rela...
kyllo 7y ago
"the slowness of using b-tree indexes instead of direct pointers to neighbor nodes" If you don't use a b-tree, you still need some other in-memory data structure like a hash table to hold the pointers. "Direct pointers" don't help you if you have to read a node from disk before you can dereference its pointers. In my case, I was working with a graph consisting of about 10M nodes and 35M rows of edges (parent-child relationships, where a parent can have many children and a child can have many parents). Many of those 10M parts weren't actively used anymore, so a minority of nodes had a majority of the relationships. I don't have access to the data anymore, but I recall being able to retrieve the transitive closure on a subgraph of ~10k nodes in 5-10 seconds, and the entire graph in about 7-8 minutes. This was on a small, possibly underpowered SQL Server instance. It's possible that Neo4j would do it faster, but I decided it was not worth moving all my data into a different database and introducing that ETL latency, to improve upon performance that was already acceptable for the business need. I have heard anecdotally that SQL Server's CTEs are more performant than PostgreSQL's, but I don't have evidence of this, and it could be outdated if Postgres has made improvements since I heard that.
- AndrewBowman 7y ago
  In Neo4j at least the node ids are offsets into the node and relationship stores, so you are literally pointer hopping through the store files from node structure to relationship structure to node structure. No need for a hash table or b-tree index (excepting finding your starting nodes in the graph before beginning traversal.)
  - kyllo 7y ago
    Wouldn't that make deletes super expensive, similar to deleting nodes from a doubly-linked list on disk in terms of complexity? How could it delete a node with millions of relationships if it needs to read all those blocks from disk to traverse all the pointers? And doesn't it cause more cache misses when the on-disk pointers refer to nodes that are spread out across different file blocks? And why does Neo4j have indexes if it claims to have no need for them? https://neo4j.com/docs/cypher-manual/current/schema/index/ https://neo4j.com/docs/cypher-manual/current/schema/index/ I don't know how Neo4j is implemented, but I'm skeptical that it's purely index-free adjacency, I suspect there is some hybrid data structure backing it.

benkrug 7y ago

Here's a super-basic test using MySQL CTEs w/1.6M nodes and 30M edges that I did a few years ago - https://intertubes.wordpress.com/2017/11/28/benchmarketing-neo4j-and-mysql/ https://intertubes.wordpress.com/2017/11/28/benchmarketing-n...

taffer 7y ago
There is also this [1] paper claiming that > [...] solutions using relational database technology [...] can offer performance superior to that of the dedicated graph databases. [1] https://event.cwi.nl/grades2013/07-welc.pdf https://event.cwi.nl/grades2013/07-welc.pdf
- AndrewBowman 7y ago
  Note that this is an old paper. They are using Neo4j 1.8.2 for this (and the community version at that), which was released in February of 2013. Neo4j is at 3.5.9 currently, with 4.0 on the horizon, so there have been 2 major releases, nearly 3, since the paper, and dozens of minor releases and patch releases. I'm sure Oracle has been making improvements as well (all of the authors are from Oracle), so in any case the paper itself is too outdated to be useful.
  - taffer 7y ago
    The benchmark [1] that Neo4j uses in its advertising [2] is from 2014, so not much newer either. [1]: https://github.com/opencredo/neo4j-in-action https://github.com/opencredo/neo4j-in-action [2]: https://neo4j.com/business-edge/connected-data-cripples-relational-performance/ https://neo4j.com/business-edge/connected-data-cripples-rela...

kyllo 7y ago

"the slowness of using b-tree indexes instead of direct pointers to neighbor nodes" If you don't use a b-tree, you still need some other in-memory data structure like a hash table to hold the pointers. "Direct pointers" don't help you if you have to read a node from disk before you can dereference its pointers. In my case, I was working with a graph consisting of about 10M nodes and 35M rows of edges (parent-child relationships, where a parent can have many children and a child can have many parents). Many of those 10M parts weren't actively used anymore, so a minority of nodes had a majority of the relationships. I don't have access to the data anymore, but I recall being able to retrieve the transitive closure on a subgraph of ~10k nodes in 5-10 seconds, and the entire graph in about 7-8 minutes. This was on a small, possibly underpowered SQL Server instance. It's possible that Neo4j would do it faster, but I decided it was not worth moving all my data into a different database and introducing that ETL latency, to improve upon performance that was already acceptable for the business need. I have heard anecdotally that SQL Server's CTEs are more performant than PostgreSQL's, but I don't have evidence of this, and it could be outdated if Postgres has made improvements since I heard that.

AndrewBowman 7y ago
In Neo4j at least the node ids are offsets into the node and relationship stores, so you are literally pointer hopping through the store files from node structure to relationship structure to node structure. No need for a hash table or b-tree index (excepting finding your starting nodes in the graph before beginning traversal.)
- kyllo 7y ago
  Wouldn't that make deletes super expensive, similar to deleting nodes from a doubly-linked list on disk in terms of complexity? How could it delete a node with millions of relationships if it needs to read all those blocks from disk to traverse all the pointers? And doesn't it cause more cache misses when the on-disk pointers refer to nodes that are spread out across different file blocks? And why does Neo4j have indexes if it claims to have no need for them? https://neo4j.com/docs/cypher-manual/current/schema/index/ https://neo4j.com/docs/cypher-manual/current/schema/index/ I don't know how Neo4j is implemented, but I'm skeptical that it's purely index-free adjacency, I suspect there is some hybrid data structure backing it.