Hacker News Reader

Comment by henryfjordan | Hacker News Reader

I implemented pretty much exactly this setup once.

For what it's worth, there's a lot of footguns with this approach. You need to be careful about infinite cycles and things like that. You also just do not get the ergonomics of using a query language that is meant for graph data. Once you get it all setup and experience the issues you will no doubt be able to build whatever you want but there's a learning curve.

In the end we switched to using Neo4j and were able to build new features a lot more quickly than we would've been able to on Postgres.

It's also worth mentioning that there are many ways to store graph data, and using an "adjacency list" like is being done here may or may not be the best way for your use case. Neo4j I think uses a different approach where nodes store info about edges they are connected to directly, so you don't even need to hit an index to follow an edge.

View on HN

> You need to be careful about infinite cycles and things like that.

Not really, just never forget this: always use `UNION`, and never `UNION ALL`, in recursive queries!

There are still ways to go wrong. Try writing a query which explores a graph from a starting node, building up a path from the start to each node as a string. Even using UNION you will get an infinite loop, because every visit to a node in the loop has a different path, so it makes a unique row.

The aggregation needs to be done after you've computed the transitive closure, not while you're computing it.

To me, that all sounds like you need to be careful.

I mean, yes? This is easy to learn the hard way, but it's also easy to learn. Once learned you don't forget.

You started the thread by disagreeing with “you need to be careful”, and the OP is pointing out that your thread conclusion is “you need to be careful”.

Maybe, but both shared useful points along the way. Elaboration IOW. All good.

I think the only way to build the path up is to do it as you're traversing, though.

Here's a small example:

  create table node (
    name varchar primary key
  );

  create table edge (
    from_name varchar not null references node (name),
    to_name varchar not null references node (name)
  );

  insert into node values
    ('Hawaii'),
    ('San Francisco'),
    ('New York'),
    ('Houston');

  insert into edge values
    ('Hawaii', 'San Francisco'),
    ('San Francisco', 'New York'),
    ('San Francisco', 'Houston'),
    ('Houston', 'New York');

  with recursive route (destination_name, path) as (
    values ('Hawaii', 'Hawaii')
    union
    select to_name, route.path || ' -> ' || to_name
    from route
    join edge on route.destination_name = edge.from_name
  )
  select * from route;

That works as long as the graph is acyclic. If you add an edge from New York to Houston, say, then the query goes into an infinite loop.

How would you do this after computing the transitive closure? And how would that avoid an infinite loop?

Ah, yes, I flubbed -- this one requires aggregation as you go. It's tricky. Ideally you could have a decent aggregation data structure for the path that lets you select a distinct sequence (path) of middle points. One could write such an aggregation function, I think. Lacking that you have to limit the length of all paths between any pair of points to the longest possible path (which is the number of points minus one), which is annoying, and then you still have to fix up each resulting path to remove any repeating suffix.

  sqlite> .schema
  CREATE TABLE edge (src text, dst text);
  sqlite> with recursive paths (src, dst, len, path) as (
     ...> select src, dst, 0, src || '->' || dst from edge
     ...> union
     ...> select p.src, e.dst, p.len + 1, p.path || '->' || e.src from paths p join edge e on p.dst = e.src where p.len < (select count(*) from (select src from edge union select dst from edge))) select * from paths;
  Hawaii|San Francisco|0|Hawaii->San Francisco
  San Francisco|New York|0|San Francisco->New York
  San Francisco|Houston|0|San Francisco->Houston
  Houston|New York|0|Houston->New York
  Houston|Hawaii|0|Houston->Hawaii
  Hawaii|Houston|1|Hawaii->San Francisco->San Francisco
  Hawaii|New York|1|Hawaii->San Francisco->San Francisco
  San Francisco|Hawaii|1|San Francisco->Houston->Houston
  San Francisco|New York|1|San Francisco->Houston->Houston
  Houston|San Francisco|1|Houston->Hawaii->Hawaii
  Hawaii|Hawaii|2|Hawaii->San Francisco->San Francisco->Houston
  Hawaii|New York|2|Hawaii->San Francisco->San Francisco->Houston
  San Francisco|San Francisco|2|San Francisco->Houston->Houston->Hawaii
  Houston|Houston|2|Houston->Hawaii->Hawaii->San Francisco
  Houston|New York|2|Houston->Hawaii->Hawaii->San Francisco
  Hawaii|San Francisco|3|Hawaii->San Francisco->San Francisco->Houston->Hawaii
  San Francisco|Houston|3|San Francisco->Houston->Houston->Hawaii->San Francisco
  San Francisco|New York|3|San Francisco->Houston->Houston->Hawaii->San Francisco
  Houston|Hawaii|3|Houston->Hawaii->Hawaii->San Francisco->Houston
  Houston|New York|3|Houston->Hawaii->Hawaii->San Francisco->Houston
  Hawaii|Houston|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco
  Hawaii|New York|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco
  San Francisco|Hawaii|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston
  San Francisco|New York|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston
  Houston|San Francisco|4|Houston->Hawaii->Hawaii->San Francisco->Houston->Hawaii
  sqlite>

