Hacker News Reader

Comment by waffle_ss | Hacker News Reader

It’s possible with recursive CTEs, but very slow.

https://stackoverflow.com/questions/52674380/improving-postg...

There's nothing essentially, inherently slower about recursive CTEs in SQL databases compared to graph database queries, it depends how they're implemented, particularly whether they take advantage of indexing and caching. They're both going to be doing fundamentally the same type of algorithm under the hood.

I've gotten recursive CTEs in SQL Server to perform quite well just by indexing the join key columns.

Graph databases like Neo4j have a very important performance characteristic called "index-free adjacency".

This means that a traversal from node to node (similar to a JOIN in a relational database) does NOT use an index. Instead, it's more like chasing pointers, jumping directly to an offset. Whereas relational databases do use an index to perform JOINS - it's essentially a set comparison, using an index to see where two sets overlap.

What this means is that the performance of joins in relational databases is dependent on the overall size of the tables, while the performance of traversals in a graph database that implements index-free adjacency is not dependent on the overall size of the data (rather just the connectedness of the nodes being traversed), because an index is not used for traversals.

There's no reason that a relational database couldn't also have index-free adjacency. Alongside every foreign key, you store a file pointer to the row with that key.

I assume that the reason relational databases don't do this is that the speedup isn't worth the complexity and performance cost of keeping those pointers up to date for the kinds of queries that relational databases usually do.

OTOH, if you could have it opt-in on a per-FK basis in an RDBMS, the cost could be avoided where not needed, but the performance benefit available where needed.

interviewed with a know-it-all type sr. engineer once, and he asked me an incredibly defensive question like, "why would i use a graph database instead of postgresql, it cant do anything that can't be done in postgres!?!?"

i'm no expert on any of this, but my response was still sufficient to get hired: you don't need a graph db, but it's easier to understand what cypher is doing than what sql is doing... that means more productivity to your lower-cost junior developers.

There is a older, but seemingly relevant, question/answer for this on stack overflow: https://stackoverflow.com/a/5611541/92359

> if you shrink a table, or update a partitioned table (causing a row to move to another partition) or if you are rebuilding a table, or export/import a table, or... or... or... the rowid will change.

If the rowids are not stable across db operations, it wouldn't make sense to use them for implementing index-free adjacency. Do any alternatives remain? If not you're back to joins.

One of the reasons why Neo4j can use index-free adjacency is that the ids used for nodes and relationships are pointers to the location of the nodes and relationships in the relevant store files. Those are stable across updates and deletes of other data, and when you delete a node, all its relationships must be deleted first so there are no hanging relationships.

Ahhh, this is the kind of thing I was looking for. Thanks!

I don't buy the index-free hype. Leaving aside the problem of a distributed implementation, imagine you have a node with lots of labeled edges going out, and you're only interested in following some of those edges. You have to find the right ones somehow - full scan of all the edges, or - an index. Or, for a more detailed comment (not mine), see eg https://www.arangodb.com/2016/04/index-free-adjacency-hybrid... .

There are of course certain structures you can use to ease the selection of the relationships you want to follow, and Neo4j does use some of its own, breaking down relationships on a node first by type, and then by incoming or outgoing, allowing a quick selection of relevant relationships to follow depending on what's desired.

Whether additional structures are used at this level or not, the point of index-free adjacency is you do not need to utilize an index at the table/label level. The cost of performing each expansion is not dependent upon the total number of relationships or nodes in the graph, as it would be for table joins. You are only ever considering the relationships on each specific node at a time as you traverse.

Seems to me as long as you have that then you've got (table) index-free adjacency.

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.

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-n...

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

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.

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

[2]: https://neo4j.com/business-edge/connected-data-cripples-rela...

"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.

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.)

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/

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.

Deletes do have an extra cost as relationships do need to be deleted first, and there are some batching approaches for handling this case. For graph databases there's not much choice on this unless you want to deal with dangling relationships (and resulting inconsistencies).

Note that deleting of nodes does not have to create new relationships between the adjacent nodes, so not quite like deleting nodes from the middle of a doubly-linked list.

A large pagecache is recommended for optimal speed, and SSDs are also recommended. Hardware continues to become cheaper.

Relational databases and Neo4j use indexes differently, which I think is part of your confusion here. We both use indexes for looking up nodes, true, but Neo4j only uses this for finding certain starting (or end) nodes in the graph. The important (and more complicated and costly) part of a query isn't finding your starting nodes...it's expanding and traversing from these nodes through your graph.

Neo4j uses index-free adjacency for traversing the graph. Relational dbs need to use table joins. One of these is only dependent on the relationships present on the nodes traversed (or rather only the relationships you're interested in, if you've specified restrictions on the relationship type and/or direction). Table joins are dependent on the size of the tables joined (then of course you must consider how many joins you must perform...and how to do these joins if there's nothing restricting which tables to join in the course of traversal).

Again, index-free adjacency does not mean that we must adhere to this in the most literal sense. Ideological purity is not the point. Graph traversals are the most complex part of a graph query, and this is where index-free adjacency is used to the advantage of native graph dbs.

And just to note, we certainly can join nodes based on property values, just like a relational database, and yes we can even use an index to speed that up, in the same manner as relational dbs. In fact you may indeed need to do this in order to create the relationships that you'll use later in your queries. Graph dbs are optimized such that if you do need to use joins, you'll perform them early, and once, so that you can take advantage of index-free adjacency during traversal in your read queries. Traversal speed and efficiency is the point of index-free adjacency.

Reply on news.ycombinator.com