3 ms·
CTEs in general are fine, just beware of using recursive CTEs to model graphs - and do graph operations - inside Postgres. My experience has been that the perf
by mindcrime 13y ago
CTEs in general are fine, just beware of using recursive CTEs to model graphs - and do graph operations - inside Postgres. My experience has been that the performance is pretty abysmal in that case, for even fairly small graphs. IMO, if you find yourself doing a lot of "graph stuff" just go ahead and store the graph in Neo4J or Titan or something.
Note that I don't mean to argue against the point of this post... CTEs are very handy. It's just that one of the more commonly cited uses for them is to do graph stuff, and my experience trying to that, specifically, has not been positive.
- craigkerstiens 13y agoRecursive CTEs can absolutely be more performance intensive, and even non recursive CTEs can be an optimization bottleneck. However from what I've seen with non recursive CTEs is that you're looking at a 1.5-2x difference in performance (in the bad cases) versus orders of magnitude. For making SQL more readable and shareable this seems a small price to pay, its much the same that people use higher level languages rather than dropping down to C for everything they need to do.
- einhverfr 13y agoAs a counter-point here, I would point out that there are cases where we've found (with the LedgerSMB project) drastic increases in performance in switching to CTE's, especially with recursive ones. The reason is that if you have a stable result set which is complex to calculate (particularly if it involves recursive processing), but needs to be checked against multiple conditions in different subqueries, it is far better to materialize it once and check a few times, than to materialize it in every subquery. For example, our menu uses a simple referential tree. Generating this with connectby() when we had to support 8.3 primarily usually worked unless you wanted to exclude a large number of rows based on permissions. In that case, it would take better part of a minute to run. Not good for a web app. Moving to recursive CTE's cut the execution time of our best performance in half, and increased our worst cases by orders of magnitude. To be honest though, for shareable code, I think views are often better because they represent a stable interface that can be documented regarding acceptable uses (should you join this view? self-join it?). What CTE's often buy you though is an ability to break a query off into multiple, independently testable pieces (where a view might be overkill due to a lack of sharing), and that allows you to better debug when something goes wrong.
- jfb 13y agoYeah, graph storage is not a problem that is amenable to a SQL solution. ISTR that this very thing basically killed Friendster.
- matwood 13y agoWhen speaking of performance you always need a dataset size qualifier (what does small mean?). I have used CTEs in MSSQL to manage graphs and it performed really well. None of the relationship tables had more than 1M rows in it though.
- mindcrime 13y agoYeah, it depends on what you're trying to do with the graph as well. I was using a mix of Postgres operations and Java code to do a Floyd-Warshall "all shortest paths" calculation. I forget how many vertices I had, but it wasn't many... on the order of hundreds or thousands, at most. And the Postgres part just totally bogged down when using CTEs. I finally switched to storing the underlying graph itself in my own hand-rolled format (and eventually ran into different bottlenecks, but that's another story). Now it's possible that if I were more of a Postgres expert, I could have tuned or optimized it to behave better. But at the minimum, I'll say that a naive graph implementation using CTEs didn't prove to scale well for me, in this given use-case.
- batbomb 13y agoDoing graph processing by explicitly populating a temp table is nearly as fast in many cases as neo4j with the added benefit of a vastly improved analytics experience if you plan to analyze the data or do range queries, etc... It is more work to do it smartly and efficiently, but it is possible. I'll try to find a python script I wrote as a PoC with SQLite. CTEs and recursive queries are okay for many cases, but they can blow up your RDBMS temp space easily if you aren't careful. Especially useless is a non-materialized view based on them.
- aidos 13y agoI'd be interested in seeing how you approach some of the things that graphs are better at. I have an understanding of creating efficient tree structures in a relational model - I haven't thought about the more general case of graphs though. I was recently involved in a project that was using neo4j as a datastore. In the end we switched to postgres because the cognitive load was lower, the tooling was better and the relationship management was easier and more explicit. The trade off is going to be that later the relationship exploration will be a little harder. My plan was to add a graph datastore back in to mirror the relationships in the system so we could query it.
- einhverfr 13y agoI think your big limiting factor in graph analysis with recursive cte's is that PostgreSQL is relational and therefore set-based. This effectively forces any search into a breadth-first search. I don't see any reason why doing breadth-first searches would be any slower on PostgreSQL than Neo4j. But the question is, what happens when bredth-first is not what you want to do? Now with some work, it should be quite possible to do depth-first or other sorts of searches, but you'd probably want to think very, very carefully about the implementation and use something besides a recursive cte. So I would expect something like "show me everything within two hops of x" to perform pretty well if you designed your query right (and you'd want to put the starting point and the limit in your CTE so you aren't pulling the whole graph first to check). I would expect "show me the shortest route from x to y" to perform much better through a non-relational approach. However getting anything to work well would require carefully thinking through your query.