Aha, nice, i didn't think of just limiting it that way! The need to postprocess this is annoying but only very mildly; i think it takes a fairly simple window function.

I had a go at changing my query to only produce one route to each node, by excluding rows in the recursive step which go to a node for which we already have a destination, but i couldn't find a way to do it which PostgreSQL would accept, because you can't use the recursive table in an outer join or a subquery.

The PostgreSQL has some advice about dealing with cycles, but i haven't worked up the mental energy to absorb it:

https://www.postgresql.org/docs/14/queries-with.html#QUERIES...

Well, it's a nice trick but it's O(N^2) in terms of output size because you have N items and paths up to N-1 long, so you have up to N ~N-length paths. If your data is guaranteed to have loops then this could be annoying.

The PG thing works trivially because you can use an array for the path and inspect the array in each iteration. That's harder to do in SQLite3, but... you could: just format a string like '%->' || src || '->%' then use it with `like()` to check if the path you're adding `src` to already has it.

Seems to be a Postgres-specific advice?

Others, for example SQLite[1], seem to advocate using UNION ALL over UNION.

[1]: https://sqlite.org/lang_with.html#recursive_query_examples

No, it's not Postgres-specific advice. Using UNION ALL in recursive queries is a mistake if you have cycles in your data. This follows from first principles and the standard.

Right, bit early so wasn't thinking in terms of cyclic data, we've only used it for acyclic graphs (typically trees).

There is some theoretical work on datalog you might be interested in. Recursive queries over sets are guaranteed to terminate if they don't contain negations / aggregations, and if they have a finite herbrand universe, which, very roughly speaking, means that no functions can return new constants or tuples of unbounded length.

eg: recursively generating the set of x := x + 1 won't terminate beacuse x goes to infinity, and you get infinite tuples. x := abs(x) is fine, since you get up to two tuples per input tuple (-1, and 1, for example).

Anyway, if you ask for the query to build up all paths (of unbounded length), it won't terminate. If you asked for shortest paths, (bounded by the number of nodes in the source database) it would.

Interesting. Most of that makes sense I think, though a bit outside my normal sphere.

I was struggling why aggregates were excluded so to speak, but I guess it's because they have to be repeatedly evaluated? Ie compute the sum, add it to the output, now you might have to recompute the sum? Perhaps I'm being dense here, left my thinking cap at home.

