7 ms·
Representing Graphs in PostgreSQL
- Epa095 2y agoThere is also https://age.apache.org/ https://age.apache.org/, an extension to facilitate graph queries in postgresql.
- lokimedes 2y agoIt was pretty dead last time I checked.
- CharlieDigital 2y agoGlad they used Cypher. One of the best and most intuitive query languages I've used personally.
- manojlds 2y agoYeah Cypher was so good and made everything so intuitive. Loved working with Neo4J for a prototype and then had to face the licensing issues and huge costs and had to abandon it.
- smidgeon 2y agoI got bitten by the same, we were looking at switching to memgraph (which is also Cypher, but C++ rather than Java), sadly abandoned for other reasons ...
- CharlieDigital 2y agoWhat reasons? Would love to know for future ref. If your org is amenable to Google Spanner or already using Spanner, it has preview support for Cypher and graph semantics: https://cloud.google.com/spanner/docs/graph/overview https://cloud.google.com/spanner/docs/graph/overview
- smidgeon 2y agoUnrelated to the tech, just the graph-based algorithm (recommender stuff) that we had in mind did not give us the results we were hoping for ... and other things were queued up to be tried ...
- mark_l_watson 2y agoThere are open source alternatives to Neo4J, and also very good scalable open source graph databases with query languages similar to Cypher. I think we are in agreement that it is a good idea to choose platform that scales both for compute and all other costs, like licensing costs.
- CharlieDigital 2y agoCan you list them? Not sure if you everyone reading is aware, but Neo4j did end up turning Cypher into the openCypher spec and that allowed a lot of other graph stores to adopt Cypher as a query language.
- mark_l_watson 2y agoI agree with you about Cypher. For a couple of decades I was a RDF and then RDF + SPARQL advocate, but I am a fairly recent convert to property graphs and Cypher.
- ikanreed 2y agoI was going to say, this is what SPARQL was designed for and it's much better at than SQL.
- alabastervlog 2y agoI had to use neo4j on a project some years ago and hated it (it didn’t help that the client forced its use for really dumb and bad reasons, wasting tons of time in the process) but Cypher is great. Only thing about it I liked. It’s very good.
- wslh 2y agoIf you are interested in the subject, also take a look at NetworkDisk[1] which enable users/devs of NetworkX[2] to work with graphs via SQLite. [1] https://networkdisk.inria.fr/ https://networkdisk.inria.fr/ [2] https://networkx.org/ https://networkx.org/
- yonisto 2y agoThis time it must be me... Bilbo is not Frodo's father (Frodo is actually Bilbo's first and second cousin, once removed)
- simpaticoder 2y agoVery good, and also Frodo refers to Bilbo as his "uncle".
- hobs 2y agoIt's also just right up front in the fellowship, he adopts Frodo because he never got around to finding a partner, implied because of his stewardship of the ring.
- ddkto 2y agoYes, but Bilbo does adopt him to make him his heir
- voodooEntity 2y agoIm a big fan of GraphDatabase's since about 10 years. I even wrote my own "in memory graph storage" in golang for a specific use case that none of the big GraphDatabase's could cover at the time. That said - i WISH people would embrase the existing GraphDatabases more and make the hosters support them as standard, rather than abusing existing relational databases for graph purposes. And to make it clear,i'm not talking about my own experimental one, i mean stuff like Neo4j, OrientDB etc.
- belter 2y agoWhen you look at AWS Neptune database implementation details, it looks realy close to the Aurora backend... :-) https://docs.aws.amazon.com/neptune/latest/userguide/migration-architectural-differences.html https://docs.aws.amazon.com/neptune/latest/userguide/migrati...
- voodooEntity 2y agoHrhr very true. Also, the last time i checked neptune, it could only be run in AWS but there was no public application image for local tinkering/dev. But its some years ago to be fair - maybe have changed.
- SJC_Hacker 2y agoThe only problem with representing graphs on an RDBMS is the queries. So whats the big issue if queries are added which can handle the graph cases?
- voodooEntity 2y agoThats like saying why do we need json we can represent it also in a textfile but accessing values can be more tricky. Sure you can represent a GraphDB in a RDBMS - but graphdbs are optimized for their specific use case. Therefor for example locking of resources is optimized for said purpose. When going a "Edge" and "Node" table approach, locking is by default rather unoptimized in many RDBMS. Just one simple example.
- t43562 2y agoltree is the one I ended up using. I don't like it much. The way it works allows you to setup a tree but you can't easily move things around within a tree once they're in. I forgot to say that it's also obviously only a tree, not a graph. It's still useful for some cases. It has a very good way of querying which is probably fast if you have very deep trees but in the end we didn't need the deep trees so it was chosen for the wrong reasons. https://www.postgresql.org/docs/current/ltree.html https://www.postgresql.org/docs/current/ltree.html You essentially have a path field in your record which lists the ids of all the records that are parents of the current one plus the current one. e.g. if your records are regions of the world and the id is the country name then the path might look like this: Earth.Europe.Poland There is support for queries like "what are all the descendants of Europe" SELECT name FROM regions WHERE path <@ 'Earth.Europe'; Or you can use matching: SELECT name FROM regions WHERE path ~ '*.Europe.*';
- simpaticoder 2y ago"CTE" refers to Postgres' "common table expression" syntax, the "WITH" keyword. See https://www.postgresql.org/docs/current/queries-with.html https://www.postgresql.org/docs/current/queries-with.html
- eatonphil 2y agoI thought this was going to be about querying a Postgres table with a graph query language (SQL/PGQ). Indeed this is coming to Postgres eventually. https://www.postgresql.org/message-id/flat/a855795d-e697-4fa5-8698-d20122126567%40eisentraut.org https://www.postgresql.org/message-id/flat/a855795d-e697-4fa... https://ashutoshpg.blogspot.com/2024/04/dbaag-with-sqlpgq.html https://ashutoshpg.blogspot.com/2024/04/dbaag-with-sqlpgq.ht...
- gunalx 2y agoLike apache age (postgres with cypher support) https://age.apache.org/ https://age.apache.org/
- eatonphil 2y agoWhat I'm talking about is going to be committed into Postgres.
- rounce 2y agoPostgraphile[1] does this via GraphQL, or have i misunderstood what you're referring to? 1: https://www.graphile.org/postgraphile https://www.graphile.org/postgraphile
- robertclaus 2y agoI've found the main advantage to this over a more specialized graph database is integration and maintenance alongside the rest of your application. Real world data is rarely just (or even mostly) graph data.
- osigurdson 2y agoIt is always good to know, at what point does "Postgres as X" break down. For instance, I know from experience that Postgres as timeseries DB (without add-ons) starts to break down in low billions of rows. It would be great to know that for graph DBs as well. I think a lot of people would prefer just to use Postgres if they can get away with it.
- scotty79 2y agoany recursive query is absurdly slow, so I think it scales wonderfully only if you match your representation to your workload
- demaga 2y agoI've done almost exactly the kind of thing described in article for a couple millions of rows. It broke down when I needed to find "friends of friends" of depth 6. None of the optimizations I could come up with helped. Neither did Apache Age. Maybe I'm just not skilled enough to handle such a workload with Postgres. But Neo4j handled it easily
- eurg 2y agoI'm not sure if you are serious or joking. "6 degrees of separation" is the famous radius for how many steps are needed such that everyone is connected. https://en.wikipedia.org/wiki/Six_degrees_of_separation https://en.wikipedia.org/wiki/Six_degrees_of_separation
- demaga 2y agoExcept that it wasn't about people at all? I was just referring to a _type_ of query
- ffsm8 2y agoWhat kind of data was it, of I may ask? Graph databases have a very narrow usecase, and it's almost always in relation to people - at least ime. Though the data type isn't really important for the performance question, the amount of data selected is. So a 6-level depth graph of connections that only connect 2-3 entities would never get into performance issues. You'd be able to go way beyond that too with such a narrow window. (3 entity Connections on 6 level join would come out to I believe ~750 rows) If you're modeling something like movies instead, with >10 actors per production you're looking at millions of rows.
- hknlof1 2y agoAt DuckCon #6 there was a talk given about implementing SQL/PGQ as an extension to DuckDB https://m.youtube.com/watch?v=QDdTbhSR2Vo https://m.youtube.com/watch?v=QDdTbhSR2Vo https://duckdb.org/community_extensions/extensions/duckpgq.html https://duckdb.org/community_extensions/extensions/duckpgq.h...
- idefine 2y agoI recently came across https://kuzudb.com/ https://kuzudb.com/ which takes a lot of inspiration from DuckDB. Seems promising for embedded.
- pella 2y agoIf you need some "Routing Graph" - check the pgRouting library https://pgrouting.org/ https://pgrouting.org/ "pgRouting library contains following features: All Pairs Shortest Path, Johnson’s Algorithm All Pairs Shortest Path, Floyd-Warshall Algorithm Shortest Path A* Bi-directional Dijkstra Shortest Path Bi-directional A\* Shortest Path Shortest Path Dijkstra Driving Distance K-Shortest Path, Multiple Alternative Paths K-Dijkstra, One to Many Shortest Path Traveling Sales Person Turn Restriction Shortest Path (TRSP)"\* see more: https://docs.pgrouting.org/latest/en/pgRouting-concepts.html#graphs https://docs.pgrouting.org/latest/en/pgRouting-concepts.html...
- mycall 2y agoIs it normally preferred to use some library such as this over a more traditional approach of nested sets, adjacency lists or ltree module?
- pella 2y agoPG Database + "The Boost Graph Library (BGL)" C++ ( https://www.boost.org/doc/libs/1_87_0/libs/graph/doc/index.html https://www.boost.org/doc/libs/1_87_0/libs/graph/doc/index.h... )+ PostGIS ==> PGRouting Just check the Workshop : https://workshop.pgrouting.org/3.0/en/index.html https://workshop.pgrouting.org/3.0/en/index.html Pedestrian Routing: https://workshop.pgrouting.org/3.0/en/basic/pedestrian.html#pgr-dijkstra https://workshop.pgrouting.org/3.0/en/basic/pedestrian.html#... Graph views: https://workshop.pgrouting.org/3.0/en/basic/graph_views.html https://workshop.pgrouting.org/3.0/en/basic/graph_views.html Create a Network Topology: https://workshop.pgrouting.org/3.0/en/advanced/chapter-12.html https://workshop.pgrouting.org/3.0/en/advanced/chapter-12.ht...
- dangoodmanUT 2y agoThis is where you start to see major limitations of OLTP, and need to look at specialized graph DBs (or indexes really) that take advantage of index-free adjacency
- gjtorikian 2y agoIt’s a neat trick! A simpler choice would be to use Postgres’ own ltree data type: https://www.postgresql.org/docs/15/ltree.html https://www.postgresql.org/docs/15/ltree.html I wrote about how we use it here: https://www.yetto.app/blog/post/how-labels-work/ https://www.yetto.app/blog/post/how-labels-work/
- jitl 2y agoThe issue with ltree is that it requires fanout on write when moving a node. The downside is you need to update every recursive descendant of the moved node to rewrite their ancestor path for the new location in the tree, so a move is O(subtree nodes), but you get to scan a subtree in using btree prefix search which is great. That makes it good for relatively static and flat data like your label hierarchy, which probably receives a new label or a repainting within a tree relatively infrequently, and might have a p95 depth of 10. That makes it also a good fit for actual human (parent, child) relationships since parent-child change is usually infrequent and the total children per layer in the tree is also small. For a tree like a Notion workspace where depth can be quite deep, and layers can easily have hundreds or hundreds of thousands of siblings, the cost at write-time when you reparent an ancestor in the worst case isn’t feasible. For something like a social graph I’m not sure how to use ltree at all since a social graph isn’t a dag.
- deleted 2y ago[deleted]
- ForHackernews 2y agoSurprised to see this article with no mention of LTree: https://www.postgresql.org/docs/current/ltree.html https://www.postgresql.org/docs/current/ltree.html First-party data structure for tree (directed, acyclic graph) data
- zamalek 2y agoThis doesn't seem to cover infinite recursion, which is one of the ugliest parts of doing this type of query with CTEs. You effectively need to concatenate all of the primary keys you've seen into a string, and check it each recursive iteration. The approach I came up with was to instead use MSSQL hierarchy IDs (there's a paper describing them, so they can be ported to any database). This specifically optimizes for ancestor-of/descendant-of queries. The gist of it is: 1. Find all cycles/strong components in the graph. Store those in a separate table, identifying each cycle with an ID. Remove all the nodes in the cycle, and insert a single node with their cycle ID instead (turning the graph into a DAG). The reason we do this is because we will always visit every node in a cycle when doing an ancestor-of/descendant-of query. +---+ +-------> B +------+ +-+-+ +-^-+ +-v-+ | A | | | C | +---+ | +-+-+ +-+-+ | | D <------+ +---+ Becomes: +---+ +---+ | A +--> 1 | +---+ +---+ +---+---+ | 1 | B | | 1 | C | | 1 | D | +---+---+ 2. You effectively want to decompose the DAG into a forest of trees. Establish a worklist and place all the nodes into it. The order in this worklist may be something that can affect performance (you want the deepest/largest tree first). Grab nodes out of this worklist and perform a depth-first search, removing nodes from the worklist as you traverse them. These nodes can then be inserted into the hierarchy ID table. You should insert all child nodes of each node, even if it has already been inserted before, but only continue traversing downwards if the node hasn't yet been inserted. +---+ +----> B +----+ +-+-+ +---+ +-v-+ +---+ | A | | D +--> E | +-+-+ +-^-+ +---+ | +---+ | +----> C +----+ +---+ Becomes: +---+ +---+ +---+ +---> B +--> D +--> E | +-+-+ +---+ +---+ +---+ | A | +-+-+ +---+ +---+ +---> C +--> D | +---+ +---+ Or, as hierarchy IDs A /1 B /1/1 D /1/1/1 E /1/1/1/1 C /1/2 D /1/2/1 Now, you do still need a recursive CTE - but it's guaranteed to terminate. The "interior" of the CTE would be a range operation over the hierarchy IDs. Basically other.hierarchy >= origin.hierarchy && other.hierarchy < next-sibling(origin.hierarchy) (for descendant-of queries). You need to recurse to handle situations involves nodes like D in the example above (if we started at C, we'd get D in the first iteration, but would need to recurse to the first D node in order to find E). This was two orders of magnitude faster than a recursive CTE using strings to prevent infinite recursion. The major disadvantage of this representation is that you can't modify it. It has to be calculated from scratch each time a node in the graph is changed. The dataset I was dealing with was 100,000s of nodes for each customer, took under a second, so that wasn't a problem. You could probably also identify changes that don't require a full rebuild (probably any change that doesn't involve a back edge or cross edge), but I never had to bother so didn't solve it.
- jakozaur 2y agoThere was a very good discussion about PostgreSQL as graph database on Hacker News about a year ago: https://news.ycombinator.com/item?id=35386948 https://news.ycombinator.com/item?id=35386948
- deleted 2y ago[deleted]