Piggybacking on your Neo4J reference....can anyone suggest any resources that would be good for someone from the SQL world who is very uninformed on graph databases to quickly get their head around the key ideas, but even more importantly, how to choose a platform among the offerings (licensing being I think a key issue, I've heard Neo4J can get expensive)...assume a large, "social media" scale system, to be safe.

you can use datomic as a good example. https://hashrocket.com/blog/posts/using-datomic-as-a-graph-d...

another good example using predicates - https://github.com/threatgrid/asami/wiki/2.-Introduction

Neo4j has a self-hosted community edition that is free, though you need to update to Enterprise to expand your DB beyond one node. It's worth noting though that scaling from a single node to a cluster is going to have some pretty huge performance issues whether you are using SQL or Neo4j to store your graph. The power of graph databases is that it should be very inexpensive to follow an edge in the graph but when that leads to a network hop you lose a lot of performance.

If you are comfortable fitting your data onto one box, then development speed is probably more important than other factors and I would just try a few databases out and especially pay attention to how good the libraries are in your programming language of choice. Neo4j for instance had high quality libraries in Java but the experience in Python was not as good.

If you have a lot of data or need next-level performance, I would start by doing some research on the various ways to store graph data and then pick a DB that supports the approach you want to take.

Vaticles typed bid intriguing

As someone who hated being in the SQL world and couldn’t figure out why until years later when I found out about graph databases, here’s one big shift:

Graph database store true relationships.

The R in RDBMS and the concept of relationships by primary keys are lies (imo). They lead people away from what true relationships can be. Databases like Neo4j are not about doing any sort of PK or join or merge-before-query. Looking up by connection is the fastest way to find information. If your RDBMS had one table for phone numbers, one for email addresses, one for first names, one for last names, one for street, and so-on it would take huge amounts of time to query to find all the detail for a single person. With a graph database it takes a small amount of time to find the first bit of info (let’s say phone number since it’s easily sorted), and then every other bit of linked data is essentially free.

Effectively, moving from RDB to a graph database just shifts relationship resolution from query time to insert/update time. Sometimes this can be an advantage. I’d even wager usually.

Well said and agreed!

This is very good news for my purposes, thank you!

It also switches you from schema-based data model to schemaless data model.

Apologies in advance; the R for relational is with respect to the tuple, that is amongst the unordered items which are serialized within a row in a table and not the keys which link different tables, the lie you find does not originate in the definition.

As someone who has wanted to love the graph dbs, keep with narrow focus top down queries where the index free adjacency lets you avoid touching the bulk of your data, and stay away from bulk queries that may need to visit everywhere multiple times, which is unfortunately where things get interesting.

The R in RDBMS stands for the mathematical term of relations which is defined as a subset of a cartesian product.

Sounds great, what are the downsides? When is it a definitely bad idea to use it?

For some basics of graph modeling take a look at https://memgraph.com/docs/memgraph/tutorials/graph-modeling.

Some differences between SQL and graph databases are covered at https://memgraph.com/blog/graph-database-vs-relational-datab....

I was looking at graph databases/Neo4j a lot early last year and found Neo4j has a lot of good resources.

You can get this book for free through their website. [1]

This have some good documentation[2], including this page "Transition from relational to graph database".[3]

[1] https://neo4j.com/graph-databases-book/

[2] https://neo4j.com/docs/getting-started/current/

[3] https://neo4j.com/docs/getting-started/current/appendix/grap...

I've been using EdgeDB in a greenfield project and loving it. Some rough edges (forgive the pun) but fantastic for prototyping / smaller projects and could be a good candidate for large projecs. I like it better than when I used neo4j a few years back for a client project. Much better license and I really like that it's built on top on postgres.

> how to choose a platform among the offerings (licensing being I think a key issue, I've heard Neo4J can get expensive)

Safest bet (knowing nothing else about your needs): Build at least three prototypes, preferably rapidly and in parallel. Only after doing so will you be able to ask the right questions that speak accurately to your specific needs and therefore be able to map actual requirements to the different graph databases.

I’d be curious what other experienced graph database people would say about their first bigger projects. Looking back, my first graph projects involved significant iteration and several restarts. And these were still necessary after having significant background knowledge about the algorithms, offerings, and trade offs.

There are many people in roles/orgs that don’t have the humility or organizational cover to admit that these early projects are largely experimental learning experiences.

> ...assume a large, "social media" scale system, to be safe.

This broad assumption is going to cost you.

Instead, I’d encourage you to reframe this assumption in more specific terms such as read, write patterns; need for consistency, availability; support expectations; your talent pool; and lots more. Estimates can be on a log10 scale: 1, 10, 100, 1000 and so on,

Reply on news.ycombinator.com